基于度中心性局部擴(kuò)展的社區(qū)劃分算法?

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

（江蘇大學(xué)計(jì)算機(jī)科學(xué)與通信工程學(xué)院 鎮(zhèn)江 212013）

1 引言

隨著通信技術(shù)和互聯(lián)網(wǎng)的高速發(fā)展，移動(dòng)智能設(shè)備日漸普及，社交網(wǎng)絡(luò)作為移動(dòng)互聯(lián)的核心應(yīng)用，已成為人們?nèi)粘贤ń涣鞯闹匾?。根?jù)新浪官方發(fā)布的2019年Q2財(cái)務(wù)報(bào)表顯示，新浪微博第二季度營收4.318億美元，六月活躍用戶高達(dá)4.86億。社交網(wǎng)絡(luò)具有實(shí)時(shí)性強(qiáng)、數(shù)據(jù)龐大、覆蓋用戶廣泛和關(guān)系維度復(fù)雜等特點(diǎn)，吸引了學(xué)術(shù)界大量學(xué)者的關(guān)注，成為熱門的研究方向。

社交網(wǎng)絡(luò)作為人類社會(huì)在虛擬網(wǎng)絡(luò)中的延伸，在人們?nèi)粘Ｉ钪邪缪萘擞又匾慕巧?，它弱化了空間的概念，使得世界上任何位置的兩個(gè)人都可能在社交網(wǎng)絡(luò)中相遇。因此社交網(wǎng)絡(luò)也具備了社區(qū)屬性，它是社交網(wǎng)絡(luò)模塊化［1］特性的一種體現(xiàn)。目前學(xué)術(shù)界沒有對(duì)社交網(wǎng)絡(luò)的社區(qū)屬性作一個(gè)統(tǒng)一定義，如若把社交網(wǎng)絡(luò)映射到圖結(jié)構(gòu)：用戶實(shí)體對(duì)應(yīng)節(jié)點(diǎn)，用戶關(guān)系對(duì)應(yīng)節(jié)點(diǎn)間鏈接，社區(qū)則是子圖結(jié)構(gòu)，社區(qū)內(nèi)部節(jié)點(diǎn)鏈接相比于社區(qū)之間更為密集。社區(qū)結(jié)構(gòu)在一定程度上反映了真實(shí)的社會(huì)關(guān)系，不同的社區(qū)往往代表了不同的用戶群體，如親友、同城交友、明星粉絲等群體，該群體內(nèi)的用戶往往具有相同興趣或?qū)傩蕴卣?。社區(qū)劃分的研究為網(wǎng)絡(luò)演化、鏈接預(yù)測、影響力分析以及信息傳播等方向提供了理論依據(jù)，在優(yōu)化基礎(chǔ)網(wǎng)絡(luò)設(shè)施、好友推薦、商業(yè)營銷，輿情監(jiān)測等領(lǐng)域有著重要的實(shí)際應(yīng)用價(jià)值。

社交網(wǎng)絡(luò)規(guī)模的進(jìn)一步擴(kuò)大，對(duì)社區(qū)劃分研究提出了更高的挑戰(zhàn)。由于高昂的時(shí)間復(fù)雜度原因，一些經(jīng)典的社區(qū)劃分算法［1］已無法滿足性能要求，而基于局部擴(kuò)展思想的社區(qū)劃分算法［2］從局部出發(fā)，逐步擴(kuò)展，而非考慮整個(gè)網(wǎng)絡(luò)信息，能快速發(fā)掘出社區(qū)結(jié)構(gòu)，適用于大規(guī)模的網(wǎng)絡(luò)中。然而，基于局部擴(kuò)展思想的社區(qū)劃分算法存在穩(wěn)定性問題，隨著選擇初始種子和擴(kuò)展方向的不同，算法運(yùn)行可能得到截然不同的結(jié)果。

