一種基于節點影響力的標簽傳播社區發現方法

中圖分類號：TP39 文獻標志碼：A

0 引言

復雜網絡的發展主要經歷了規則網絡、隨機圖、復雜網絡3個階段[1-3]。復雜網絡即呈現高度復雜性的網絡，由大量個體（節點）和它們之間的相互作用（邊）組成。

現實世界中復雜網絡無處不在，復雜網絡的研究可用圖論和復雜網絡理論分析，得出網絡的拓撲結構、節點度分布、小世界效應、無標度性等重要特征[4]。復雜網絡在許多領域中都有著舉足輕重的作用[5-6]。金融市場方面，通過構建股票交易網絡，可以分析股票之間的相關性，為投資者提供參考。社交媒體方面，通過分析社交網絡中的用戶行為和社交趨勢，可以實現對用戶的精準營銷和社交輿情的預測。生物醫學方面，通過構建基因調控網絡和蛋白質互作網絡，可以研究基因和蛋白質之間的相互作用機制，為藥物研發提供新的思路。交通網絡方面，通過分析交通網絡的拓撲結構和交通流量數據，可以有效地提高交通系統的運行效率和安全性。

此外，復雜網絡還應用于網絡安全、城市管理、人機交互等領域，發揮著越來越重要的作用。綜上所述，復雜網絡是一個高度復雜且多樣的系統，具有廣闊的應用前景和深入的研究價值。隨著科學技術的不斷發展和人類對各領域認知的深入，復雜網絡的應用和研究將會得到更加廣泛的拓展[7]

1節點影響力的計算方法

1.1節點影響力的衡量方法

關于節點影響力的衡量方法主要有4種，分別是基于節點鄰居數量、路徑、特征向量、節點移除和收縮等。基于節點鄰居數量主要有度中心性、半局部中心性；基于路徑主要有接近中心性、介數中心性;基于特征向量主要有PageRank、LeaderRank、HITS算法；基于節點移除和收縮主要有節點收縮法、殘余接近中心性等方法[8-10] 。

1.2節點的直接影響力和間接影響力

給定無權且沒有平行邊的簡單網絡 G=（V，E） ，邊 （i，j） 是由節點 i 和節點 j 這2個節點組成的點對構成。在網絡結構中，節點對于一條邊的影響來源于2方面，一個是來自構成該條邊的2個節點的直接影響，另一個是來自構成該條邊的2個節點的間接影響。直接影響是如果該節點的度數越大，則對此邊的影響力越小，類比社交網絡可以充分理解，一個人的朋友越少，那么朋友們對這個人的影響就更大，聯系更為緊密。 d_i 表示節點 i 的度， NC（i，j） ）表示直接影響。計算公式如下：

間接影響是通過點對之間的共有鄰居節點產生的，其中 NH（i） 表示節點 χ_i 的鄰居節點集合，則間接影響 VC（i，j） 計算公式如下：

節點影響力計算公式如下：

1.3基于節點影響力的HITS改進算法

考慮到節點影響力的衡量方法有局部最優結果和復雜度太高等問題，本文提出基于節點影響力的HITS改進算法。首先將所有節點的 α_a 值和 h 值設為weight，計算出每個節點更新后的 Δ_a 值。然后根據更新后的 a 值重新計算節點的 h 值并將這2個值進行歸一化處理。迭代執行上述步驟直到滿足結束循環條件，輸出結果。算法步驟總結如表1所示。

表1HITS改進算法步驟

2本文社區發現算法內容及步驟

首先根據計算節點影響力，從大到小依次排序。然后依據此順序進行更新，計算每條邊的重要性并看作其標簽影響力。最后，在標簽傳播過程中，如果鄰居節點中有多種標簽的選擇，則選擇鄰居節點中同種標簽的鏈接重要性累加值更大的。迭代執行上述步驟直到達到停止迭代條件，輸出結果。算法步驟總結如表2所示。

