融入社區評估的節點重要性分析

孫百兵，孫家政，何 泉，杜彥輝

1.中國人民公安大學 信息網絡安全學院，北京 100038

2.中國人民公安大學 偵查學院，北京 100038

當前，世界正處在經濟全球化的高速發展階段，社會經濟不斷發展，隨之而來也有競爭的加劇、新舊企業的更替，社會矛盾也在逐漸顯現，群體性事件、團體活動不斷增加[1-2]。公安機關面臨的巨大維穩壓力。為此，如何正確識別群體中起到關鍵作用的人物就顯得非常具有研究意義。

隨著社交網絡分析研究的不斷深入，各種各樣的事務都可以被轉化成社交網絡，通過社交網絡分析可以更好地了解事務的特征[3-4]。在實際生活中，將目標群體映射為社交網絡，即使該網絡擁有眾多節點，節點間關系復雜，也可以通過節點重要性分析識別群體中起到關鍵作用的重要節點，把握住重要節點便可以掌控整個網絡[5]。因此，如何準確、高效地對社交網絡進行重要度分析有著廣闊的發展前景。

目前節點重要性分析已經取得了很多研究成果。然而，現階段的節點重要性算法很容易造成重要節點聚集的情況，這種情況也被稱為“富人俱樂部”現象。造成這現象的根本原因是重要性算法的“重要節點的鄰居節點也很重要”思想，該思想會造成與群體核心成員有直接關系的普通成員的影響力被抬高，而與核心成員沒有直接聯系但是也起到較大作用的其他成員的影響力會被相對壓低，從而造成不客觀的評價結果。針對此問題，本文分析目標群體網絡的拓撲結構，將群體根據鏈路結構的疏密進行社區劃分，評估社區在整個群體中的重要程度，并綜合考慮節點在本社區的影響力以及其他社區的聯通能力，提出了融合社區評估的節點重要性分析算法（node importance analysis integrated with community assessment，NI-CA）。

1 相關工作

關鍵節點是在整個網絡具有較大影響的節點[6-7]，如何評價該影響力具有很多角度和方法，最經典評價指標有度中心性、特征向量中心性、介數中心性和K核分解等。近年來，國內外學者在經典算法的基礎上不斷完善改進，提出了很多新的評價方法。Bian等人[8]將多種評價指標與證據理論相結合，結合了多種算法的優越性，改進了算法性能。Zhang等人[9]將度值和K核值的結合作為定義節點初始權值，運用庫侖定律融合度量節點在網絡中的重要性。Li等人[10]結合了聚類系數與鄰域內度值總和，提出聚類度的評價指標，提高了度中心性的準確度，但是也增大了計算的時間復雜度。Fei等人[11]研究認為節點的影響力與網絡中其他節點有關，將目標節點的鄰域與網絡最短路徑相結合，綜合考慮每個節點與目標節點的相互關系得出影響力估值。Xu等人[12]針對目前大多重要性算法只針對靜態網絡的問題，提出能夠面向動態網絡的ALR算法，該算法將偏加權體系與Leaderrank算法相結合，提高算法在動態網絡的適用性。Xu等人[13]認為節點的重要程度考慮其鄰接信息熵，在加權網絡用節點的強度來計算信息熵而在有向網絡則綜合了節點的入度和出度值。Yang等人[14]認為實際中的網絡很多是在不斷變化的，所以網絡中各邊的權重也在不斷變化，提出了灰色關聯和SIR傳染病模型相結合的評價方法，對網絡中的各個權重進行動態分配。Zhong等人[15]利用魯棒性的思路，按照特定順序刪除網絡中的節點，分析剩余網絡的連通性等特征，并以此評估被刪除節點的重要性。

2 基于社區評估的節點重要性算法