針對(duì)基于貪婪優(yōu)化Surprise函數(shù)的社區(qū)劃分算法［3］（AGSO）初始種子鏈接隨機(jī)選擇策略而導(dǎo)致不穩(wěn)定性問題，本文以AGSO算法為基礎(chǔ)進(jìn)行改進(jìn)，提出了一種基于度中心性局部擴(kuò)展的社區(qū)劃分算法（Community Detection Algorithm Based on De?gree-Centralized Local Extension，DCLE）。在初始鏈接選擇階段，計(jì)算每個(gè)節(jié)點(diǎn)的度中心性［4］（De?gree Centrality），其次將網(wǎng)絡(luò)鏈接兩端節(jié)點(diǎn)的度中心性之和作為鏈接的度中心性并降序排序，將度中心性最大的鏈接作為初始鏈接加入網(wǎng)絡(luò)結(jié)構(gòu)中。避免了AGSO算法隨機(jī)選擇而帶來的不穩(wěn)定性問題，提高算法性能和生成社區(qū)的質(zhì)量。

2 相關(guān)工作

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

3 概念及定義

3.1 社交網(wǎng)絡(luò)

社交網(wǎng)絡(luò)作為真實(shí)社會(huì)在網(wǎng)絡(luò)世界中的延伸，可以抽象為圖結(jié)構(gòu)G=（V，E），其中V=｛v1，v2，v3，…，vn｝為網(wǎng)絡(luò)中節(jié)點(diǎn)集合，n=|V|表示網(wǎng)絡(luò)節(jié)點(diǎn)的數(shù)量，E=｛eij|，vi，vj∈V，i≠j｝表示鏈接關(guān)系集合，其中表示節(jié)點(diǎn)vi和vj之間存在鏈接關(guān)系。

3.2 社區(qū)結(jié)構(gòu)

社區(qū)是網(wǎng)絡(luò)拓?fù)鋱D中的子圖結(jié)構(gòu)，如圖1所示，社區(qū)結(jié)構(gòu)內(nèi)部節(jié)點(diǎn)鏈接的密度高于社區(qū)之間鏈接的密度，意味著社區(qū)內(nèi)部關(guān)系更為密切，也符合對(duì)現(xiàn)實(shí)社會(huì)社區(qū)的認(rèn)知。

圖1 社區(qū)結(jié)構(gòu)

3.3 度中心性

在無向圖中，度（Degree）表示該節(jié)點(diǎn)的鄰邊的個(gè)數(shù)。度越大表示該節(jié)點(diǎn)在網(wǎng)絡(luò)中越重要，而大型網(wǎng)絡(luò)中節(jié)點(diǎn)的度往往很大，無法直觀地度量節(jié)點(diǎn)的重要程度，因此采用度中心性［4］（Degree Centrality）作為節(jié)點(diǎn)在網(wǎng)絡(luò)中重要程度的直接度量。一個(gè)節(jié)點(diǎn)的度中心性越大，表示該節(jié)點(diǎn)在網(wǎng)絡(luò)中鄰邊越多，影響力越大。度中心性是社交網(wǎng)絡(luò)中影響力的一種度量方式，其測量和節(jié)點(diǎn)的度直接相關(guān)，計(jì)算公式為

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

3.4 評(píng)價(jià)指標(biāo)

3.4.1 模塊度Q函數(shù)

模塊度Q函數(shù)最早由Newman和Girvan提出，定義為網(wǎng)絡(luò)結(jié)構(gòu)中社區(qū)內(nèi)部鏈接所占比例與隨機(jī)網(wǎng)絡(luò)中社區(qū)內(nèi)部鏈接比例期望的差值。通常用模塊度Q值衡量社區(qū)劃分的質(zhì)量，Q值越大，表明劃分的社區(qū)結(jié)構(gòu)準(zhǔn)確性越高。模塊度Q函數(shù)公式為

式中：m為網(wǎng)絡(luò)中鏈接總數(shù)，Aij表示網(wǎng)絡(luò)對(duì)應(yīng)鄰接矩陣的一個(gè)元素，當(dāng)vi和vj之間存在鏈接關(guān)系時(shí)，Aij為1，否則為0；ki表示節(jié)點(diǎn)的度；?（Ci，Cj）表示社區(qū)Ci和Cj是否相同，Ci=Cj時(shí)為1，否則為0。

