高兵 宋敏 鄒啟杰 秦靜

摘 要：為進(jìn)一步優(yōu)化重疊社區(qū)檢測(cè)算法，提出了一種新的基于度和節(jié)點(diǎn)聚類(lèi)系數(shù)的節(jié)點(diǎn)重要性定義，按照節(jié)點(diǎn)重要性降序更新節(jié)點(diǎn)，固定節(jié)點(diǎn)更新策略，提高社區(qū)檢測(cè)的穩(wěn)定性。在此基礎(chǔ)上，提出了一種基于圖嵌入和多標(biāo)簽傳播的重疊社區(qū)檢測(cè)算法（overlapping community detection based on graph embedding and multi-label propagation algorithm，OCD-GEMPA）。該算法結(jié)合node2vec模型對(duì)節(jié)點(diǎn)進(jìn)行低維向量表示，構(gòu)建節(jié)點(diǎn)之間的權(quán)重值矩陣，根據(jù)權(quán)重值計(jì)算標(biāo)簽歸屬系數(shù)，據(jù)此選擇標(biāo)簽，避免了隨機(jī)選擇問(wèn)題。在真實(shí)數(shù)據(jù)集和人工合成數(shù)據(jù)集上對(duì)該算法進(jìn)行實(shí)驗(yàn)驗(yàn)證。實(shí)驗(yàn)結(jié)果表明，與其他重疊社區(qū)檢測(cè)算法相比，OCD-GEMPA在EQ和NMI這兩個(gè)指標(biāo)都有明顯提升，具有更好的準(zhǔn)確性和穩(wěn)定性。

關(guān)鍵詞：多標(biāo)簽傳播；圖嵌入；重疊社區(qū)檢測(cè)；節(jié)點(diǎn)重要性；節(jié)點(diǎn)更新策略

中圖分類(lèi)號(hào)：TP391?? 文獻(xiàn)標(biāo)志碼：A??? 文章編號(hào)：1001-3695（2024）05-021-1428-06

doi： 10.19734/j.issn.1001-3695.2023.09.0423

Overlapping community detection based on graph embedding and multi-label propagation algorithm

Abstract：In order to further optimize the overlapping community detection algorithm， this paper proposed a new definition of node importance based on degree and node clustering coefficient， and the nodes were updated in descending order of node importance， and the node update strategy was fixed to improve the stability of community detection. On this basis， this paper proposed an OCD-GEMPA. The algorithm combined the node2vec model to represent the nodes in a low-dimensional vector， constructed a matrix of weight values between nodes， calculated the label attribution coefficient according to the weight values， and selected labels accordingly， avoiding the problem of random selection. Experimental verification of the algorithm on real data sets and synthetic data sets shows that compared to other overlapping community detection algorithms， the OCD-GEMPA algorithm has significant improvements in both EQ and NMI indicators， with better accuracy and stability.

Key words：multi-label propagation; graph embedding; overlapping community detection; node importance; node update strategy

0 引言

現(xiàn)實(shí)生活中，各類(lèi)網(wǎng)絡(luò)隨處可見(jiàn)，例如社交網(wǎng)絡(luò)、道路交通網(wǎng)絡(luò)、文獻(xiàn)引用網(wǎng)絡(luò)，以及生物蛋白質(zhì)網(wǎng)絡(luò)［1］等。這些大規(guī)模的復(fù)雜網(wǎng)絡(luò)有著巨大的潛在價(jià)值信息。社區(qū)結(jié)構(gòu)［2］作為復(fù)雜網(wǎng)絡(luò)的重要特征，通常表現(xiàn)為社區(qū)內(nèi)部節(jié)點(diǎn)聚集，社區(qū)間節(jié)點(diǎn)分散的特點(diǎn)。然而在真實(shí)世界中，社區(qū)結(jié)構(gòu)呈現(xiàn)出一定的重疊性，即某些節(jié)點(diǎn)可能同時(shí)屬于多個(gè)社區(qū)。挖掘重疊社區(qū)結(jié)構(gòu)對(duì)于理解網(wǎng)絡(luò)中的多重歸屬性、揭示隱藏的關(guān)系、精細(xì)化社區(qū)劃分以及實(shí)現(xiàn)個(gè)性化推薦和定制服務(wù)具有重要的意義。

近年來(lái)，重疊社區(qū)檢測(cè)［3］的研究已經(jīng)取得了重大進(jìn)展，涌現(xiàn)了各種算法。其中具有代表性的算法包括基于局部擴(kuò)展優(yōu)化的算法［4］、基于派系過(guò)濾的算法［5］和基于鏈接劃分的算法［6］等。上述算法對(duì)于挖掘網(wǎng)絡(luò)社區(qū)結(jié)構(gòu)有一定效果，但其運(yùn)算優(yōu)化能力較弱，針對(duì)大規(guī)模網(wǎng)絡(luò)的社區(qū)劃分問(wèn)題較為乏力。相比之下，標(biāo)簽傳播算法的思想簡(jiǎn)單易于實(shí)現(xiàn)，無(wú)須優(yōu)化預(yù)定義的目標(biāo)函數(shù)和社區(qū)的先驗(yàn)信息就能夠以接近線性的時(shí)間復(fù)雜度挖掘出復(fù)雜網(wǎng)絡(luò)中的社區(qū)結(jié)構(gòu)。Gregory［7］提出的COPRA就是標(biāo)簽傳播算法中的典型代表。COPRA是標(biāo)簽傳播算法LPA［8］的擴(kuò)展版，其最大的優(yōu)勢(shì)在于采用多標(biāo)簽策略從而可以挖掘網(wǎng)絡(luò)中的重疊社區(qū)結(jié)構(gòu)，但仍未解決標(biāo)簽傳播算法的節(jié)點(diǎn)執(zhí)行順序所帶來(lái)的不穩(wěn)定性問(wèn)題。在執(zhí)行COPRA算法時(shí)，每次的社區(qū)劃分結(jié)果相差較大，劃分質(zhì)量高低不均，算法的穩(wěn)定性較差。另外，基于COPRA執(zhí)行過(guò)程的分析可知，因?yàn)镃OPRA無(wú)差別對(duì)待節(jié)點(diǎn)，所以標(biāo)簽傳播過(guò)程中存在標(biāo)簽隨機(jī)選擇的問(wèn)題，從而使得算法準(zhǔn)確度不高。

