張曉芬，　封　筠，　賈寧寧

(石家莊鐵道大學(xué) 信息科學(xué)與技術(shù)學(xué)院，河北 石家莊　050043)

?

種子節(jié)點非重疊社團挖掘算法研究

張曉芬，封筠，賈寧寧

(石家莊鐵道大學(xué) 信息科學(xué)與技術(shù)學(xué)院，河北 石家莊050043)

提出一種新型的種子節(jié)點社團挖掘算法，首先，利用主成分分析技術(shù)由單一性節(jié)點重要性評價指標(biāo)提取出綜合性評價指標(biāo)，挑選評價指標(biāo)值最大的節(jié)點作為種子節(jié)點，對其進行廣度優(yōu)先搜索，指標(biāo)值大的節(jié)點不斷地影響指標(biāo)值小的節(jié)點，得到種子節(jié)點所在的社團結(jié)構(gòu)。然后，從已知社團結(jié)構(gòu)外選取綜合性評價指標(biāo)值最大的節(jié)點重復(fù)上述過程，得到初始社團結(jié)構(gòu)集合。對于社團結(jié)構(gòu)間存在重疊節(jié)點情況，根據(jù)重疊節(jié)點與兩個社團間的連邊數(shù)解決重疊節(jié)點的歸屬問題，得到最終網(wǎng)絡(luò)的社團結(jié)構(gòu)?；鶞?zhǔn)網(wǎng)絡(luò)的實驗結(jié)果表明，所提出的綜合評價指標(biāo)能更好地表征節(jié)點的重要性，與譜方法社團挖掘?qū)嶒灲Y(jié)果相比，所提出的種子節(jié)點社團挖掘算法具有較高性能。

社團挖掘；種子節(jié)點；節(jié)點重要性綜合評價指標(biāo)；復(fù)雜網(wǎng)絡(luò)；非重疊社團

現(xiàn)實世界中許多規(guī)模較大且復(fù)雜的網(wǎng)絡(luò)，如社會關(guān)系網(wǎng)絡(luò)、生物分子網(wǎng)絡(luò)等被看作復(fù)雜網(wǎng)絡(luò)，社團結(jié)構(gòu)是復(fù)雜網(wǎng)絡(luò)的一個重要拓?fù)涮卣?。社團結(jié)構(gòu)是指社團內(nèi)部結(jié)構(gòu)緊密，社團間結(jié)構(gòu)稀疏，對社團結(jié)構(gòu)的分析與挖掘具有重要的學(xué)術(shù)研究價值和實際意義[1]。當(dāng)前復(fù)雜網(wǎng)絡(luò)社團結(jié)構(gòu)挖掘大多基于聚類算法研究，復(fù)雜網(wǎng)絡(luò)的聚類算法大致可歸結(jié)為3類算法：(1)優(yōu)化聚類算法。該類算法又可分為譜方法和局部搜索。(2)啟發(fā)類算法。(3)其它類算法。該類算法又可分為相似度算法和混合搜索。然而，基于聚類的社團挖掘算法需事先確定社團的個數(shù)，但隨著網(wǎng)絡(luò)規(guī)模的不斷擴大，獲得全網(wǎng)的信息十分困難且時間復(fù)雜度較高。近年來，局部社團挖掘算法得到關(guān)注，其降低了計算的復(fù)雜度，但限于起始節(jié)點降低了挖掘的社團質(zhì)量。本文給出了基于主成分分析技術(shù)由單一性節(jié)點重要性評價指標(biāo)提取出的一種綜合性評價指標(biāo)尋找社團的種子節(jié)點，利用種子節(jié)點進行廣度優(yōu)先搜索策略進行社團挖掘，提高了社團質(zhì)量，同時通過對這些種子節(jié)點的重點保護以提高整個網(wǎng)絡(luò)的可靠性。

1　相關(guān)知識

