基于相關拓撲勢的社團發現算法

趙文濤 趙好好 孟令軍

1(河南理工大學計算機科學與技術學院 河南 焦作 454000)2(河南省普通高等學校礦山信息化研究重點實驗室 河南 焦作 454000)

基于相關拓撲勢的社團發現算法

趙文濤1,2趙好好1孟令軍1

1(河南理工大學計算機科學與技術學院 河南 焦作 454000)2(河南省普通高等學校礦山信息化研究重點實驗室 河南 焦作 454000)

針對傳統算法社團劃分精度較低以及模塊度函數分辨率低的問題，提出一種基于相關拓撲勢的社團發現算法，簡稱BITP算法。該算法考慮節點的相關性因素，引入相關拓撲勢來衡量節點的影響力，尋找出其中的極大勢值點，采用標簽傳播的思想對社團的規模進行控制。在人工合成網絡和真實網絡上，與多種算法進行實驗對比，結果表明該算法多次運行結果相對穩定且社團劃分精度較高。算法時間復雜度為O(n)，且不需要先驗知識，更適合大規模復雜網絡上的社團結構挖掘。

社團結構 復雜網絡 相關拓撲勢 標簽傳播

0 引 言

復雜網絡的結構特性是現實系統中個體之間復雜關系的真實表現。大量實證研究結果表明，真實網絡結構不僅普遍具有小世界和無標度等特性，而且呈現出明顯的社團結構[1-3]。社團結構是指網絡中的節點根據某種共同屬性，子集合內部節點之間的連接相對緊湊，子集合之間節點之間的連接相對稀疏[2]。

Girvan和Newman最先提出了基于邊界數的社團發現算法，稱為GN算法[1]，但算法效率和社團劃分精度較低。隨后，Newman等人又引入模塊度函數[3]來對社團劃分質量進行評價。之后，人們采用多種方法來對模塊度進行優化以達到更好的社團劃分效果，例如FASTGREEDY算法[4]、MULTILEVEL算法[5]等。然而近期研究表明，模塊度定義存在分辨率的限制，不適合劃分社團規模大小不一的網絡結構。而真實網絡結構通常存在異質性，社團大小不均勻，模塊度優化方法很難保證社團結構挖掘的準確性。另外，其他一些快速算法雖然效率很高，卻是以損失精度為代價，諸如LPA算法[6]、WALKTRAP算法[7]、LEC算法[8]、SPINGLASS算法[9]、INFOMAP算法[10]等。

鑒于模塊度定義存在的缺陷，為了有效揭示網絡內在的社團結構，淦文燕等[11]提出了一種基于拓撲勢的網絡社團發現算法，將數據場中拓撲勢的概念引入至社團發現。隨后，張健沛[12]、石立新[13]、張桂杰[14]等人基于拓撲勢并結合其他方法進行相關算法的優化，驗證其各自算法的有效性。

這些基于拓撲勢的社團發現算法均是基于傳統拓撲勢函數，本文提出了一種基于相關拓撲勢的社團發現算法(簡稱BITP算法)。在傳統拓撲勢的基礎上，結合節點之間的相關性定義，引入相關拓撲勢的概念。該方法不需要先驗知識，通過相關拓撲勢來衡量網絡中節點的影響力，采用標簽傳播的方法進行社團結構的挖掘，算法相對穩定，社團劃分精度較高。

1 相關概念

1.1 相關性

文獻[15]中相關性定義了無向無權網絡中用于衡量節點之間關系的緊密度，具體定義如下：

(1)

1.2 拓撲勢

物理學中用場來描述物質粒子間的相互作用。物理場是其中的一種，用來描述拓撲場的標量勢函數。勢場分為長程場和短程場。在長程場中，勢值的大小與距離成反比，在距離場源很遠的地方仍然存在著場力的作用(如重力勢場和靜電勢場)。而在短程場中，中心勢場的勢值會隨著距離的增大而急劇下降，相應的場力也會很快衰減至零。受物理場思想的啟發，諸多研究傾向于采用代表短程場且具有良好數學性質的高斯勢函數描述節點間的相互作用。

給定網絡G=(V,E)，其中，V={1,2,…,n}為節點的非空有限集。根據拓撲勢場中勢函數定義[16]，任意節點i∈V的拓撲勢可表示為：

(2)

其中，dij表示節點i與j之間的最短路徑長度；影響因子σ用于控制每個節點的影響范圍；mi表示節點i(i=1,2,…,n)的固有屬性(如質量等)。

傳統的拓撲勢計算[11-14]中將每個節點視為均質的，拓撲勢TP(TopologicalPotential)計算式可表達為：

(3)

1.3 相關拓撲勢

