基于共鄰節點相似度的社區劃分算法

付立東 郝偉 李丹 李凡

摘 要：復雜網絡中的社區結構能幫助人們認識網絡的基本結構及其功能。針對目前多數社區劃分算法準確率低、復雜度高的問題，提出了一種基于共鄰節點相似度的社區劃分算法。首先，為了計算節點間相似度值，提出了相似度模型，該模型通過將被測節點對的鄰居節點引入一并計算，提高了相似度度量的準確性;然后，計算節點局部影響力值，能客觀地表現出節點在所處網絡中的重要性;其次，結合節點相似度值和節點局部影響力值對節點進行層次聚類，完成網絡社區結構的初步劃分;最后，通過聚合初步劃分的子社區，獲得復雜網絡的最優模塊度值。仿真結果表明，在網絡的社區特征模糊時，與新的基于局部相似度的社區發現算法（CDALS）相比，所提算法的準確率提高了14%，證明了所提提法更能夠準確、有效地劃分復雜網絡的社區結構。

關鍵詞：共鄰節點;相似度度量;節點局部影響力;模塊度;社區劃分

Abstract： The community structure in complex networks can help people recognize basic structure and functions of network. Aiming at the problems of low accuracy and high complexity of most community division algorithms， a community division algorithm based on similarity of common neighbor nodes was proposed. Firstly， a similarity model was proposed in order to calculate the similarity between nodes. In the model， the accuracy of similarity measurement was improved by calculating the tested node pairs and their neighbor nodes together. Secondly， local influence values of nodes were calculated， objectively showing the importances of nodes in the network. Thirdly， the nodes were hierarchically clustered according to the similarity and local influence values of nodes， and preliminary division of network community structure was completed. Finally， the preliminary divided sub-communities were clustered until the optimal modularity value was obtained. The simulation results show that compared with the new Community Detection Algorithm based on Local Similarity （CDALS）， the proposed algorithm has the accuuracy improved by 14%， which proves that the proposed algorithm can divide the community structure of complex networks accurately and effectively.

Key words： common neighbor node; similarity measurement; local influence of node; modularity; community division

0 引言

復雜網絡是復雜系統的典型表現形式，得到了經濟學、生物學和社會學等不同學科學者的廣泛關注，成為當今的熱點研究課題[1-2]，而通過網絡的社區結構來分析研究網絡的功能和特征，已經成為復雜網絡的研究趨勢。網絡的社區結構[3]，是網絡中的個體之間按照某種規則而自然形成或人為構造的一種關系，社區結構的特征表現為將網絡分割成多個子網絡，子網絡內部的鏈接比較緊密，而子網絡之間的鏈接則比較稀疏[4]。

當前在社區網絡的定義、發現和識別等方面有許多研究[5-7]。節點間的相似度是復雜網絡節點的一個特性，越相似的節點越容易聚集成群、形成社區結構[8]，針對這個特性提出了很多社區劃分算法。顧亦然等[9]提出了一種新的基于局部相似度的社區發現算法（a new Community Detection Algorithm based on Local Similarity， CDALS），通過引入節點對及其共同鄰居間相互聯絡的親密程度，定義了新的相似度指標，基于網絡節點相似度矩陣，結合改進的K均值（K-means）聚類方法對網絡節點進行相似性聚類，實現網絡的社區劃分;梁宗文等[10]定義了節點全局和局部相似性衡量指標，將節點按相似性合并條件劃分到同一個社區中，待所有節點都被劃分到社區中后終止算法，完成網絡的社區劃分，本文將此算法記為Similarity算法。目前，基于節點相似度的社區劃分算法都普遍具有算法復雜度高、準確性較低的問題。針對該問題，本文考慮到節點對與共同鄰居節點之間的關系，定義了新的節點相似性度量，利用節點局部影響力和模塊度度量作為閾值，進而準確、有效地進行社區劃分。

1 相關定義

1.1 相似度模型

以每個網絡節點作為背景，結合其所有鄰居節點，形成以此節點為核心的星型鄰域網絡[11]。圖1表示無向網絡G=（V，E），其中V={v1，v2，…，vn}表示節點的集合，E={（vi，vj）|vi，vj∈V}表示邊的集合，用藍色標記網絡G中的節點x和節點y，紅色標記節點x和節點y的鄰居節點，深黑色標記它們的共同鄰居節點。以節點x和節點y分別為核心的星型鄰域網絡X和星型鄰域網絡Y如圖2所示。

對星型鄰域網絡中的節點進行描述：

在式（1）中，0表示節點不屬于這個星型鄰域網絡，1表示節點屬于這個星型鄰域網絡。aX，Y表示屬于星型鄰域網絡X且不屬于星型鄰域網絡Y的節點總數，bX，Y表示屬于星型鄰域網絡Y且不屬于星型鄰域網絡X的節點總數;如果cX，Y=0，則表示星型鄰域網絡X和星型鄰域網絡Y沒有共同鄰居節點。

將圖2星型鄰域網絡用圖3文氏圖來表示。