針對(duì)COPRA存在的不足，很多學(xué)者對(duì)其做了改進(jìn)。Lu等人［9］提出了一種改進(jìn)的重疊社區(qū)檢測(cè)算法LPANNI，引入了鄰居節(jié)點(diǎn)影響指標(biāo)NMI，在更新節(jié)點(diǎn)標(biāo)簽時(shí)計(jì)算不同鄰居節(jié)點(diǎn)的NMI值，以更好地衡量不同節(jié)點(diǎn)的重要程度，解決了無(wú)差別對(duì)待節(jié)點(diǎn)的問(wèn)題。將NMI值作為標(biāo)簽選擇的依據(jù)，極大地避免了節(jié)點(diǎn)標(biāo)簽的隨機(jī)選擇。為了進(jìn)一步提高社區(qū)發(fā)現(xiàn)的準(zhǔn)確率，劉繼等人［10］提出了一種基于圈結(jié)構(gòu)的LPANNI優(yōu)化算法，該算法采用了一種新的指標(biāo)（圈比）來(lái)衡量節(jié)點(diǎn)重要性，并按照節(jié)點(diǎn)重要性固定節(jié)點(diǎn)序列，進(jìn)一步增加標(biāo)簽傳播過(guò)程的穩(wěn)定性。但是以上兩種改進(jìn)算法在計(jì)算鄰居節(jié)點(diǎn)影響力的時(shí)候僅考慮了節(jié)點(diǎn)的局部拓?fù)浣Y(jié)構(gòu)，忽略了不相鄰的節(jié)點(diǎn)之間也存在著一定的關(guān)聯(lián)。

為了更好地利用網(wǎng)絡(luò)的全局拓?fù)浣Y(jié)構(gòu)，已有許多學(xué)者將圖嵌入［11］應(yīng)用到復(fù)雜網(wǎng)絡(luò)社區(qū)發(fā)現(xiàn)問(wèn)題上，其中最常見(jiàn)的就是圖嵌入與傳統(tǒng)聚類(lèi)算法的融合。Yang等人［12］提出了一種基于節(jié)點(diǎn)相似性和網(wǎng)絡(luò)嵌入的復(fù)雜網(wǎng)絡(luò)社區(qū)發(fā)現(xiàn)算法。該算法結(jié)合node2vec［13］獲取節(jié)點(diǎn)間的相似性值，并據(jù)此建立偏好網(wǎng)絡(luò)，完成初始社劃分。然后按照度量指標(biāo)篩選出中心節(jié)點(diǎn)，利用K-means完成最終的社區(qū)劃分。Hu等人［14］提出了一種結(jié)合node2vec和譜聚類(lèi)的社區(qū)發(fā)現(xiàn)算法。該算法首先利用node2vec獲取節(jié)點(diǎn)的嵌入向量，然后利用這些向量構(gòu)建譜聚類(lèi)算法的相似性矩陣，以對(duì)數(shù)據(jù)點(diǎn)進(jìn)行聚類(lèi)操作，從而得到社區(qū)劃分的結(jié)果。圖嵌入可以更好地利用網(wǎng)絡(luò)中的全局結(jié)構(gòu)信息，為下游任務(wù)提供良好的基礎(chǔ)，但是傳統(tǒng)聚類(lèi)只能用于非重疊社區(qū)結(jié)構(gòu)的檢測(cè)。因此，需要進(jìn)一步研究和開(kāi)發(fā)適用于重疊社區(qū)檢測(cè)的圖嵌入社區(qū)發(fā)現(xiàn)算法。

目前，研究人員提出了許多基于節(jié)點(diǎn)相似性和節(jié)點(diǎn)重要性的社區(qū)檢測(cè)算法，旨在能夠進(jìn)一步提高算法的準(zhǔn)確性和穩(wěn)定性。文獻(xiàn)［9］提出標(biāo)簽傳播算法引入了節(jié)點(diǎn)重要性NI和基于Jaccard改進(jìn)的相似性度量sim。但是，該算法在相似性度量上需要使用路徑長(zhǎng)度閾值α以控制計(jì)算復(fù)雜度，且sim并未充分利用網(wǎng)絡(luò)中的全局拓?fù)浣Y(jié)構(gòu)信息。文獻(xiàn)［12］將圖嵌入引入到社區(qū)檢測(cè)領(lǐng)域，提出了無(wú)參數(shù)社區(qū)劃分算法，解決了文獻(xiàn)［9］超參數(shù)設(shè)置問(wèn)題，同時(shí)也提高了節(jié)點(diǎn)相似性的準(zhǔn)確度。但是，圖嵌入與傳統(tǒng)聚類(lèi)的結(jié)合卻不能挖掘出更復(fù)雜的重疊社區(qū)結(jié)構(gòu)。

綜上所述，基于標(biāo)簽傳播的改進(jìn)算法并沒(méi)有兼顧穩(wěn)定性和全局拓?fù)浣Y(jié)構(gòu)的綜合考量。本文提出的基于圖嵌入模型的標(biāo)簽傳播改進(jìn)算法，結(jié)合了改進(jìn)的節(jié)點(diǎn)重要性排序方法以及更高階的相似性度量，以進(jìn)一步提高社區(qū)劃分的準(zhǔn)確性和穩(wěn)定性。

本文貢獻(xiàn)主要包括以下幾個(gè)方面：

