融合節點屬性的局部多重社區發現算法

摘 要：局部多重社區發現是社交網絡分析中的關鍵技術，旨在揭示網絡中用戶的多重歸屬和復雜聯系。針對現有局部多重社區發現算法大多基于網絡拓撲結構，忽視節點屬性信息的問題，提出了融合節點屬性的局部多重社區發現算法（MLCDINA）。該算法將屬性網絡的結構和屬性信息相結合為節點對之間的邊權重，并通過隨機游走評估節點間結構和屬性的融合重要性（IISA）。此外，該算法引入了考慮邊權重的局部聚類系數和親密度隨機游走（IRW），以增強對子圖稠密性和IISA的評估。實驗結果表明，MLCDINA在真實屬性網絡上的Jaccard F1-score較現有算法有顯著提升，驗證了其在局部多重社區發現任務中的有效性。

關鍵詞：局部社區發現；屬性網絡；隨機游走

中圖分類號：O157.5"" 文獻標志碼：A"" 文章編號：1001-3695（2025）01-006-0042-06

doi： 10.19734/j.issn.1001-3695.2024.06.0190

Multiple local community detection with integrated node attributes

Abstract： Multiple local community detection is a key technology in social network analysis， aiming to reveal the multiple affiliations and complex connections of users within networks. Addressing the issue that most existing multiple local community detection algorithms are based on network topology and neglect node attribute information， this paper introduced an algorithm named multiple local community detection with integrated node attributes （MLCDINA）. This algorithm combined the structure and attribute information of the attributed network to determine the edge weights between node pairs and evaluated the importance of the integration of structure and attributes （IISA） through random walks. In addition， the algorithm introduced a local clustering coefficient that considered edge weights and an intimacy random walk （IRW） to enhance the evaluation of subgraph density and IISA. Experimental results indicate that MLCDINA significantly improves the Jaccard F1-score over existing algorithms on real attributed networks， verifying its effectiveness in multiple local community detection tasks.

Key words：local community detection; attributed network; random walk

0 引言

局部多重社區發現對于社交網絡研究具有重要意義。局部多重社區發現方法能夠揭示節點所屬的多個緊密聯系和共同興趣的群體，這些社區可能具有不同的特征和功能，不僅有助于了解社交網絡的功能及演化過程，而且在推薦系統、輿情監測等多個領域也顯示出其獨特價值［1，2］。

局部多重社區發現［3～10］是局部社區發現的一個擴展，聚焦于發現網絡中的重疊社區結構，即一個節點可以同時屬于多個社區，這種方法在分析社交網絡時尤為重要，因為它更準確地模擬了現實世界中個體會同時參與多個社交群體的現象。

屬性網絡不僅包含節點與節點之間的拓撲關系，各個節點還擁有豐富的屬性信息，例如在社交網絡上對用戶的文字描述、與用戶相關的評論以及用戶特有的圖片等。合理地利用屬性信息可以彌補基于網絡拓撲結構的局部多重社區發現方法的不足，有助于更精準地揭示用戶所屬的社區信息，擴展了局部多重社區發現方法的應用場景。

針對屬性網絡的全局社區發現，眾多研究者已經提出了許多基于不同思想和技術的方法［11～18］，主要包括基于屬性加權的方法、基于嵌入表示的方法、基于元啟發式的方法、基于非負矩陣分解的方法等。其中，基于屬性加權的方法［11～15］是一類經典的處理屬性網絡的方法，它利用節點屬性對網絡的邊賦予權重，得到加權圖后再進行聚類。

針對局部多重社區發現也已有大量研究［3～10］，如基于種子集擴展的方法、基于k-clique的方法和基于非負矩陣分解的方法等。然而，這些研究聚焦于如何利用網絡拓撲結構或節點拓撲性質在網絡中挖掘局部社區結構，未考慮社交網絡中不同群體間用戶屬性存在較大差異這一特性，導致在社交網絡上發現的局部社區往往存在局限性。因此，針對社交網絡的局部多重社區發現問題，不僅需要考慮網絡拓撲結構，還要充分利用豐富的節點屬性信息以挖掘局部社區結構。

HoSIM算法［5］是基于種子集擴展的方法中具有代表性的一種方法，其主要思想是基于節點的高階結構重要性發現局部社區中的核心成員，并根據核心成員以及種子節點逐步擴展以發現局部社區。然而在研究社交網絡時，HoSIM算法［5］存在一些不足。基于網絡拓撲結構評估節點重要性，未考慮節點屬性對節點重要性的影響；在隨機游走的子圖采樣過程中，基于局部聚類系數的子圖采樣策略在屬性網絡中得到結構稠密但屬性相似程度較低的子圖，導致與種子節點屬性差異較大的節點可能獲得較高評分；主動隨機游走（active random walk，ARW）在評估節點重要性時，提高了與該節點直接相連的節點的重要性，導致邊緣節點也會獲得較高的重要性，影響局部社區中核心節點的識別。

