基于核心節點的網絡社區發現方法研究

張擁華

（湖南工業職業技術學院，湖南 長沙 410208）

1 引言

隨著信息技術的飛速發展，各種開放式的電子商務應用平臺不斷涌現，人們之間的溝通越來越多地依賴于虛擬的交互平臺和現代技術手段，虛擬的社會網絡開始走進人們的生活，并誕生了網絡社區的新生事物。對網絡社區的數據進行分析、挖掘，揭示數據背后的規律、知識，作為各種不同應用的決策支撐成為許多研究人員關注的領域。虛擬的網絡社區不同于真實世界的社會，網絡社區的成員通常存在許多交集，而且一個成員可能歸屬于不同的社區，從而存在重疊的現象，匈牙利的社會科學家Palla通過大量的實驗證明重疊社區現象存在的普遍性，可以用貼標簽的方式來形象地描述重疊社區與非重疊社區的區別，非重疊社區就是社區中的節點只能貼上一個標簽，表示該節點只能歸屬于這一個社區，而重疊社區則沒有這個限制，社區中任意一個都可以貼上多個標簽，表示這個節點同時屬于這些社區，就好比我們同時加入好多個興趣圈子，里面有音樂圈子、籃球圈子、運動養生圈子等等。基于Palla的派系過濾理論的方法有：T.S.Evans的Clique Graph[1]，CPM算法[2]，基于極大子團合并的EAGLE算法[3]。

由于網絡規模呈不斷增加的趨勢，在進行社區發現過程中，難以獲得網絡的全局信息，因此，研究人員提出從網絡的局部信息入手進行研究，并設計了基于局部社區的算法，實驗證明采用局部社區進行計算的算法能成功獲得社區結構，同時，也可以使用在重疊社區與非重疊社區發現工作中，具有重要的實踐意義和價值，具有代表性的算法主要包括：基于極大子團擴張的GCE算法[4]、Clauset的Local Modularity方法[5]等。

本文將針對傳統社區發現算法的不足之處，提出一種基于核心節點的局部社區擴張算法EALCN（Expansion Algorithm based on Local Community Core Nodes），并對算法的時間復雜度進行分析，最后通過仿真實驗證明該算法在大多數高度重疊的社區發現上具有一定的優勢，具有一定的可行性。

2 問題定義

在本文中，網絡都被定義成多個局部社區的集合，而局部社區則是由核心節點以及圍繞這個核心節點的一系列的節點組成。一個節點是否被納入到一個社區中則是由適應度函數F來決定，一個局部社區S包含節點n，當且僅當n滿足F(n)＞0。局部社區都是從一個初始節點開始，通過適應度函數不斷判斷社區外的節點是否加入到社區中，從而不斷壯大社區規模，直到沒有合適的節點可以加入社區中。經過多次的迭代之后，網絡中所有節點便都分配到不同的社區中。如圖1所示，是一個局部社區的例子，圖中的網絡由幾個結構非常明顯的局部社區構成，紅色節點表示核心節點，其具有極大的度數，黑色的節點則是普通成員節點。從圖中我們可以很清晰看到重疊社區重疊部分高度重疊的特征，重疊的程度通常都是跟初始節點以及適應度函數相關。

圖1 一個局部社區的例子

3 基于核心節點的局部社區發現算法

局部社區的發現大體都是由一個種子節點開始，然后經過不斷地擴張，最終形成一個社區。諸如LFM這些傳統的社區發現算法，通常都是采用隨機的方式選取初始節點，這樣選出來的節點往往都不是核心節點，這樣就會造成算法的準確性極低。GCE算法嘗試使用網絡中的極大子團替代節點作為種子擴張，但是極大子團的獲取需要大量的計算，這就使得算法的效率大幅度降低。根據網絡節點度的分布特征我們知道，網絡中度數很大的節點是少量的，大多數節點度是很小的，而這些度數很大的節點往往也是社區的核心，所有我們完全可以通過找出這類節點作為種子節點來進行擴張。考慮到權重對種子節點的影響，我們在選取種子節點時，將權重也加入影響因素中。基于此，本文提出了一種基于核心節點的社區發現算法，該算法首先發現網絡中的一系列核心節點，然后將他們的跟隨者加入到社區中，從而形成社區結構。具體流程如圖2所示。

圖2 算法流程圖

3.1 種子節點的選取

在現實生活中，每個人都有自己的興趣圈子，在這些圈子里每個人都扮演者不同的角色，比如你關注的某個網絡主播要開始主播，你可能就會去加入到這個圈子中去，但是這個主播是這個圈子的核心，起著引導作用，而大多數的關注只是一個普通的參與者。這個就清晰地反映出在一個社交圈中，每個人的影響力是不同的，他對這個社交圈所起到的作用也就不一樣，換句話說就是他在這個社交圈中的重要性不一樣。上文提到過，我們認為局部社區就是核心節點及其跟隨者所構成的群體結構。因此，最快找出這個社區的方法就是先找出其核心節點，然后再圍繞核心節點進行社區擴張。由無標度網絡模型，我們知道網絡中的節點大多數度數是很小的，只有少量的節點的度數很大。那么假設網絡中的每一個節點都至少歸屬于一個社區(獨立節點自成一個社區)，則社區中必定會存在著這樣一個核心節點。

首先，本文對PageRank算法進行改進，使其能夠適應無向圖的節點排序，以找出網絡中的潛在核心節點。

