種子節(jié)點(diǎn)非重疊社團(tuán)挖掘算法研究

張曉芬，　封　筠，　賈寧寧

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

?

種子節(jié)點(diǎn)非重疊社團(tuán)挖掘算法研究

張曉芬，封筠，賈寧寧

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

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

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

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

1　相關(guān)知識(shí)

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

1.1度中心性(Degree centrality)

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

(1)

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

1.2接近度(Closeness)

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

(2)

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

1.3介數(shù)(Betweenness)

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

(3)

1.4特征向量(Eigenvector centrality)

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

(4)

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

2　綜合性評(píng)價(jià)指標(biāo)的建立

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

2.1綜合性評(píng)價(jià)指標(biāo)的建立過(guò)程

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

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

(5)

步驟二：?jiǎn)我辉u(píng)價(jià)指標(biāo)的主成分分析。

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

基本步驟如下：

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

(6)

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

(7)

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

(4)計(jì)算主成分貢獻(xiàn)率及累計(jì)貢獻(xiàn)率。

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

(5)計(jì)算主成分載荷

(8)

(6)計(jì)算主成分得分

(9)

3　算法描述與分析

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

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

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

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

初始化：社團(tuán)、集合S初始化為空集。

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

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

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

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

If(X=null)

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

Else

將vi的鄰居節(jié)點(diǎn)集X加入社團(tuán)C中

(2)計(jì)算X的鄰居節(jié)點(diǎn)集。

If (X=null)

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

Else

IfZ(X)>Z(T)

計(jì)算T的鄰居節(jié)點(diǎn)集W

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

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

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

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

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

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

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

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

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

Step2:If(集合S中只有一個(gè)社團(tuán)Ci)。

將Ci加入集合U中，在集合S中刪除社團(tuán)Ci，goto 輸出

Else

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

If (無(wú)重疊節(jié)點(diǎn))

將Ci加入集合U中，在集合S中刪除社團(tuán)Ci，goto Step 1

Else

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

{

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

T屬于社團(tuán)Ci

If(E(T,Ci)

T屬于社團(tuán)Cj

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

T屬于對(duì)它有較強(qiáng)影響力的社團(tuán)

}

將Ci加入集合U中，在集合S中刪除社團(tuán)Ci，gotoStep1。

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

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

4　實(shí)驗(yàn)結(jié)果與分析

4.1綜合性評(píng)價(jià)指標(biāo)的驗(yàn)證

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

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

圖2　節(jié)點(diǎn)的評(píng)價(jià)指標(biāo)得分比較

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

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

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

圖3　度中心性評(píng)價(jià)指標(biāo)的連通子圖

圖4　接近度評(píng)價(jià)指標(biāo)的連通子圖

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

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

圖5　介數(shù)評(píng)價(jià)指標(biāo)的連通子圖

圖6　特征向量評(píng)價(jià)指標(biāo)的連通子圖

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

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

4.2社團(tuán)劃分結(jié)果

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

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

圖7　綜合性評(píng)價(jià)指標(biāo)的連通子圖

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

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

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

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

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

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

圖10　本文算法對(duì)Football網(wǎng)絡(luò)的實(shí)驗(yàn)結(jié)果

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

4.3與譜方法比較

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

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

(10)

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

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

(11)

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

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

(12)

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

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

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

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

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

5　結(jié)語(yǔ)

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

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

[2]晉建志.復(fù)雜網(wǎng)絡(luò)基于節(jié)點(diǎn)重要性的社團(tuán)探測(cè)及社團(tuán)演化模型研究[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é)點(diǎn)影響力的局部社團(tuán)發(fā)現(xiàn)算法[J].小型微型計(jì)算機(jī)系統(tǒng),2013, 34(9):975-980.

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

[8]丁連紅,時(shí)鵬.網(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é)點(diǎn)非重疊社團(tuán)挖掘算法研究[J].石家莊鐵道大學(xué)學(xué)報(bào):自然科學(xué)版,2016,29(3):93-100.