目前，學(xué)者們主要從3個方面進行節(jié)點重要度的研究：(1)社會網(wǎng)絡(luò)分析方法，通過分析網(wǎng)絡(luò)中某些有用的信息，評估不同節(jié)點的重要性，例如節(jié)點的度中心性、介數(shù)、接近度及權(quán)重等屬性[2]；(2)系統(tǒng)科學(xué)分析方法，利用網(wǎng)絡(luò)的連通性來反映系統(tǒng)某種功能的完整性，通過度量節(jié)點刪除對網(wǎng)絡(luò)連通的破壞程度來反映網(wǎng)絡(luò)節(jié)點的重要性，即“破壞性等價于重要性”，基于該思想學(xué)者們提出了系統(tǒng)的“核和核度”理論[3]，并通過對核度計算方法的定義實現(xiàn)了節(jié)點重要度的評價；(3)信息搜索領(lǐng)域分析方法，主要是通過分析網(wǎng)頁之間的鏈接關(guān)系計算網(wǎng)頁節(jié)點的重要性，例如著名的Pagerank算法[4]和HITS算法[5]等?，F(xiàn)主要應(yīng)用社會網(wǎng)絡(luò)分析方法中的4種指標(biāo)，分別為節(jié)點的點度中心性、接近度、介數(shù)和特征向量。

1.1度中心性(Degree centrality)

度中心性強調(diào)節(jié)點對網(wǎng)絡(luò)的直接影響，節(jié)點自身的連接總數(shù)體現(xiàn)了個體對網(wǎng)絡(luò)的影響。節(jié)點的度中心性越大，該節(jié)點可能就越重要。度中心性CD(v)的定義為

(1)

式中，deg(v)代表節(jié)點v的度；n代表網(wǎng)絡(luò)中節(jié)點的個數(shù)。

1.2接近度(Closeness)

接近度是利用信息在網(wǎng)絡(luò)傳播速度的快慢來決定節(jié)點重要性的，跟節(jié)點最短路徑或最小距離概念關(guān)系密切。它是比較網(wǎng)絡(luò)中每一節(jié)點到達其它所有節(jié)點最短路徑之和的差異來確定信息在網(wǎng)絡(luò)中傳播速度的快慢的。節(jié)點的接近度為節(jié)點到其它所有節(jié)點距離之和的倒數(shù)。節(jié)點i的接近度越大，表明節(jié)點越居于網(wǎng)絡(luò)的中心，它在網(wǎng)絡(luò)中就越重要。

(2)

式中，d(pi,pk)表示以pi為起點pk為終點的路徑所包含的邊的數(shù)量。

1.3介數(shù)(Betweenness)

節(jié)點的介數(shù)為經(jīng)過該節(jié)點的最短路徑數(shù)量，節(jié)點i的介數(shù)越大，說明該節(jié)點在網(wǎng)絡(luò)中越重要。

(3)

1.4特征向量(Eigenvector centrality)

特征向量闡述了一個節(jié)點的重要性不僅與自己的度有關(guān)，而且與鄰居節(jié)點的重要性有關(guān)，公式為

(4)

式中，xi為節(jié)點i的重要性度量值；aij為鄰接矩陣中的元素；c為常數(shù)。

2　綜合性評價指標(biāo)的建立

節(jié)點的度中心性、接近度、介數(shù)和特征向量都為單一性評價指標(biāo)，每一種指標(biāo)都有其局限性。度中心性排序算法的結(jié)果比較粗糙，接近度排序算法在很大程度上都依賴于網(wǎng)絡(luò)的拓?fù)浣Y(jié)構(gòu)，介數(shù)排序算法的時間復(fù)雜度很高且對于多數(shù)處于邊緣的節(jié)點無法判斷其重要性。因此，首先提出了一種結(jié)合節(jié)點的度中心性、接近度、介數(shù)和特征向量的綜合性評價指標(biāo)。

2.1綜合性評價指標(biāo)的建立過程

步驟一：構(gòu)造指標(biāo)矩陣。

假設(shè)有n個樣本，對于4種單一性的評價指標(biāo)，先構(gòu)成一個n×4的數(shù)據(jù)指標(biāo)矩陣

(5)

步驟二：單一評價指標(biāo)的主成分分析。

主成分分析(Principal Component Analysis，PCA)是一種常用的基于變量協(xié)方差矩陣對信息進行處理、壓縮和抽取的有效方法。

基本步驟如下：

