一種基于節點局部相似度的標簽傳播算法

孫美琪,薛 濤，梁家瑞

(1.西安工程大學 計算機科學學院,陜西 西安 710048；太原理工大學 軟件學院，山西 晉中 030600)

0 引 言

隨著信息技術的高速發展,各種社會媒體產生了龐大的網絡數據,很多現實世界的問題被抽象成了復雜網絡,如生物網絡、社交網絡等。社區結構[1]作為一種數據組織形式,存在于各種復雜網絡之中[2],是揭示復雜網絡結構特性的一個重要指標,發現社區結構并提取其內在規律對研究復雜網絡具有重要意義。如在疾病傳播網絡中,根據病人之間的關系網絡,采取有效的隔離和治療措施以杜絕疾病的傳播;在犯罪網絡中,借助社區結構可以更加精準快速地找到犯罪成員及其關鍵人物,為公安部門快速破案提供技術支持。

早期的社區發現研究都認為節點之間是互相獨立的,最經典的GN算法[3],通過連續的網絡分解獲得最終的社區結構。然而,隨著研究的不斷深入,網絡中出現了越來越多的重疊社區。文獻[4-5]都是通過網絡拓撲結構以及節點屬性研究重疊社區,缺點是效率較低。文獻[6]的MISAGA(mining interesting subgraphs in attributed graph algorithm)通過計算節點之間的關聯度,來衡量頂點對子圖的隸屬程度,從而發現社區結構。文獻[7]提出的MOGA-OCD(multi-objective genetic algorithm)基于邊緣編碼以及優化的適應度函數可提高社區內部的連通性,但是算法復雜度較高。對于大型網絡,可以借助大數據計算引擎實現社區發現算法,如Canopy-K-means[8]算法的并行化就可用于大型網絡的節點預處理環節。

在眾多社區發現算法中,標簽傳播算法(label propagation algorithm,LPA)[9]因其簡單高效而受到廣泛關注。但該算法隨機性強,易導致結果不穩定,學者們由此提出很多相關的改進算法[10-13],但只專注于挖掘非重疊社區。GREGORY提出了COPRA(community overlap propagation algorithm),但其社區劃分結果不穩定[14]。文獻[15]的LPPB(label-propagation-probability-based)根據節點的屬性特征計算其在更新過程中標簽的傳播概率,以此來提高結果的準確性。NI-LPA(node importance-label propagation algorithm)[16]基于節點的重要性,在LPA的基礎上僅僅使用網絡拓撲結構,將算法改進后用于非重疊社區發現。OMKLP(overlapping community detection in complex networks based on multi kernel label propagation)[17]根據識別出的核心局部節點優化了異步傳播策略,從而可以快速識別社區的內部節點以及邊界節點。文獻[18]的LRMLPA,首先使用LeaderRank對節點的重要性進行度量,之后通過對節點進行團擴展得到粗糙團再開始傳播標簽。文獻[19]提出的算法通過讓節點按照PageRank值更新標簽,達到了穩定社區結構的效果。但是大多數算法還是忽略了相鄰節點之間的局部相似性,因為同一社區中的個體通常會具有相似的屬性特征。基于此，本文提出基于節點局部相似度的標簽傳播算法COPRALS。首先以搜索到的極小完全子圖作為初始社區開始標簽傳播;其次在傳播和更新標簽時,將節點局部相似度的排序作為依據,以此來保證算法的穩定性。

1 COPRA算法

1.1 算法基本思想

COPRA算法是在LPA算法上的擴展。該算法引入從屬系數b,用于衡量節點對社區的隸屬程度,節點可以擁有的最多的標簽數目由v決定,v表示每個節點最多可以歸屬的社區數目。從屬系數的計算式為

(1)

式中：c為社區；N(x)為節點x的鄰節點集；bt(c,x)為在第t次迭代時x對c的從屬系數。從式(1)可以看出，COPRA采用同步更新方式,即當前節點的標簽更新只能由其余節點上一輪更新的標簽來決定。本文采用的是Raghavan[9]等人提出的異步更新方式,即

(2)

式中：N1(x)為節點x的未更新鄰節點集；N2(x)為節點x已更新的鄰節點集；N(x)=N1(x)+N2(x)。節點x在第t次的標簽更新取決于2部分：一是節點x的未更新鄰居節點的上次更新結果,二是節點x的已更新鄰居節點的本次更新結果。