針對上述問題，本文對HoSIM算法［5］進行了改進，提出了一種融合節點屬性的局部多重社區發現算法（MLCDINA）。主要的貢獻如下：

a）在隨機游走的采樣子圖中，將子圖的結構信息和屬性信息融合后賦給節點對之間的邊權重，以衡量社交網絡中用戶之間的結構和屬性的相似程度，以便后續隨機游走評估節點的結構和屬性的融合重要性（IISA）評分。

b）提出了考慮邊權重的局部聚類系數，以衡量節點的鄰居節點的相似程度以及聚集成團的程度，使得在隨機游走的子圖采樣過程中，得到的采樣子圖稠密且屬性相似度高。

c）在標準隨機游走的基礎上，考慮到社交網絡中用戶之間不同親密程度，提出了一種新的隨機游走變體，稱為親密度隨機游走（IRW）。在評估節點的結構和屬性的融合重要性（IISA）評分時，降低了只與其相連的邊緣節點的重要性，能夠有效地度量節點的結構和屬性的融合重要性（IISA）評分。

1 相關工作

1.1 局部多重社區發現算法

現有的局部多重社區發現方法主要是基于種子集擴展的、基于k-clique的和基于非負矩陣分解的方法。a）基于種子集擴展的方法。Hollocou等人［3］提出的Multicom通過種子集的得分函數對嵌入在低維向量空間中的網絡進行聚類，找到新的種子，然后將其擴展到多個社區。Liu等人［4］通過網絡表示找到高質量種子，然后逐個擴展高質量種子以獲得多個可能重疊的社區。Li等人［5］提出的HoSIM算法基于HoSI評估節點的重要性，以及主動隨機游走（ARW）來評估節點之間的HoSI分數，并在此基礎上提出了包含子圖采樣、核心成員識別、局部社區發現三個階段的HoSIM算法來發現局部社區。Li等人［6］通過尋找包含種子節點的相關質心節點來自動確定社區數量，并利用高質量的種子集合來發現對應的社區。b）基于k-clique的方法。文獻［7，8］通過挖掘符合其結構定義的特定子圖結構進而發現局部社區。然而，基于k-clique的方法在發現社區時并不靈活，因為其發現的社區結構必須符合它們的結構定義。此外，k-clique的參數k在實際中很難確定，會顯著地影響結果。c）基于非負矩陣分解的方法。文獻［9，10］利用非負矩陣分解（non-negative matrix factorization，NMF）估計采樣子圖中的社區數目，并將節點分配到社區中，但這類方法并未充分利用網絡的結構。這些方法依賴于節點的拓撲性質或網絡的拓撲結構，并未針對社交網絡中的其他屬性信息進行整合利用。

1.2 屬性網絡社區發現算法

屬性網絡社區發現算法種類繁多，基于屬性加權的方法是其中一類經典的處理屬性網絡的方法，主要思路是利用節點屬性對網絡的邊賦予權重，得到加權圖后再進行聚類。文獻［11］使用結構和屬性相似性計算兩個連接節點之間的權重得到權重矩陣，再基于改進標簽傳播算法檢測社區。文獻［12］將節點的屬性和拓撲結構相結合，從具有相互鏈接的節點的屬性圖中生成加權圖，在此基礎上根據擴散方法進行社區發現。Wang等人［13］提出了一種基于圖卷積網絡的無監督學習方法，融合網絡拓撲和屬性信息來揭示隱藏的社區結構。Hu等人［14］通過在加權圖上建模網絡結構和節點屬性的高階模式來提升社區檢測的性能。Guo等人［15］提出了一種基于有偏隨機游走的網絡嵌入算法，設計拓撲加權度和屬性加權度來增強在社區內外邊界處的隨機游走，以精確提取社區。可以看出，基于屬性加權的方法展現出了良好的擴展性和適應性，并且具有計算復雜度較低等優點。本文參考基于屬性加權方法的一般思路，將屬性網絡的結構信息和屬性信息融合轉換為邊權重構建加權圖后進行局部多重社區發現。

2 融合節點屬性的局部多重社區發現算法分析

融合節點屬性的局部多重社區發現算法（MLCDINA）面向屬性網絡進行局部多重社區發現。核心思路是融合屬性網絡的結構信息和屬性信息轉換為邊權重以構建應用親密度隨機游走（IRW）的加權子圖，再基于IRW評估節點的結構和屬性的融合重要性（IISA）評分，最后基于評分進行局部多重社區發現。算法整體分為三步：a）子圖采樣，目的是獲取種子節點周圍合理大小的子圖，在減少計算量的同時盡可能涵蓋種子節點可能所屬的所有社區；b）核心成員識別，通過節點的結構和屬性的融合重要性（IISA）評分識別子圖內的可能存在的社區的核心成員；c）局部社區發現，以發現的核心節點和種子節點作為擴展種子集合，進一步應用適用于含權網絡的PPR算法［19］以發現局部社區。

2.1 問題描述

