基于度中心性局部擴展的社區劃分算法?

柳曾雄 施化吉 李 雷 施磊磊 孫祥瑜

（江蘇大學計算機科學與通信工程學院 鎮江 212013）

1 引言

隨著通信技術和互聯網的高速發展，移動智能設備日漸普及，社交網絡作為移動互聯的核心應用，已成為人們日常溝通交流的重要渠道。根據新浪官方發布的2019年Q2財務報表顯示，新浪微博第二季度營收4.318億美元，六月活躍用戶高達4.86億。社交網絡具有實時性強、數據龐大、覆蓋用戶廣泛和關系維度復雜等特點，吸引了學術界大量學者的關注，成為熱門的研究方向。

社交網絡作為人類社會在虛擬網絡中的延伸，在人們日常生活中扮演了愈加重要的角色，它弱化了空間的概念，使得世界上任何位置的兩個人都可能在社交網絡中相遇。因此社交網絡也具備了社區屬性，它是社交網絡模塊化［1］特性的一種體現。目前學術界沒有對社交網絡的社區屬性作一個統一定義，如若把社交網絡映射到圖結構：用戶實體對應節點，用戶關系對應節點間鏈接，社區則是子圖結構，社區內部節點鏈接相比于社區之間更為密集。社區結構在一定程度上反映了真實的社會關系，不同的社區往往代表了不同的用戶群體，如親友、同城交友、明星粉絲等群體，該群體內的用戶往往具有相同興趣或屬性特征。社區劃分的研究為網絡演化、鏈接預測、影響力分析以及信息傳播等方向提供了理論依據，在優化基礎網絡設施、好友推薦、商業營銷，輿情監測等領域有著重要的實際應用價值。

社交網絡規模的進一步擴大，對社區劃分研究提出了更高的挑戰。由于高昂的時間復雜度原因，一些經典的社區劃分算法［1］已無法滿足性能要求，而基于局部擴展思想的社區劃分算法［2］從局部出發，逐步擴展，而非考慮整個網絡信息，能快速發掘出社區結構，適用于大規模的網絡中。然而，基于局部擴展思想的社區劃分算法存在穩定性問題，隨著選擇初始種子和擴展方向的不同，算法運行可能得到截然不同的結果。

針對基于貪婪優化Surprise函數的社區劃分算法［3］（AGSO）初始種子鏈接隨機選擇策略而導致不穩定性問題，本文以AGSO算法為基礎進行改進，提出了一種基于度中心性局部擴展的社區劃分算法（Community Detection Algorithm Based on De?gree-Centralized Local Extension，DCLE）。在初始鏈接選擇階段，計算每個節點的度中心性［4］（De?gree Centrality），其次將網絡鏈接兩端節點的度中心性之和作為鏈接的度中心性并降序排序，將度中心性最大的鏈接作為初始鏈接加入網絡結構中。避免了AGSO算法隨機選擇而帶來的不穩定性問題，提高算法性能和生成社區的質量。

2 相關工作

