基于社區劃分的學術論文推薦模型

黃泳航 湯庸 李春英 湯志康 劉繼偉

摘要：針對學術社交網絡獨有的社交性，構建了基于社區劃分的學術論文推薦模型。模型選擇社區復雜好友關系網絡圖中最大連通分量作為數據處理邏輯單元，在此基礎上進行核心關系網劃分，并采用非參數控制的方式，在所建立的核心關系網內建立標簽，在學術社交網絡中通過標簽傳播進行社區劃分，根據社區劃分結果在社區內部的用戶之間推薦學術論文。該社區劃分算法與經典社區劃分算法在人工網絡上進行仿真實驗，結果表明該算法在不同特征的人工網絡上皆能取得良好的社區發現質量。

關鍵詞：核心關系網；社區劃分；標簽傳播；自適應閾值；學術論文推薦

中圖分類號：TP391.3 文獻標志碼：A

Abstract：An academic paper recommendation model based on community partition was proposed according to sociability in social network. The model regarded the largest connected component in complex network as the logic unit in data processing， and divided up the largest connected component into nonintersect kernel subnetwork. The labels would be established according to kernel subnetwork by nonparameter control mode. Communities were divided in scholar social network through label propagation， and academic papers were recommended among the users in the communities by the results of the community partition. The proposed community partition method was compared with the classic community partition method in the experiments on artificial network. The experimental results show that the proposed method can achieve good community partition qualities on different characteristic artificial networks.

Key words：kernel subnetwork； community partition； label propagation； selfadaptive threshold； academic paper recommendation

0 引言

近幾年，社交網站發展迅速，已滲入主流文化以及人們的日常生活中，備受網民關注[1]。隨著學術社交網絡的興起，學者在學術社交網絡中發掘論文的需求激增。面對學術社交網絡中海量的論文，學者難以檢索高質量或獲取自己感興趣的論文；同時，優秀的推薦算法不僅可以為學者尋找其感興趣的論文，而且也可以為學術社交網絡謀取豐厚的利潤。因此，發掘用戶感興趣的論文成為一個新的研究方向。

目前，關于社交網絡的推薦算法，國內外的研究主要分為兩個方面：一個方面是以現有的信息為基礎，通過語義分析進行發掘建立推薦模型。例如，文獻[2]提出的信息庫學習自動機的推薦模型，該模型是利用連續型學習自動機在隨機和高噪聲環境中優化參數的卓越性能，代替原有的梯度下降算法進行大型稀疏矩陣的奇異值分解計算，使得重構矩陣與原矩陣之間的誤差進一步降低，提高了后續預測算法的精確度。文獻[3]對學生能力評估過程進行主題建模，采用局部社區發現算法對學生各方面能力進行合理的等級分類等。與此同時，以用戶的使用習慣為基礎，根據用戶的登錄信息等推薦模式也可以歸為此類。例如，文獻[4]通過考慮用戶對服務的興趣剖面以及服務對標簽的滿足度剖面，所提出的基于用戶興趣和服務滿足度的服務搜索和推薦算法。文獻[5]以用戶所發表的內容建立學習自動機和訓練樣本，在訓練樣本的基礎上進行推薦。文獻[6]則以多用戶所組成的群體為單位，根據群體所發表的信息與發表的地點建立的推薦模型等等。然而，這類算法建立于用戶所填寫的信息上，對一些缺乏信息的用戶欠缺考慮。對于這部分在社交網絡的惰性群體，認為對最后的好友推薦結果影響力不大，往往采取直接剔除的方法，使得算法數據集的準確性受到一定的影響，只能在具有大量活躍用戶的社區進行推薦。另一方面是先在社交復雜網絡中固有的拓撲關系圖之上進行社區發現，劃分社區之后再發掘其中潛在關系進行推薦。此方面的社區發現方式多種多樣。例如，文獻[7]利用拓撲圖中的完全子圖建立標簽，根據標簽在圖中的節點傳播結果劃分社區。文獻[8]則以拓撲圖中的三角形拓撲結構為網絡社區分層嵌套模式中的基本社區單元，經過粗化迭代，令網絡拓撲結構圖中的高階多邊形逐步向低階多邊形演化，最終演化成社區。與此成為對比，文獻[9]則首先為每個節點賦予一個獨立的標簽，然后根據節點的影響力大小進行排序，在標簽傳播的過程中，綜合網絡的結構傳播特性和節點的屬性特征共同計算標簽傳播的概率，同時利用節點的歷史標簽記錄修正標簽更新結果，最后將傳播后具有相同標簽的節點劃分為同一社區。也有部分學者利用物理分析的方法進行社區發現。例如，文獻[10]把拓撲關系圖上的節點視為粒子，在之間建立引力作用，通過彼此的引力關系劃分社區；文獻[11]則是對邊建立多層光譜關系，通過一系列的數學分析求出社區。

