大規模網絡中局部層次重疊社區的檢測

王一萍

大規模網絡中局部層次重疊社區的檢測

王一萍

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

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

復雜網絡；等級社區；社區檢測；分散

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

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

1 背景知識

1.1 鄰域網絡

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

1.2 鏈接強度度量

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

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

1.3 分區密度

2 LDLC算法

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

LDLC算法描述：

2.1 加載egonet初始化社區

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

2.3 計算鏈接節點對的相似性

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

2.4 創建樹狀圖

2.5 分析LDLC

2.6 減少搜索空間

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

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

3 實驗評估

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

3.1 數據集

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

表1 分值比較

3.2 算法的評估

3.3 執行時間比較

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

表2 執行時間比較 s

4 結論

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

[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] 潘劍飛，董一鴻，陳華輝，等．基于結構緊密性的重疊社區發現算法[J]．電子學報，2019（1）：63-66

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

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

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

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

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

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

[10] 時京晶．三種經典復雜網絡社區結構劃分算法研究[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