(1)對原始指標(biāo)數(shù)據(jù)做標(biāo)準(zhǔn)化處理，采集p維隨機向量x=(x1,x2,…,xp)T(文中p取為4)，n個樣本xi=(xi1，xi2，…，xip)T,i=1,2,…,n,n>p,構(gòu)造樣本陣，對樣本陣元進行如下標(biāo)準(zhǔn)化變換，獲得標(biāo)準(zhǔn)化矩陣Z

(6)

(2)由標(biāo)準(zhǔn)化矩陣Z求相關(guān)系數(shù)矩陣

(7)

(3)計算特征值與特征向量。

(4)計算主成分貢獻率及累計貢獻率。

一般取累計貢獻率達85%～95%的特征值，λ1,λ2,…λm所對應(yīng)的第1、第2、…第m(m

(5)計算主成分載荷

(8)

(6)計算主成分得分

(9)

3　算法描述與分析

算法的主要思想：根據(jù)綜合性評價指標(biāo)尋找種子節(jié)點，根據(jù)種子節(jié)點進行廣度優(yōu)先搜索策略進行社團挖掘[6]，最后，解決重疊節(jié)點的歸屬問題。算法分為兩個階段：(1) 根據(jù)綜合性評價指標(biāo)確定種子節(jié)點，然后挖掘種子節(jié)點所在社團的結(jié)構(gòu)，描述如算法1；(2)解決重疊節(jié)點的歸屬問題，描述如算法2。

算法1：以種子節(jié)點為社團中心的社團挖掘算法。

輸入：無權(quán)無向網(wǎng)絡(luò)G(V,E)；

輸出：社團結(jié)構(gòu)集合S；

初始化：社團、集合S初始化為空集。

Step 1:根據(jù)綜合性評價指標(biāo)尋找種子節(jié)點。

根據(jù)綜合性評價指標(biāo)計算網(wǎng)絡(luò)G中每個節(jié)點x的指標(biāo)值Z(x)，將Z(x)最大的節(jié)點vi作為種子節(jié)點，將種子節(jié)點加入社團C中。

Step 2:根據(jù)種子節(jié)點進行廣度優(yōu)先搜索策略進行社團挖掘。

(1) 計算新加入社團C內(nèi)節(jié)點的鄰居節(jié)點集X。

If(X=null)

將社團C加入集合S中，在網(wǎng)絡(luò)G中刪除社團C內(nèi)的節(jié)點，goto4)

Else

將vi的鄰居節(jié)點集X加入社團C中

(2)計算X的鄰居節(jié)點集。

If (X=null)

將社團C加入集合S中同時在網(wǎng)絡(luò)G中刪除社團C內(nèi)的節(jié)點，goto4)

Else

IfZ(X)>Z(T)

計算T的鄰居節(jié)點集W

IfZ(X)>max(Z(W))

將T加入X所在的社團C內(nèi)

(3)對新加入社團C內(nèi)的節(jié)點goto 2，直至新加入的節(jié)點的指標(biāo)值小于其任何一鄰居節(jié)點的指標(biāo)值，將社團C加入集合S中，同時在網(wǎng)絡(luò)G中刪除社團C內(nèi)的節(jié)點。

(4)判斷網(wǎng)絡(luò)G中是否還有剩余節(jié)點。若沒有，完成社團劃分。否則，goto Step1。

算法2：解決重疊節(jié)點的歸屬問題。

輸入：從算法1得到的社團結(jié)構(gòu)集合S；

輸出：社團結(jié)構(gòu)集合U；

初始化：社團結(jié)構(gòu)集合U初始化為null。

Step 1: 從集合S(C1,C2，…，Ck)中依次選取集合S的社團Ci(i=1,2,…，k)；

Step2:If(集合S中只有一個社團Ci)。

將Ci加入集合U中，在集合S中刪除社團Ci，goto 輸出

Else

Ci與其它社團依次比較是否有重疊節(jié)點

If (無重疊節(jié)點)

將Ci加入集合U中，在集合S中刪除社團Ci，goto Step 1

Else

按序找出與Ci有重疊節(jié)點的社團，比較重疊節(jié)點集T與社團Ci、Cj的連邊數(shù)E(T,Ci)，E(T,Cj)