3.4.2 Surprise函數(shù)

Surprise函數(shù)［7］是一種區(qū)別于傳統(tǒng)Q函數(shù)的模塊化評(píng)價(jià)指標(biāo)，它描述了在給定該隨機(jī)模型的情況下，網(wǎng)絡(luò)的某個(gè)劃分與社區(qū)節(jié)點(diǎn)和鏈接的期望分布之前的距離。其公式為

式中：F表示網(wǎng)絡(luò)結(jié)構(gòu)中最大的鏈接數(shù)；n表示網(wǎng)絡(luò)中實(shí)際的鏈接數(shù)；M表示網(wǎng)絡(luò)中社區(qū)之間最大的鏈接數(shù)；p表示社區(qū)內(nèi)部實(shí)際的鏈接數(shù)。實(shí)驗(yàn)表明，Surprise函數(shù)不存在分辨率問題。Surprise值越大表示社區(qū)劃分的結(jié)果越接近真實(shí)的社區(qū)結(jié)構(gòu)。

3.5 AGSO算法

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

4 DCLE算法

4.1 算法思想

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

算法步驟如下。

輸入：節(jié)點(diǎn)集合V，鏈接集合E，已加入網(wǎng)絡(luò)鏈接集合added_edges，其鄰近節(jié)點(diǎn)集合added_nei?bor_vertices，以及鄰近鏈接集合added_neibor_edges

輸出：社區(qū)集合C

1）初始化網(wǎng)絡(luò)為n個(gè)節(jié)點(diǎn)和0條鏈接；

2）根據(jù)式（1）計(jì)算所有節(jié)點(diǎn)v的度中心性；

3）將鏈接e兩端節(jié)點(diǎn)的度中心性之和作為鏈接的度中心性，并降序排序；

4）將度中性最高的鏈接作為種子鏈接，加入到網(wǎng)絡(luò)中，計(jì)算當(dāng)前Surprise增量，并依次更新added_edges，added_neibor_vertices和added_neibor_edges集合，執(zhí)行步驟5），直至added_neibor_edges集合為空；

5）依次計(jì)算added_neibor_edges中鏈接加入到網(wǎng)絡(luò)中的Surprise增量，將增量最大的鏈接從add?ed_neibor_edges中移除并加入到added_edges，依次更新added_neibor_vertices和added_neibor_edges，并保存當(dāng)前網(wǎng)絡(luò)的Surprise值。循環(huán)執(zhí)行步驟5），直至所有鏈接都無法使網(wǎng)絡(luò)的Surprise值增大或added_neibor_edges集合為空。

4.2 算法復(fù)雜度分析

給定節(jié)點(diǎn)數(shù)為n和鏈接數(shù)為m的網(wǎng)絡(luò)，DCLE算法時(shí)間復(fù)雜度如下。

1）計(jì)算所有節(jié)點(diǎn)度中心性需要時(shí)間復(fù)雜度為O（n）；

2）計(jì)算所有鏈接度中心性需要時(shí)間復(fù)雜度為O（m）；

3）迭代過程中，鏈接擴(kuò)展需要時(shí)間復(fù)雜度為kclink2d，其中k為社區(qū)數(shù)量，clink為社區(qū)內(nèi)部加入鏈接的平均個(gè)數(shù)，d是網(wǎng)絡(luò)節(jié)點(diǎn)平均度。

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

5 實(shí)驗(yàn)結(jié)果與分析

DCLE算法在理論上有較好性能，解決了AG?SO算法不穩(wěn)定性問題，為了驗(yàn)證算法在真實(shí)網(wǎng)絡(luò)上的可行性，本節(jié)分別在Zachary Karate Club網(wǎng)絡(luò)和多個(gè)LFR人工生成網(wǎng)絡(luò)上對(duì)DCLE算法進(jìn)行實(shí)驗(yàn)，并將其與AGSO算法在相同實(shí)驗(yàn)條件下對(duì)比分析。其中AGSO算法對(duì)初始種子選擇敏感，因此分別運(yùn)行十次取最優(yōu)值作為最終運(yùn)行結(jié)果，并將模塊度Q函數(shù)值和Surprise值作為評(píng)價(jià)指標(biāo)。

