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

0 引言

復雜網(wǎng)絡的發(fā)展主要經(jīng)歷了規(guī)則網(wǎng)絡、隨機圖、復雜網(wǎng)絡3個階段[1-3]。復雜網(wǎng)絡即呈現(xiàn)高度復雜性的網(wǎng)絡，由大量個體（節(jié)點）和它們之間的相互作用（邊）組成。

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

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

1節(jié)點影響力的計算方法

1.1節(jié)點影響力的衡量方法

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

1.2節(jié)點的直接影響力和間接影響力

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

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

節(jié)點影響力計算公式如下：

1.3基于節(jié)點影響力的HITS改進算法

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

表1HITS改進算法步驟

2本文社區(qū)發(fā)現(xiàn)算法內(nèi)容及步驟

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

表2本文社區(qū)發(fā)現(xiàn)算法步驟

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

本文實驗所用數(shù)據(jù)集是Karate、Dolphin和Football網(wǎng)絡，這3個真實網(wǎng)絡的基本情況如表3所示。

表33個真實網(wǎng)絡的基本情況

在上述數(shù)據(jù)集上，通過與幾種標簽傳播社區(qū)發(fā)現(xiàn)算法進行對比實驗。

3.1評價指標

3.1.1 模塊度Q（modularity）

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

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

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 出現(xiàn)的概率； Σ 表示求和; log 表示對數(shù)（通常以2為底）。NMI值越大表示社區(qū)劃分效果越好。

3.2Karate網(wǎng)絡上實驗結果對比分析

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

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

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

3.3Dolphin網(wǎng)絡上實驗結果對比分析

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

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

3.4Football網(wǎng)絡上實驗結果對比分析

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

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

4結語

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

參考文獻

[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，F(xiàn)ENG J. On the spectral characterizationand scalable mining of network communities[J].IEEETransactions on Knowledge amp; Data Engineering，2011（2）：326-337.

[7]馮拓宇，劉佳寧，曹子奇，等.社區(qū)發(fā)現(xiàn)方法研究綜述[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算法的高速鐵路網(wǎng)絡關鍵站點識別方法研究[J].交通運輸工程與信息學報，2020（1）：84-90.

[10]張格豪，劉偉，王睿鑫垚，等.基于多屬性決策的復雜網(wǎng)絡關鍵影響力節(jié)點的識別研究[J].無線互聯(lián)科技，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