節點的相關性從網絡拓撲結構的角度出發，充分考慮節點之間連邊的數目對節點之間關系的影響。給定網絡，節點之間的相關性是固定的、不可改變的，故可以將其視為網絡中節點的固有屬性。

式(3)中傳統的拓撲勢計算方法忽略了節點固有屬性對節點拓撲勢的影響作用，而實際復雜網絡中不同節點對單個節點影響程度不同，即相關程度不同。故本文考慮節點之間的相關性，提出節點的相關拓撲勢函數，表示方式如下：

(4)

其中，P(i,j)為節點相關矩陣P中第i行第j列的元素值，即節點i與節點j的相關性。

勢函數中影響因子σ用來控制節點的影響力跳數，節點的影響力跳數定義為：

(5)

考慮節點的影響力跳數，節點的相關拓撲勢ITP(InterrelatedTopologicalPotential)可由式(6)推出：

(6)

在無向無權網絡中(以Karate網絡為例)，計算所有節點的TP和ITP指標，并畫出其分布，如圖1和圖2所示。網絡中節點ITP指標呈局部聚集狀態，社團的區分效果要比TP指標更加明顯。分別將采用TP指標和ITP指標的社團發現算法簡稱為BTP算法和BITP算法，后面將對這兩種算法作對比分析。

圖1 TP指標

圖2 ITP指標

2 算法描述

本文考慮網絡中節點之間的相關性，引入節點的相關拓撲勢。算法采用貪婪局部搜索的方法搜索網絡中的局部極大勢值節點，初始化極大值節點的標簽為各自的節點標號，然后采用標簽傳播的方法更新其余節點的標簽。

在傳統的LPA算法[6]中，節點標簽傳播規則分為兩步：第一步，將節點i的標簽更新為其鄰居節點中標簽數目最多的標簽；第二步，若其鄰居節點中標簽數目最多的標簽有多個時，則隨機選擇其中一個作為節點i的標簽。這樣的隨機操作容易造成算法的不穩定，社團劃分結果不夠準確。因此，本文的標簽傳播規則為：

Step1 將節點i的標簽更新為其鄰居節點中標簽數目最多的標簽；

Step2 若其鄰居節點中標簽數目最多的標簽有多個時，選擇其中相關拓撲勢最大的作為節點i的標簽。

BITP算法

輸入：無向無權網絡G=(V,E)，其中，V={1,2,…,n}。

輸出：局部社團C={C1,C2,…,Ck}，其中k為局部社團數目。

算法步驟：

(1) 計算所有節點相關拓撲勢；

(2) 采用貪婪局部搜索的方法尋找網絡中的局部極大勢值節點；

(3) 將這些極值點的標簽分別初始化為它們各自的節點標號，網絡中的其他節點的標簽初始化為0。

(4) 按照上述標簽傳播規則依次對網絡中其余節點進行標簽更新。

(5) 標簽相同的節點同屬于同一個局部社團，輸出局部社團{C1,C2,…,Ck}。

在BITP算法中，計算節點的相關拓撲勢的時間復雜度為O(2n)，n為網絡中節點數；貪婪局部搜索極大值的時間復雜度為O(n)，標簽更新的時間復雜度為O(n)。本文算法總的時間復雜度為O(2n+n+n)=O(n)。

3 實驗評價標準

3.1 模塊度指標

模塊度[3]用來比較社團劃分結果與隨機圖之間的差異。定義如下：

(7)

其中，m為網絡中節點的數目；∑in表示一個社團內部的連邊數目；∑tot表示一個社團內部所有節點度的總和。

3.2NMI指標

標準化互信息NMI[17](NormalizedMutualInformation)常用來衡量社團劃分結果與真實社團結構之間的相近程度。定義如下：

(8)

其中，A、B分別為兩個不同的局部社團所代表的向量；I(A,B)是向量A和向量B的互信息；H(A)是向量A的信息熵；H(B)是向量B的信息熵。NMI的取值為[0,1]，NMI值越大說明社團劃分結果與真實社團結構越相似，越小則反之。

3.3VI指標

信息差異VI[18](VariationofInformation)常用來衡量社團劃分結果與真實社團結構之間的差異。定義如下：

VI=H(A|B)+H(B|A)

(9)

其中，A、B分別為兩個不同的局部社團所代表的向量；H(A|B)是向量A對于向量B的條件熵；H(B|A)是向量B對于向量A的條件熵。VI的取值為[0,log(m)]，m為網絡中節點的數目。VI值越小說明社團劃分結果與真實社團結構差異越小，越大則反之。

4 實驗結果與分析

為了驗證BITP算法的準確性與有效性，分別在人工合成網絡和真實網絡上與多種算法進行實驗對比。

4.1 人工合成網絡