5.1 Zachary Karate Club數(shù)據(jù)集

Zachary Karate Club網(wǎng)絡(luò)［11］為社會(huì)學(xué)家Zachary歷時(shí)兩年觀察美國某一空手道俱樂部34名成員之間社會(huì)關(guān)系得到的關(guān)系網(wǎng)絡(luò)，包含34個(gè)節(jié)點(diǎn)和78條鏈接，其網(wǎng)絡(luò)結(jié)構(gòu)如圖2所示，該數(shù)據(jù)集是社區(qū)發(fā)現(xiàn)領(lǐng)域中的經(jīng)典數(shù)據(jù)集。

圖2 Zachary Karate Club網(wǎng)絡(luò)結(jié)構(gòu)

表1 Zachary Karate Club數(shù)據(jù)集

DCLE算法和AGSO算法在Zachary Karate Club數(shù)據(jù)集上的實(shí)驗(yàn)結(jié)果如表2所示。由于AGSO算法初始鏈接選擇隨機(jī)，因此運(yùn)行十次，得到十組模塊度Q值和Surprise值。從表2可以看出，AGSO算法在Zachary Karate Club網(wǎng)絡(luò)上運(yùn)行得到模塊度Q值和Surprise值處上下波動(dòng)狀態(tài)。

表2 Zachary Karate Club數(shù)據(jù)集實(shí)驗(yàn)結(jié)果

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

圖3 模塊度Q值曲線

圖4 Surprise值曲線

在小概率（同鏈接規(guī)模成反比）情況下，DCLE算法結(jié)果和AGSO算法一致；其他情況下DCLE算法的社區(qū)質(zhì)量要優(yōu)于AGSO算法，能穩(wěn)定且準(zhǔn)確地發(fā)覺社區(qū)結(jié)構(gòu)。

5.2 LFR人工網(wǎng)絡(luò)數(shù)據(jù)集

LFR網(wǎng)絡(luò)［14］是同真實(shí)數(shù)據(jù)集極為相似的人工生成數(shù)據(jù)集，可以通過配置參數(shù)以模擬各類場景，配置參數(shù)包括節(jié)點(diǎn)個(gè)數(shù)N、混雜參數(shù)μ、節(jié)點(diǎn)平均度k、節(jié)點(diǎn)最大度kmax、最小社區(qū)規(guī)模cmin和最大社區(qū)規(guī)模cmax。為了驗(yàn)證DCLE算法在大型網(wǎng)絡(luò)結(jié)構(gòu)中的性能，本文生成如表3所示的多個(gè)人工網(wǎng)絡(luò)結(jié)構(gòu)。

表3 LFR網(wǎng)絡(luò)數(shù)據(jù)結(jié)構(gòu)

圖5展示了DCLE算法和AGSO算法在不同規(guī)模LFR網(wǎng)絡(luò)上的實(shí)驗(yàn)結(jié)果對(duì)比情況。左側(cè)為DCLE算法運(yùn)行得到的Surprise值，而右側(cè)為AGSO算法多次運(yùn)行后取Surprise最大值。在初始種子鏈接選擇階段，相比于AGSO算法的隨機(jī)選擇，DCLE算法初始選擇社區(qū)內(nèi)部鏈接，直接導(dǎo)致DCLE算法運(yùn)行最終得到的Surprise值要高于AGSO算法。表明在大型網(wǎng)絡(luò)結(jié)構(gòu)上，DCLE算法的性能也要優(yōu)于AGSO算法。

圖5 LFR數(shù)據(jù)集實(shí)驗(yàn)結(jié)果

綜上所述，DCLE算法擁有良好的運(yùn)行性能，解決了AGSO算法的穩(wěn)定性問題，可以快速而準(zhǔn)確地發(fā)掘復(fù)雜網(wǎng)絡(luò)中的社區(qū)結(jié)構(gòu)，提升了所劃分社區(qū)的質(zhì)量。

6 結(jié)語

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