基于節點鏈接重要性的社區方法研究

基金項目：江西科技學院自然科學技術項目；項目編號：23ZRYB05。江西省教育廳科學技術研究項目；項目編號：GJJ2202622。

作者簡介：朱葉（1996—），女，助教，碩士研究生；研究方向：復雜網絡，社區發現。

摘要：關于社區結構較為常見的一種描述是關于強弱社區的闡述，一條邊由2個節點構成，此2個節點對這條邊有直接影響，是通過此2個節點的鄰接點數目直接影響。除此之外，其間接關聯性是通過此2個節點的公共鄰居節點對網絡其余部分的間接影響。文章從這2個方面考慮，得到一種新的社區發現算法。文章采用10個社區結構清晰度不同的人工生成網絡數據集，通過與幾種社區發現算法進行對比實驗。實驗證明，從幾種不同的評價指標角度而言，文章研究算法在社區結構清晰度不同的人工生成網絡數據集上都有較好的結果。

關鍵詞：節點鏈接重要性；中心度；社區發現；復雜網絡

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

0引言

在20世紀，隨著計算機和互聯網的普及，人們開始研究由節點和邊構成的復雜系統，即復雜網絡。在現實生活中，復雜網絡廣泛存在于各個領域，例如，生物方面的蛋白質相互作用網絡、道路方面的交通網絡、人際交流方面的社交網絡、電力系統方面的電力網絡等［1-3］。在復雜網絡中，“社區”的含義通常指網絡中一組節點之間具有相對緊密的連接關系、節點之間的連接頻次較高、可以視為一個相對獨立的子網絡。具體而言，社區發現是通過分析網絡中節點之間的連接關系和節點自身的屬性特征，來挖掘網絡中的社區結構。這些社區結構可以反映網絡中不同節點之間的相似性和聚集程度，幫助人們更好地理解網絡的整體結構和動態行為。因此，人們開始注意到“社區”的存在和影響力。

在復雜網絡中，節點之間的連接關系往往呈現復雜的結構和模式，社區發現可以幫助人們識別和區分這些結構，從而更好地理解網絡的整體結構和特征。復雜網絡在現實生活中廣泛存在，它們具有小世界［4］、無標度［5］和社區結構［6］等特征，這些特征使得復雜網絡在各個領域中都發揮著重要的作用。例如，在生物方面，通過分析這些網絡的結構和動態，可以揭示生物系統的功能和行為，有助于理解疾病的發生和發展機制以及藥物的作用方式。在交通網絡中，通過對道路和交通樞紐的拓撲結構和流量動態進行分析，可以優化交通規劃和管理，提高交通系統的效率和可靠性。在社交網絡中，通過對用戶之間的鏈接關系進行分析，可以揭示用戶的社交行為和影響力，從而為社交媒體的運營提供支持。在電力系統中，通過對發電站、變壓器、輸電線路和用電設備之間的鏈接關系進行分析，可以評估電力系統的脆弱性和故障傳播的風險，優化電力資源的分配和管理，有助于制定預防和應對措施，提高電力系統的穩定性和效率。

總之，復雜網絡在各個領域都有廣泛應用，通過分析網絡的結構和動態，可以揭示系統的本質和行為規律，有助于解決實際問題。

1節點鏈接重要性的計算方法

定義1節點鏈接關系重要性。在給定的圖G=（V，E）中，如果設定一條邊為（i，j），那么di指以i這個點為端點的邊數，也稱為度數。NC（i，j）指節點i和j對該節點構成的邊（i，j）的影響。若以此節點為端點的邊數越多（即di越大），那么該節點對以此節點為端點構成的這條邊的影響力越小。NC（i，j）計算方法的表達式如下：

NC（i，j）=1di+1dj（1）

VC（i，j）指i和j這2個節點共同的鄰居節點對節點鏈接關系重要性的影響，它描述了這2個節點與網絡其他部分之間的相關性。若是i和j這2個節點沒有共同的鄰居節點，那么就不會產生影響，否則這2個節點就可以通過它們共同的鄰居節點，間接影響此2個節點構成的邊（i，j）的節點鏈接關系重要性。VC（i，j）計算公式表示如下：

VC（i，j）=（|NH（i）∩NH（j）|+1）×NC（i，j）（2）

公式中NH（i）指節點i所有鄰居節點的集合，而NH（i）∩NH（j）同理指節點i所有鄰居節點和節點j所有鄰居節點的交集，即節點i和節點j公共鄰居節點的集合。因此，|NH（i）∩NH（j）|指的是該集合的基數，即集合中元素的個數。節點鏈接關系重要性計算公式表示如下：

ω（i，j）=NC（i，j）if

2VC（i，j）+NC（i，j）ifdi=1

digt;1or

ordj=1

djgt;1（3）

以圖1中邊（2，3）和邊（4，5）的節點鏈接重要性計算作為示例，節點2和節點3在網絡中的度都為3，所以節點2對邊（2，3）的貢獻是1/3，節點3對邊（2，3）的貢獻也是1/3，故節點2和節點3對邊（2，3）的直接貢獻是1/3+1/3，即2/3。而節點2和節點3的公共鄰居有2個，分別是節點1和節點4，因此節點2和節點3對邊（2，3）的間接貢獻是（2+1）×2/3，即2。根據節點鏈接重要性公式，節點2和節點3的度數都不等于1，因此，邊（2，3）的重要性為間接貢獻的2倍加上直接貢獻，即2×2+2/3=4667。

節點4和節點5在網絡中的度都為4，所以節點4對邊（4，5）的貢獻是1/4，節點5對邊（4，5）的貢獻也是1/4，故節點4和節點5對邊（4，5）的直接貢獻是1/4+1/4，即1/2。而節點4和節點5的公共鄰居有0個，因此節點4和節點5對邊（4，5）的間接貢獻是（0+1）×1/2，即1/2。根據節點鏈接重要性公式，節點4和節點5的度數都不等于1，因此，邊（4，5）的重要性為間接貢獻的2倍加上直接貢獻，即2×1/2+1/2=15。

