大規(guī)模網(wǎng)絡(luò)中局部層次重疊社區(qū)的檢測(cè)

王一萍

大規(guī)模網(wǎng)絡(luò)中局部層次重疊社區(qū)的檢測(cè)

王一萍

（齊齊哈爾大學(xué) 計(jì)算機(jī)與控制工程學(xué)院，黑龍江 齊齊哈爾 161006）

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

復(fù)雜網(wǎng)絡(luò)；等級(jí)社區(qū)；社區(qū)檢測(cè)；分散

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

本文將重點(diǎn)放在網(wǎng)絡(luò)中單個(gè)節(jié)點(diǎn)的鄰接點(diǎn)上，提取它的可能重疊社區(qū)．借鑒鏈接聚類的思想，采用相似性度量，有效地處理社區(qū)之間密集鏈接的重疊．直覺上，當(dāng)對(duì)鏈接分組時(shí)，應(yīng)該捕獲鏈接屬于多個(gè)重疊社區(qū)的節(jié)點(diǎn)．利用一種基于分散度的聯(lián)結(jié)強(qiáng)度的測(cè)量來量化參與多個(gè)社區(qū)的相鄰節(jié)點(diǎn)．

1 背景知識(shí)

1.1 鄰域網(wǎng)絡(luò)

大規(guī)模圖的挖掘通常基于節(jié)點(diǎn)的局部鄰域[6-7]，允許對(duì)給定節(jié)點(diǎn)的鄰接點(diǎn)集合進(jìn)行各種分析．集中于節(jié)點(diǎn)的局部鄰域，以擴(kuò)展到大型網(wǎng)絡(luò)中，因?yàn)榭梢詫?duì)網(wǎng)絡(luò)中的所有節(jié)點(diǎn)并行執(zhí)行．在社交網(wǎng)絡(luò)的背景下，這個(gè)節(jié)點(diǎn)的直接鄰接點(diǎn)通常被稱為結(jié)點(diǎn)的鄰域網(wǎng)絡(luò)（egonet）．

1.2 鏈接強(qiáng)度度量

對(duì)于社交網(wǎng)絡(luò)，有共同背景的人更有可能分享共同活動(dòng)． 因此，嵌入性可有效地應(yīng)用于夫妻的識(shí)別[5]85．

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

1.3 分區(qū)密度

2 LDLC算法

LDLC是一種聚類算法，目標(biāo)是揭示網(wǎng)絡(luò)中單個(gè)目標(biāo)節(jié)點(diǎn)可能重疊社區(qū)的層次結(jié)構(gòu)

LDLC算法描述：

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

2.2 計(jì)算u的鄰接點(diǎn)的遞歸分散值

2.3 計(jì)算鏈接節(jié)點(diǎn)對(duì)的相似性

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

2.4 創(chuàng)建樹狀圖

2.5 分析LDLC

2.6 減少搜索空間

LDLC工作在目標(biāo)節(jié)點(diǎn)的egonet上，因?yàn)榫W(wǎng)絡(luò)全局結(jié)構(gòu)中的社區(qū)檢測(cè)對(duì)于大規(guī)模的圖來說是費(fèi)時(shí)的．然而在網(wǎng)絡(luò)中某些節(jié)點(diǎn)的egonet中檢測(cè)社區(qū)可能具有同等的成本．特別是，許多現(xiàn)實(shí)世界的網(wǎng)絡(luò)，如互聯(lián)網(wǎng)、萬維網(wǎng)和引文網(wǎng)，表現(xiàn)出冪律度分布，其中一些節(jié)點(diǎn)度很大．因此，這些節(jié)點(diǎn)各自egonet的大小通常與網(wǎng)絡(luò)的大小相當(dāng)．

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

3 實(shí)驗(yàn)評(píng)估

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

3.1 數(shù)據(jù)集

數(shù)據(jù)集包括５個(gè)不同大小的社交網(wǎng)絡(luò)、合著網(wǎng)絡(luò)和協(xié)作網(wǎng)絡(luò)（見表1）．使用Python2.7和Snap.py接口實(shí)現(xiàn)了LDLC系統(tǒng)．

表1 分值比較

3.2 算法的評(píng)估

3.3 執(zhí)行時(shí)間比較

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

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

4 結(jié)論

本文提出一種大規(guī)模網(wǎng)絡(luò)上局部社區(qū)檢測(cè)算法LDLC．LDLC的重點(diǎn)是網(wǎng)絡(luò)中目標(biāo)節(jié)點(diǎn)的egonet，并對(duì)egonet的鏈接對(duì)進(jìn)行分層聚類．研究了評(píng)估網(wǎng)絡(luò)中聯(lián)結(jié)強(qiáng)度的度量，通過使用遞歸色散度量來平衡２個(gè)鏈接的相似性，并優(yōu)先考慮在單個(gè)上下文中功能的相互鄰居對(duì)鏈接的分組．因此，該方法能夠適當(dāng)?shù)靥幚碇丿B社區(qū)，并提供更高的準(zhǔn)確性．同時(shí)，也揭示了網(wǎng)絡(luò)中節(jié)點(diǎn)社區(qū)的豐富層次結(jié)構(gòu)，并將LDLC與３種最先進(jìn)的本地社區(qū)檢測(cè)方法進(jìn)行比較，以突出LDLC方法在處理多個(gè)社區(qū)的重疊區(qū)域時(shí)的有效性．此外，對(duì)真實(shí)社區(qū)的準(zhǔn)確性，發(fā)現(xiàn)LDLC在廣泛的公開可用網(wǎng)絡(luò)中的性能顯著優(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] 潘劍飛，董一鴻，陳華輝，等．基于結(jié)構(gòu)緊密性的重疊社區(qū)發(fā)現(xiàn)算法[J]．電子學(xué)報(bào)，2019（1）：63-66

[4] 牛新征，司偉鈺，佘堃．基于進(jìn)化聚類的動(dòng)態(tài)網(wǎng)絡(luò)社團(tuán)發(fā)現(xiàn)[J]．軟件學(xué)報(bào)，2017（7）：42-46

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

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

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

[8] 張振宇，朱培棟，王可，等．拓?fù)浣Y(jié)構(gòu)與節(jié)點(diǎn)屬性綜合分析的社區(qū)發(fā)現(xiàn)算法[J]．計(jì)算機(jī)技術(shù)與發(fā)展，2018（4）：33-37

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

[10] 時(shí)京晶．三種經(jīng)典復(fù)雜網(wǎng)絡(luò)社區(qū)結(jié)構(gòu)劃分算法研究[J]．電腦與信息技術(shù)，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-），女，黑龍江伊春人，副教授，碩士，從事復(fù)雜網(wǎng)絡(luò)與群智能研究．E-mail：wypyzh2002@163.com