1.2 算法步驟

1) 在初始化期間,網絡中的每個節點都有一個標簽(x,1),它表示該節點的社區號。

2) 在網絡中,以隨機的順序迭代更新節點標簽,每個節點從直接連接的節點標簽中,選取從屬系數大于1/v前v個標簽作為本輪更新結果；若情況不唯一,則隨機選擇一組節點標簽作為該節點標簽。

3) 反復操作2)直至所有標簽趨于穩定。

4) 標簽相同的被劃分至同一社區。

2 COPRALS算法

從上節可以得出COPRA算法存在以下缺陷:①初始化時會為網絡中每個節點分配唯一的標簽,這樣會導致后續的每輪標簽更新迭代時耗費很多時間;②標簽傳播的開始會隨機選擇1個節點進行,在節點更新自身標簽時,若從屬系數一樣大時,會隨機選擇一組標簽賦予當前節點。這樣，強的隨機性會降低算法的穩定性,從而影響社區結構的質量。因此,本文以多標簽傳播算法COPRA為基礎，在標簽初始化階段時,先計算網絡中所有節點的度數,只為節點度數大于閾值的節點賦予標簽。然后尋找網絡中的極小完全子圖,以這些子圖作為標簽傳播的開始。并依據本文提出的局部相似度對節點進行排序,利用異步更新策略不斷迭代更新每個節點標簽,直至所有節點標簽趨于穩定。

2.1 標簽初始化

在標簽傳播算法思想中,網絡中每個節點依據其鄰居所攜帶的標簽來更新自身的標簽,而網絡中那些度數很小甚至為0的節點,擁有的標簽往往直接由其鄰居決定。由此可知,COPRA算法初始化時為每個節點賦予標簽,并以此作為后續迭代更新的依據,這樣會耗費大量時間。因此,本文在初始化標簽時不會為度數小于等于閾值dth(本文中dth取1)的節點分配標簽,這樣既減少了節點標簽的初始化數目,又減少了更新此類節點的成本,時間復雜度將會降低。

其次,以CPM(cliqne percolation method)算法[20]思想為基礎，采用以網絡中若干個連接緊密的極小完全子圖作為標簽傳播的原始社區，其中一個極小完全子圖代表網絡中一個相互連通的三角形。在標簽傳播初期,每個節點接收到的鄰居節點的標簽比較分散,因此在局部范圍內若已有緊密連接的社區,使其攜帶相同的標簽,那么迭代更新過程中會收斂更快,算法效率也會得到提升。

2.2 標簽選擇

COPRA算法的標簽選擇階段會為當前節點可能擁有的所有標簽的隸屬度進行排序,選擇隸屬度最大的一組標簽賦予該節點,若情況不唯一則會隨機選擇一組標簽賦予節點。從分析得知,在此過程中,如果先選擇了重要性較小的節點,那么這些節點又會反過來影響重要性較大的節點,從而導致 “標簽回流”，這樣會造成社區結構的不穩定,影響社區發現的質量。因此,本文以局部相似度指數來為節點進行排序,選擇與當前節點更相似的鄰居所攜帶的標簽來保證算法的穩定性,進而達到提高社區發現質量的效果。

在社交網絡中,節點之間的相似性可以很好地反映它們之間的相關性以及緊密程度。如果節點a有b和c等2個鄰接節點,若a與b的相似性越高,a就越容易接受到來自b的標簽信息,即a與b更可能來自于同一社區中。為此，本文提出局部相似度指數(S)計算方式，即

(j∈N(i))

(3)

(4)

式中：N(i)為節點i的鄰居節點集；N(j)為節點j的鄰居節點集；t為節點i和j的公共鄰居；CCi為節點i的聚類系數；ei為節點i的所有鄰居之間的連邊；ki為節點i的度。

提出的節點之間的局部相似度指數是Jaccard系數以及局部聚類系數[21]的組合。Jaccard系數反映的是節點之間的相似性,通常情況下，2個節點之間的公共鄰居越多,節點之間的相似度就越大。聚類系數CCi可以度量網絡中節點間的聚類程度,它代表了相鄰節點之間的關系緊密程度。本文采用的是局部聚類系數,即公共鄰居聚集程度的累積,該值反映了節點之間的公共鄰居的聚集程度,由2方面決定:第一,2個節點之間公共鄰居的數量;第二,每個公共鄰居的聚類系數。因為2個節點之間的公共鄰居越多,其關系越密切,公共鄰居就是節點之間的紐帶。由此可得,在標簽選擇的過程中,節點應該選擇與自己最為相似的鄰居的標簽,其最相似節點定義為