{

If (E(T,Ci)>E(T,Cj))

T屬于社團Ci

If(E(T,Ci)

T屬于社團Cj

If(E(T,Ci)=E(T,Cj))

T屬于對它有較強影響力的社團

}

將Ci加入集合U中，在集合S中刪除社團Ci，gotoStep1。

3.1算法的時間復(fù)雜度分析

綜合性評價指標(biāo)中構(gòu)造矩陣使用介數(shù)和接近度，需計算任意兩節(jié)點間的最短路徑，使用Floyd算法求解最短路徑，因此復(fù)雜度為O(n3)，使用主成分分析時間復(fù)雜度為O(n3)，因此，構(gòu)造綜合性評價指標(biāo)所需的時間復(fù)雜度為O(n3)。在算法1中反復(fù)地比較節(jié)點間的綜合性評價指標(biāo)值，時間復(fù)雜度為，在算法2中解決重疊節(jié)點的歸屬問題，時間復(fù)雜度小于O(n)。所以本文算法的時間復(fù)雜度為O(n3)。

4　實驗結(jié)果與分析

4.1綜合性評價指標(biāo)的驗證

采用ARPT網(wǎng)絡(luò)驗證度中心性、接近度、介數(shù)、特征向量和綜合性評價指標(biāo)的有效性，結(jié)果如圖1、圖2所示。

圖1　ARPT網(wǎng)絡(luò)拓?fù)鋱D

圖2　節(jié)點的評價指標(biāo)得分比較

采用上述5種指標(biāo)分別得到ARPT網(wǎng)節(jié)點重要程度排序，刪除前4個重要節(jié)點后看連通的子圖數(shù)來判斷該評價指標(biāo)的優(yōu)劣。連通子圖的數(shù)量越多說明刪除的節(jié)點越重要。

度中心性評價指標(biāo)刪除前4個重要節(jié)點(2,3,14,6)后，ARPT網(wǎng)分為5個連通子圖。如圖3所示。

接近度評價指標(biāo)刪除前4個重要節(jié)點(3,19,12,18)后，ARPT網(wǎng)分為2個連通子圖。如圖4所示。

圖3　度中心性評價指標(biāo)的連通子圖

圖4　接近度評價指標(biāo)的連通子圖

介數(shù)評價指標(biāo)刪除前4個重要節(jié)點(3,12,6,4)后，ARPT網(wǎng)分為4個連通子圖。如圖5所示。

特征向量評價指標(biāo)刪除前4個重要節(jié)點(2,15,14,3)后，ARPT網(wǎng)分為4個連通子圖。如圖6所示。

圖5　介數(shù)評價指標(biāo)的連通子圖

圖6　特征向量評價指標(biāo)的連通子圖

綜合性評價指標(biāo)刪除前4個重要節(jié)點(3,2,14,12)后，ARPT網(wǎng)分為5個連通子圖。如圖7所示。

由分析得出度中心性評價指標(biāo)和綜合性評價指標(biāo)刪除重要節(jié)點后得到的連通子圖數(shù)較多，在度中心性評價指標(biāo)中2，3，14節(jié)點的得分都為0.2，因此不能判斷哪個節(jié)點更重要，而在綜合性評價指標(biāo)中2，3，14節(jié)點的得分分別為0.234 5，0.273 9，0.223 2。所以提出的綜合性評價指標(biāo)找出的重要節(jié)點準(zhǔn)確性較高。

4.2社團劃分結(jié)果

4.2.1Zachary網(wǎng)絡(luò)

Zachary網(wǎng)絡(luò)[7]是社會學(xué)家Zachary在1970—1972年間對其觀察和研究的空手道俱樂部中成員的社會關(guān)系構(gòu)建的一個社會網(wǎng)絡(luò)，如圖8所示。網(wǎng)絡(luò)含有34個節(jié)點和78條邊，它們分別代表俱樂部成員和成員之間的社會關(guān)系。在觀察期間，俱樂部主管和校長對是否需要提高收費標(biāo)準(zhǔn)的問題意見不一致，俱樂部分成了兩個小俱樂部，主管和校長分別是這兩個小俱樂部的核心人物。圖8為Zachary基準(zhǔn)網(wǎng)絡(luò)，圓圈節(jié)點表示以主管為核心的俱樂部，方形表示以校長為核心的俱樂部網(wǎng)絡(luò)。