給定一個無向圖G=（V，E，X），其中V={vi}表示節點的集合，E表示邊的集合。A=［aij］n×n表示無向圖G的鄰接矩陣，若節點i和j之間存在邊，則aij=1，否則aij=0。X={x1，x2，…，xn}，其中xi∈Rm是與節點vi相關聯的實值屬性向量。對于一個概率向量p和任一節點u∈V，令p［u］表示在p中關于u的概率。令C={C1，C2，…，Cm}表示每個包含種子節點vs的真實社區的集合，其中vs∈V是屬于節點集合的一個種子節點。本文關注的問題是發現一組包含vs的社區集合C′={C′1，C′2，…，C′k} ，使得對于任一社區Ci∈C，存在發現到的社區C′i∈C′滿足C′i=Ci。

2.2 評價指標

本文使用Jaccard F1-score來評估社區發現方法的有效性。Jaccard F1-score指標的計算需要先計算平均召回率和平均精確率。其中平均召回率的計算如下：

給定任一種子節點vs∈V，發現到的社區集合為C′，對于一個真實社區Ci∈C，它的召回率計算式如下：

進而，平均召回率計算式如下：

類似地，給定任一種子節點vs∈V，真實社區集合為C，對于一個發現到的社區C′j∈C′，它的精確率計算式如下：

進而，平均精確率計算式如下：

則給定任一種子節點vs∈V，它的F1-score計算式如下：

在評估局部多重社區發現算法的性能時，采用Jaccard F1-score是因為其綜合了精確率與召回率兩個關鍵指標，提供了一個均衡的視角來衡量算法在識別社區結構時的效果。精確率反映了算法識別出的社區中包含的正確節點與所有識別節點的比例，而召回率則度量了算法成功找回的正確節點與真實社區中節點的比例。Jaccard F1-score作為精確率與召回率的調和平均，只有在兩者均較高時才能獲得較高的分數，從而確保了算法在社區的準確識別與完整性上的表現。

特別是在處理局部多重社區發現問題時，節點可能同時屬于多個社區，Jaccard F1-score能夠有效地捕捉這種社區重疊的特性。因此，它不僅能夠評價算法在單一社區發現上的準確性，還能在社區重疊的情況下提供更為公正的評價。

2.3 定義

本文定義了邊權重、融合邊權重的局部聚類系數、擴散、結構和屬性的融合重要性（IISA）、親密度隨機游走（IRW）、子圖對節點IISA評分、節點的IISA評分、核心成員等八個定義，其中邊權重參考了基于屬性加權的方法普遍采用的一般定義。

1）邊權重

結構權重是基于網絡拓撲結構提取的，而網絡拓撲結構是社區發現中最重要的相似性度量。節點u和v的結構權重采用Jaccard相似性計算。它是節點u和v的共同鄰居節點數與u和v的所有鄰居節點數的比值。N（u）為節點u的鄰居節點的集合。節點u和v的Jaccard相似度J（u，v）的計算如式（1）所示。

由于研究的屬性為連續數值型屬性，故節點間的屬性權重采用余弦相似度計算。xi是與節點vi相關聯的實值屬性向量。節點u和v的屬性余弦相似度CS（u，v）計算如式（2）所示。

融合Jaccard相似度J（u，v）和屬性余弦相似度CS（u，v），α為控制J（u，v）和CS（u，v）之間平衡的參數。若節點u和v之間存在邊，則auv=1，否則auv=0。邊權重W（u，v）計算如式（3）所示。

W（u，v）=auv［αJ（u，v）+（1－α）CS（u，v）］（3）

其中：α=1對應于只考慮拓撲結構情況，α=0對應于只考慮節點屬性情況。一般來說，可以引入一個非線性融合函數來代替式（3），然而這顯然會使模型變得更加復雜。鑒于社交網絡中網絡的結構信息和屬性信息均體現了現實社區的某些特征，后續實驗部分針對α的取值進行了敏感性分析。

2）融合邊權重的局部聚類系數

給定一個節點u∈V，ku是節點u的度數，局部聚類系數Lcc（u）為u的所有鄰居之間連接邊數與所有鄰居之間最大可能的邊數之比，其計算如式（4）所示。

在含權網絡中，W（i， j）表示節點i和j之間的邊權重，定義融合邊權重的局部聚類系數wLcc（u）為節點u的局部聚類系數與其鄰居節點之間的平均邊權重之積，其計算如式（5）所示。

局部聚類系數衡量了種子節點與其鄰居節點之間的內聚性［20］。然而對于含權網絡，僅僅考慮網絡拓撲結構的局部聚類系數未能考慮到鄰居節點之間的同質性［21］，未能充分利用含權網絡的信息。據式（3），本文定義的邊權重實際上由衡量拓撲相似度的Jaccard相似度和衡量屬性相似度的余弦相似度組成，其可以很好地反映節點對之間的拓撲和屬性的同質性水平。在局部聚類系數的基礎上，融入鄰居節點之間的平均邊權重的局部聚類系數可以反映種子節點的鄰居節點的成團程度以及同質性水平，更好地利用了含權網絡的信息。