近些年，諸多學者在社區劃分方向作出大量探索和研究工作，涌現了一大批優秀的科研成果，諸多社區劃分算法已經應用到了實際。其中最為經典的是由Newman和Grivan［1］提出的基于分裂思想的GN算法。GN算法不斷刪除網絡中具有最大邊介數的鏈接，直至網絡中所有的鏈接都被刪除。GN算法的時間復雜度為O（m2n），其中m為網絡中鏈接的數量，n為網絡規模，因此GN算法不適用于大規模的網絡結構，但其開創了社區劃分領域的先河，具有重要意義。為了優化GN算法時間復雜度問題，Newman等［6］隨后提出了基于聚類思想的CNM算法，首先將網絡中每個節點初始為社區，其次按照模塊度Q增量進行社區合并，直至整個網絡結構的模塊度Q值無法增大。但CNM算法存在分辨率問題［7］，在大社區和小社區的共存網絡結構中性能不佳。Reghavan等［8］首次提出了LPA算法，通過向鄰居節點傳遞標簽，最終擁有相同標簽的節點屬于同一個社區。LPA算法擁有將近線性的時間復雜度，已被廣泛應用。Gregory［9］提出了COPRA算法以識別重疊社區問題，允許一個節點攜帶多個標簽和隸屬度，并隨機選擇節點更新標簽。劉世超等［10］提出了基于標簽傳播概率的重疊社區發現算法LPPB，通過網絡結構信息計算標簽傳播的概率。冷作福［3］提出了一種基于貪婪優化Surprise函數的社區劃分算法［3］（AGSO），該算法從局部擴展，將Surprise增量最大的邊依次加入到網絡中，每次擴展迭代過程中，該算法不考慮剩余全部候選鏈接，而是將已加入鏈接的鄰近鏈接加入到網絡中，直至候選鏈接集合為空或所有候選鏈接都使網絡的Surprise值增加時，算法結束。該算法基于貪婪思想進一步降低了時間復雜度，且不存在分辨率問題，但算法選取初始鏈接時使用隨機策略，不同的初始鏈接直接導致不同的精度和性能，多次執行將得到不同的結果，最終取最優值作為社區劃分結果。

3 概念及定義

3.1 社交網絡

社交網絡作為真實社會在網絡世界中的延伸，可以抽象為圖結構G=（V，E），其中V=｛v1，v2，v3，…，vn｝為網絡中節點集合，n=|V|表示網絡節點的數量，E=｛eij|，vi，vj∈V，i≠j｝表示鏈接關系集合，其中表示節點vi和vj之間存在鏈接關系。

3.2 社區結構

社區是網絡拓撲圖中的子圖結構，如圖1所示，社區結構內部節點鏈接的密度高于社區之間鏈接的密度，意味著社區內部關系更為密切，也符合對現實社會社區的認知。

圖1 社區結構

3.3 度中心性

在無向圖中，度（Degree）表示該節點的鄰邊的個數。度越大表示該節點在網絡中越重要，而大型網絡中節點的度往往很大，無法直觀地度量節點的重要程度，因此采用度中心性［4］（Degree Centrality）作為節點在網絡中重要程度的直接度量。一個節點的度中心性越大，表示該節點在網絡中鄰邊越多，影響力越大。度中心性是社交網絡中影響力的一種度量方式，其測量和節點的度直接相關，計算公式為

式中：D（i）為節點vi的度，n-1表示節點vi和其它所有節點最大可能產生的鏈接數。節點vi度中心性DC（i）取值在0～1之間，DC（i）=0表示節點vi和其他任何節點都沒有鏈接，DC（i）=1表示節點vi和其他所有節點都有鏈接關系。

3.4 評價指標

3.4.1 模塊度Q函數

模塊度Q函數最早由Newman和Girvan提出，定義為網絡結構中社區內部鏈接所占比例與隨機網絡中社區內部鏈接比例期望的差值。通常用模塊度Q值衡量社區劃分的質量，Q值越大，表明劃分的社區結構準確性越高。模塊度Q函數公式為

式中：m為網絡中鏈接總數，Aij表示網絡對應鄰接矩陣的一個元素，當vi和vj之間存在鏈接關系時，Aij為1，否則為0；ki表示節點的度；?（Ci，Cj）表示社區Ci和Cj是否相同，Ci=Cj時為1，否則為0。

3.4.2 Surprise函數

Surprise函數［7］是一種區別于傳統Q函數的模塊化評價指標，它描述了在給定該隨機模型的情況下，網絡的某個劃分與社區節點和鏈接的期望分布之前的距離。其公式為

式中：F表示網絡結構中最大的鏈接數；n表示網絡中實際的鏈接數；M表示網絡中社區之間最大的鏈接數；p表示社區內部實際的鏈接數。實驗表明，Surprise函數不存在分辨率問題。Surprise值越大表示社區劃分的結果越接近真實的社區結構。