這里，H（X）表示星型鄰域網絡X中全部節點集合，H（X|Y）表示屬于星型鄰域網絡X且不屬于星型鄰域網絡Y的節點集合，H（X，Y）表示星型鄰域網絡X和星型鄰域網絡Y的全部節點集合，I（X，Y）表示星型鄰域網絡X和星型鄰域網絡Y共有的節點集合。

注 在式（3）中，MAX（H（X），H（Y））、12（H（X）+H（Y））、H（X，Y）這三個變量存在的意義是對變量I（X，Y）取值范圍進行限定，從作用上來說是等價的，本文不考慮這三個變量間的比較。

基于以上這些基礎，對兩個星型鄰域網絡間相互缺少的節點進行數字化度量，例如星型鄰域網絡Y在星型鄰域網絡X中缺少的節點，那么網絡X中的節點與網絡Y中的每一個節點進行匹配，定義如下：

對式（4）中進行匹配的節點i和節點j星型鄰域網絡化處理，可得：

其中：h（w，z）=w/（z（z-1）/2），w代表兩個星型鄰域網絡中所有節點進行劃分后每個星型鄰域網絡含有的節點個數，z代表兩個星型鄰域網絡包含的節點總數，z（z-1）/2表示為兩個星型鄰域網絡的網絡強度。

星型鄰域網絡X中所有節點再求和，至此得到星型鄰域網絡Y在星型鄰域網絡X中缺少的節點度量：

最后對星型鄰域網絡X進行度量：

其中：w為星型鄰域網絡X包含的節點總數，z為兩個星型鄰域網絡包含的所有節點數。

同理，對星型鄰域網絡Y的定義同星型鄰域網絡X的定義一樣。

1.2 共鄰節點相似度定義

基于相似度模型，節點x和節點y的相似性度量：

1.3 節點局部影響力

該指標從源節點的最近鄰節點和次近鄰節點出發，能有效地識別出局部信息下節點的影響力，給定網絡中的一個節點i，其局部影響力指標Li定義：

其中：Γi和Πj分為節點i的最近鄰節點集合和次近鄰節點集合，Nv為節點i的次近鄰節點度數。

如圖4所示，網絡包含8個節點，對該網絡進行節點局部影響力計算，結果如表1所示。以節點3為例，具體計算方法為：節點3包含4個最近鄰節點（1，2，6，8），以及2個次近鄰節點（4，7），由式（10）得：w3=5，由式（9）可知節點3的局部影響力L3=w1+w2+w6+w8=21。各節點度值Ki，近鄰節點數Ni，次近鄰節點度數總和Wj以及節點局部影響力Li如表1所示。

相關研究文獻[12]表明，當獲取到給定網絡的節點影響力集后，對這些節點進行聚類，通常能獲得穩定的社區結構。

2 基于共鄰節點相似度的社區發現算法

好的社區發現算法應該同時滿足兩個條件：1）較低的時間復雜度;2）較高的社區劃分準確度。然而現有的很多算法難以同時達到以上兩點，針對上面兩個條件，本文提出了一種新的基于共鄰節點相似度的社區發現算法。

2.1 算法改進

本文在計算節點間的相似度值時，計算擁有共同鄰居節點的節點對間的相似度，若節點間沒有共鄰節點，則認為兩者相似度為0;若節點間有共鄰節點，則兩者的相似度取決于共鄰節點的數量和共鄰節點占鄰居節點總數的比重，共鄰節點占鄰居節點總數比重越大，則兩節點間的相似度就越高?；谙嗨贫饶Ｐ?，將式（1）中得到的cX，Y是否等于0作為是否繼續計算兩個節點相似度的依據：如果cX，Y不等于0，則繼續進行相似度值計算;反之，則結束此節點對間的計算，以此來達到降低算法復雜度的目的。

其次，當前大多數局部相似度度量都只關注節點與共同鄰居節點間的聯系，而忽視除共同鄰居節點外其他鄰居節點對節點間相似度的貢獻，基于此，本文在提出相似度模型時，引入式（4）和（5），將被測節點對的所有鄰居節點對節點相似度的作用一并計算，提高了相似度度量的準確性。

最后，針對傳統社區發現算法隨機選取一個節點作為初始社區，并且將當前節點可能會與多個節點具有相同的相似度時，不能確定選取哪一個節點作為下一個當前節點等特殊情況考慮進去，因此加入節點的局部影響力，在節點進行聚類時加以輔助，以便達到高質量的劃分效果。節點影響力可以客觀地表現出節點在所處網絡中的重要性，而且不會增加算法的時間復雜度，所以它適合用來進行節點聚類。

基于以上因素，這樣算法將節點間的相似度度量轉化成為星型鄰域網絡間的相似度度量，在相似度、節點影響力的基礎上，本文提出基于共鄰節點相似度的社區劃分算法。

2.2 算法描述

步驟一 初始社區形成。

1）對給定的網絡，按照式（8）獲得n*n的共鄰節點相似度矩陣S，S={Sij}，n=|V|，其中n為節點數，V為節點集，初始聚類時，將每個節點看作一個獨立的社區。

2）根據節點局部影響力表，在節點集V中選取影響力最大的節點i，將其置為當前節點，根據相似度矩陣選取與當前節點i相似度值最高的節點j。V=V-i。