節點具有較高的融合邊權重的局部聚類系數，不僅反映了該節點與鄰居節點之間較高的內聚性，同時也反映了聚集的節點群具有較高的同質性。這種同質性不僅體現在節點屬性的相似性上，還體現在節點間連接的緊密程度上。由于后續提出的親密度隨機游走（IRW）傾向于選擇與種子節點屬性和結構更接近的路徑進行游走，所以在同質性較高的社區中，IRW能夠更加精確地識別出社區邊界，避免因網絡噪聲或邊緣節點的影響而偏離社區核心。因此，融合邊權重的局部聚類系數不僅是對節點局部結構的量化描述，也為后續的IRW提供了良好的游走環境，進而在社區發現任務中實現更優的性能表現。

3）擴散

給定一個離種子節點u最大距離為l的含權自我中心網絡Gw|u，l|，u∈V，網絡中的邊權重通過式（3）計算得到，對種子節點u進行擴散記為dif（k）l（u），在Gw|u，l|中，從節點u開始執行k步隨機游走，得到概率向量p（k）|u，l|。

在進行擴散操作時，由于在網絡中某些節點可能擁有過多的鄰居節點，所以在這些節點上進行擴散操作將顯著增加計算開銷。為了減少擴散操作的計算量，根據式（5）計算每個鄰居節點的wLcc值，并取排序最高的前10個的鄰居節點，再對這10個鄰居節點分別進行同樣的操作，使最終獲得的子圖大小最多不超過101個節點。

4）結構和屬性的融合重要性（IISA）

給定一個節點u∈V和它的l-距離含權自我中心網絡Gw|u，l|，任一節點v∈Gw|u，l|對節點u的結構和屬性的融合重要性分數，稱為IISA（u，v）。節點v在u的概率向量p（k）|u，l|中的值為p（k）|u，l|［v］，用p（k）|u，l|［v］來度量節點v對u的IISA分數。

5）親密度隨機游走（IRW）

將隨機游走的過程理解為一個節點給另一個節點發送信息的過程，例如在一對節點u和v之間，完成這一過程可以分為兩步，第一步為節點u向v發送信息，第二步則是節點v接收u的信息，因此信息從節點u轉移到節點v受到節點u和v之間的親密度的影響。

對任意一個節點u，與鄰居節點v的親密度為Q（u，v），其計算如式（6）所示。

節點v對u的親密度Q（v，u）為

故信息從節點u轉移到節點v的概率Pt（u，v）為

由于研究對象是無向圖，所以W（u，v）=W（v，u）。故式（8）可進一步推導為

由于信息在傳遞過程中受親密度影響，故信息并不是一定會從一個節點傳遞到另一個節點，信息停留在原節點的概率Ps（u，v）為

對任一節點u，根據離節點u最大距離為l的含權自我中心網絡Gw|u，l|誘導而來的轉移概率矩陣為

有偏的隨機游走可以使得隨機過程更加符合現實世界中的非均質性和復雜性，更準確地描述了現實系統的真實特性，但現有大多數有偏的隨機游走忽略了社交網絡中不同角色的親密程度。通過親密度這一機制，很好地模擬了現實生活中不同角色之間的不同親密程度，有效提高了相似度更高節點重要性的同時降低了邊緣節點以及相似度低的節點的重要性，進而更有效地度量節點的IISA評分，以發現社區中的核心成員。

在隨機游走中，如果要找到種子節點周圍的所有重要節點，則子圖范圍自然越大越好，然而子圖范圍過大會增加大量不必要的計算。根據文獻［22］，2跳子圖中的擴散概率足以發現種子節點周圍的重要節點，設置隨機游走的步數k為4，以保證子圖中的每個節點至少擴散兩次概率。

6）子圖對節點IISA評分

子圖對節點的IISA評分反映了一個子圖對一個節點的重要程度，定義如下：

給定一個子圖Gsub=（Vsub，Esub），對任一節點u∈V，子圖Gsub對節點u的IISA評分按以下過程計算：a）對節點u進行擴散，得到概率向量p（k）|u，l|；b）對所有v∈Vsub，計算節點v對u的結構和屬性的融合重要性分數IISA（u，v）并求和，得到子圖Gsub對節點u的IISA評分IISA（u，Gsub），其計算為

7）節點的IISA評分

節點的IISA評分由鄰居節點擴散到種子節點的總概率計算得到，定義如下：

對任一v∈V，V|v，l|是Gw|v，l|的節點集合，對每個u∈V|v，l|進行擴散，節點v的IISA評分為IISA（v），其計算如式（14）所示。

8）核心成員

社區的核心成員是社區內部IISA得分最高的少數節點。

2.4 算法過程

在HoSIM算法［5］的基礎上，對其進行了適應屬性網絡的改造。算法主要步驟分為子圖采樣、核心成員檢測和局部社區發現三個階段，通過三個階段最終發現包含種子節點在內的多個局部社區。