實際的社交群體中，具有較高影響力的人物或許具有一定的聚集性。但是在利用節點重要性算法進行理論分析時，這種聚集性被不斷放大，導致具有較高影響力的節點都處于群體核心位置，而沒有處于核心位置的節點影響力被過分低估，從而造成了“兩極分化”的現象。由此可見傳統算法在針對目標群體搜索重點人的應用上并不完善，據此，本文提出融合社區評估的節點重要性（NI-CA）算法。

2.1 社區評估

社區評估（community assessment，CA）是本文提出的衡量目標群體各社區重要程度的評價指標。本文根據社交網絡的鏈路結構將目標群體進行社區劃分，并根據各社區節點數量和平均路徑長度分析其重要程度。

模塊度是評價社區劃分效果優良的關鍵指標[16]，一個好的劃分結果其表現形式是：在社區內部的節點相似度較高，而在社區外部節點的相似度較低。模塊度也是Louvain算法[17]的核心思想，Louvain算法是一種基于模塊度高效社區劃分算法，除了運算速度快、時間復雜度低，還有很高的準確度，不會遺漏小型社區。因此，本文采用Louvain算法對目標群體進行社區劃分。

Louvain算法思想簡單，是一個不斷迭代和合并的過程，在這個過程中是否需要進行下一次是由模塊度增益來確定的。網絡中的模塊度值計算方法如公式（1）所示：

其中，Aij代表節點i和j之間邊的權重，Ki表示所有指向節點i的連邊權重之和，Kj同理。δ(i,j)表示判斷i與j是否為同一個社區，如果為同一個社區此值為1，否則為0。如一個節點從當前社區移動到另外一個社區時，圖的結構就會發生變化，相應的模塊度也會發生變化，把這種變化稱為模塊度增益，用ΔQ表示，計算方法如公式（2）所示：

∑in表示在社區C中的所有邊權值之和；C表示指點a要加入的社團；a表示將要移動的節點；Ki,in表示i點到C的所有邊的權值之和；∑tot表示所有連接到社區C的邊的權值之和。Louvain算法在初始的分區階段有盡可能多的社區有節點。對每一個節點i，考慮將它加入到它的鄰居節點j并計算模塊度增量的變化，如果模塊度增量變化大于0，則將它放到對應模塊度變量變化最大的鄰居節點，否則，該節點仍然保持在原來的社區，直至全網絡沒有可以分配的節點后停止迭代。

譚躍進等人提出了一種凝聚度的評估方式[18]，具有較高的準確性。目標群體網絡的凝聚度取決于群體中各成員間的聯通能力和群體規模，聯通能力用網絡的平均路徑長度l衡量，群體規模用成員數量n衡量。對于有n個成員的目標群體網絡G的凝聚度如公式（3）所示：

其中，節點i和節點j是目標網絡的不同的兩個節點，dij代表節點i和節點j之間的最短距離。當n＝1時，ω[G]=1。

本文運用Louvain算法將目標群體網絡劃分成t個社區，各社區分別用C1,C2,…,Ct表示。對網絡社區分別進行重要性評估時，本文將需要評估的社區中的所有節點聚合為一個超節點，其他社區保持原樣，C1,C2,…,Ct各社區分別聚合后形成的網絡分別記為C1,C2,…,Ct，根據聚合后使得網絡凝聚程度變化率評估社區重要性，在評估下一個社區時，原聚合的社區恢復成原本的拓撲結構，社區劃分和聚合的過程如圖1所示。

圖1 社區劃分和聚合Fig.1 Community segmentation and aggregation

定義1基于社區劃分和凝聚度的社區評估（CA）可以進一步表示為公式（4），ω[Gi]的值表示Ci社區的重要度值。

2.2 基于社區評估的節點重要性算法

針對傳統節點重要性算法的高影響力節點過度聚集的現象，本文提出的NI-CA算法在評估節點影響力時，考慮目標節點在其社區外部影響力的同時，融合該節點在其本社區的影響力。由于對目標群體網絡進行社區評估，并且分析了目標節點的局域影響力，NI-CA算法可以在客觀評價節點重要性的同時避免節點影響力的“兩極分化”。

