大規(guī)模網絡中局部層次重疊社區(qū)的檢測

王一萍

大規(guī)模網絡中局部層次重疊社區(qū)的檢測

王一萍

（齊齊哈爾大學 計算機與控制工程學院，黑龍江 齊齊哈爾 161006）

現實世界網絡的規(guī)模越來越大，使得檢測社區(qū)的工作變得更具有挑戰(zhàn)性．提出了一種可擴展的局部社區(qū)檢測方法，可有效地發(fā)現網絡中給定節(jié)點的重疊社區(qū)．通過考慮圖中鏈接對的相似性及它們在多個環(huán)境中的參與程度，確定加入鏈接對的順序，形成有意義的分層社區(qū)．實驗評估時使用了5個大型真實網絡的真實社區(qū)，結果表明，LDLC算法在準確性和效率方面都顯著優(yōu)于最先進的方法．

復雜網絡；等級社區(qū)；社區(qū)檢測；分散

社區(qū)結構是現實世界網絡的一個重要特性[1]．社區(qū)是有共同屬性的節(jié)點組，如2個人可能在同一所學校、2部電影可能至少有一個共同演員．然而，社區(qū)往往是重疊的．如社交網絡中某個人可能存在很多社區(qū)，如家人、同事、大學同學社區(qū)等．很明顯社區(qū)可能以不同方式重疊，如同事也可能是大學同學．重疊社區(qū)可能有一個復雜的聯結結構，與不重疊社區(qū)相比，識別重疊社區(qū)更具挑戰(zhàn)性．早期社區(qū)檢測方法側重于對網絡節(jié)點進行分組，或者側重于刪除分離集群的鏈接[2]764．然而，這些方法沒有考慮社區(qū)重疊，從而無法準確地表示網絡的社區(qū)結構．已有很多算法允許節(jié)點屬于幾個重疊社區(qū)[3-5]，但不適用于大數據的海量圖．需要從全局結構轉移到網絡的局部觀點，在局部上擴展感興趣社區(qū)中的一組目標節(jié)點．

本文將重點放在網絡中單個節(jié)點的鄰接點上，提取它的可能重疊社區(qū)．借鑒鏈接聚類的思想，采用相似性度量，有效地處理社區(qū)之間密集鏈接的重疊．直覺上，當對鏈接分組時，應該捕獲鏈接屬于多個重疊社區(qū)的節(jié)點．利用一種基于分散度的聯結強度的測量來量化參與多個社區(qū)的相鄰節(jié)點．

1 背景知識

1.1 鄰域網絡

大規(guī)模圖的挖掘通?；诠?jié)點的局部鄰域[6-7]，允許對給定節(jié)點的鄰接點集合進行各種分析．集中于節(jié)點的局部鄰域，以擴展到大型網絡中，因為可以對網絡中的所有節(jié)點并行執(zhí)行．在社交網絡的背景下，這個節(jié)點的直接鄰接點通常被稱為結點的鄰域網絡（egonet）．

1.2 鏈接強度度量

對于社交網絡，有共同背景的人更有可能分享共同活動． 因此，嵌入性可有效地應用于夫妻的識別[5]85．

使用式（4），發(fā)現式（4）第3次迭代后產生的值較好．

1.3 分區(qū)密度

2 LDLC算法

LDLC是一種聚類算法，目標是揭示網絡中單個目標節(jié)點可能重疊社區(qū)的層次結構

LDLC算法描述：

2.1 加載egonet初始化社區(qū)

2.2 計算u的鄰接點的遞歸分散值

2.3 計算鏈接節(jié)點對的相似性

目的是得出共享公共節(jié)點egonet中所有對鏈接的相似性．為此，對于egonet中的每個節(jié)點，檢查其鏈接的所有可能節(jié)點的相似性，使用小頂堆可以使保持鏈接對的相似性排序．首先使用Jaccard相似系數計算2個鏈接的距離，然后使用之前計算的遞推分散值來平衡這個距離，使用公式（6），最后將得到的相似值插入堆中，保持所有節(jié)點對的相似性．

2.4 創(chuàng)建樹狀圖

2.5 分析LDLC

2.6 減少搜索空間

LDLC工作在目標節(jié)點的egonet上，因為網絡全局結構中的社區(qū)檢測對于大規(guī)模的圖來說是費時的．然而在網絡中某些節(jié)點的egonet中檢測社區(qū)可能具有同等的成本．特別是，許多現實世界的網絡，如互聯網、萬維網和引文網，表現出冪律度分布，其中一些節(jié)點度很大．因此，這些節(jié)點各自egonet的大小通常與網絡的大小相當．

算法有效地發(fā)現具有大型egonet節(jié)點的社區(qū)結構，需要在egonet上應用一種采樣技術來減少搜索空間．一種簡單的方法是執(zhí)行隨機抽樣，隨機抽取egonet中節(jié)點的一個子集，并將LDLC應用于包含這些節(jié)點的相應子圖上．這種方法成功地減少執(zhí)行算法所需的時間，然而，度數高的節(jié)點鄰域的隨機樣本可能包括許多不同的節(jié)點．