然而，由于學術社交網絡存在大量的學術論文可供分享，以上算法忽視單一學者與分享論文形成一對多的關系，導致最終學術論文推薦并不理想。因此，部分學者在此基礎上，又針對學術論文推薦的特殊性提出不同的推薦模型：文獻[12]介紹了一種根據論文摘要建立數據庫索引，通過對索引進行語義分析得出推薦結果的方法；文獻[13]則是基于論文的內容與引用關系進行推薦；文獻[14]通過提取論文的特征，建立集成的科技論文推薦框架，為科研社交網絡中的研究者提供個性化論文推薦服務；文獻[15]則根據文檔在主題上的分布概率，考慮主題之間的關聯，發掘文檔間的潛在關系建立垂直模型進行推薦；文獻[16]則對PageRank算法和內容過濾進行改進，提出了一種面向論文投稿推薦的垂直搜索引擎的主要模塊設計及實現方法。雖然上述的方法對于學術論文的推薦有一定的貢獻，但是在推薦的過程中忽視了學術社交網絡中的好友關系，造成一定程度上的精度丟失，從這些算法的推薦結果來看，為用戶所推薦論文與該用戶缺乏關聯度，推薦結果不是很理想。

針對學術社交網絡獨有的社交性，本文擬構建一個基于社區劃分的學術論文推薦模型。該模型以學術社交網絡的好友關系拓撲圖為基礎，在其中發現核心關系子網。以核心關系網中節點的標簽和權重為基礎，更新整個學術社交網絡中節點標簽及權重。標簽傳播過程中采用自適應閾值方式剔除無意義標簽進行社區發現。在學術社交網絡中建立社區，在社區內好友間共享文獻達到論文推薦的目的。

1 自適應標簽傳播算法

本模型著重考慮學術社區中的社交關系，在推薦學術論文之前根據學術社交網絡中的好友拓撲關系圖發掘其中的社區。因此，本文首先提出基于核心關系網的社區劃分算法——自適應標簽傳播算法（Adaptive Label Propagation Algorithm， ALPA）。該社區劃分算法在學術社交網絡拓撲圖中發掘核心關系網并對核心關系網中的節點賦予標簽和權重，然后采用同步標簽傳播的方式計算全部節點的標簽和權重，在算法的迭代過程中利用自適應閾值剔除不合理的標簽，最終擁有同一個標簽的節點屬于同一個社區。

1.1 基本定義

定義1 完全圖。學術社交網絡的好友關系拓撲圖由圖G={V， E}表示，其中V表示用戶的集合，E表示好友關系的集合。若圖G存在子集Gs，且Gs中任意兩點都相鄰，則稱此圖為完全圖。

定義2 核心關系網。在圖G={V， E}中，以V中未賦予標簽的度數最大的節點vi及其鄰接節點中未賦予標簽的度數最大的節點vj為初始邊尋找完全圖Gs。若GsG，且不存在任何完全圖GtG，使得GsGt，則稱Gs為核心關系網。

1.2 算法初始化

因為該算法是根據核心關系網建立社區，所以每一個社區至少包含一個核心關系網。據此，算法初始化的關鍵是在G中尋找核心關系網。具體過程如下所示。

1）對V中所有節點賦予label=0；

2）取V中label=0的節點，按照定義2尋找核心關系網。如果同時存在多個滿足label=0且度數最大的點，則隨機選取一個；

3）label=label+1；

4）將有序對（label，1）賦予給核心關系網節點對應的標簽集，結果為{（label，1）}，其中label為節點的標簽，1為該標簽對應的權重；

5）重復2）～4），直到在G={V， E}中不存在核心關系網，過程停止。

1.3 標簽傳播