節點的社區內部影響力應當考慮節點在本社區的聯通能力，由于介數考慮的是網絡中所有最短路徑的占比問題，因此介數中心性能夠很好地反映點或邊在整個社區中的重要性。本文引入介數中心性對節點內部的聯通能力進行評價，其核心思想是認為的處于網絡中間位置的節點相比于周邊節點具有“更大的人際關系影響”。對于節點i的介數中心性（betweenness centrality，BC）的計算公式如公式（5）所示：

其中，v(i)表示經過節點i的最短路徑個數，∑δst表示網絡中是從頂點s到頂點t的最短路徑數，V是網絡G的節點集合。對于節點在其社區內部影響力評價，還應當考慮目標節點所在社區的整體影響力，社區評估的影響力越大，該社區領袖的影響力越大。

定義2社區成員的內部影響力（internal influence）用I表示，C1社區成員i的內部影響力如公式（6）所示，其中BCiC1表示節點i在其社區內部的介數中心性值。

在實際生活中，如果一個人在其他社區有很多朋友，他可以發揮重要的角色來接收和傳播他的圈子周圍的信息，因此本文在評估重要性時還要考慮該節點在其社區外部的影響力。

定義3社區成員的外部影響力（external influence）用E表示，節點i的外部影響力計算公式可以進一步表示為：

節點j是節點i的鄰居節點，當節點j與節點i不屬于同一社區時，aij=1；當節點j與節點i屬于同一社區時，aij=0。CA(j)表示節點j所在社區的社區評估值。

定義4基于社區評估的節點重要性算法NI-CA，綜合考慮目標節點在其社區外部影響力和該節點在其本社區的影響力，節點i的重要性度值可以表示為：

基于標準化歐氏距離的修正：

標準化歐氏距離公式是基于二維坐標的直線距離，可以消除在計算兩因素時，其中一個因素數值過大從而壓制另一因素的弊端。

2.3 NI-CA算法應用步驟

根據社交網絡的拓撲結構分析成員重要度的研究，傳統算法很容易得出高影響力成員“扎堆”的結果，而未處于網絡核心位置的其他成員的影響力卻相對被低估。以詐騙團伙為例，對于一個擁有幾百甚至上千的團伙，團伙中的每個成員都有各自的分工，有指揮組、劇本組、一線電話組、二線電話組、倒賣電話卡組、洗錢組等。每個組都有該組中相對重要的成員，而根據傳統節點重要性算法分析，重要成員大都集中在處于網絡核心位置的指揮組，即使是指揮組中的只起到輔助作用的人員也會得出很高的影響力估值，而其他組中的起到一定作用的成員影響力被相對低估。針對這一問題，對一個已知目標人群的社交網絡G=(V,E)，基于社區評估的NI-CA算法的應用步驟如下：

步驟1根據目標網絡的拓撲結構，運用Louvain算法對網絡進行社區劃分，將群體劃分為多個小群體。

步驟2對被劃分后各社區進行重要性評估，分別聚合各社區節點，根據公式（3）和公式（4）計算出各社區在整個網絡中的重要程度CA值。

步驟3根據目標節點所在社區的社區評估CA值和鏈路結構，通過公式（5）和公式（6）計算出目標節點的社區內部影響力，找出各社區的領導人。

步驟4考慮目標節點的跨社區聯通性，通過公式（7）計算出目標節點的社區外部影響力。

步驟5將步驟3和步驟4的計算結果有機結合，通過公式（8）、（9）計算出目標節點的NI-CA值。

NI-CA算法流程如圖2所示。

圖2 NI-CA算法流程圖Fig.2 Flow chart of NI-CA algorithm

社區評估（CA）的計算如算法1所示：

算法1社區重要性評估

輸入：無向網絡G=（V，E）

輸出：各社區重要性度值CA(Ci)

1.將G中各個點初始化為一個社團，根據式（1）計算此時的模塊性值；