3 實驗評估

將LDLC與基于種子集展開的3種效果較好的社區(qū)檢測算法進行了比較，即LEMON，LOSP，Heat-Kernel[10]．這3種算法基于局部社區(qū)檢測思想，可在相同的實驗設置中與LDLC方法進行比較．

3.1 數據集

數據集包括５個不同大小的社交網絡、合著網絡和協作網絡（見表1）．使用Python2.7和Snap.py接口實現了LDLC系統．

表1 分值比較

3.2 算法的評估

3.3 執(zhí)行時間比較

執(zhí)行時間評估LDLC見表2．采用citeHeSBHL方法，對于每個數據集，執(zhí)行5 000次LDLC試驗，包括均勻隨機地選擇網絡中的一個節(jié)點作為種子．對于數據集5個較小的網絡，對LEMON，LOSP，HeatKernel執(zhí)行相同的實驗．由表2可以看出，LDLC在執(zhí)行時間方面明顯優(yōu)于LEMON和LOSP．這是預期的，因為LDLC只在目標節(jié)點的egonet上操作．為了產生egonet，只需要在目標節(jié)點的所有鄰居的集合上應用交集．相反，LEMON和LOSP執(zhí)行多個隨機游走來生成目標節(jié)點周圍的本地鄰域，這一過程在時間上要花費得多．

表2 執(zhí)行時間比較 s

4 結論

本文提出一種大規(guī)模網絡上局部社區(qū)檢測算法LDLC．LDLC的重點是網絡中目標節(jié)點的egonet，并對egonet的鏈接對進行分層聚類．研究了評估網絡中聯結強度的度量，通過使用遞歸色散度量來平衡２個鏈接的相似性，并優(yōu)先考慮在單個上下文中功能的相互鄰居對鏈接的分組．因此，該方法能夠適當地處理重疊社區(qū)，并提供更高的準確性．同時，也揭示了網絡中節(jié)點社區(qū)的豐富層次結構，并將LDLC與３種最先進的本地社區(qū)檢測方法進行比較，以突出LDLC方法在處理多個社區(qū)的重疊區(qū)域時的有效性．此外，對真實社區(qū)的準確性，發(fā)現LDLC在廣泛的公開可用網絡中的性能顯著優(yōu)于大部分算法．

[1] Fortunato S．Community detection in graphs[J]．Physics Reports，2010（3）：161-174

[2] Ahn Y Y，Bagrow J P，Lehmann S．Link communities reveal multiscale complexity in networks[J]．Nature，2010（466）：761-764

[3] 潘劍飛，董一鴻，陳華輝，等．基于結構緊密性的重疊社區(qū)發(fā)現算法[J]．電子學報，2019（1）：63-66

[4] 牛新征，司偉鈺，佘堃．基于進化聚類的動態(tài)網絡社團發(fā)現[J]．軟件學報，2017（7）：42-46

[5] 吳蔚蔚，劉功申，黃晨．基于相似度的社團劃分算法[J]．計算機工程，2015（11）：84-89

[6] 宋俐，謝剛，楊云云．基于模糊聚類的社團劃分算法[J]．計算機工程，2016（8）：6-11

[7] 邱少明，於濤，杜秀麗，等．基于節(jié)點多屬性相似凝聚的社團劃分算法[J]．計算機工程，2019（8）：54-60

[8] 張振宇，朱培棟，王可，等．拓撲結構與節(jié)點屬性綜合分析的社區(qū)發(fā)現算法[J]．計算機技術與發(fā)展，2018（4）：33-37

[9] 朱牧，孟凡榮，周勇．基于鏈接密度聚類的重疊社區(qū)發(fā)現算法[J]．計算機研究與發(fā)展，2013（12）：65-70

[10] 時京晶．三種經典復雜網絡社區(qū)結構劃分算法研究[J]．電腦與信息技術，2011（4）：71-72

Detecting local hierarchical overlapping communities of large network

WANG Yiping

（School of Computer and Control Engineering，Qiqihar University，Qiqihar 161006，China）

The growing size of real-world networks makes detecting community more challenging．An extensible local community detection method is proposed，which can effectively find the overlapping communities of a given node in the network．By considering the similarity of the link pairs in the figure and their participation in multiple environments，determine the order in which the link pairs are added to form a meaningful hierarchical community．The results show that the LDLC algorithm is significantly superior to the most advanced methods in both accuracy and efficiency．

complex networks；hierarchical communities；community detection；dispersion

TP393

A

10.3969/j.issn.1007-9831.2020.10.007

1007-9831（2020）10-0027-05

2020-05-28

王一萍（1971-），女，黑龍江伊春人，副教授，碩士，從事復雜網絡與群智能研究．E-mail：wypyzh2002@163.com