a）提出了一種新的節(jié)點(diǎn)重要性定義，通過(guò)綜合考慮節(jié)點(diǎn)度和鄰居節(jié)點(diǎn)間關(guān)聯(lián)程度這兩個(gè)因素，可以更全面地評(píng)估節(jié)點(diǎn)的重要性；

b）設(shè)計(jì)了一種帶權(quán)重的社區(qū)歸屬系數(shù)公式，相對(duì)于傳統(tǒng)的隨機(jī)選擇方法，降低節(jié)點(diǎn)標(biāo)簽的隨機(jī)選擇性，從而更準(zhǔn)確地捕捉節(jié)點(diǎn)的歸屬關(guān)系；

c）提出了一種基于圖嵌入和多標(biāo)簽選擇的重疊社區(qū)檢測(cè)算法OCD-GEMPA，與傳統(tǒng)重疊社區(qū)檢測(cè)算法相比，算法的準(zhǔn)確度得到了顯著提升。

1 基本概念

G=（V，E）表示無(wú)向無(wú)權(quán)圖，其中V={v1，v2，…，vn}表示圖的頂點(diǎn)集合，E={e1，e2，…，en}表示圖的邊集合，n和m分別表示圖中節(jié)點(diǎn)和邊的數(shù)量。

定義1 重疊社區(qū)。網(wǎng)絡(luò)中的重疊社區(qū)集合C定義為

其中：n′表示重疊社區(qū)數(shù)量；C中的元素表示為一個(gè)重疊社區(qū)，重疊社區(qū)之間可能包含多個(gè)相同的節(jié)點(diǎn)。

定義2 圖嵌入。圖嵌入是一種將圖形數(shù)據(jù)映射到低維向量空間的技術(shù)，能夠?qū)?fù)雜的圖結(jié)構(gòu)轉(zhuǎn)換為連續(xù)的向量表示，從而便于進(jìn)行機(jī)器學(xué)習(xí)和數(shù)據(jù)分析任務(wù)。具體過(guò)程如圖1所示。

2 OCD-GEMPA算法的設(shè)計(jì)與實(shí)現(xiàn)

本文提出了基于圖嵌入和多標(biāo)簽傳播的重疊社區(qū)檢測(cè)算法（overlapping community detection based on graph embedding and multi-label propagation algorithm，OCD-GEMPA），如圖2所示，該算法的核心部分主要包括節(jié)點(diǎn)更新順序和標(biāo)簽更新策略?xún)蓚€(gè)方面。下面從這兩個(gè)方面闡述算法的思想以及具體的實(shí)現(xiàn)過(guò)程。

2.1 節(jié)點(diǎn)更新順序

目前存在的一些多標(biāo)簽傳播算法在初始化階段平等看待每個(gè)節(jié)點(diǎn)，并按照隨機(jī)順序?qū)?jié)點(diǎn)進(jìn)行更新，這使得算法極具不穩(wěn)定性。對(duì)節(jié)點(diǎn)進(jìn)行重要性評(píng)估，并將其作為節(jié)點(diǎn)更新的依據(jù)，能夠極大地降低標(biāo)簽傳播過(guò)程中所發(fā)生的不確定性。在OCD-GEMPA中，根據(jù)節(jié)點(diǎn)重要性值的大小對(duì)節(jié)點(diǎn)更新序列進(jìn)行降序排列。節(jié)點(diǎn)重要性越大，節(jié)點(diǎn)成為潛在社區(qū)中心的可能性越大。重要性大的節(jié)點(diǎn)先更新在一定程度上能夠加快算法的收斂速度。

針對(duì)于節(jié)點(diǎn)的重要性評(píng)估問(wèn)題，目前存在著許多衡量方法。其中，最為常用的方法主要包括度中心性、k-shell算法以及PageRank算法等。但是以上算法在評(píng)估節(jié)點(diǎn)重要性時(shí)，僅考慮節(jié)點(diǎn)本身的重要程度，卻忽略了其鄰居節(jié)點(diǎn)之間的緊密程度。節(jié)點(diǎn)本身的連接數(shù)量固為重要，但是鄰居節(jié)點(diǎn)之間的鏈接緊密度不容忽視，因?yàn)樗饬苛苏w的鏈接關(guān)系，能夠更加準(zhǔn)確地評(píng)估一個(gè)節(jié)點(diǎn)的重要程度。

基于以上分析，在描述節(jié)點(diǎn)重要性方面，綜合考慮了節(jié)點(diǎn)的度和局部聚類(lèi)系數(shù)，提出了一種新的基于度和節(jié)點(diǎn)聚類(lèi)系數(shù)的節(jié)點(diǎn)重要性定義，不但考慮了節(jié)點(diǎn)本身的連接數(shù)，還考慮了節(jié)點(diǎn)的鄰居之間的連接緊密度。節(jié)點(diǎn)i的重要性NI（i）定義為

其中：ki表示與節(jié)點(diǎn)i存在鏈接關(guān)系的節(jié)點(diǎn)數(shù)量；CC（i）表示節(jié)點(diǎn)i的局部聚類(lèi)系數(shù)；Ri表示與節(jié)點(diǎn)i存在鏈接關(guān)系的鄰居節(jié)點(diǎn)之間的鏈接數(shù)量（可借助經(jīng)過(guò)i的三角形數(shù)得到）。

以圖3的無(wú)向無(wú)權(quán)圖為例，計(jì)算節(jié)點(diǎn)3的重要性NI（3）的值。其中k3=3，R3=5（虛線部分表示通過(guò)節(jié)點(diǎn)3的三角形個(gè)數(shù)）， CC（3）=1.67，那么NI（3）=3×（1+1.67）=8.01，同理，節(jié)點(diǎn)5的NI值為4×（1+0.1.33）=9.32，通過(guò)計(jì)算可知節(jié)點(diǎn)5的重要性大于節(jié)點(diǎn)3。

