基于核心節(jié)點的網(wǎng)絡(luò)社區(qū)發(fā)現(xiàn)方法研究

張擁華

（湖南工業(yè)職業(yè)技術(shù)學院，湖南 長沙 410208）

1 引言

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

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

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

2 問題定義

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

圖1 一個局部社區(qū)的例子

3 基于核心節(jié)點的局部社區(qū)發(fā)現(xiàn)算法

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

圖2 算法流程圖

3.1 種子節(jié)點的選取

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

首先，本文對PageRank算法進行改進，使其能夠適應(yīng)無向圖的節(jié)點排序，以找出網(wǎng)絡(luò)中的潛在核心節(jié)點。

G=＜V,E,w＞是一個無向加權(quán)網(wǎng)絡(luò)，w表示權(quán)重，則任意節(jié)點i的PR值為：

其中，N是網(wǎng)絡(luò)G中節(jié)點總數(shù)；wij為邊ij的權(quán)重；c為調(diào)節(jié)因子，為一個常數(shù)，通常設(shè)置為0.85左右，Si即為節(jié)點的度。上述定義是基于遞歸定義的?？梢钥闯觯總€節(jié)點的PR值都依賴于其鄰接節(jié)點的PR值，而且后者會按照自身權(quán)值與前者所有鄰接節(jié)點權(quán)值之和之比來將自身的PR值分配給前者。

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

?

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

3.2 局部社區(qū)的擴張

本算法定義了一個適應(yīng)度函數(shù)，只有選取了適當?shù)姆N子節(jié)點，便可以通過貪婪算法來不斷擴大適應(yīng)度函數(shù)，從而獲取得到一個最優(yōu)的社區(qū)結(jié)構(gòu)。該適應(yīng)度函數(shù)可以計算出任意子圖的適應(yīng)度，子圖的適應(yīng)度反映出了子圖內(nèi)部與外部的連接密度情況，對子圖做任何的修改都會引起適應(yīng)度的變化。通過不斷修改子圖的成員，添加或者刪除，使得子圖的適應(yīng)度不斷增大，直到子圖的適應(yīng)度不在發(fā)生變化為止，此時便得到了最優(yōu)的社區(qū)結(jié)構(gòu)。

對于一個給定的社區(qū)S,那么S的適應(yīng)度為：

其中，Kin(s)是社區(qū)S的內(nèi)部節(jié)點度數(shù)和，Kout(s)是社區(qū)S與外部的連接數(shù)之和,α為一個可控制社區(qū)規(guī)模大小的參數(shù)。

節(jié)點適應(yīng)度是指一個節(jié)點對于社區(qū)適應(yīng)度的貢獻，所以對于一個給定的節(jié)點A，那么其對于社區(qū)S的節(jié)點適應(yīng)度為：

其中，S+A表示將節(jié)點A加入社區(qū)S后的社區(qū)。

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

?

經(jīng)過上述過程，便可以由一個初始核心節(jié)點得到一個社區(qū)結(jié)構(gòu)。

3.3 局部社區(qū)的優(yōu)化——合并冗余社區(qū)

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

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

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

4 仿真與性能分析

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

表1 實驗環(huán)境

圖3為原始網(wǎng)絡(luò)圖，圖4為使用EALCN算法后得到的優(yōu)化處理結(jié)果。

圖3 原始網(wǎng)絡(luò)圖

圖4 使用EALCN算法劃分結(jié)果

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

5 結(jié)束語

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

[1]柴變芳,于劍,賈彩燕,等.一種姓于隨機塊欖喂的快速廣義社區(qū)發(fā)現(xiàn)算法[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+.