算法1 MLCDINA

輸入：無向圖G=（V，E，X）；種子節點vs。

輸出：社區集合C′={ C′1，C′2，…，C′k}。

初始化C′=。

將G=（V，E，X），vs輸入子圖采樣算法得到采樣的含權子圖Gwsub和外部鄰接節點集合Vexterior。

將Gwsub和vs輸入核心成員識別算法得到所有核心成員集合core_members_sets。

for each node_set core_members_set∈core_members_sets do

將Gwsub、Vexterior、vs和core_members_set輸入局部社區發現算法得到社區C′i；

將C′i加入到C′中；

end for

return C′={ C′1，C′2，…，C′k}

2.4.1 子圖采樣

在這一階段，算法為種子節點采樣一個包含與種子節點和社區核心成員最相關的節點的子圖。采樣過程分為兩步，算法先采樣一個初始子圖，然后再迭代往初始子圖中添加節點以獲取最終采樣子圖。同時，為了后續評價社區成員與外部節點的關系，保留最終采樣子圖的部分外部鄰接節點。

算法2 子圖采樣

輸入：無向圖G=（V，E，X）；種子節點vs。

輸出：采樣子圖Gwsub和外部鄰接節點集合Vexterior。

初始化Gsub=［vs］。

while |Gsub|lt;N1 do

Gsub=BFS（Gsub）；

end

根據式（3）計算Gsub中的節點對的邊權重得到含權子圖Gwsub。

將Gwsub和vs輸入適用于含權網絡的PPR算法得到概率向量pvec。

選取概率向量中概率最大的前N1個節點構成初始子圖Gwsub。

初始化add_number=0。

while add_numberlt;N2 do

獲取Gwsub的鄰居節點neigh_nodes；

for each node neigh_node∈neigh_nodes do

對neigh_node進行擴散操作；

根據式（13）計算Gwsub對neigh_node的IISA評分；

end for

根據IISA評分對neigh_nodes進行降序排列，取前N個節點加入Gwsub；

add_number=add_number+N；

end while

Vexterior=BFS（Gwsub，2）。//對Gwsub執行兩輪BFS

return Gwsub，Vexterior

在第一步中，算法首先迭代地從種子節點開始執行BFS以獲得子圖Gsub。當Gsub的大小大于閾值N1時，停止BFS過程。根據式（3）計算Gsub內的節點對的邊權重構建含權子圖Gwsub。然后，算法應用適用于含權網絡的PPR算法［19］對Gwsub內的種子節點進行概率擴散。選取概率向量中概率最大的前N1個節點構成初始子圖Gwsub。

在第二步中，算法迭代地挑選Gwsub的鄰居節點（即外部鄰接節點），并對鄰居節點中的每個節點進行擴散。算法根據式（13）計算Gwsub對鄰居節點中每個節點的IISA評分。然后，算法將節點按照降序排列，并在Gwsub中加入前N個節點。當加入的節點數大于一個閾值N2時，這個迭代過程結束。由于一般真實社區的規模都小于100，故設定N1、N2為100，N為10。

此外，由于發現一個社區不僅需要評價社區內成員，還需要評價社區成員與外部節點之間的關系，所以需要保留采樣子圖的外部鄰接節點。算法執行兩輪BFS從Gwsub獲得節點作為Gwsub的外部鄰接節點集合Vexterior。

2.4.2 核心成員識別

在這一階段，算法的目的是發現采樣子圖內的社區核心成員集合。算法計算采樣子圖內每個節點的IISA評分，挑選評分高于種子節點的節點作為核心成員，并根據其在采樣子圖內的獨立連通分支，將其劃分為互不相交的核心成員集合。

算法3 核心成員識別

輸入：含權子圖Gwsub；種子節點vs。

輸出：所有核心成員集合core_members_sets。

for each node vi∈Gwsub do

對vi進行擴散操作；

end for

for each node vi∈Gwsub do

根據式（14）計算vi的IISA評分；

end for

選擇IISA評分大于種子節點IISA評分的節點作為核心成員core_members。

在Gwsub中發現core_members的獨立連通分支。

根據獨立連通分支將core_members劃分為互不相交的集合core_members_sets。

return core_members_sets

在對子圖進行采樣后，算法識別Gwsub內部社區的核心成員。算法對Gwsub中的每個節點進行擴散操作，并根據式（14）計算Gwsub中每個節點的IISA得分。然后，算法選擇IISA評分大于種子節點IISA評分的節點作為核心成員。最后，算法基于核心節點發現Gwsub內部的獨立連通分支。同時，根據獨立連通分支將核心成員劃分為互不相交的集合。因此，算法自動確定包含種子節點的社區數目。

2.4.3 局部社區發現