2.2 標(biāo)簽更新策略

根據(jù)文獻(xiàn)［8］提出的多標(biāo)簽傳播策略，算法能夠檢測(cè)到網(wǎng)絡(luò)中的重疊社區(qū)結(jié)構(gòu)，其中每個(gè)節(jié)點(diǎn)可以擁有多個(gè)社區(qū)標(biāo)簽，即節(jié)點(diǎn)可被劃分到多個(gè)社區(qū)。然而在算法中，當(dāng)節(jié)點(diǎn)接收到來(lái)自鄰居節(jié)點(diǎn)的標(biāo)簽并去除掉無(wú)效標(biāo)簽的時(shí)候，會(huì)存在以下兩種隨機(jī)選擇的情況：

a）當(dāng)待選擇的鄰居節(jié)點(diǎn)標(biāo)簽具有同樣的歸屬系數(shù)值時(shí)，節(jié)點(diǎn)就會(huì)隨機(jī)選擇其中一個(gè)；

b）如果所有標(biāo)簽的歸屬系數(shù)都小于閾值也會(huì)隨機(jī)選擇其中一個(gè)。

為了盡可能避免這種隨機(jī)選擇的情況，算法采用圖嵌入模型node2vec對(duì)節(jié)點(diǎn)進(jìn)行低維向量表示，然后構(gòu)建節(jié)點(diǎn)間相似性矩陣，并將其作為歸屬系數(shù)權(quán)重，使得節(jié)點(diǎn)更偏重選擇跟它最具相似性的節(jié)點(diǎn)標(biāo)簽。

目前存在許多關(guān)于節(jié)點(diǎn)相似性的計(jì)算方法，比如Jaccard相似性、Dice相似度、katz指標(biāo)等，但是它們都有一定的局限性。例如，Jaccard沒(méi)有充分利用網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)信息，僅考慮節(jié)點(diǎn)一階鄰居共同數(shù)量，Katz指標(biāo)權(quán)重衰減因子的最優(yōu)值只能通過(guò)大量的實(shí)驗(yàn)驗(yàn)證獲得等。

圖嵌入是一種深度學(xué)習(xí)方法，它將復(fù)雜的圖數(shù)據(jù)映射為低維稠密的向量，相較于其他相似性度量，向量空間有更豐富的方法工具集。目前，基于圖嵌入的標(biāo)簽傳播算法較少，大都是基于圖嵌入做傳統(tǒng)聚類(lèi)（K-means）的非重疊社區(qū)發(fā)現(xiàn)算法，將圖嵌入結(jié)合到標(biāo)簽傳播算法中，不僅能夠極大程度地保留網(wǎng)絡(luò)的拓?fù)浣Y(jié)構(gòu)信息，獲取更高階的相似性度量，提高算法的準(zhǔn)確度，同時(shí)還能夠檢測(cè)出網(wǎng)絡(luò)中的重疊社區(qū)結(jié)構(gòu)，更加符合真實(shí)的結(jié)構(gòu)劃分。

在OCD-GEMPA算法中使用node2vec模型進(jìn)行網(wǎng)絡(luò)表示學(xué)習(xí)。不同于基于DFS鄰域的DeepWalk［15］和基于BFS鄰域的LINE［16］，node2vec是一種綜合考慮DFS鄰域和BFS鄰域的圖嵌入方法，可以看作是DeepWalk的一種擴(kuò)展。它采用了有偏的隨機(jī)游走算法并結(jié)合 skip-gram 算法學(xué)習(xí)圖嵌入，通過(guò)參數(shù)設(shè)置來(lái)控制搜索策略，從而有效地平衡了 embedding 的同質(zhì)性和結(jié)構(gòu)有效性。 相比于DeepWalk，node2vec優(yōu)化了采樣方式與序列生成方式，提高效率的同時(shí)也提升了效果。

以圖4（a）為例，采用node2vec模型學(xué)習(xí)網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)，獲取節(jié)點(diǎn)的低維向量表示。通過(guò)對(duì)節(jié)點(diǎn)做embedding，節(jié)點(diǎn)之間的相似度就轉(zhuǎn)換成了向量之間的相似度。采用余弦相似度去衡量?jī)蓚€(gè)向量之間的相似性，即為兩個(gè)向量的點(diǎn)積除以?xún)蓚€(gè)向量大小的乘積，具體公式如下：

其中：A、B表示兩個(gè)向量，Ai表示向量A的第i個(gè)元素。

基于以上方法獲得圖2的節(jié)點(diǎn)相似性矩陣W如式（5）所示，其中行列表示節(jié)點(diǎn)ID。

為了避免標(biāo)簽過(guò)多從而造成傳播過(guò)程的復(fù)雜性，本文算法采用主導(dǎo)標(biāo)簽策略，只傳播社區(qū)歸屬系數(shù)最大的主導(dǎo)標(biāo)簽，為保證主導(dǎo)標(biāo)簽的唯一性，當(dāng)出現(xiàn)多個(gè)時(shí)隨機(jī)選擇一個(gè)，節(jié)點(diǎn)u的主導(dǎo)標(biāo)簽具體表示如下：

當(dāng)節(jié)點(diǎn)u更新其標(biāo)簽時(shí)，它從其鄰居節(jié)點(diǎn)接收多個(gè)主標(biāo)簽，并形成標(biāo)簽集如下所示。

LND={l（Dl1，b1），l（Dl2，b2），…，l（Dlv，bv）}（7）

其中：v∈N（u），N（u）表示節(jié)點(diǎn)u的鄰居節(jié)點(diǎn)集合；bv表示節(jié)點(diǎn)v對(duì)社區(qū)Dlv的社區(qū)歸屬系數(shù)。