在核心關系網建立之后，利用自適應標簽傳播算法計算節點的標簽和權重，達到極大限度地減少冗余標簽，提高模型的穩定性的目的。采用穩定的同步標簽傳播方式，根據復雜網絡小世界原則，節點在算法的多次迭代過程后一定會獲得標簽。標簽權重的大小與節點在多個標簽中的度數分布有關。為了避免標簽被過度傳播，一些權重較小的標簽在算法迭代過程中不斷被剔除。具體標簽更新規則如下所示。

1.4 算法復雜度分析

設復雜網絡圖G有n個節點。初始化的時候，對點集V中所有的節點賦予label=0，時間復雜度為O（n）。在圖中建立核心關系網，由于要取label=0的度數最大的節點v，先對V中的所有節點按度數進行排序，將消耗O（n2）的時間復雜度。算法初始化時，需要考察每一個節點v的鄰接節點以建立核心關系網，需要O（n log n）的時間復雜度。最終對核心關系網中的點賦予（label，1）的權重，考慮到圖的節點有可能都被劃入核心關系網中，故將達到O（n）的時間復雜度。因此，建立核心關系網的時間復雜度為最高階O（n2）。在標簽傳播階段，每一個節點v的標簽更新僅在其鄰接矩陣中進行，此過程需要的時間復雜度為O（n log n）。最后刪除重疊社區的子社區，時間復雜度同樣為O（n log n）。綜上，社區發現算法的時間復雜度為O（n）+O（n2）+O（n log n），近似為平方階O（n2）。

2 實驗分析

2.1 社區劃分性能分析與評估

本文將設計實驗對算法社區劃分性能進行分析與評估。實驗將采用Benchmark Graphs （BG）圖集作為人工網絡數據集。BG圖集是利用特定參數產生的、社區規模不均一分布的復雜網絡，其是在社區發現算法缺乏統一評價標準情況下的一種用于直接反應社區發現算法優劣的人工網絡[17]。BG圖集將產生一個固有的社區劃分結果與其生成的人工網絡相匹配。如果一個社區劃分算法在BG圖集產生的人工網絡上劃分結果，與BG圖集固有的社區劃分結果越為吻合，則說明該社區劃分算法越為精準。

本文設置的BG圖集人工網絡具體參數如表1所示。n是網絡的節點數，k為節點的平均度數，kmax為節點的最大度數，cmax是一個社區的最大節點數，cmin為一個社區的最小節點數?；旌蠀郸虥Q定社區結構明顯程度，其取值范圍是[0，1]。取值越大，生成的人工網絡社區結構越不明顯。當取值為0時，整個網絡是一個社區；當取值為1時，則是一個隨機網絡。如圖4所示的，2個對應μ值分別為0.1和0.8的人工網絡，從中可以非常直觀地看出，μ值較小時，BG圖集產生的人工網絡社區結構明顯；而當μ值較大時，人工網絡的社區結構則變得模糊。隨著設置的μ值增大，社區劃分算法越難以在此類型的人工網絡上實現社區劃分，劃分結果越難以與BG圖集固有的社區劃分結果吻合。

實驗將本文算法與標簽傳播算法（Label Propagation Algorithm， LPA）[19]、 COPRA算法[20]、CFinder算法[21]等經典社區劃分算法進行對比，對本文算法的社區劃分性能進行評估。在實驗運行之前，由于COPRA算法在提前預測重疊社區數x的值才能執行，考慮到設置的BG圖集重疊社區數為4，所以將COPRA算法的x分別預設為x=4，以最適狀態執行，同時設置x=5作為此算法不能在最適狀態運行時的對照組。

在上述數據集上分別運行ALPA、COPRA算法（x=4）和COPRA算法（x=5）、LPA、CFinder算法各10次，使用式（1）計算NMI值，執行多次取平均值，用于消除各算法在標簽傳播時不穩定所造成的誤差。各運行10次取平均值作最終的結果，考慮執行結果與BG圖集固有的社區劃分結果的吻合程度，從而評測各個算法的社區劃分性能。各個數據集上的實驗結果如圖5所示。