圖7　綜合性評價指標(biāo)的連通子圖

圖8　Zachary網(wǎng)絡(luò)實際社團結(jié)構(gòu)

將本文算法用于Zachary空手道俱樂部網(wǎng)絡(luò)，得到的社團結(jié)構(gòu)與實際完全一致。

4.2.2Football網(wǎng)絡(luò)

該網(wǎng)絡(luò)表示的是美國大學(xué)生足球聯(lián)賽[3]2000年第一季度的比賽日程。網(wǎng)絡(luò)中有115個節(jié)點613 條邊，其中節(jié)點代表由學(xué)校名字命名的足球隊，連邊表示它們之間的規(guī)則季度賽。這些足球隊被分成12個聯(lián)盟，每個聯(lián)盟包含5到13個足球隊，同一個聯(lián)盟中的球隊比賽比不同聯(lián)盟的球隊比賽更頻繁。實際聯(lián)盟劃分如圖9所示，從上到下從左到右社團編號依次為：1，2，3，…，12。

將本文算法對Football網(wǎng)絡(luò)進行分析，得到的社團結(jié)構(gòu)如圖10。

圖9　Football網(wǎng)絡(luò)實際社團結(jié)構(gòu)

圖10　本文算法對Football網(wǎng)絡(luò)的實驗結(jié)果

由劃分結(jié)果可知社團1完全包含實際聯(lián)盟1。社團2完全包含實際聯(lián)盟2。社團3和4完全包含實際聯(lián)盟3。社團5和6完全包含實際聯(lián)盟4。除節(jié)點79外，社團7完全包含實際聯(lián)盟5。社團9和10完全包含實際聯(lián)盟7。社團11和12完全包含實際聯(lián)盟8。社團13完全包含實際聯(lián)盟9。除節(jié)點29和59外，社團14完全包含實際聯(lián)盟10。除111和113節(jié)點外，社團17完全包含實際聯(lián)盟12。將較小節(jié)點數(shù)記為錯誤節(jié)點數(shù)，統(tǒng)計錯誤節(jié)點數(shù)為11。

4.3與譜方法比較

為了表征社團劃分效果的好壞主要用到3個性能指標(biāo)[7]：

(1) 正確率(Correct rate,CR)，定義為

(10)

式中，n表示為正確劃分的社團個數(shù)；N是整個網(wǎng)絡(luò)中包含的節(jié)點總數(shù)。

(2)聚類準(zhǔn)確率(ClusteringAccuracy,CA是指被正確劃分的節(jié)點數(shù)占總節(jié)點數(shù)的比例)，定義為

(11)

式中，nt表示被正確劃分到第t個社團的節(jié)點數(shù)；N是整個網(wǎng)絡(luò)中包含的節(jié)點總數(shù)。

(3)RandIndex指標(biāo)(RI，用于衡量劃分結(jié)果所得社團中節(jié)點與實際社團中節(jié)點的一致性)。定義為

(12)

式中，n00表示節(jié)點對中，屬于不同實際社團，同時被劃分到不同社團中的節(jié)點對個數(shù)；n11表示節(jié)點對中，屬于同一社團，同時被劃分到相同社團的節(jié)點對個數(shù)；N是整個網(wǎng)絡(luò)的節(jié)點總數(shù)。

將提出的算法與基于Laplace矩陣的譜方法和基于Normal矩陣的譜方法[8]作性能比較，如表1、表2所示。

表1　在Zachary’s karate network網(wǎng)絡(luò)上3種算法的性能對比

表2　在American college football network網(wǎng)絡(luò)上3種算法的性能對比

由表1、表2可知，所提出的算法比基于Laplace、Normal矩陣的譜方法在CR，CA和RI性能指標(biāo)上都有所提高。對于性能指標(biāo)CR：在Zachary網(wǎng)絡(luò)上，本文算法比基于Laplace、Normal矩陣的譜方法提高了3.03%,在Football網(wǎng)絡(luò)上，本文算法與基于Laplace矩陣的譜方法相等，比基于Normal矩陣的譜方法提高了6.11%。對于性能指標(biāo)CA：在Zachary網(wǎng)絡(luò)上，本文算法比基于Laplace、Normal矩陣的譜方法提高了3.03%,在Football網(wǎng)絡(luò)上，本文算法比基于Laplace、Normal矩陣的譜方法分別提高了235.97%、147.41%。對于性能指標(biāo)RI：在Zachary網(wǎng)絡(luò)上，本文算法比基于Laplace、Normal矩陣的譜方法提高了6.23%,在Football網(wǎng)絡(luò)上，本文算法比基于Laplace、Normal矩陣的譜方法分別提高了64.67%、4 142.20%。