構(gòu)建的節(jié)點(diǎn)相似性矩陣作為社區(qū)歸屬系數(shù)的權(quán)重值。從上述構(gòu)建的矩陣可以看出，節(jié)點(diǎn)間的相似值均不相同，從而極大地避免歸屬系數(shù)相同而導(dǎo)致的節(jié)點(diǎn)隨機(jī)選擇標(biāo)簽的現(xiàn)象，其中帶權(quán)重的新歸屬系數(shù)計(jì)算如下：

2.3 算法設(shè)計(jì)

2.3.1 算法步驟描述

首先，根據(jù)本文提出的基于度和節(jié)點(diǎn)聚類(lèi)系數(shù)的節(jié)點(diǎn)重要性定義，計(jì)算所有節(jié)點(diǎn)的節(jié)點(diǎn)重要性值，并將它們降序排列，以確定節(jié)點(diǎn)更新的順序；然后，初始化節(jié)點(diǎn)的標(biāo)簽，將其默認(rèn)設(shè)置為主導(dǎo)標(biāo)簽；接下來(lái)，使用帶權(quán)重的社區(qū)歸屬系數(shù)來(lái)更新節(jié)點(diǎn)的標(biāo)簽，將具有較大歸屬系數(shù)的標(biāo)簽設(shè)置為節(jié)點(diǎn)的主導(dǎo)標(biāo)簽；選擇相鄰節(jié)點(diǎn)的主導(dǎo)標(biāo)簽，并過(guò)濾掉具有較小社區(qū)歸屬系數(shù)的無(wú)效標(biāo)簽，從而形成節(jié)點(diǎn)的主導(dǎo)標(biāo)簽集合；最后，當(dāng)節(jié)點(diǎn)的主導(dǎo)標(biāo)簽集合不再發(fā)生變化或達(dá)到最大迭代次數(shù)T時(shí)，算法停止，從而得到最終的重疊社區(qū)結(jié)構(gòu)。

算法1 OCD-GEMPA

2.3.2 節(jié)點(diǎn)更新與標(biāo)簽傳播示例

圖4介紹了OCD-GEMPA算法的節(jié)點(diǎn)更新和標(biāo)簽傳播過(guò)程，對(duì)節(jié)點(diǎn)NI值進(jìn)行降序排序從而獲得的節(jié)點(diǎn)更新順序?yàn)?→5→9→2→4→6→8→3→7。

以圖4（a）為給定的簡(jiǎn)單無(wú)向無(wú)權(quán)圖為例，首先，初始化節(jié)點(diǎn)標(biāo)簽為每個(gè)節(jié)點(diǎn)對(duì)應(yīng)的ID并將所有節(jié)點(diǎn)的歸屬系數(shù)設(shè)置為1，如圖4（b）所示。按照節(jié)點(diǎn)更新順序進(jìn)行節(jié)點(diǎn)標(biāo)簽傳播，以節(jié)點(diǎn)1為例，其相鄰節(jié)點(diǎn)2，4，5，6，8，9的標(biāo)簽為（2，1）（4，1）（5，1）（6，1）（8，1）（9，1），然后根據(jù)給定的帶權(quán)重的歸屬計(jì)算公式計(jì)算出標(biāo)簽的新歸屬系數(shù)值，從而得到新的節(jié)點(diǎn)標(biāo)簽集合{（2，0.160），（4，0.165），（5，0.178），（6，0.169）， （8，0.167），（9，0.170）}，按照標(biāo)簽長(zhǎng)度的倒數(shù)去掉無(wú)效標(biāo)簽，即去掉（2，0.160）（4，0.165）這兩個(gè)標(biāo)簽，最后對(duì)剩下的標(biāo)簽進(jìn)行標(biāo)準(zhǔn)化處理從而得到節(jié)點(diǎn)1最終的標(biāo)簽集合為{（5，0.249），（6，0.251），（8，0.247），（9，0.253）}，主導(dǎo)標(biāo)簽為（9，0.253），其余節(jié)點(diǎn)標(biāo)簽傳播過(guò)程與節(jié)點(diǎn)1相同，得到的最終節(jié)點(diǎn)標(biāo)簽集結(jié)果如圖4（c）所示。經(jīng)過(guò)兩次迭代，每個(gè)節(jié)點(diǎn)的標(biāo)簽集合不再發(fā)生變化，算法結(jié)束，整個(gè)網(wǎng)絡(luò)劃分成兩個(gè)社區(qū)，其中節(jié)點(diǎn)1為重疊節(jié)點(diǎn)，劃分結(jié)果如圖4（d）所示。

2.4 時(shí)間復(fù)雜度分析

假設(shè)n代表網(wǎng)絡(luò)中節(jié)點(diǎn)的個(gè)數(shù)，m代表邊的個(gè)數(shù)，k代表網(wǎng)絡(luò)節(jié)點(diǎn)的平均度數(shù)，T代表最大迭代次數(shù)。在固定節(jié)點(diǎn)更新順序階段，節(jié)點(diǎn)重要性計(jì)算的時(shí)間復(fù)雜度是O（kn+nk2），節(jié)點(diǎn)重要性排序采用基數(shù)排序算法，時(shí)間復(fù)雜度是O（n），那么在固定節(jié)點(diǎn)更新順序階段的總時(shí)間復(fù)雜度為O（kn+nk2）。在標(biāo)簽傳播階段，生成節(jié)點(diǎn)相似性矩陣的時(shí)間復(fù)雜度是O（n2），標(biāo)簽傳播的時(shí)間復(fù)雜度取決于算法的迭代次數(shù)，對(duì)于第一次迭代，它的時(shí)間復(fù)雜度是O（kn），則第一次迭代的總時(shí)間復(fù)雜度為O（n2+kn），那么標(biāo)簽傳播階段的總時(shí)間復(fù)雜度是O（T（kn+n2）。

3 實(shí)驗(yàn)分析