表2本文社區發現算法步驟

3多種算法實驗結果對比分析

本文實驗所用數據集是Karate、Dolphin和Football網絡，這3個真實網絡的基本情況如表3所示。

表33個真實網絡的基本情況

在上述數據集上，通過與幾種標簽傳播社區發現算法進行對比實驗。

3.1評價指標

3.1.1 模塊度Q（modularity）

在不清楚網絡中有多少個社區和每個社區中有多少個節點的現實情況下，模塊度作為復雜網絡分析中常用的一種度量指標由Newman和Girvan在2004提出[1]。其計算公式如下：

e_ii 為社區關聯矩陣 E 中對角線上的元素，表示子區 i 內邊數與圖中邊數的比值； a_i 表示子區 i 內的節點度數和與圖中所有節點度數和的比值。 Q 值范圍是[-0.5，1），但通常人們只關心其正值部分，因為負值表示社區劃分的質量很差，即社區內部的連接比隨機分布還要稀疏。其中， Q 值越接近1，表示網絡劃分出的社區結構的強度越強，即劃分質量越好。相反，Q 值越接近0，表示社區劃分的質量越差。

3.1.2標準化互信息

標準化互信息（Normalized MutualInformation，NMI）是一種用于度量2個聚類或分類結果之間相似度的指標[12]，其計算公式如下：

其中， X 和 Y 代表2個需要比較的聚類或分類結果。 I（X;Y） 表示 X 和 Y 之間的互信息，它衡量了2個隨機變量之間的相關性。 H（X） 和 H（Y） 分別是 X 和 Y 的熵，邊緣分布分別為 。其中， p（x） 表示信息源中符號 x 出現的概率； Σ 表示求和; log 表示對數（通常以2為底）。NMI值越大表示社區劃分效果越好。

3.2Karate網絡上實驗結果對比分析

Karate網絡在本文算法中被劃分成3個社區，分別是節點4、5、6、10、16，節點8、14、15、18、20、22、23、24、25、26、27、28、29、30、31、32、33以及剩下的節點為最后一個社區。實驗對比了多種標簽傳播算法在空手道俱樂部網絡上的效果。這些算法在空手道俱樂部網絡上的Q和NMI對比結果如圖1所示。

本文在Karate真實網絡上進行算法結果對比時，采用的是模塊度和標準化互信息這2個常用指標。就這2個指標而言，本文算法的結果都是最佳，本文算法 Q 和NMI結果分別為0.402和0.5684，尤其是在 Q 這一指標上明顯優于其他標簽傳播算法。

圖1多種算法在空手道俱樂部網絡上的 Q 和NMI對比結果

3.3Dolphin網絡上實驗結果對比分析

Dolphin網絡在本文算法中被劃分成7個社區，分別是節點46、49所在的社區1，節點3、8、59所在的灰色社區，節點0、2、10、42、47、28、30所在的社區2，節點4、11、15、18、21、23、24、29、35、45、51、55所在的社區3等。通過實驗，對比了多種標簽傳播算法在海豚家族關系網絡上的效果。這些算法在海豚家族關系上的 Q 和NMI對比結果如圖2所示。本文在Dolphin真實網絡上進行算法結果對比時，采用的是模塊度和標準互信息這2個常用指標，就NMI指標而言，本文算法的結果為0.4514，低于半同步LPA算法的0.4791，但是本文算法在 Q 這一指標上的結果為0.5184，明顯優于其他標簽傳播算法。總之，本文算法效果更佳。

圖2多種算法在海豚家族關系網絡上的 Q 和NMI對比結果

3.4Football網絡上實驗結果對比分析

Football網絡在本文算法中被劃分成11個社區，分別是節點11、24、28、50、69、90所在的社區1，節點46、49、53、67、83、88、73、110、114所在的社區2，節點44、48、57、66、75、86、91、92、112所在的社區3，節點0、4、9、16、23、41、93、104所在的社區4等。本文算法與其他標簽傳播算法在足球隊網絡上的結果進行對比，對比結果如圖3所示。本文在Football真實網絡上進行算法結果對比時，采用的是模塊度和標準化互信息這2個常用指標。就這2個指標而言，本文算法的結果都是最佳，本文算法 Q 和NMI結果分別為0.6032和0.9095，尤其是在NMI這一指標上明顯優于其他標簽傳播算法結果，本文算法整體上效果更好。

圖3多種算法在足球隊網絡上的 Q 和NMI對比結果

4結語

由于傳統的標簽傳播算法存在2方面問題，一方面是節點更新順序的不確定性，一方面是節點影響力相同。針對這2方面問題，本文提出一種基于節點影響力的標簽傳播社區發現方法。算法通過節點影響力計算方法計算每個節點的影響力，得到一個重要性序列，保證傳播過程中標簽選擇的唯一性，從而得到社區劃分結果。在3種真實網絡上，對比其他幾種經典標簽傳播社區檢測算法，在模塊度、標準化互信息方面都有比較好的結果，證明了所提算法具有良好的效果。

參考文獻

[1]PAL E，RENYI A R. On random graphs[J].Publicationes Mathematicae，1959，6：290-297.

[2]WATTS D，STROGATZ S. Collective dynamics of“small-world”networks [J].Nature，1998（6684）：440-442.

[3]BARABASI A L，ALBERT R. Emergence of scaling inrandom networks[J].Science，1999（5439） ：509-512.

[4] IMRE，DERENYI，GERGELY，et al. Clique percolationin random networks[J].Physical Review Letters，2005（16） ：160202.

[5]ROLLAND T，TASAN M，CHARLOTEAUX B，et al.A proteome-scale map of the human interactome network[J]. Cell，2014，159：1212-1226.

[6]BO Y，LIU J，FENG J. On the spectral characterizationand scalable mining of network communities[J].IEEETransactions on Knowledge amp; Data Engineering，2011（2）：326-337.

[7]馮拓宇，劉佳寧，曹子奇，等.社區發現方法研究綜述[J].中國電子科學研究院學報，2024（6）：487-498，503.

[8]FU L D，GAO L，MA X K.A centrality measurebased on spectral optimization of modularity density[J].中國科學：信息科學（英文版），2010（9）：1727-1737.

[9]陳錦渠，劉杰，殷勇，等.基于改進LeaderRank算法的高速鐵路網絡關鍵站點識別方法研究[J].交通運輸工程與信息學報，2020（1）：84-90.

[10]張格豪，劉偉，王睿鑫垚，等.基于多屬性決策的復雜網絡關鍵影響力節點的識別研究[J].無線互聯科技，2023（16）：116-123.

[11]CLAUSET A. Finding local community structure innetworks[J].Physical Review E，2005（2） ：26132-26137.

[12]STREHL A，GHOSH J. Cluster ensembles：aknowledge reuse framework for combining multiplepartitions[J]. Journal of Machine Learning Research，2002（3） ：583-617.

（編輯 王雪芬）

Abstract：Community discovery isanimportant task in complex networkanalysis，which aims to identify closely related subnetwork in the network.Through communitydiscovery，we canbetter understandand usethe structured and modular phenomena in thenetwork，andprovide important information for analyzing thecharacteristicsof complex networks.The traditional label propagation algorithm has twoproblems，one is theuncertaintyof nodeupdate order， the other is the same node influence.In order to solve these two problems，a label propagation community discovery method basedonnode influence isproposed.Experimentsshowthat inseveral real network datasets，the new community discoveryalgorithm isbeter thanseveral other classical tag propagation community detection algorithms， and has better results inthe evaluation indexes such as modularityand standard mutual information，which proves that the proposed algorithm has good effect.

Key words： node influence; label dissemination; community discovery; complex network