在這一階段，算法的目的是根據核心成員集合以及種子節點，得到最終的局部社區。算法分為三步：a）根據核心成員集合以及種子節點得到擴展節點集合；b）根據擴展節點集合應用適用于含權網絡的PPR算法得到局部社區；c）根據局部社區對其外部以及內部節點的IISA分數進行增加和刪除操作，得到最終的局部社區。

算法4 局部社區發現

輸入：含權子圖Gwsub；外部鄰接節點集合Vexterior；種子節點vs；一組核心成員集合core_members_set。

輸出：社區C′i。

選擇core_members_set中IISA得分最高的節點作為核心節點core_node。

在Gwsub中尋找一條從vs到core_node的最短路徑short_path。

獲取處于Gwsub內的core_node的鄰居節點core_neigh_nodes。

將short_path上的節點和core_neigh_nodes合并作為擴展節點集合extend_nodes。

由Gwsub中的所有節點和Vexterior中的所有節點構成連通子圖Gunion。

根據式（3）計算Gunion中的節點對的邊權重得到含權子圖Gwunion。

將Gwunion和extend_nodes輸入適用于含權網絡的PPR算法得到社區C′i。

由C′i中的所有節點構成連通子圖GwC′i。

獲取GwC′i的外部鄰接節點集合out_nodes。

for each node out_node∈out_nodes do

根據式（13）計算GwC′i對out_node的IISA評分IISA（out_node，GwC′i）；

if IISA（out_node，GwC′i）gt;δadd do

將out_node加入到C′i中；

end for

for each node inside_node∈C′i do

根據式（13）計算GwC′i對inside_node的IISA評分IISA（inside_node，GwC′i）；

if IISA（inside，GwC′i）lt;δremove do

將inside_node從C′i中移除；

end for

return C′i

首先，為了選擇一組高質量的擴展節點，算法從核心成員集合中選擇IISA得分最高的節點作為核心節點，并在Gwsub中探索一條從種子節點到核心節點的最短路徑。然后，算法將最短路徑上的節點和Gwsub內核心節點的鄰居節點作為擴展節點集合。通過這種方式，算法可以分別基于相應的高質量擴展節點集合準確地發現不同的社區。

在第二步中，由Gwsub中的節點和Vexterior中的節點共同構成的連通子圖Gunion，在Gunion上為未賦權重的邊根據式（3）計算得到含權子圖Gwunion。采用適用于含權網絡的PPR算法［19］，在α=0.99和ε=0.001的情況下，將種子節點集生長為Gwunion內部的社區。

為了充分利用核心節點和種子節點，在適用于含權網絡的PPR［19］中對核心節點和種子節點初始化更高的概率權重。因此，核心節點和種子節點都比其他節點有更高的概率在Gwunion上擴散，從而生成的社區更容易分別覆蓋相應的成員。

最后，算法進行添加操作和刪除操作，進一步提高檢測到的社區C′i的質量。其中，添加操作是指在Gwunion內部，如果C′i構成的子圖對其某一外部鄰接節點的IISA分數大于給定的閾值δadd，則將該節點添加到C′i中。當不存在滿足條件的外部鄰接節點時，該過程結束。刪除操作是指從C′i中刪除一個內部節點，如果C′i構成的子圖對該節點的IISA得分小于給定的閾值δremove，則刪除該節點。當不存在滿足條件的內部節點時，該過程結束。

3 實驗分析

實驗分析的目的是在屬性社交網絡上驗證IRW相比于ARW更有效，以及MLCDINA相比于已有局部多重社區發現算法發現的結果更準確。實驗評價指標采用Jaccard F1-score。在五個真實屬性網絡上進行了實驗。對于每個網絡，分別從屬于不同社區數量的所有節點組中挑選100個種子節點。

3.1 數據集

選取Politics-UK、Politics-IE、Football、Olympics、Rugby 5個公開數據集進行實驗，均屬于Twitter數據集［23］。Politics-UK是從2012年英國419名議員的Twitter賬號中收集的。這些賬戶根據其政治隸屬關系被分配到五個不相交的社區。Politics-IE數據集來自348名愛爾蘭政治家和政治組織，每個用戶有1 047個維度屬性，用戶分布在7個社區。Football包含248名活躍在Twitter上的英超足球運動員，他們被分配到20個互不相交的社區，每個社區對應一個英超俱樂部。Olympics包含倫敦2012年夏季奧林匹克運動會的464名運動員和組織，他們被分為28個互不相交的社區，對應不同的奧林匹克運動項目。Rugby收集了活躍在Twitter上的854名國際橄欖球聯盟球員、俱樂部和組織，由15個國家對應的重疊社區組成。每個數據集中節點的屬性都是節點對應的Twitter賬號的推文中重復500次以上的單詞列表，詞頻為屬性值，因此節點的屬性個數并不相同，表1列出了這些節點屬性去重后的總數。Rugby中部分節點屬于2個真實社區，Politics-UK、Politics-IE、Football、Olympics四個數據集中所有節點均只屬于1個真實社區。將上述數據集進行數據清洗后，其數據信息如表1所示。其中：參數N表示網絡中的節點總數; M表示網絡中的總連邊數；A表示網絡中的所有節點去重后的屬性總個數；c表示網絡的社區個數。