本文使用了7個(gè)不同規(guī)模的真實(shí)數(shù)據(jù)集和4個(gè)人工合成數(shù)據(jù)集對(duì)OCD-GEMPA算法進(jìn)行了實(shí)驗(yàn)。所有實(shí)驗(yàn)都在一臺(tái)搭載3.20 GHz的AMD Ryzen 7 5800H處理器和16 GB內(nèi)存的筆記本電腦上進(jìn)行。實(shí)驗(yàn)代碼均采用Python 3.8編寫(xiě)。

3.1 真實(shí)數(shù)據(jù)集和人工數(shù)據(jù)集

3.1.1 真實(shí)數(shù)據(jù)集

表1詳細(xì)列出了實(shí)驗(yàn)所需的7個(gè)真實(shí)網(wǎng)絡(luò)數(shù)據(jù)集，n表示網(wǎng)絡(luò)的節(jié)點(diǎn)個(gè)數(shù)，m表示網(wǎng)絡(luò)中邊的數(shù)量，k表示網(wǎng)絡(luò)中的平均度數(shù)。

3.1.2 人工數(shù)據(jù)集

LFR benchmark基準(zhǔn)程序是近年來(lái)較為廣泛使用的人工基準(zhǔn)網(wǎng)絡(luò)程序，因?yàn)槠渖傻木W(wǎng)絡(luò)可以很好地表示出節(jié)點(diǎn)度和社區(qū)規(guī)模分布的異質(zhì)性，通過(guò)調(diào)節(jié)參數(shù)來(lái)生成不同網(wǎng)絡(luò)，主要參數(shù)說(shuō)明如表2所示。

本實(shí)驗(yàn)使用LFR基準(zhǔn)程序生成了四組網(wǎng)絡(luò)，為了更好地驗(yàn)證算法的準(zhǔn)確性，每一組都會(huì)設(shè)置一個(gè)可變參數(shù)，以LFR1為例，u設(shè)置為0.1～0.5，其他參數(shù)保持不變，詳細(xì)的參數(shù)設(shè)置如表3所示。

3.2 對(duì)比算法介紹及參數(shù)設(shè)置

為了能夠更好地驗(yàn)證OCD-GEMPA的性能，將其與DEMON［17］、LFM_EX［18］、SLPA［19］、COPRA四種重疊社區(qū)檢測(cè)基線算法進(jìn)行對(duì)比實(shí)驗(yàn)，下面是算法介紹以及參數(shù)設(shè)置。

a）LFM_EX：一種基于適應(yīng)度函數(shù)和社區(qū)相似性的改進(jìn)LFM算法，解決了LFM算法由于其回溯步驟所產(chǎn)生的不歸屬任何一個(gè)社區(qū)的離散節(jié)點(diǎn)問(wèn)題。

b）DEMON：一種以局部?jī)?yōu)先的方法發(fā)現(xiàn)分層和重疊社區(qū)的算法。

c）SLPA：基于說(shuō)話人-聽(tīng)眾規(guī)則的標(biāo)簽傳播重疊社區(qū)檢測(cè)算法。

d）COPRA：基于標(biāo)簽傳播的重疊社區(qū)檢測(cè)算法，RAK的改進(jìn)算法。

本文對(duì)比算法的參數(shù)設(shè)置如下：COPRA算法中v的范圍為3～8;對(duì)于SLPA算法，在合成網(wǎng)絡(luò)中，標(biāo)記概率閾值r從0.01～0.1變化，間隔為0.01，而在真實(shí)網(wǎng)絡(luò)中，r從0.05～0.5變化。

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

3.3.1 模塊度EQ

模塊度EQ［20］用于評(píng)價(jià)社區(qū)劃分結(jié)果的優(yōu)劣。模塊度值越接近1，則表示社區(qū)劃分的質(zhì)量越高；反之模塊度越小，表明社區(qū)劃分結(jié)果較差。模塊度的定義如下：

其中：m為網(wǎng)絡(luò)中邊的總數(shù)；c為劃分得到的社區(qū)的數(shù)目；Oi為節(jié)點(diǎn)i所屬的社區(qū)個(gè)數(shù)；ki為節(jié)點(diǎn)i的度；Aij用于判斷節(jié)點(diǎn)i和j之間是否存在連接，若存在連接則Aij為1，否則為０。

3.3.2 標(biāo)準(zhǔn)化互信息NMI

標(biāo)準(zhǔn)化互信息（normalized mutual information，NMI）［21］是用于測(cè)量?jī)煞N數(shù)據(jù)分布之間吻合程度的一種方法，可以作為網(wǎng)絡(luò)社區(qū)劃分結(jié)果的評(píng)價(jià)指標(biāo)。其公式如下：

其中：CA為標(biāo)準(zhǔn)社區(qū)劃分的結(jié)果；CB為算法所得到社區(qū)劃分的結(jié)果；矩陣Ｎ的行對(duì)應(yīng)標(biāo)準(zhǔn)社區(qū)結(jié)果，列對(duì)應(yīng)算法得到的社區(qū)檢測(cè)結(jié)果；Ni.為第i行的總和；N.j為第j列的總和。NMI值越大，說(shuō)明算法劃分社區(qū)的效果越好。

3.4 真實(shí)數(shù)據(jù)集上的實(shí)驗(yàn)結(jié)果

3.4.1 EQ

圖5為OCD-GEMPA與其他四種基線算法在7個(gè)真實(shí)數(shù)據(jù)集上的實(shí)驗(yàn)結(jié)果。從圖中可以看出，OCD-GEMPA除在netscience數(shù)據(jù)集上EQ值略低于SLPA之外，在其他真實(shí)數(shù)據(jù)集上的EQ值均高于另外四種基線算法。另外，與SLPA和COPRA這兩種多標(biāo)簽傳播算法相比較，OCD-GEMPA總體上表現(xiàn)更好，這說(shuō)明引入圖嵌入模型計(jì)算節(jié)點(diǎn)相似度矩陣作為歸屬系數(shù)的權(quán)重值能夠更好地指導(dǎo)標(biāo)簽選擇，在一定程度上提高了算法的準(zhǔn)確度。