3.5 AGSO算法

AGSO算法［3］是一種基于Surprise函數的局部擴展社區劃分算法，其根本出發點在于網絡結構的模塊度特性，即社區內部的鏈接緊密，而社區之間的鏈接較為稀疏。如若l是社區內部的一條鏈接，那么l周圍鏈接也很有可能是社區內部的鏈接。因此將鏈接l加入到網絡中后，不必考慮剩下全部的候選鏈接，僅僅考慮鏈接l附近的候選鏈接，這樣能減少搜索空間，極大程度上降低時間復雜度，提升社區劃分的效率。但是AGSO算法存在分辨率問題，原因在于AGSO算法第一步，無論將哪條鏈接加入到網絡中，Surprise增量都是相同的，因此文獻作者在初始鏈接選擇階段，隨機選擇一條鏈接加入到網絡中，多次實驗后取最優值作為最終結果。

4 DCLE算法

4.1 算法思想

DCLE算法是一種基于度中心性局部擴展的社區劃分算法，針對AGSO算法初始鏈接選擇隨機而導致的穩定性問題，DCLE算法在初始種子鏈接選擇階段，引入節點和鏈接的度中心性概念，根據社區結構內部鏈接較為密切這一特性，節點度中心性越高，則節點處于社區內部的概率越大，在擴展階段，每次將鏈接加入網絡結構中后，不再考慮剩下所有的鏈接，僅僅將該已加入網絡中的鏈接的鄰近鏈接作為候選鏈接。依次計算所有候選鏈接加入網絡后的Surprise增量，將Surprise值增量最大鏈接加入到網絡中，并將該鏈接從候選集合中刪除，直至所有鏈接都無法使網絡Surprise值增加或候選鏈接集合為空時，算法結束，得到社區劃分結果。

算法步驟如下。

輸入：節點集合V，鏈接集合E，已加入網絡鏈接集合added_edges，其鄰近節點集合added_nei?bor_vertices，以及鄰近鏈接集合added_neibor_edges

輸出：社區集合C

1）初始化網絡為n個節點和0條鏈接；

2）根據式（1）計算所有節點v的度中心性；

3）將鏈接e兩端節點的度中心性之和作為鏈接的度中心性，并降序排序；

4）將度中性最高的鏈接作為種子鏈接，加入到網絡中，計算當前Surprise增量，并依次更新added_edges，added_neibor_vertices和added_neibor_edges集合，執行步驟5），直至added_neibor_edges集合為空；

5）依次計算added_neibor_edges中鏈接加入到網絡中的Surprise增量，將增量最大的鏈接從add?ed_neibor_edges中移除并加入到added_edges，依次更新added_neibor_vertices和added_neibor_edges，并保存當前網絡的Surprise值。循環執行步驟5），直至所有鏈接都無法使網絡的Surprise值增大或added_neibor_edges集合為空。

4.2 算法復雜度分析

給定節點數為n和鏈接數為m的網絡，DCLE算法時間復雜度如下。

1）計算所有節點度中心性需要時間復雜度為O（n）；

2）計算所有鏈接度中心性需要時間復雜度為O（m）；

3）迭代過程中，鏈接擴展需要時間復雜度為kclink2d，其中k為社區數量，clink為社區內部加入鏈接的平均個數，d是網絡節點平均度。

綜合上述分析，DCLE算法的時間復雜度為m+n+kclink2d，略高于AGSO算法，但由于AGSO算法不穩定性問題而采用多次運行取Surprise最優值策略，DCLE算法最終運行時間低于AGSO算法。

5 實驗結果與分析

DCLE算法在理論上有較好性能，解決了AG?SO算法不穩定性問題，為了驗證算法在真實網絡上的可行性，本節分別在Zachary Karate Club網絡和多個LFR人工生成網絡上對DCLE算法進行實驗，并將其與AGSO算法在相同實驗條件下對比分析。其中AGSO算法對初始種子選擇敏感，因此分別運行十次取最優值作為最終運行結果，并將模塊度Q函數值和Surprise值作為評價指標。