3.2 IRW的有效性

為驗證IRW的有效性，MLCDINA其他過程不變，在擴散操作中，分別采用ARW和IRW，在上述五個真實屬性網絡上進行了實驗。實驗結果如圖1所示。Rugby1表示實驗選取的種子節點為Rugby中只屬于1個社區的節點，Rugby2表示實驗選取的種子節點為Rugby中屬于2個社區的節點。與HoSIM［5］提出的ARW對比，本文IRW在真實屬性網絡上得到的結果更準確，這表明IRW相比于ARW更適用于真實屬性網絡。

據圖1，可以觀察到IRW相比ARW在Politics-UK、Politics-IE、Rugby上的優勢更為明顯，而在Football、Olympics上只有微弱優勢。Politics-UK、Politics-IE、Rugby社區規模更大，屬性分布更為集中，而Football、Olympics上社區規模較小，網絡中屬性異質性更大。在屬性分布較為集中的數據集上，IRW能夠更有效地利用節點屬性信息來指導游走過程，有效識別核心節點，因此優勢更為明顯。相比之下，在屬性異質性較大的網絡中，節點之間的屬性相似度水平都較低，導致IRW相比ARW的優勢較為微弱。

3.3 真實屬性網絡上的比較

由于尚未發現有在屬性網絡上進行局部多重社區發現的相關算法研究，所以選取不考慮節點屬性的局部多重社區發現算法進行比較。對比的算法有Multicom［3］、HoSIM［5］、MLC［9］。對比算法的參數設置均參照對應論文中的最佳設置，其中Multicom［3］的實驗結果只取包含種子節點的社區進行F1-score計算。實驗結果如表2所示。每行數據集中最優和次優的結果用粗體標記。

從表2可以看出，MLCDINA在每個數據集上都取得了最大的F1-score，總體上優于其他4種算法。MLC［3］和Multicom［9］在Politics-UK、Politics-IE和Rugby上的表現較差，這是因為Politics-UK、Politics-IE和Rugby的真實社區規模都較大，這表明這兩種算法容易發現較小規模的局部社區，而不適用于真實社區規模較大的網絡。HoSIM［5］在Politics-UK和Politics-IE上的表現較好，這表明該算法更適用于真實社區規模較大的網絡。MLCDINA在各個數據集上表現較為穩定，由此可見結合屬性信息對于局部社區發現具有重要意義，能夠有效緩解網絡結構的差異性。上述結果綜合表明，無論網絡的真實社區規模大小，MLCDINA都表現出較為良好的有效性，這表明該算法能有效地指導在真實屬性網絡中的局部多重社區發現。

3.4 參數敏感性分析

由于在融合節點屬性和結構信息時，參數的選擇對算法性能影響較大，本文還研究了參數α的取值對于算法的影響。實驗結果如表3所示，每行數據集中最優的結果用粗體標記。

據表3，可以觀察到在五個真實屬性網絡上，MLCDINA的F1-score在平衡結構權重和屬性權重的參數取值為0.5時達到最高，顯示出算法在此條件下能夠較好地平衡結構信息和屬性信息，實現最優的社區劃分效果。然而，這種最優性能在不同數據集上存在差異，其中在Politics-UK和Politics-IE上α變動對F1-score的影響較小，而另外三個數據集上影響較大。同時算法在不同α的取值下，在Politics-UK和Politics-IE上的F1-score比其他數據集都高，說明Politics-UK和Politics-IE上的社區結構相對更明顯。由此推斷算法在社區結構相對明顯的網絡上對于參數α的敏感性相對較低，而在社區結構更復雜的網絡上參數α對于社區發現結果的影響較大。

4 結束語

針對現有局部多重社區發現算法未能有效整合節點屬性的問題，提出了一種融合節點屬性的局部多重社區發現算法（MLCDINA）。將屬性網絡的結構信息和屬性信息融合后賦給節點對之間的邊權重，以便后續隨機游走評估節點的結構和屬性的融合重要性（IISA）；提出了考慮邊權重的局部聚類系數，用于隨機游走的采樣子圖稠密且屬性相似度高；考慮到社交網絡中用戶之間不同親密程度，提出了親密度隨機游走（IRW）以有效地度量節點的IISA評分，綜合利用網絡結構信息和屬性信息挖掘社交網絡中的局部社區。實驗結果表明，MLCDINA在真實屬性網絡上優于已有算法。相比于無向圖，有向圖更符合現實社交網絡，且更精確地表示了節點間的關系，然而有向圖的社區結構更為復雜，且節點間存在非對稱關系，需要重建節點的重要性評估指標。因此MLCDINA雖然具有擴展至有向圖的潛力，但需要解決一系列理論和計算上的挑戰。

參考文獻：