2.for viin V

節點到其鄰居節點所在的社區，根據式（1）、（2）計算模塊度的變化ΔQ，若移動后致使ΔQ變化最大，則移動成功，否則保持不變；

end for

3.fori=1 to t/*t為社區個數）*/

將Ci社區分別聚合后形成的網絡記為Gi；

根據式（3）、（4）計算各社區重要性評估值CA(Ci)；end for

4.return各社區評估CA值

基于社區評估的節點重要性（node importance algorithm based on community assessment，NI-CA）如算法2所示：

算法2節點重要性評估的NI-CA算法

輸入：無向網絡G=（V，E），各社區評估值

輸出：網絡中各節點重要度NI-CA值

1.統計各社區的網絡拓撲結構；

2.for viin V

根據公式（5）、（6）計算目標節點在其社區內部影響力；

根據公式（7）計算目標節點與其他社區間聯通能力；

根據公式（8）、（9）計算目標節點的綜合重要性；

end for

3.return每個節點的重要度NI-CA值

3 實驗與分析

3.1 數據描述

本文選取四個不同的鏈路網絡進行驗證實驗，分別是空手道俱樂部（Karate）網絡[19]、《冰與火之歌》（A Song of Ice and Fire）人物關系網絡[20]、Facebook社交賬號數據集[21]和中國某地區詐騙團伙（fraud ring）人物關系。其中Karate網絡是最常用的復雜網絡數據集之一，源自于美國一所大學空手道俱樂部的真實人物關系，在眾多社交網絡實驗中被應用；A Song of Ice and Fire是美國著名長篇奇幻小說，其人物角色眾多，關系復雜，適合作為實驗數據；Facebook是目前最大的線上社交平臺之一，可以代表線上交流網絡進行實驗；Fraud ring網絡源自于已經偵破的網絡詐騙犯罪案件（長興縣劉東等詐騙案與劉羅亮等詐騙案，詳見裁判文書網（2020）浙0522刑初15、16號判決書），本文根據該組織的成員的職務分工構建鏈路網絡，該案件系犯罪團伙的典型代表，案件清晰、判決明確，非常適合進行驗證實驗。以上四種網絡的基本特征如表1所示。

表1 網絡數據基本參數Table 1 Basic parameters of network data

其中，N表示數據集中的節點數量，E代表節點間的邊數，＜K＞表示數據集的度平均值，Kmax表示網絡數據中節點度的最大值，C表示網絡的平均聚類系數，＜d＞表示網絡的平均最短路徑。

3.2 實驗設計及分析

本文的研究目的是根據拓撲結構，對群體網絡中的成員進行重要性評價。為了驗證算法的優越性，運用四個不同類型的群體網絡作為實驗數據，通過SI傳染病模型、魯棒性測試以及肯德爾相關系數進行驗證，橫向對比度指標（degree）、特征向量中心性（eigenvector）、介數中心性（betweenness）和PageRank的實驗結果。Degree指標表示一個節點的鄰居節點越多，節點的重要性越大；Eigenvector指標既考慮鄰居節點的數量，也考慮鄰居節點的重要性，是一種迭代的計算過程；Betweenness指標由經過目標節點的最短路徑數目來刻畫節點的重要性；PageRank算法最初用作互聯網網頁重要度的計算，后廣泛用于節點重要性評估，它對每個節點賦予一個正實數，代表節點的重要度，經過隨機游走模型，PageRank值越高，節點就越重要。

3.2.1 SI模型實驗

SI傳播模型[22-24]驗證節點重要性準確度的最常用的方法之一，其中S表示易感染者（Susceptible），I表示已感染者（Infectious）。SI模型是將部分節點作為傳染源（I狀態），以β的概率不斷傳染與其鄰近的易感染者（S狀態）。