j=arg maxSij,j∈N(i)

(5)

節點局部相似度的計算步驟為

Input:Undirected unweighted graphG(V,E)

Output:Max-neighbors-list(Vi,Vj,Sij)

1) Initialization undirected unweighted graphG(V,E)

2) ForVi(i=1→N) inG(V,E) do

4) End for

5) ForVi(i=1→N) inG(V,E) do

7) End for

8) ForVi(i=1→N) inG(V,E) do

10) End for

11) ForVi(i=1→N) inG(V,E) do

12) According to Eq(7) traverse Similarity-list(Vi,Vj,Sij) and found maxSij

13) Complete Max-neighbors-list←(Vi,Vj,Simij)

14) End for

15) End

2.3 算法描述

步驟1 輸入網絡G(V,E)，計算網絡中節點的度，為度數大于dth的節點分配標簽(Cx,1)。

步驟2 根據式(4)計算網絡中節點的S值，并按降序排列。

步驟3 搜索網絡中以度較高節點為中心的極小完全子圖，為完全子圖內的所有節點賦予相同標簽(Cy,1)。

步驟4 當前節點接收來自鄰居節點的從屬系數大于1/v前v個標簽。

步驟5 若選擇標簽情況不唯一，則選擇S值大的節點所擁有的標簽，并將從屬系數歸一化。

步驟6 重復步驟4～5，直至所有節點標簽不再改變或算法達到最大迭代次數。

步驟7 輸出所有節點標簽集合，標簽相同的為同一社區。

3 實驗及分析

3.1 擴展模塊度

本文使用擴展模塊度(EQ)作為評價社區結構質量的指標,即

(6)

式中：m為網絡中邊的個數；Oi為節點i屬于社區的數量;di為節點i的度；δ(Ci,Cj)為如果節點i和節點j在同一個社團，則值為1,否則為0。

3.2 標準互信息

標準互信息(INM)可以評估算法生成的社區結構與標準社區結構的相似度。即

H(y|x)norm]

(7)

式中：x和y分別為真實的社區結構和算法生成的社區結構。

3.3 實驗分析

為了驗證本文算法的有效性和可行性,分別在真實網絡和人工合成網絡中進行測試。

3.3.1 真實網絡數據集 數據集一是Zachary Karate Club[22],包含34個節點和78條邊,個體表示每位成員,邊表示成員之間的社交關系,其社區劃分結果如圖1所示。

圖 1 Karate社區劃分結果Fig.1 Division result of Karate community

表1是基于本文提出的算法在dth=1,v=2時,重復運行10 次后取平均值得到的結果,由于COPRA算法存在很強的隨機性,所以實驗時將COPRA算法重復運行30次。將本文算法與COPRA、OMKLP、LRMLPA算法進行對比,可發現本文算法的EQ值有所提升,說明使用此算法發現的社區結構質量較高。但是，由于此算法初始時搜索了極小完全子圖,計算了節點之間的局部相似度,因此本文算法執行時耗時間稍多。

表 1 Karate數據集實驗結果Tab.1 Experimental results of Karate dataset

數據集二是Dolphin Social Betwork[23]。 網絡有62個節點,159條邊。其社區劃分結果如圖2所示。

圖 2 Dolphin社區劃分結果Fig.2 Result of Dolphin community division

由于網絡規模并不大,因此本實驗設置dth=1,v=2 時,同樣重復執行本算法10次后取平均值得到的結果。表2為本文算法與COPRA、OMKLP、LRMLPA算法的模塊度和運行時間的對比分析,依然可以看出算法的模塊度有所提高。

表 2 Dolphin數據集實驗結果Tab.2 Experimental results of Dolphin dataset

3.3.2 人工合成網絡 LFR基準網絡是由Lancichinetti等提出的人工網絡,LFR benchmark是用于生成人工網絡的基準程序,可以根據個人需求生成網絡圖,生成的網絡具有真實網絡的特性。利用基準程序生成了4種網絡,如表3所示。