根據上述方法，節點鏈接重要性計算的算法步驟總結如表1所示。

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

最初，把網絡中節點設定在同一社區，設定源節點的距離無窮大，只有當距離不超出范圍時，才結合算法1和中心度方法計算此時的中心度。找到中心度最大的邊并移除，且需要記錄此時的連通分量和模塊度。迭代執行上述操作，直到所有邊都被移除。從記錄中找出模塊度最大的情況，此時的連通分量即算法結果。本文社區發現算法內容及步驟如表2所示。

3多種算法的對比分析

本文采用的數據集是10個人工生成的GN基準網絡，這些網絡是通過Lancichinetti等［7］提出的LFR人工基準程序生成的gml文件，該網絡的節點總數有128個，邊總數有1024條，平均度數是16，社區數是4個，而且128個節點均勻分布在4個社區中。在人工生成網絡中，mu作為模糊參數，影響著社區結構的清晰程度。為了進一步實驗本文算法的有效性，本文將mu的值在0至05之間，等距離生成10個人工網絡，在此10個人工生成網絡上，通過與幾種社區發現算法進行對比實驗。本文采用的評價指標如下：

（1）模塊度Q（Modularity）。

Q=∑i（eii-a2i）（4）

∑eii和∑eij分別指相同社區的節點邊數與總邊數的比值以及社區i中節點相連的邊數與總邊數的比值。模塊度越大說明結果越好，一般取值在03至07之間。

（2）標準化互信息（NormalizedMutualInformation，NMI）。

NMI（X;Y）=2I（X;Y）H（X）+H（Y）（5）

其中，2個隨機變量（X;Y）的聯合分布為p（x，y），邊緣分布分別為p（x），p（y）。NMI值越大表示社區劃分效果越好。

（3）調整蘭德系數（AdjustedRandIndex，ARI）。

ARI=RI-E（RI）max（RI）-E（RI）（6）

其中，a表示節點真實情況和預測情況同為錯的個數，b表示節點真實情況和預測情況同為對的個數，m代表節點個數。ARI值越大表示社區劃分結果與真實情況越吻合。

生成的人工基準網絡采用3種評價標準，與GN、FN、Louvain、LPA4種算法進行對比分析。在模塊度方面，幾種算法的對比結果如圖2所示。網絡中社區的結構清晰度與生成網絡的mu參數有關，mu的值越大，社區結構越模糊，更難得到準確的結果，因此所有算法模塊度的值呈現下降趨勢。當mu取值較小時，社區結構比較清晰，各類算法的Q值都相同且結果良好。除了LPA算法之外，其他的幾種算法在mu取值015～03的Q值仍是比較接近。當mu取值在03～04時，社區結構較為模糊，LPA算法的Q取值為0，本文算法較于其他算法的結果仍是比較接近。當mu取值大于04時，本文算法較于其他算法的Q值結果更好。

在NMI和ARI等方面，幾種算法的對比結果如圖3—4所示。當mu較小時，社區結構比較清晰，各類算法的ARI和NMI的值都取值是1。除了LPA算法之外，其他的幾種算法在mu取值02～03的ARI和NMI仍是接近1。當mu大于03，社區結構較為模糊，LPA算法的ARI和NMI取值為0，本文算法較于其他算法的結果都比較好。

4結語

關于社區結構較為常見的一種描述是關于強弱社區的闡述，一條邊是由2個節點構成，此2個節點對這條邊有直接影響，是通過此2個節點的鄰接點數目直接影響。除此之外，間接關聯性是通過此2個節點的公共鄰居節點對網絡其余部分的間接影響。本文從此2方面進行考慮，得到一種新的社區發現算法。本文采用的數據集是10個人工生成的GN基準網絡，而網絡中社區的結構清晰度與生成網絡的mu參數有關，mu的值越大，社區結構越模糊，更難得到準確的結果。因此，本文將mu值從0至05以005為間距，采用10個社區結構清晰度不同的人工生成網絡數據集，通過與幾種社區發現算法進行對比實驗。實驗證明，本文算法在社區結構清晰度不同的人工生成網絡數據集上，從幾種不同的評價指標角度而言都有較好的結果。

參考文獻

［1］LESKOVECJ，LANGKJ，DASGUPTAA，etal.Communitystructureinlargenetworks：naturalclustersizesandtheabsenceoflargewell-definedclusters［J］.InternetMathematics，2008（1）：29-123.

［2］THOMASR，MURATT，BENOITC，etal.Aproteome-scalemapofthehumaninteractomenetwork.［J］.Cell，2014（5）：1212-1226.

［3］STANISLAWS，BOGDANG，PIOTRB，etal.Predictingcommunityevolutioninsocialnetworks［J］.Entropy，2015（5）：3053-3096.

［4］WATTSDJ，STROGATZSH.Collectivedynamicsof‘small-world’networks［J］.Nature，1998（6684）：440-442.

［5］BARABASIAL，ALBERTR.Emergenceofscalinginrandomnetworks.［J］.Science，1999（5439）：509-512.

［6］DERENYII，PALLAG，VICSEKT.Cliquepercol-ationinrandomnetworks［J］.PhysicalReviewLetters，2005（16）：160202.

［7］LANCICHINETTIA，FORTUNATOS，RADICCHIF.Benchmarkgraphsfortestingcommunitydetectionalgorithms［J］.PhysicalReviewE，Statistical，Nonlinear，andSoftMatterPhysics，2008（4）：46110-46114.

（編輯王雪芬）