實驗采用LFR(Lancichinetti-Fortunato-Radicchi)[19]基準網絡來生成人工合成網絡。網絡中的節點度和社團大小均符合冪律分布。混合參數μ用來控制局部社團內部連接數與外部連接的比例，取值為[0,1]。其值越小說明內部連接比較緊密，社團結構較強；反之，社團結構較弱。本文僅取其值0.1～0.8。根據μ取值不同對應生成8個不同的人工合成網絡，并分別在這些網絡上多次運行GN、CNM、LPA、WALKTRAP、LEC、SPINGLASS、INFOMAP、MULTILEVEL、BTP、BITP等十種社團發現算法。人工合成網絡具體參數設置分別如表1所示。

表1 人工網絡參數設置

為了比較這些算法社團劃分結果與真實網絡結構之間差異，分別記錄它們劃分結果的模塊度指標、NMI指標和VI指標，這些指標通過算法運行100次求算術平均值而來。圖3反映了十種算法在人工網絡上劃分結果的各種指標隨μ值變化的對比情況。

圖3 十種算法在500節點網絡上各種指標變化曲線圖

總體上，各種算法的模塊度指標隨μ值的增大均有所下降。GN、LPA和INFOMAP三種算法尤為明顯，隨μ值增大，模塊度逐漸趨向于零，說明這些算法運行時不穩定，而其他幾種算法相對較穩定。NMI指標和VI指標隨μ值的變化，即社團結構的不明顯，均呈現出一定程度的波動。基于拓撲勢的兩種算法BTP和BITP比其他幾種算法效果好，與真實網絡結構更為相近。與BTP算法相比，BITP算法的NMI指標較高，VI指標較低。這是由于BITP算法考慮到真實網絡中節點的相關性信息，劃分出來的社團結構要比BTP算法更加合理，與真實網絡結構也更為接近，差異也較小。

4.2 真實網絡數據集

為了進一步驗證本文算法社團劃分的效果，在真實網絡數據集對其進行測試，以空手道俱樂部網絡[20]和寬吻海豚網絡[21]為例。

空手道俱樂部網絡可表示為G=<34,78>，即網絡中節點數為34、邊的數目為78。采用BITP算法對其進行社團結構挖掘，首先計算網絡中所有節點的相關拓撲勢，節點的相關拓撲勢分布如圖4(a)所示。其中，極大勢值為節點1和節點34，分別初始化這兩個節點的標簽為各自的標號(即標簽分別設為1和34)。然后按照上述標簽傳播規則更新其余節點的標簽。最終社團劃分結果如圖4(b)所示。多次運行BITP算法，與真實網絡結構相比，均只有節點3被劃分錯誤，準確率為94.4%，模塊度為0.3600。

圖4 空手道俱樂部網絡社團結構

寬吻海豚網絡可表示為G=<62,159>，即網絡中節點數為62、邊的數目為159。節點的相關拓撲勢分布如圖5(a)所示。極大勢值為節點46和節點58，分別初始化這兩個節點的標簽為46和58。然后按照上述標簽傳播規則更新其余節點的標簽。最終社團劃分結果如圖5(b)所示。多次運行BITP算法，與真實網絡結構相比，均只有節點28和節點40被劃分錯誤，準確率為93.8%，模塊度為0.3735。

圖5 寬吻海豚網絡社團結構

將BITP算法和其他幾種算法在這兩個真實網絡數據集上進行社團結構挖掘的結果進行對比分析。表2反映了這幾種算法對應的模塊度指標、NMI指標和VI指標。可以看出，本文算法在兩個真實網絡數據集上的NMI指標最高，VI指標最低。

表2 幾種算法對應的各種指標對比

5 結 語

本文提出了一種基于相關拓撲勢的社團發現算法。算法將節點的相關性引入到拓撲勢的計算中，并采用標簽傳播的方法控制社團規模。與幾種傳統的社團發現算法在人工合成網絡和真實網絡上進行驗證，結果表明本文算法相對穩定且能夠取得較高的社團劃分精度。整個算法時間復雜度為O(n)，適合于大規模復雜網絡的社團結構挖掘。針對現有社團結構研究大部分針對無向無權網絡，下階段考慮將基于拓撲勢的算法應用到加權網絡中，并進一步提高算法各方面的性能。

[1]GirvanM,NewmanMEJ.Communitystructureinsocialandbiologicalnetworks[J].ProceedingsoftheNationalAcademyofSciencesoftheUnitedStatesofAmerica,2002,99(12):7821-7826.

[2]NewmanMEJ.Detectingcommunitystructureinnetworks[J].TheEuropeanPhysicalJournalB-CondensedMatterandComplexSystems,2004,38(2):321-330.

[3]NewmanMEJ,GirvanM.Findingandevaluatingcommunitystructureinnetworks[J].PhysicalReviewE,2004,69(2):026113.