當μ≥0.3時，LPA無法發現社區結構；同時當μ≥0.6時，COPRA算法無法發現社區結構。而本文所提出的ALPA無論社區結構是否明顯，皆能保持一個良好的社區發現質量，雖然與此同時表現較好的CFinder算法也能夠在各個μ值上的數據集上發現社區，但是社區發現性能隨著μ值的加大而不如ALPA，并且在各個數據集中出現不穩定的現象。圖5（c）和（d）顯示的是在規模較小的人工網絡上的社區發現質量。隨著社區結構變得不明顯，LPA、COPRA算法的性能不斷下降，CFinder算法的性能在不穩定的同時，由始至終未能達到ALPA的高性能， ALPA則一直保持著較好的社區發現質量。無論社區結構如何，ALPA則仍然保持著良好的態勢，能夠穩定、良好地劃分社區；同時ALPA無須像COPRA算法預設置復雜網絡可能重疊社區數x，由于具有自適應的特點外，所以無論待發現復雜網絡社區規模大小，社區結構是否模糊，皆能很好地發現社區。

2.2 推薦模型的應用

通過上述的社區劃分性能分析與評估對比得知，ALPA具有良好的社區發現性能。因此可以將ALPA應用于自主開發的面向科研工作者的社交網絡服務平臺——學者網（http：//www.scholat.com），為用戶發掘更多潛在學術論文。利用ALPA在學者網內的好友拓撲關系圖上劃分出社區結構，對同一社區中的用戶分享的論文以點擊率進行倒序排序，并選擇點擊率前10位的論文推送給社區內的每位學者。

本文在學者網用戶數據中選取11000條好友關系數據，消除噪聲之后共10920條數據進行實驗。如圖6（a）所示，在應用本算法之前，此10920條數據好友關系所構成的是一個未劃分社區的好友關系復雜網絡。在該復雜網絡中，應用ALPA經歷5次迭代，如圖6（b）所示，最終劃分出181個極大團，108個社區，對各個社區中的用戶，推薦該社區內所有用戶所發表的論文。

通過使用本文的潛在好友推薦方法，學者網已為其注冊用戶提供了有效的潛在學術論文推薦服務，如圖7所示。這是本文算法為學者網中一位屬于社區第1、2、3、7、28、56社區用戶所推薦的學術論文的效果圖，所推薦的學術論文皆是該用戶的好友所分享的，該用戶與其大多數好友之間存在共同興趣與研究領域，必然會樂于接受推薦結果，如果該用戶需要瀏覽更多推薦結果，可以點擊下方的按鈕，加載更多的論文推薦結果。

3 結語

本文設計了一種基于社區劃分的學術論文推薦模型。首先對算法進行初始化，獲得復雜網絡中的全部核心關系網，再根據核心關系網中節點的標簽和權重，采用同步標簽傳播方式更新網絡中節點的標簽和權重，最終將網絡劃分為若干個社區，并對社區內的用戶推薦學術論文。ALPA采用自適應閾值的處理方式剔除無意義的標簽，避免了預先輸入參數對未知復雜網絡的局限性，因此其更能夠自適應于真實的社交網絡。隨著社交網絡的蓬勃發展，社交網絡中用戶之間的關系也更加錯綜復雜，規模也在迅速增大。在此背景下，如何提高推薦算法的時間復雜度是一個可以繼續研究的方向。另一方面，可以對該算法進行并行化處理，使其能夠應對復雜網絡大數據所帶來的挑戰。

參考文獻：

[1]高嫻子，蔣建國.近年來我國社交網絡發展研究[D].廣州：暨南大學，2011：1-61.（GAO X Z， JIANG J G. Research on the development of Chinas social network[D]. Guangzhou： Jinan University， 2011：1-61.）

[2]荊羽純，葛昊，江文，等.一種基于學習自動機的推薦算法改進[J].計算機應用研究，2016，34（1）：32-34.（JING Y C， GE H， JIANG W， et al. Learning automatabased improvement for recommendation algorithm[J]. Application Research of Computers， 2016，34（1）：32-34.）

[3]石博，何楚，卓桐，等.慕課教學中基于局部社區發現的主題交互模型[J].計算機應用研究，2014，32（6）：1724-1727.（SHI B， HE C， ZHUO T， et al. Topic interaction model based on local community detection for MOOC teaching process[J]. Application Research of Computers， 2014，32（6）：1724-1727.）

[4]鄧華平，趙海燕，陳慶奎， 等.基于用戶興趣和服務滿足度的服務搜索和推薦算法[J].計算機應用研究，2014，32（9）：2613-2617.（DENG H P， ZHAO H Y， CHEN Q K， et al. Service search and recommendation algorithm based on users interest and service satisfaction[J]. Application Research of Computers， 2014， 32（9）：2613-2617.）