G=＜V,E,w＞是一個無向加權網絡，w表示權重，則任意節點i的PR值為：

其中，N是網絡G中節點總數；wij為邊ij的權重；c為調節因子，為一個常數，通常設置為0.85左右，Si即為節點的度。上述定義是基于遞歸定義的。可以看出，每個節點的PR值都依賴于其鄰接節點的PR值，而且后者會按照自身權值與前者所有鄰接節點權值之和之比來將自身的PR值分配給前者。

具體的PR值計算請看下列中的偽代碼：

?

經過排序后的節點，排名靠前的都有成為核心節點的潛質了，但是，初始化是非常關鍵的。選擇一個正確的節點作為初始節點進行擴張可以快速地得到一個正確的社區結構，然而從一個錯誤初始節點開始那么結果往往是很糟糕的。為了避免先后選出的節點都位于同一個社區中，本文采取了更少的鄰居節點的方法，即在選擇核心節點時，先判斷此節點與先前的核心節點的共同鄰居數，當這個數大于閾值時，則棄置它，即核心節點之間的共同鄰居數必須小于閾值β。

3.2 局部社區的擴張

本算法定義了一個適應度函數，只有選取了適當的種子節點，便可以通過貪婪算法來不斷擴大適應度函數，從而獲取得到一個最優的社區結構。該適應度函數可以計算出任意子圖的適應度，子圖的適應度反映出了子圖內部與外部的連接密度情況，對子圖做任何的修改都會引起適應度的變化。通過不斷修改子圖的成員，添加或者刪除，使得子圖的適應度不斷增大，直到子圖的適應度不在發生變化為止，此時便得到了最優的社區結構。

對于一個給定的社區S,那么S的適應度為：

其中，Kin(s)是社區S的內部節點度數和，Kout(s)是社區S與外部的連接數之和,α為一個可控制社區規模大小的參數。

節點適應度是指一個節點對于社區適應度的貢獻，所以對于一個給定的節點A，那么其對于社區S的節點適應度為：

其中，S+A表示將節點A加入社區S后的社區。

局部社區發現算法通常都是由一個初始節點開始，然后不斷進行社區擴張，從而形成完整的社區結構。但是，算法的結果受到算法擴張模式的影響是極大的。一般地，算法中都出現節點震蕩、重復計算和畸形生長的問題，因此，本文定義的社區發現流程如算法2所示。

?

經過上述過程，便可以由一個初始核心節點得到一個社區結構。

3.3 局部社區的優化——合并冗余社區

幾乎所有的重疊社區發現算法都無可避免地會遇到“過渡重疊”的問題，這類社區也被稱為冗余社區。雖然我們在極力地提高種子節點的選擇精準度，以及優化社區的擴張模式，但是網絡本身的不確定性以及算法本身在參數的控制上存在的不確定性，會造成社區與社區之間出現嚴重的交叉現象。為了檢測出社區間的冗余情況，以及合并冗余社區，本文定義了一個重疊度來定量地刻畫社區的冗余情況。

給定兩個社區C1和C2，則他們之間的重疊度為：

當社區的重疊程度超過閾值時，將兩個社區進行合并操作，經過反復的實驗，可以發現這個閾值設為0.65左右較為合適。在構造局部社區的同時，冗余社區的檢測工作也在同步進行，在一個社區結構形成之后，立即對其檢測，如果該社區的冗余度小于設定的閾值，便接受這個社區；如果大于設定的閾值，那么就放棄這個社區。通過反復進行這些操作，可以盡可能避免過度重疊的社區出現。

4 仿真與性能分析

為了證明本文所提出的EALCN算法的有效性，在如表1所示的環境下進行試驗。

表1 實驗環境

圖3為原始網絡圖，圖4為使用EALCN算法后得到的優化處理結果。

圖3 原始網絡圖

圖4 使用EALCN算法劃分結果

比較圖3和圖4，使用EALCN算法可以獲得多個覆蓋全網絡的局部社區，并且具有算法復雜度小、執行效率高的特點。

5 結束語

本文針對目前網絡規模不斷增大的情況下，難以獲得網絡全局信息的現實問題，利用網絡中的局部信息來實現對目標函數的優化。具體而言是通過修改PageRank算法來獲取初始核心節點，然后由初始核心節點開始，通過不斷地優化目標函數來構建局部社區結構。實驗證明，本文提出的EALCN算法能有效地改進網絡社區的劃分效果，提高社區劃分的準確性。

[1]柴變芳,于劍,賈彩燕,等.一種姓于隨機塊欖喂的快速廣義社區發現算法[J].軟件報.2013,24(11):2699-2709.

[2].G.Palla,1.Derenyi,I.Farkas,T.Vicsek.Uncovering the overlapping community structure of complex networks in nature and society.Nature.2005,435(7043):814-818.

[3]H.Shen,X.Cheng,K.Cai,M.B.Hu.Detect overlapping and hierarchical community structure in networks.Physica A:Statistical Mechanics and its Applications.2009,388(8):1706-1712.

[4]C Lee,F Reid,A McDaid,N Hurley.Detecting highly overlapping community structure by greedy clique expansion IA].ln Proc.SNA-KDD Workshop1?"1,Washington DC,USA:IEEE,2010.33-42.

[5]A.Clauset.Finding local community structure in networks.Physical Review E.2005,72(2):026132+.