3.4.2 穩(wěn)定性分析

為了驗(yàn)證算法的穩(wěn)定性，將OCD-GEMPA算法與COPRA、SLPA這兩個(gè)經(jīng)典的標(biāo)簽傳播算法在六個(gè)真實(shí)數(shù)據(jù)集上進(jìn)行20次模塊度方差值的實(shí)驗(yàn)。表4列出了穩(wěn)定性實(shí)驗(yàn)的結(jié)果，可以看出，節(jié)點(diǎn)之間的權(quán)重極大地降低了標(biāo)簽隨機(jī)選擇的可能性，算法的穩(wěn)定性更好。

3.5 人工合成網(wǎng)絡(luò)上的實(shí)驗(yàn)結(jié)果

3.5.1 混合參數(shù)mu變化對(duì)算法的影響

圖6給出了隨著混合參數(shù)mu的不斷增加，各算法在LFR1網(wǎng)絡(luò)上的EQ值和NMI值變化。mu值不斷增加，社區(qū)相互混合，網(wǎng)絡(luò)結(jié)構(gòu)就會(huì)越復(fù)雜。以COPAR為例，在mu從0.3增加到0.4這個(gè)過(guò)程中，EQ和NMI兩值的下降幅度最大。這是因?yàn)樵谏鐓^(qū)結(jié)構(gòu)相互混合的情況下，每個(gè)社區(qū)都受到鄰居社區(qū)噪聲的影響，那么在標(biāo)簽傳播過(guò)程中鄰居節(jié)點(diǎn)的選擇就是關(guān)鍵，COPRA隨機(jī)選擇鄰居節(jié)點(diǎn)，而OCD-GEMPA是根據(jù)節(jié)點(diǎn)權(quán)重值選擇，所以從整體上看，OCD-GEMPA的下降趨勢(shì)較小，整體性能相對(duì)較好。

3.5.2 重疊節(jié)點(diǎn)參數(shù)on變化對(duì)算法的影響

圖7展示的是在重疊節(jié)點(diǎn)參數(shù)on的不斷增加的情況下，各算法在LFR2上的EQ值和NMI值變化。重疊節(jié)點(diǎn)的增加也就意味著社區(qū)之間的重合越多，網(wǎng)絡(luò)結(jié)構(gòu)越復(fù)雜。由圖7（a）知，on與EQ值呈負(fù)相關(guān)。從整體上看，OCD-GEMPA無(wú)論是EQ還是NMI值均優(yōu)于其他算法，變化幅度最小。這是因?yàn)閳D嵌入學(xué)習(xí)網(wǎng)絡(luò)拓?fù)洌ㄟ^(guò)考慮高階臨近度獲取節(jié)點(diǎn)之間更好的相似性，即便網(wǎng)絡(luò)結(jié)構(gòu)復(fù)雜，依舊可以選擇當(dāng)下最相似的鄰居節(jié)點(diǎn)，為標(biāo)簽傳播奠定良好的基礎(chǔ)。

3.5.3 重疊節(jié)點(diǎn)的社團(tuán)隸屬數(shù)om變化對(duì)算法的影響

如圖8（a）所示，隨著om值的增加，各算法在LFR3數(shù)據(jù)集上的EQ值呈現(xiàn)下降趨勢(shì)。COPRA整體波動(dòng)較大，這是因?yàn)樗惴ㄔ趫?zhí)行過(guò)程中存在鄰居節(jié)點(diǎn)隨機(jī)選擇的問(wèn)題，使得準(zhǔn)確度較低，穩(wěn)定性較差。OCD-GEMPA采用節(jié)點(diǎn)相似性矩陣作為標(biāo)簽歸屬系數(shù)的權(quán)重極大地避免了鄰居隨機(jī)選擇，在準(zhǔn)確度和穩(wěn)定度上都有了很大提高。整體表現(xiàn)優(yōu)于其他四類(lèi)基線算法。

3.5.4 節(jié)點(diǎn)數(shù)量n變化對(duì)算法的影響

圖9展示的是隨著網(wǎng)絡(luò)規(guī)模的不斷擴(kuò)大，各算法在LFR4數(shù)據(jù)集上的具體表現(xiàn)。很明顯，COPRA、SLPA和OCD-GEMPA整體波動(dòng)性較小且EQ值和NMI值較高，說(shuō)明標(biāo)簽傳播算法在大規(guī)模網(wǎng)絡(luò)重疊社區(qū)發(fā)現(xiàn)問(wèn)題上也具有良好的性能。而局部擴(kuò)展優(yōu)化算法LFM_EX的EQ值和NMI值呈現(xiàn)下降趨勢(shì)，這說(shuō)明該算法不適合大規(guī)模網(wǎng)絡(luò)的社區(qū)檢測(cè)。從整體看，OCD-GEMPA在網(wǎng)絡(luò)節(jié)點(diǎn)n不斷增加的情況下依然能夠很好地檢測(cè)重疊社區(qū)，主要原因是固定的節(jié)點(diǎn)更新順序和節(jié)點(diǎn)依據(jù)權(quán)重值選擇鄰居標(biāo)簽這兩方面使算法的準(zhǔn)確度和穩(wěn)定性都得到了很大的提高。

表5列出了節(jié)點(diǎn)數(shù)量由1 000～10 000組成的不同人工網(wǎng)絡(luò)上各算法劃分的重疊社區(qū)數(shù)量對(duì)比情況，true表示真實(shí)劃分結(jié)果。從表5可以清楚地看出，隨著網(wǎng)絡(luò)規(guī)模的不斷擴(kuò)大，OCD-GEMPA仍能夠正確地劃分社區(qū)。

