基于共鄰節(jié)點相似度的社區(qū)劃分算法

付立東 郝偉 李丹 李凡

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

關(guān)鍵詞：共鄰節(jié)點;相似度度量;節(jié)點局部影響力;模塊度;社區(qū)劃分

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 引言

復(fù)雜網(wǎng)絡(luò)是復(fù)雜系統(tǒng)的典型表現(xiàn)形式，得到了經(jīng)濟(jì)學(xué)、生物學(xué)和社會學(xué)等不同學(xué)科學(xué)者的廣泛關(guān)注，成為當(dāng)今的熱點研究課題[1-2]，而通過網(wǎng)絡(luò)的社區(qū)結(jié)構(gòu)來分析研究網(wǎng)絡(luò)的功能和特征，已經(jīng)成為復(fù)雜網(wǎng)絡(luò)的研究趨勢。網(wǎng)絡(luò)的社區(qū)結(jié)構(gòu)[3]，是網(wǎng)絡(luò)中的個體之間按照某種規(guī)則而自然形成或人為構(gòu)造的一種關(guān)系，社區(qū)結(jié)構(gòu)的特征表現(xiàn)為將網(wǎng)絡(luò)分割成多個子網(wǎng)絡(luò)，子網(wǎng)絡(luò)內(nèi)部的鏈接比較緊密，而子網(wǎng)絡(luò)之間的鏈接則比較稀疏[4]。

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

1 相關(guān)定義

1.1 相似度模型

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

對星型鄰域網(wǎng)絡(luò)中的節(jié)點進(jìn)行描述：

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

將圖2星型鄰域網(wǎng)絡(luò)用圖3文氏圖來表示。

這里，H（X）表示星型鄰域網(wǎng)絡(luò)X中全部節(jié)點集合，H（X|Y）表示屬于星型鄰域網(wǎng)絡(luò)X且不屬于星型鄰域網(wǎng)絡(luò)Y的節(jié)點集合，H（X，Y）表示星型鄰域網(wǎng)絡(luò)X和星型鄰域網(wǎng)絡(luò)Y的全部節(jié)點集合，I（X，Y）表示星型鄰域網(wǎng)絡(luò)X和星型鄰域網(wǎng)絡(luò)Y共有的節(jié)點集合。

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

基于以上這些基礎(chǔ)，對兩個星型鄰域網(wǎng)絡(luò)間相互缺少的節(jié)點進(jìn)行數(shù)字化度量，例如星型鄰域網(wǎng)絡(luò)Y在星型鄰域網(wǎng)絡(luò)X中缺少的節(jié)點，那么網(wǎng)絡(luò)X中的節(jié)點與網(wǎng)絡(luò)Y中的每一個節(jié)點進(jìn)行匹配，定義如下：

對式（4）中進(jìn)行匹配的節(jié)點i和節(jié)點j星型鄰域網(wǎng)絡(luò)化處理，可得：

其中：h（w，z）=w/（z（z-1）/2），w代表兩個星型鄰域網(wǎng)絡(luò)中所有節(jié)點進(jìn)行劃分后每個星型鄰域網(wǎng)絡(luò)含有的節(jié)點個數(shù)，z代表兩個星型鄰域網(wǎng)絡(luò)包含的節(jié)點總數(shù)，z（z-1）/2表示為兩個星型鄰域網(wǎng)絡(luò)的網(wǎng)絡(luò)強(qiáng)度。

星型鄰域網(wǎng)絡(luò)X中所有節(jié)點再求和，至此得到星型鄰域網(wǎng)絡(luò)Y在星型鄰域網(wǎng)絡(luò)X中缺少的節(jié)點度量：

最后對星型鄰域網(wǎng)絡(luò)X進(jìn)行度量：

其中：w為星型鄰域網(wǎng)絡(luò)X包含的節(jié)點總數(shù)，z為兩個星型鄰域網(wǎng)絡(luò)包含的所有節(jié)點數(shù)。

同理，對星型鄰域網(wǎng)絡(luò)Y的定義同星型鄰域網(wǎng)絡(luò)X的定義一樣。

1.2 共鄰節(jié)點相似度定義

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

1.3 節(jié)點局部影響力

該指標(biāo)從源節(jié)點的最近鄰節(jié)點和次近鄰節(jié)點出發(fā)，能有效地識別出局部信息下節(jié)點的影響力，給定網(wǎng)絡(luò)中的一個節(jié)點i，其局部影響力指標(biāo)Li定義：

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

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

相關(guān)研究文獻(xiàn)[12]表明，當(dāng)獲取到給定網(wǎng)絡(luò)的節(jié)點影響力集后，對這些節(jié)點進(jìn)行聚類，通常能獲得穩(wěn)定的社區(qū)結(jié)構(gòu)。

2 基于共鄰節(jié)點相似度的社區(qū)發(fā)現(xiàn)算法

好的社區(qū)發(fā)現(xiàn)算法應(yīng)該同時滿足兩個條件：1）較低的時間復(fù)雜度;2）較高的社區(qū)劃分準(zhǔn)確度。然而現(xiàn)有的很多算法難以同時達(dá)到以上兩點，針對上面兩個條件，本文提出了一種新的基于共鄰節(jié)點相似度的社區(qū)發(fā)現(xiàn)算法。

2.1 算法改進(jìn)

本文在計算節(jié)點間的相似度值時，計算擁有共同鄰居節(jié)點的節(jié)點對間的相似度，若節(jié)點間沒有共鄰節(jié)點，則認(rèn)為兩者相似度為0;若節(jié)點間有共鄰節(jié)點，則兩者的相似度取決于共鄰節(jié)點的數(shù)量和共鄰節(jié)點占鄰居節(jié)點總數(shù)的比重，共鄰節(jié)點占鄰居節(jié)點總數(shù)比重越大，則兩節(jié)點間的相似度就越高。基于相似度模型，將式（1）中得到的cX，Y是否等于0作為是否繼續(xù)計算兩個節(jié)點相似度的依據(jù)：如果cX，Y不等于0，則繼續(xù)進(jìn)行相似度值計算;反之，則結(jié)束此節(jié)點對間的計算，以此來達(dá)到降低算法復(fù)雜度的目的。

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

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

基于以上因素，這樣算法將節(jié)點間的相似度度量轉(zhuǎn)化成為星型鄰域網(wǎng)絡(luò)間的相似度度量，在相似度、節(jié)點影響力的基礎(chǔ)上，本文提出基于共鄰節(jié)點相似度的社區(qū)劃分算法。

2.2 算法描述

步驟一 初始社區(qū)形成。

1）對給定的網(wǎng)絡(luò)，按照式（8）獲得n*n的共鄰節(jié)點相似度矩陣S，S={Sij}，n=|V|，其中n為節(jié)點數(shù)，V為節(jié)點集，初始聚類時，將每個節(jié)點看作一個獨(dú)立的社區(qū)。

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