表3中N為節點數目;k為網絡中的平均度數;cmin為規模最小的社區節點數;cmax為規模最大的社區的節點數;kmax為網絡中的最大度數;um為節點在社區外部的度數與該節點總度數的比值,比值越小說明社區結構越清晰;on為網絡中重疊節點數目;om為重疊節點所隸屬的社區數目。人工合成網絡的實驗結果如圖3～6所示。

表 3 4種人工網絡參數設置Tab.3 Parameter settings of four kinds of artificial network

圖 3 R1網絡的INM值Fig.3 INM value of R1 network

圖 4 R2網絡的INM值Fig.4 INM value of R2 network

圖 5 R3網絡的INM值Fig.5 INM value of R3 network

R1網絡中重疊節點數為100,屬于小規模重疊程度的重疊網絡,R2網絡重疊節點數為200,屬于較大規模重疊的網絡。從圖3可以看出,COPRA在um=0.5以及LRMLPA、OMKLP在um=0.6時幾乎已獲取不到社區結構,但是本文算法在um=0.6時,此時社區結構變得模糊,依然可以獲取到重疊社區結構。從圖4可知,在網絡中重疊節點增多的情況下,隨著um的逐漸增大,本文算法效果依然較好。

圖 6 R4網絡的INM值Fig.6 INM value of R4 network

R3網絡以及R4網絡的um取值相同,即2個網絡的社區結構清晰程度相同。R3網絡的重疊節點數為100,屬于較小規模重疊程度的網絡,R4網絡的重疊節點數是R3網絡的2倍,屬于重疊程度較大的網絡。從圖5以及圖6可以看出,本文算法的INM均高于其他算法,說明本文算法的結果更符合真實情況。

4 結 語

本文提出了一種基于標簽傳播思想的改進的重疊社區發現算法,即基于節點局部相似度的標簽傳播算法COPRALS。避免了隨機選擇標簽帶來的算法穩定性差的缺陷。通過在真實網絡和人工網絡中的實驗測試，表明：本文提出的COPRALS比同類算法發現的社區結構質量更高,且更接近于真實的社區結構。如何將本文算法擴展到分布式環境中,用于發現大規模復雜網絡社區結構將是下一階段工作的重點。

參考文獻(References)：

[1]FORTUNATOS.Communitydetectioningraphs[J].PhysicsReports,2010,486(3/4/5):75-174.

[2]MATH,WANGY,TANGML,etal.LED:Afastoverlappingcommunitiesdetectionalgorithmbasedonstructuralclustering[J].Neurocomputing,2016,207:488-500.

[3]GIRVANM,NEWMANMEJ.Communitystructureinsocialandbiologicalnetworks[J].ProceedingsoftheNationalAcademyofSciencesoftheUSA,2002,99(12):7821-7826.

[4]WANGMM,ZUOWL,WANGY.Animproveddensitypeaks-basedclusteringmethodforsocialcirclediscoveryinsocialnetworks[J].Neurocomputing,2016,179:219-227.

[5] 杜航原,裴希亞,王文劍.面向屬性網絡的重疊社區發現算法[J].計算機應用,2019,39(11):3151-3157.

DUHY,PEIXY,WANGWJ.Overlappingcommunitydetectionalgorithmforattributednetworks[J].JournalofComputerApplications,2019,39(11):3151-3157.(inChinese)

[6]HETT,CHANKCC.MISAGA:Analgorithmformininginterestingsubgraphsinattributedgraphs[J].IEEETransactionsonCybernetics,2018,48(5):1369-1382.

[7]BELLO-ORGAZG,SALCEDO-SANZS,CAMACHOD.Amulti-objectivegeneticalgorithmforoverlappingcommunitydetectionbasedonedgeencoding[J].InformationSciences,2018,462:290-314.

[8] 郭衛霞,薛濤,李婷.基于Hadoop的Canopy-K-means并行算法的學生成績與畢業流向關系分析[J].西安工程大學學報,2018,32(6):705-712.

GUOWX,XUET,LIT.AnalysisofstudentscoreandgraduationdestinationbasedonHadoop′sCanopy-K-meansparallelalgorithm[J].JournalofXi’anPolytechnicUniversity,2018,32(6):705-712.(inChinese)