4 結(jié)束語(yǔ)

本文提出了一種基于圖嵌入和多標(biāo)簽傳播的重疊社區(qū)檢測(cè)算法OCD-GEMPA。該算法采用固定節(jié)點(diǎn)更新策略，提出了一種新的度量節(jié)點(diǎn)重要性的衡量方法和帶權(quán)重的社區(qū)歸屬系數(shù)公式，極大地避免了節(jié)點(diǎn)隨機(jī)選擇，提高了算法的準(zhǔn)確度。節(jié)點(diǎn)屬性對(duì)于節(jié)點(diǎn)的相似性度量也有著很重要的參考價(jià)值，下一步將繼續(xù)研究帶有節(jié)點(diǎn)屬性的重疊社區(qū)發(fā)現(xiàn)問(wèn)題。

參考文獻(xiàn)：

［1］Li Meizi，Lu Shuyi，Zhang Lele，et al. A community detection method for social network based on community embedding ［J］. IEEE Trans on Computational Social Systems，2021，8（2）： 308-318.

［2］Acman M，Van Dorp L，Santini J M，et al. Large-scale network analysis captures biological features of bacterial plasmids ［J］. Nature Communications，2020，11（1）： 2452.

［3］Gao Yang，Yu Xiangzhan，Zhang Hongli. Overlapping community detection by constrained personalized PageRank ［J］. Expert Systems with Applications，2021，173： 114682.

［4］郭娜，鄭曉艷. 基于最大生成樹(shù)的重疊社區(qū)發(fā)現(xiàn)算法 ［J］. 計(jì)算機(jī)應(yīng)用研究，2020，37（S2）： 170-172，180. （Guo Na，Zheng Xiao-yan. Overlapping community discovery algorithm based on maximum spanning tree ［J］. Application Research of Computers，2020，37（S2）： 170-172，180.）

［5］Gupta S K，Singh D P，Choudhary J. A review of clique-based overlapping community detection algorithms ［J］. Knowledge and Information Systems，2022，64（8）： 2023-2058.

［6］Gabardo A C，Berretta R，Moscato P. M-link： a link clustering memetic algorithm for overlapping community detection ［J］. Memetic Computing，2020，12： 87-99.

［7］Gregory S. Finding overlapping communities in networks by label pro-pagation ［J］. New Journal of Physics，2010，12（10）：103018.

［8］Li Chunying，Tang Yong，Tang Zhikang，et al. Motif-based embedding label propagation algorithm for community detection ［J］. International Journal of Intelligent Systems，2022，37（3）： 1880-1902.

［9］Lu Meilian，Zhang Zhenglin，Qu Zhihe，et al. LPANNI： overlapping community detection using label propagation in large-scale complex networks ［J］. IEEE Trans on Knowledge and Data Enginee-ring，2018，31（9）： 1736-1749.

［10］劉繼，賈芳弟. 基于圈結(jié)構(gòu)的 LPANNI 優(yōu)化算法 ［J］. 計(jì)算機(jī)應(yīng)用研究，2022，39（9）：2717-2722，2744. （Liu Ji，Jia Fangdi. LPANNI optimization algorithm based on circle structure ［J］. Application Research of Computers，2022，39（9）：2717-2722，2744.）

［11］Wang Xiao，Bo Deyu，Shi Chuan，et al. A survey on heterogeneous graph embedding： methods，techniques，applications and sources ［EB/OL］. （2022）. https：//arxiv.org/abs/2011.14867.

［12］Yang Xuhua，Wang Lei，Ye Lei，et al. Complex network community detection algorithm based on node similarity and network embedding ［J］. Computer Science，2022，49（3）： 121-128.

［13］Grover A，Leskovec J. node2vec： scalable feature learning for networks ［C］// Proc of the 22nd ACM SIGKDD International Confe-rence on Knowledge Discovery and Data Mining.New York：ACM Press，2016： 855-864.

［14］Hu Fang，Liu Jia，Li Liuhuan，et al. Community detection in complex networks using node2vec with spectral clustering ［J］. Physica A： Statistical Mechanics and its Applications，2020，545： 123633.

［15］Berahmand K，Nasiri E，Rostami M，et al. A modified DeepWalk method for link prediction in attributed social network ［J］. Computing，2021，103： 2227-2249.

［16］Zhang Zhengyan，Yang Cheng，Liu Zhiyuan，et al. Cosine： compressive network embedding on large-scale information networks ［J］. IEEE Trans on Knowledge and Data Engineering，2020，34（8）： 3655-3668.

［17］Coscia M，Rossetti G，Giannotti F，et al. DEMON： a local-first disco-very method for overlapping communities ［C］// Proc of the 18th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining.New York：ACM Press，2012： 615-623.

［18］Zhang Lingxiao，Yan Xuefeng. An improved LFM algorithm based on fitness function and community similarity ［C］//Proc of IEEE International Conference on Parallel & Distributed Processing with Applications，Big Data & Cloud Computing，Sustainable Computing & Communications，Social Computing & Networking. Piscataway，NJ：IEEE Press，2019： 9-15.

［19］Xie Jierui，Szymanski B K，Liu Xiaoming. SLPA： uncovering overlapping communities in social networks via a speaker-listener interaction dynamic process ［C］// Proc of the 11th IEEE International Confe-rence on Data Mining Workshops. Piscataway，NJ：IEEE Press，2011： 344-349.

［20］Chattopadhyay S，Basu T，Das A K，et al. A similarity based genera-lized modularity measure towards effective community discovery in complex networks ［J］. Physica A： Statistical Mechanics and Its Applications，2019，527： 121338.

［21］Hesamipour S，Balafar M A. A new method for detecting communities and their centers using the Adamic/Adar Index and game theory ［J］. Physica A： Statistical Mechanics and Its Applications，2019，535： 122354.