5　結(jié)語

本文提出一種基于種子節(jié)點的社團挖掘算法，該算法首先給出了一種綜合性評價指標(biāo)尋找社團的種子節(jié)點，對種子節(jié)點進行廣度優(yōu)先搜索策略挖掘社團結(jié)構(gòu)，算法思想簡單同時提高了挖掘出的社團質(zhì)量。從實驗仿真分析可以看出，該算法與基于Laplace、Normal矩陣的譜方法相比具有較高的性能。進一步的工作：將該算法用于生物網(wǎng)絡(luò)中的蛋白質(zhì)相互作用網(wǎng)絡(luò)(PPI)。

[1]范超翔,范磊.基于用戶節(jié)點相似度的局部社團挖掘[D].上海：上海交通大學(xué)，2014.

[2]晉建志.復(fù)雜網(wǎng)絡(luò)基于節(jié)點重要性的社團探測及社團演化模型研究[D].武漢：華中師范大學(xué)，2014.

[3]Murray S,Mark W Knotty.Centrality finding the connective core of a complex network[J].PLoS ONE,2012,7(5):e36579.

[4]Brin S,Page L.The anatomy of a large-scale hyper textual web search engine[J].Computer Networks and ISDN Systems,1998,30(1-7):107-117.

[5]Kleinberg J M.Authoritative sources in a hyperlinked environment[J].Journal of the ACM,1999,46(5):604-632.

[6]易秀雙,韓也挺,王興偉.一種基于節(jié)點影響力的局部社團發(fā)現(xiàn)算法[J].小型微型計算機系統(tǒng),2013, 34(9):975-980.

[7]賈寧寧,封筠.復(fù)雜網(wǎng)絡(luò)中社團發(fā)現(xiàn)算法研究及應(yīng)用[D].石家莊：石家莊鐵道大學(xué)，2014.

[8]丁連紅,時鵬.網(wǎng)絡(luò)社區(qū)發(fā)現(xiàn)[M].北京:化學(xué)工業(yè)出版社,2008.

Study on Community Mining Algorithm Based on Seed Node for Non Overlapping

Zhang Xiaofen,Feng Jun,Jia Ningning

(School of Information Science and Technology,Shijiazhuang Tiedao University,Shijiazhuang 050043,China)

A novel algorithm based on seed node for community mining is proposed in this paper. Firstly, a comprehensive evaluating index for node importance is extracted from single indicators by using principal component analysis. Node with the maximum index value is selected as a seed node and breadth-first search operation for seed node is executed. Nodes with greater index value affect smaller nodes gradually and the community structure where seed node is located is gotten.Then, node is chosen with the largest index value from the outside known community structure.The above process is repeated and the initial community set is gotten.For the overlapping nodes between communities, Overlapping nodes and the number of edges between two communities is used to solve the attribution problem. Finally, the ultimate community structure of the entire network is established.The experimental results for benchmark networks show that comprehensive evaluating index is more suitable for node importance than single ones. Compared with spectral method, the performance of the presented algorithm based on seed node is higher.

community mining;seed node;comprehensive evaluating index for node importance;complex networks; non overlapping community

2015-09-28責(zé)任編輯:車軒玉DOI:10.13319/j.cnki.sjztddxxbzrb.2016.03.17

河北省自然科學(xué)基金(F2013210109)

張曉芬(1989-), 女,碩士研究生,主要從事復(fù)雜網(wǎng)絡(luò)的研究。E-mail: 1270291637@qq.com

TP393

A

2095-0373(2016)03-0093-08

張曉芬，封筠，賈寧寧.種子節(jié)點非重疊社團挖掘算法研究[J].石家莊鐵道大學(xué)學(xué)報:自然科學(xué)版,2016,29(3):93-100.