公式（10）所表達的含義為：對于網絡中的狀態為易感染S的節點i，如果該節點與感染狀態I的節點j接觸，節點i將會以β概率被傳染，從而成為感染狀態節點，成為新的感染源，更新狀態為I(i)，而原感染狀態I的節點j，狀態不會再發生變化。此刻這些節點又成為新的感染源，感染網絡中其他節點，直至網絡中所有節點都變為I狀態，傳播過程結束。

由圖3可以看出，當感染到達T時刻，SI模型的最終狀態是網絡中所有節點都感染為I類節點。因此，本文依托SI傳播模型，衡量組織中具有重要角色的成員向其他成員傳遞其影響力的傳播能力，并根據傳播結果進行評價，傳播越快、感染數量越多，則說明感染源節點對于其所在的網絡重要程度準確性越高，即算法得出的網絡重要節點排序越準確。

圖3 SI傳播過程圖Fig.3 SI propagation process diagram

實驗結果如圖4所示，縱坐標為感染者的數量，橫坐標為迭代次數。實驗結果表明NI-CA算法的效果整體較好，在Karate網絡和Fraud ring網絡因為節點數較少，傳播效果最為明顯，各傳播實驗效果差別明顯。A Song of Ice and Fire人物網絡和Facebook網絡節點數較多，傳播結果的區分不明顯，但是仍然能夠看出在A Song of Ice and Fire人物網絡中的傳播效果最好，即在該網絡中，NI-CA算法評價的重要節點具有更高的連通性，可以更快速地將信息傳遍整個網絡。在Facebook網絡中的傳播效果前期并不是最優，但是在中后期的傳播速度明顯提升，也就說明在Facebook網絡中，NI-CA算法在計算各節點重要性時，最初評價效果并不突出，但是中后期對節點的重要性評價較為準確。傳統節點重要性算法因為重要節點聚集，將這些節點作為傳播源時，信息傳播會大量出現重疊的情況，即花費太多時間重復將信息傳播給聚集圈周圍的節點。NI-CA算法通過社區評估找出不同社區的重要成員，并以此為傳播源進行信息傳播，由于信息源較為分散，所以傳播至整個網絡的速度更快，有效減少了信息傳播重疊的情況。

圖4 SI傳播實驗結果Fig.4 Experimental results of SI propagation

3.2.2 魯棒性測試

魯棒性指標[25-27]可以衡量某些節點在被移除后網絡功能變化情況。在網絡魯棒性實驗仿真中，按照節點重要度排序順序依次移除節點。這樣可以考察攻擊一部分節點使之失去效果后，即移除該節點，網絡整體結構和功能上的變化，用圖中的最大連通分量中的節點數目與整個圖中節點的總數目得到比值，作為衡量復雜網絡功能魯棒性的強弱。比值越接近1，說明整個網絡中實現功能的結構體越大越完整，也說明魯棒性越強。其計算方式如公式（11）所示：

L是表示最大聯通分量，G為當前的圖，θ隨著被移除節點數i的增加而下跌如果該曲線下降的越快，則認為移除的節點越能使網絡碎片化的程度越高。換句話說，如果依次移除通過節點重要性算法得到的節點序列可以使整個網絡的碎片化程度越大，則這樣的節點越重要，這個算法也就越好。

由于魯棒性測試中，在依次移除節點時，移除到中后期的網絡會非常分散，并且無法對比出各算法之間的優越性差異，所以本實驗分別運用NI-CA指標、Degree指標、Eigenvector指標、Betweenness指標和PageRank的實驗結果分別對四個不同的網絡進行節點重要度計算，按照各種計算出的節點重要性排序依次移除各網絡的節點，橫向對比各算法之間的θ值。

