基于圖嵌入和多標(biāo)簽傳播的重疊社區(qū)檢測算法

高兵 宋敏 鄒啟杰 秦靜

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

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

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

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

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

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

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

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

本文貢獻主要包括以下幾個方面：

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

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

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

1 基本概念

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

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

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

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

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

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

2.1 節(jié)點更新順序

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

2.3 算法設(shè)計

2.3.1 算法步驟描述

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

算法1 OCD-GEMPA

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

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

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

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

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

3 實驗分析

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

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

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

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

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

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

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

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

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

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

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

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

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

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

3.3 評價指標(biāo)

3.3.1 模塊度EQ

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

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

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

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

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

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

3.4.1 EQ

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

3.4.2 穩(wěn)定性分析

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

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

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

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

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

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

3.5.3 重疊節(jié)點的社團隸屬數(shù)om變化對算法的影響

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

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

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

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

4 結(jié)束語

本文提出了一種基于圖嵌入和多標(biāo)簽傳播的重疊社區(qū)檢測算法OCD-GEMPA。該算法采用固定節(jié)點更新策略，提出了一種新的度量節(jié)點重要性的衡量方法和帶權(quán)重的社區(qū)歸屬系數(shù)公式，極大地避免了節(jié)點隨機選擇，提高了算法的準(zhǔn)確度。節(jié)點屬性對于節(jié)點的相似性度量也有著很重要的參考價值，下一步將繼續(xù)研究帶有節(jié)點屬性的重疊社區(qū)發(fā)現(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］郭娜，鄭曉艷. 基于最大生成樹的重疊社區(qū)發(fā)現(xiàn)算法 ［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］. 計算機應(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.