[4]ClausetA,NewmanMEJ,MooreC.Findingcommunitystructureinverylargenetwork[J].PhysicalReviewE,2004,70(6):066111.

[5]BlondelVD,GuillaumeJL,LambiotteR,etal.Fastunfoldingofcommunitiesinlargenetworks[J].JournalofStatisticalMechanics:TheoryandExperiment,2008(10):P10008.

[6]RaghavanUN,AlbertR,KumaraS.Nearlineartimealgorithmtodetectcommunitystructuresinlarge-scalenetworks[J].PhysicalReviewE,2007,76(3):036106.

[7]PonsP,LatapyM.Computingcommunitiesinlargenetworksusingrandomwalks[C]//Proceedingsofthe20thInternationalSymposiumonComputerandInformationSciences,2005:284-293.

[8]NewmanMEJ.Findingcommunitystructureusingtheeigenvectorsofmatrices[J].PhysicalReviewE,2006,74(3):036104.

[9]GfellerD,DeLRP.Spectralcoarsegrainingandsynchronizationinoscillatornetworks[J].PhysicalReviewLetters,2008,100(17):174104.

[10]RosvallM,BergstromCT.Mapsofrandomwalksoncomplexnetworksrevealcommunitystructure[J].ProceedingsoftheNationalAcademyofSciencesoftheUnitedStatesofAmerica,2008,105(4):1118-1123.

[11] 淦文燕,赫南,李德毅,等.一種基于拓撲勢的網絡社區發現算法[J].軟件學報,2009,20(8):2241-2254.

[12] 張健沛,李泓波,楊靜,等.基于拓撲勢的網絡社區節點重要度排序算法[J].哈爾濱工程大學學報,2012,33(6):745-752.

[13] 石立新,張俊星.基于勢函數的標簽傳播社區發現算法[J].計算機應用,2010,34(3):738-741.

[14] 張桂杰,張健沛,楊靜,等.基于拓撲勢的局部化重疊社區識別[J].吉林大學學報:理學版,2015,53(4):730-738.

[15]ZhangY,WangJ,WangY,etal.Parallelcommunitydetectiononlargenetworkswithpropinquitydynamics[C]//Proceedingsofthe15thACMSIGKDDConferenceonKnowledgeDiscoveryandDataMining,2009:997-1006.

[16]GanWY.Studyontheclusteringproblemindatamining[D].Nanjing:NanjingUniversityofScienceandTechnology,2003.

[17]DanonL,Díaz-GuileraA,DuchJ,etal.Comparingcommunitystructureidentification[J].JournalofStatisticalMechanics:TheoryandExperiment,2005(9):P09008.

[18]Meil?M.Comparingclusteringsbythevariationofinformation[C]//16thAnnualConferenceonLearningTheoryand7thKernelWorkshop,2003:173-187.

[19]LancichinettiA,FortunatoS,RadicchiF.Bechmarkgraphsfortestingcommunitydetectionalgorithms[J].PhysicalReviewE,2008,78(4):046110.

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

[21]LusseauD,SchneiderK,BoisseauOJ,etal.ThebottlenosedolphincommunityofDoubtfulSoundfeaturesalargeproportionoflong-lastingassociations[J].BehavioralEcologyandSociobiology,2003,54(4):396-405.

COMMUNITY DETECTION ALGORITHM BASED ON INTERRELATED TOPOLOGICAL POTENTIAL

Zhao Wentao1,2Zhao Haohao1Meng Lingjun1

1(SchoolofComputerScienceandTechnology,HenanPolytechnicUniversity,Jiaozuo454000,Henan,China)2(KeyLaboratoryofMineInformationResearchatGeneralUniversitiesinHenanProvince,Jiaozuo454000,Henan,China)

Since the traditional methods obtain low precision in division and low resolution in module function, an algorithm of community detection BITP is proposed based on the interrelated topological potential. The algorithm introduces the interrelated topological potential to evaluate the influence of nodes by considering the correlation factor between nodes. The nodes with extreme potential are searched at first. The sizes of the local communities are controlled by adopting the method of label propagation. The experimental results on synthetic and real-world networks show that the proposed algorithm is relatively stable and achieves higher precision. It is more suitable for detecting community structure in large-scaled and complex networks with a time complexity ofO(n)andnopriorknowledge.

Community structure Complex network Interrelated topological potential Label propagation

2015-09-17。河南省科技攻關計劃項目(142102210435)；河南省高等學校礦山信息化重點學科開放實驗室開放基金項目(ky2012-02)。趙文濤，教授，主研領域：數據庫，數據挖掘，大數據。趙好好，碩士生。孟令軍，碩士生。

TP

ADOI:10.3969/j.issn.1000-386x.2017.01.047