[9]RAGHAVANUN,ALBERTR,KUMARAS.Nearlineartimealgorithmtodetectcommunitystructuresinlarge-scalenetworks[J].PhysicalReviewEStatalNonlinear&SoftMatterPhysics,2007,76(3):036106.

[10]XINGY,MENGFR,ZHOUY,etal.Anodeinfluencebasedlabelpropagationalgorithmforcommunitydetectioninnetworks[J/OL].TheScientificWorldJournal,2014:1-13.http://downloads.hindawi.com/journals/tswi/2014/627581.pdf.

[11]HEM,LENGMW,LIF,etal.Anodeimportancebasedlabelpropagationapproachforcommunitydetection[M]//AdvancesinIntelligentSystemsandComputing.Heidelberg:Springer-Verlag,2013:249-257.

[12] 石夢雨,周勇,邢艷.基于LeaderRank的標簽傳播社區發現算法[J].計算機應用,2015,35(2):448-451.

SHIMY,ZHOUY,XINGY.CommunitydetectionbylabelpropagationwithLeaderRankmethod[J].JournalofComputerApplications,2015,35(2):448-451.(inChinese)

[13] 張蕾,錢峰,趙姝,等.基于邊權的穩定標簽傳播社區發現算法[J].小型微型計算機系統,2019,40(2):314-319.

ZHANGL,QIANF,ZHAOS,etal.Stablelabelpropagationalgorithmbasedonedgeweightsforcommunitydetection[J].JournalofChineseComputerSystems,2019,40(2):314-319.(inChinese)

[14]GREGORYS.Findingoverlappingcommunitiesinnetworksbylabelpropagation[J].NewJournalofPhysics,2010,12(10):103018.

[15] 劉世超,朱福喜,甘琳.基于標簽傳播概率的重疊社區發現算法[J].計算機學報,2016,39(4):717-729.

LIUSC,ZHUFX,GANL.Alabel-propagation-probability-basedalgorithmforoverlappingcommunitydetection[J].ChineseJournalofComputers,2016,39(4):717-729.(inChinese)

[16]KOUNIIBE,KAROUIW,ROMDHANELB.Nodeimportancebasedlabelpropagationalgorithmforoverlappingcommunitydetectioninnetworks[J].ExpertSystemsWithApplications,2019:113020.

[17] 鄧琨,李文平,余法紅,等.基于多核心標簽傳播的復雜網絡重疊社區識別方法[J].通信學報,2017,38(2):53-66.

DENGK,LIWP,YUFH,etal.Overlappingcommunitydetectionincomplexnetworksbasedonmultikernellabelpropagation[J].JournalonCommunications,2017,38(2):53-66.(inChinese)

[18] 龔宇,張智,顧進廣.基于LeaderRank的多標簽傳播重疊社區發現算法[J].計算機應用研究,2018,35(6):1738-1741.

GONGY,ZHANGZ,GUJG.Multi-labelpropagationalgorithmforoverlappingcommunitydetectionbasedonLeaderRank[J].ApplicationResearchofComputers,2018,35(6):1738-1741.(inChinese)

[19] 馬健,劉峰,李紅輝,等.采用PageRank和節點聚類系數的標簽傳播重疊社區發現算法[J].國防科技大學學報,2019,41(1):183-190.

MAJ,LIUF,LIHH,etal.OverlappingcommunitydetectionalgorithmbylabelpropagationusingPageRankandnodeclusteringcoefficients[J].JournalofNationalUniversityofDefenseTechnology,2019,41(1):183-190.(inChinese)

[20]PALLAG,DERéNYII,FARKASI,etal.Uncoveringtheoverlappingcommunitystructureofcomplexnetworksinnatureandsociety[J].Nature,2005,435(7043):814.

[21]PANXH,XUGQ,WANGB,etal.Anovelcommunitydetectionalgorithmbasedonlocalsimilarityofclusteringcoefficientinsocialnetworks[J].IEEEAccess,2019(7):121586-121598.

[22]ZACHARYWW.Aninformationflowmodelforconflictandfissioninsmallgroups[J].JournalofAnthropologicalResearch,1977,33(4):452-473.

[23]LUSSEAUD,SCHNEIDERK,BOISSEAUOJ,etal.ThebottlenoseDolphincommunityofoubtfulsoundfeaturesalargeproportionoflong-lastingassociations[J].BehavioralEcohgyandSociobiology,2003,54(4):396-405.