5.1 Zachary Karate Club數據集

Zachary Karate Club網絡［11］為社會學家Zachary歷時兩年觀察美國某一空手道俱樂部34名成員之間社會關系得到的關系網絡，包含34個節點和78條鏈接，其網絡結構如圖2所示，該數據集是社區發現領域中的經典數據集。

圖2 Zachary Karate Club網絡結構

表1 Zachary Karate Club數據集

DCLE算法和AGSO算法在Zachary Karate Club數據集上的實驗結果如表2所示。由于AGSO算法初始鏈接選擇隨機，因此運行十次，得到十組模塊度Q值和Surprise值。從表2可以看出，AGSO算法在Zachary Karate Club網絡上運行得到模塊度Q值和Surprise值處上下波動狀態。

表2 Zachary Karate Club數據集實驗結果

其中第四次結果最為理想，同DCLE算法實驗結果一致，即AGSO算法初始鏈接選擇為度中心性最大鏈接時，可以得到最優模塊度Q和Surprise值；當初始鏈接選擇為社區內部鏈接時，AGSO算法也能得到較好的結果；而當初始鏈接選擇為社區之間鏈接時，AGSO算法得到的模塊度Q和Surprise值較低。DCLE算法和AGSO算法的模塊度Q值和Sur?prise值曲線分別如圖3和圖4所示。

圖3 模塊度Q值曲線

圖4 Surprise值曲線

在小概率（同鏈接規模成反比）情況下，DCLE算法結果和AGSO算法一致；其他情況下DCLE算法的社區質量要優于AGSO算法，能穩定且準確地發覺社區結構。

5.2 LFR人工網絡數據集

LFR網絡［14］是同真實數據集極為相似的人工生成數據集，可以通過配置參數以模擬各類場景，配置參數包括節點個數N、混雜參數μ、節點平均度k、節點最大度kmax、最小社區規模cmin和最大社區規模cmax。為了驗證DCLE算法在大型網絡結構中的性能，本文生成如表3所示的多個人工網絡結構。

表3 LFR網絡數據結構

圖5展示了DCLE算法和AGSO算法在不同規模LFR網絡上的實驗結果對比情況。左側為DCLE算法運行得到的Surprise值，而右側為AGSO算法多次運行后取Surprise最大值。在初始種子鏈接選擇階段，相比于AGSO算法的隨機選擇，DCLE算法初始選擇社區內部鏈接，直接導致DCLE算法運行最終得到的Surprise值要高于AGSO算法。表明在大型網絡結構上，DCLE算法的性能也要優于AGSO算法。

圖5 LFR數據集實驗結果

綜上所述，DCLE算法擁有良好的運行性能，解決了AGSO算法的穩定性問題，可以快速而準確地發掘復雜網絡中的社區結構，提升了所劃分社區的質量。

6 結語

針對AGSO算法由于初始鏈接選擇使用隨機策略而導致的社區劃分結果不穩定問題，本文提出一種基于度中心性的局部擴展DCLE算法以對其進行改進。通過計算網絡節點的度中心性，并將鏈接兩端節點的度中心性之和作為鏈接的度中心性并排序，將度中心性最高的鏈接作為初始鏈接并加入到網絡中。在局部擴展過程中，僅考慮已加入鏈接鄰近的鏈接作為候選鏈接，不再考慮剩下所有的鏈接，提高了社區劃分的時間效率，保證了社區劃分結果的穩定性。基于Zachary Karate Club和LFR人工生成網絡數據集上的實驗表明，相比于AGSO算法，DCLE算法的運行時間低，而穩定更高，驗證了基于度中心性局部擴展的社區劃分算法在社區劃分方向的可行性和有效性。當然，本文仍然存在需要提高的部分，如每次加入鏈接后，都要計算一次Surprise增量，如何提出一種更高效的方式去衡量鏈接擴展的效果，有待進一步的研究。