魯棒性實驗結果如圖5所示，橫坐標為移除節點占比，縱坐標為最大連通分量規模占比。由于很多網絡在節點移除后期剩下節點大多是單節點，為了實驗效果的區分度，本實驗將節點移除至最大連通分量規模占比低于0.1時結束實驗。繪制曲線可以準確地得到移除節點對圖的影響過程，從而間接衡量了節點重要性排序的效果。實驗結果表明各算法在前期移除節點的過程中效果相差不大，但是在持續的移除過程中，各算法之間的差別逐漸顯現。NI-CA算法的實驗結果整體較好，但是在Karate網絡中的實驗效果并不突出，此外，在Facebook網絡和Fraud ring網絡的實驗前中期效果顯著，但是在實驗后期效果較差。整體而言，按照NI-CA算法計算結果順序移除節點，對目標網絡的破壞性較大，移除后網絡更加分散。傳統節點重要性算法所形成的重要節點聚集現象，在魯棒性測試中可以明顯看出該現象的影響，當移除一個重要節點后，下一次移除的節點很可能是該節點的鄰居節點，從而對網絡的整體性破壞很小。NI-CA算法通過評估節點的社區內部、外部影響力，有效減少了重要節點聚集的現象，更快速地分散整個網絡。

圖5 魯棒性測試結果Fig.5 Robustness test results

3.2.3 肯德爾相關系數驗證

肯德爾相關系數τ[28-29]是一個用來測量兩組序列相關性的統計值，在統計學領域多用于分布未知、數據類型離散的相關樣本的比較，取值范圍在-1到1之間，當τ為1時，表示兩個隨機變量擁有一致的等級相關性；當τ為-1時，表示兩個隨機變量擁有完全相反的等級相關性；當τ為0時，表示兩個隨機變量是相互獨立的。由此可知，當通過算法得出的重點人排序與網絡中真實的頭部重點人比較時，肯德爾相關系數越大，說明和諧的節點數越多、算法效果越好。

其中，nc和nd分別表示和諧以及不和諧的個數，n為網絡節點總數，公式（12）之所以用和諧與不和諧的個數差除n(n-1)÷2，是為了解決歸一化問題。

本文選取Karate網絡、A Song of Ice and Fire人物網絡和Fraud ring網絡進行肯德爾相關系數實驗，通過網絡結構背后的實際意義、劇情和主演列表以及中國裁判文書網對相關Fraud ring判決文書確定各網絡的關鍵節點序列，分別運用NI-CA指標、Degree指標、Eigenvector指標、Betweenness指標和PageRank算法所計算出的重要成員進行相關性分析，橫向比較各組數據的肯德爾相關系數。

四種網絡的肯德爾相關系數驗證結果如表2所示，實驗結果顯示，各算法對Karate網絡節點的驗證都較為準確，NI-CA算法的優越性并沒有過于突出，但對于其他三個網絡NI-CA算法結果相較于其他算法更為準確，即NI-CA算法對各網絡頭部重點人評價適用性、準確性較高。該結果表明NI-CA算法整體上準確性較高，同時適用大型網絡和小型網絡。

表2 肯德爾相關系數實驗結果Table 2 Kendall correlation coefficient experimental results

4 總結

本文提出了基于社區評估的NI-CA算法，對劃分社區后的目標人群進行社區評估分析，通過融合成員社區內部影響力和外部連通性，識別各社區的領袖人物，削弱傳統節點重要性分析的“富人俱樂部”現象。于該理論，本文運用四個不同的社交網絡進行驗證，驗證表明NI-CA算法準確性高，受網絡結構特征的影響較小，所需數據維度少、普適性高，除用于目標人群關鍵人員挖掘，還可用于網絡輿論控制等能抽象出具有此類網絡拓撲特征的案件模型。

本文提出的方法還有一定的不足之處，本文在考慮節點的外部連通性上仍有改進空間。另外，在本文的研究基礎上仍有需要進一步研究的事項，例如本文所使用的網絡為靜態網絡，綜合考慮網絡中節點的時序特征對其重要性的影響。此外，有向網絡和加權網絡的重要節點挖掘，例如email交流的社交網絡，考慮節點間關系的有向性和兩節點之間的交流次數，也是后續工作的研究方向之一。