[5]HANG Y. Incorporating phraselevel sentiment analysis on textual reviews for personalized recommendation[C]// WSDM 2015： Proceedings of the 8th ACM International Conference on Web Search and Data Mining.New York：ACM， 2015： 435-440.

[6]YUAN Q， CONG G， LIN C. COM： a generative model for group recommendation[C]// KDD14： Proceedings of the 20th ACM SIGKDD Conference on Knowledge Discovery and Data Mining. New York：ACM， 2014：80-90.

[7]沈海燕，李星毅.一種新的基于標簽傳播的重疊社區發現算法 [J].軟件導刊，2015，14（4）：59-62.（SHEN H Y， LI X Y. A new overlapping community structure detecting algorithm by label propagation[J]. Software Guide， 2015，14（4）：59-62.）

[8]康穎，于博，古曉艷，等.一種面向大規模社會信息網絡的多層社區發現算法[J].計算機學報， 2015，38（1）：1-14.（KANG Y， YU B， GU X Y，et al. A multilevel community detection algorithm for largescale social information networks[J]. Chinese Journal of Computers， 2015，38（1）：1-14.）

[9]劉世超，朱福喜，甘琳.基于標簽傳播概率的重疊社區發現算法[J/OL].[2015-07-22].http：//www.cnki.net/kcms/detail/11.1826.TP.20150722.1205.014.html.（LIU S C， ZHU F X， GAN L. A labelpropagationprobabilitybased algorithm for overlapping community detection[J/OL]. [2015-07-22].http：//www.cnki.net/kcms/detail/11.1826.TP.20150722.1205.014.html）

[10]董宇欣，遲闊，印桂生.基于引力作用的可選粒度社區發現算法[J].哈爾濱工程大學學報，2015，36（6）：1-6.（DONG Y X， CHI K， YIN G S. Optional granularity community detection algorithm based on gravitation[J]. Journal of Harbin Engineering University， 2015，36（6）：1-6.）

[11]ZHANG X， NEWMAN M. Multiway spectral community detection in networks[EB/OL].[2015-01-22]. http：//arxiv.org/abs/1507.05108.

[12]HOXHA K， KIKA A， GANI E， et al. Towards a modular recommender system for research papers written in Albanian[J]. International Journal of Advanced Computer Science and Applications， 2015，5（4）：160-168.

[13]蔡阿妮，周傲英. 基于內容與引用關系的學術論文推薦[D].上海：華東師范大學，2014：1-82.（CAI A N， ZHOU A Y. Recommending research paper based on content and citation graph[D].Shanghai： East China Normal University， 2014：1-82.）

[14]孫見山，劉志迎，馬建.科研社交網絡中的論文推薦[D].合肥：中國科學技術大學， 2014：1-101.（SUN J S， LIU Z Y，MA J. Article recommendation in research social network[D].Hefei： University of Science and Technology of China， 2014：1-101.）

[15]黃澤明，魯明羽.基于主題模型的學術論文推薦系統研究[D].大連：大連海事大學， 2013：1-68.（HUANG Z M， LU M Y. Research on recommended system of scholar paper based on topic model[D].Dalian： Dalian Maritime University， 2013：1-68.）

[16]徐鎮，李廉.基于垂直搜索引擎的論文投稿推薦系統研究[D].蘭州：蘭州大學，2014：1-67.（XU Z，LI X. Research on a recommendation system for paper submission based on vertical search engine[D]. Lanzhou： Lanzhou University， 2014：1-67.）

[17]LANCICHINETTI A， FORTUNATO S， RADICCHI F. Benchmark graphs for testing community detection algorithms[J]. Physical Review E， 2008，78（4）：046110.

[18]LANCICHINETTI A， FORTUNATO S， KERTESZ J. Detecting the overlapping and hierarchical community structure in complex networks[J].New Journal of Physics， 2009，11（3）：033015.

[19]RAGHAVAN U， ALBERT R， KUMARA S. Near linear time algorithm to detect community structures in largescale networks[J]. Physical Review E， 2011，84（3）：036103.

[20]GREGORY S. Finding overlapping communities in networks by label [J].New Journal of Physics， 2010， 12（10）：103018.

[21]PALLA G， DERENYI I， FARKAS I， et al. Uncovering the overlapping community structure of complex networks in nature and society[J]. Nature， 2005， 435（7043）： 814-818.