［1］史艷翠， 王嫄， 趙青， 等. 基于局部擴展的社區發現研究現狀［J］. 通信學報， 2019， 40（1）： 149-162. （Shi Yancui， Wang Yuan， Zhao Qing， et al. Research status of community detection based on local expansion［J］. Journal on Communications， 2019， 40（1）： 149-162.）

［2］付立東， 劉佳會， 王秋紅. 基于密度峰值的標簽傳播社區發現算法［J］. 計算機應用研究， 2023， 40（8）： 2323-2328. （Fu Lidong， Liu Jiahui， Wang Qiuhong. Label propagation community discovery algorithm based on density peak［J］. Application Research of Computers， 2023， 40（8）： 2323-2328.）

［3］Hollocou A， Bonald T， Lelarge M. Multiple local community detection［J］. ACM SIGMETRICS Performance Evaluation Review， 2018， 45（3）： 76-83.

［4］Liu Jiaxu， Shao Yingxia， Su Sen. Multiple local community detection via high-quality seed identification over both static and dynamic networks［J］. Data Science and Engineering， 2021， 6（3）： 249-264.

［5］Li Boyu， Wang Meng， Hopcroft J E， et al. HoSIM： higher-order structural importance based method for multiple local community detection［J］. Knowledge-Based Systems， 2022， 256： 109853.

［6］Li Boyu， Kamuhanda D， He Kun. Centroid-based multiple local community detection ［J］. IEEE Trans on Computational Social Systems， 2024， 11（1）： 455-464.

［7］Liu Qing， Zhu Yifan， Zhao Minjun， et al. VAC： vertex-centric attributed community search［C］// Proc of the 36th International Confe-rence on Data Engineering. Piscataway， NJ： IEEE Press，2020：937-948.

［8］Li Qiyan， Zhu Yuanyuan， Ye Junhao， et al. Skyline group queries in large road-social networks revisited ［J］. IEEE Trans on Know-ledge and Data Engineering， 2023， 35（3）： 3115-3129.

［9］Kamuhanda D， He Kun. A nonnegative matrix factorization approach for multiple local community detection［C］// Proc of IEEE/ACM International Conference on Advances in Social Networks Analysis and Mining. Piscataway， NJ： IEEE Press， 2018： 642-649.

［10］Kamuhanda D， Wang Meng， He Kun. Sparse nonnegative matrix factorization for multiple-local-community detection［J］. IEEE Trans on Computational Social Systems， 2020， 7（5）： 1220-1233.

［11］Rostami M， Oussalah M. A novel attributed community detection by integration of feature weighting and node centrality［J］. Online Social Networks and Media， 2022， 30： 100219.

［12］Berahmand K， Haghani S， Rostami M， et al. A new attributed graph clustering by using label propagation in complex networks［J］. Journal of King Saud University-Computer and Information Sciences， 2022， 34（5）： 1869-1883.

［13］Wang Xiaofeng， Li Jianhua， Yang Li， et al. Unsupervised learning for community detection in attributed networks based on graph convolutional network［J］. Neurocomputing， 2021， 456： 147-155.

［14］Hu Lun， Pan Xiangyu， Yan Hong， et al. Exploiting higher-order patterns for community detection in attributed graphs［J］. Integrated Computer-aided Engineering， 2021， 28（2）： 207-218.

［15］Guo Kun， Zhao Zizheng， Yu Zhiyong， et al. Network embedding based on biased random walk for community detection in attributed networks［J］. IEEE Trans on Computational Social Systems， 2023， 10（5）： 2279-2290.

［16］Sun Jianyong， Zheng Wei， Zhang Qingfu， et al. Graph neural network encoding for community detection in attribute networks［J］. IEEE Trans on Cybernetics， 2022， 52（8）： 7791-7804.

［17］Berahmand K， Mohammadi M， Saberi-Movahed F， et al. Graph regu-larized nonnegative matrix factorization for community detection in attributed networks［J］. IEEE Trans on Network Science and Engineering， 2023， 10（1）： 372-385.

［18］Qin Meng， Lei Kai. Dual-channel hybrid community detection in attributed networks［J］. Information Sciences， 2021， 551： 146-167.

［19］彭茂， 張媛. 帶權網絡的個性化 PageRank 計算［J］. 南京信息工程大學學報： 自然科學版， 2016， 8（2）： 116-122. （Peng Mao， Zhang Yuan. Computing personalized PageRank in weighted networks［J］. Journal of Nanjing University of Information Science amp; Technology： Natural Science， 2016， 8（2）： 116-122.）

［20］Nascimento M C V. Community detection in networks via a spectral heuristic based on the clustering coefficient［J］. Discrete Applied Mathematics， 2014， 176： 89-99.

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

［22］Zhang Muhan， Chen Yixin. Link prediction based on graph neural networks ［EB/OL］. （2018-11-20）. https：//arxiv.org/abs/1802.09691.

［23］Greene D， Cunningham P. Producing a unified graph representation from multiple social network views［C］// Proc of the 5th Annual ACM Web Science Conference. New York： ACM Press， 2013： 118-121.