趙文濤 趙好好 孟令軍

1(河南理工大學(xué)計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院 河南 焦作 454000)2(河南省普通高等學(xué)校礦山信息化研究重點(diǎn)實(shí)驗(yàn)室 河南 焦作 454000)

基于相關(guān)拓?fù)鋭?shì)的社團(tuán)發(fā)現(xiàn)算法

趙文濤1,2趙好好1孟令軍1

1(河南理工大學(xué)計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院 河南 焦作 454000)2(河南省普通高等學(xué)校礦山信息化研究重點(diǎn)實(shí)驗(yàn)室 河南 焦作 454000)

針對(duì)傳統(tǒng)算法社團(tuán)劃分精度較低以及模塊度函數(shù)分辨率低的問(wèn)題，提出一種基于相關(guān)拓?fù)鋭?shì)的社團(tuán)發(fā)現(xiàn)算法，簡(jiǎn)稱BITP算法。該算法考慮節(jié)點(diǎn)的相關(guān)性因素，引入相關(guān)拓?fù)鋭?shì)來(lái)衡量節(jié)點(diǎn)的影響力，尋找出其中的極大勢(shì)值點(diǎn)，采用標(biāo)簽傳播的思想對(duì)社團(tuán)的規(guī)模進(jìn)行控制。在人工合成網(wǎng)絡(luò)和真實(shí)網(wǎng)絡(luò)上，與多種算法進(jìn)行實(shí)驗(yàn)對(duì)比，結(jié)果表明該算法多次運(yùn)行結(jié)果相對(duì)穩(wěn)定且社團(tuán)劃分精度較高。算法時(shí)間復(fù)雜度為O(n)，且不需要先驗(yàn)知識(shí)，更適合大規(guī)模復(fù)雜網(wǎng)絡(luò)上的社團(tuán)結(jié)構(gòu)挖掘。

社團(tuán)結(jié)構(gòu) 復(fù)雜網(wǎng)絡(luò) 相關(guān)拓?fù)鋭?shì) 標(biāo)簽傳播

0 引 言

復(fù)雜網(wǎng)絡(luò)的結(jié)構(gòu)特性是現(xiàn)實(shí)系統(tǒng)中個(gè)體之間復(fù)雜關(guān)系的真實(shí)表現(xiàn)。大量實(shí)證研究結(jié)果表明，真實(shí)網(wǎng)絡(luò)結(jié)構(gòu)不僅普遍具有小世界和無(wú)標(biāo)度等特性，而且呈現(xiàn)出明顯的社團(tuán)結(jié)構(gòu)[1-3]。社團(tuán)結(jié)構(gòu)是指網(wǎng)絡(luò)中的節(jié)點(diǎn)根據(jù)某種共同屬性，子集合內(nèi)部節(jié)點(diǎn)之間的連接相對(duì)緊湊，子集合之間節(jié)點(diǎn)之間的連接相對(duì)稀疏[2]。

Girvan和Newman最先提出了基于邊界數(shù)的社團(tuán)發(fā)現(xiàn)算法，稱為GN算法[1]，但算法效率和社團(tuán)劃分精度較低。隨后，Newman等人又引入模塊度函數(shù)[3]來(lái)對(duì)社團(tuán)劃分質(zhì)量進(jìn)行評(píng)價(jià)。之后，人們采用多種方法來(lái)對(duì)模塊度進(jìn)行優(yōu)化以達(dá)到更好的社團(tuán)劃分效果，例如FASTGREEDY算法[4]、MULTILEVEL算法[5]等。然而近期研究表明，模塊度定義存在分辨率的限制，不適合劃分社團(tuán)規(guī)模大小不一的網(wǎng)絡(luò)結(jié)構(gòu)。而真實(shí)網(wǎng)絡(luò)結(jié)構(gòu)通常存在異質(zhì)性，社團(tuán)大小不均勻，模塊度優(yōu)化方法很難保證社團(tuán)結(jié)構(gòu)挖掘的準(zhǔn)確性。另外，其他一些快速算法雖然效率很高，卻是以損失精度為代價(jià)，諸如LPA算法[6]、WALKTRAP算法[7]、LEC算法[8]、SPINGLASS算法[9]、INFOMAP算法[10]等。

鑒于模塊度定義存在的缺陷，為了有效揭示網(wǎng)絡(luò)內(nèi)在的社團(tuán)結(jié)構(gòu)，淦文燕等[11]提出了一種基于拓?fù)鋭?shì)的網(wǎng)絡(luò)社團(tuán)發(fā)現(xiàn)算法，將數(shù)據(jù)場(chǎng)中拓?fù)鋭?shì)的概念引入至社團(tuán)發(fā)現(xiàn)。隨后，張健沛[12]、石立新[13]、張桂杰[14]等人基于拓?fù)鋭?shì)并結(jié)合其他方法進(jìn)行相關(guān)算法的優(yōu)化，驗(yàn)證其各自算法的有效性。

這些基于拓?fù)鋭?shì)的社團(tuán)發(fā)現(xiàn)算法均是基于傳統(tǒng)拓?fù)鋭?shì)函數(shù)，本文提出了一種基于相關(guān)拓?fù)鋭?shì)的社團(tuán)發(fā)現(xiàn)算法(簡(jiǎn)稱BITP算法)。在傳統(tǒng)拓?fù)鋭?shì)的基礎(chǔ)上，結(jié)合節(jié)點(diǎn)之間的相關(guān)性定義，引入相關(guān)拓?fù)鋭?shì)的概念。該方法不需要先驗(yàn)知識(shí)，通過(guò)相關(guān)拓?fù)鋭?shì)來(lái)衡量網(wǎng)絡(luò)中節(jié)點(diǎn)的影響力，采用標(biāo)簽傳播的方法進(jìn)行社團(tuán)結(jié)構(gòu)的挖掘，算法相對(duì)穩(wěn)定，社團(tuán)劃分精度較高。

1 相關(guān)概念

1.1 相關(guān)性

文獻(xiàn)[15]中相關(guān)性定義了無(wú)向無(wú)權(quán)網(wǎng)絡(luò)中用于衡量節(jié)點(diǎn)之間關(guān)系的緊密度，具體定義如下：

(1)

1.2 拓?fù)鋭?shì)

物理學(xué)中用場(chǎng)來(lái)描述物質(zhì)粒子間的相互作用。物理場(chǎng)是其中的一種，用來(lái)描述拓?fù)鋱?chǎng)的標(biāo)量勢(shì)函數(shù)。勢(shì)場(chǎng)分為長(zhǎng)程場(chǎng)和短程場(chǎng)。在長(zhǎng)程場(chǎng)中，勢(shì)值的大小與距離成反比，在距離場(chǎng)源很遠(yuǎn)的地方仍然存在著場(chǎng)力的作用(如重力勢(shì)場(chǎng)和靜電勢(shì)場(chǎng))。而在短程場(chǎng)中，中心勢(shì)場(chǎng)的勢(shì)值會(huì)隨著距離的增大而急劇下降，相應(yīng)的場(chǎng)力也會(huì)很快衰減至零。受物理場(chǎng)思想的啟發(fā)，諸多研究?jī)A向于采用代表短程場(chǎng)且具有良好數(shù)學(xué)性質(zhì)的高斯勢(shì)函數(shù)描述節(jié)點(diǎn)間的相互作用。

給定網(wǎng)絡(luò)G=(V,E)，其中，V={1,2,…,n}為節(jié)點(diǎn)的非空有限集。根據(jù)拓?fù)鋭?shì)場(chǎng)中勢(shì)函數(shù)定義[16]，任意節(jié)點(diǎn)i∈V的拓?fù)鋭?shì)可表示為：

(2)

其中，dij表示節(jié)點(diǎn)i與j之間的最短路徑長(zhǎng)度；影響因子σ用于控制每個(gè)節(jié)點(diǎn)的影響范圍；mi表示節(jié)點(diǎn)i(i=1,2,…,n)的固有屬性(如質(zhì)量等)。

傳統(tǒng)的拓?fù)鋭?shì)計(jì)算[11-14]中將每個(gè)節(jié)點(diǎn)視為均質(zhì)的，拓?fù)鋭?shì)TP(TopologicalPotential)計(jì)算式可表達(dá)為：

(3)

1.3 相關(guān)拓?fù)鋭?shì)

節(jié)點(diǎn)的相關(guān)性從網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)的角度出發(fā)，充分考慮節(jié)點(diǎn)之間連邊的數(shù)目對(duì)節(jié)點(diǎn)之間關(guān)系的影響。給定網(wǎng)絡(luò)，節(jié)點(diǎn)之間的相關(guān)性是固定的、不可改變的，故可以將其視為網(wǎng)絡(luò)中節(jié)點(diǎn)的固有屬性。

式(3)中傳統(tǒng)的拓?fù)鋭?shì)計(jì)算方法忽略了節(jié)點(diǎn)固有屬性對(duì)節(jié)點(diǎn)拓?fù)鋭?shì)的影響作用，而實(shí)際復(fù)雜網(wǎng)絡(luò)中不同節(jié)點(diǎn)對(duì)單個(gè)節(jié)點(diǎn)影響程度不同，即相關(guān)程度不同。故本文考慮節(jié)點(diǎn)之間的相關(guān)性，提出節(jié)點(diǎn)的相關(guān)拓?fù)鋭?shì)函數(shù)，表示方式如下：

(4)

其中，P(i,j)為節(jié)點(diǎn)相關(guān)矩陣P中第i行第j列的元素值，即節(jié)點(diǎn)i與節(jié)點(diǎn)j的相關(guān)性。

勢(shì)函數(shù)中影響因子σ用來(lái)控制節(jié)點(diǎn)的影響力跳數(shù)，節(jié)點(diǎn)的影響力跳數(shù)定義為：

(5)

考慮節(jié)點(diǎn)的影響力跳數(shù)，節(jié)點(diǎn)的相關(guān)拓?fù)鋭?shì)ITP(InterrelatedTopologicalPotential)可由式(6)推出：

(6)

在無(wú)向無(wú)權(quán)網(wǎng)絡(luò)中(以Karate網(wǎng)絡(luò)為例)，計(jì)算所有節(jié)點(diǎn)的TP和ITP指標(biāo)，并畫(huà)出其分布，如圖1和圖2所示。網(wǎng)絡(luò)中節(jié)點(diǎn)ITP指標(biāo)呈局部聚集狀態(tài)，社團(tuán)的區(qū)分效果要比TP指標(biāo)更加明顯。分別將采用TP指標(biāo)和ITP指標(biāo)的社團(tuán)發(fā)現(xiàn)算法簡(jiǎn)稱為BTP算法和BITP算法，后面將對(duì)這兩種算法作對(duì)比分析。

圖1 TP指標(biāo)

圖2 ITP指標(biāo)

2 算法描述

本文考慮網(wǎng)絡(luò)中節(jié)點(diǎn)之間的相關(guān)性，引入節(jié)點(diǎn)的相關(guān)拓?fù)鋭?shì)。算法采用貪婪局部搜索的方法搜索網(wǎng)絡(luò)中的局部極大勢(shì)值節(jié)點(diǎn)，初始化極大值節(jié)點(diǎn)的標(biāo)簽為各自的節(jié)點(diǎn)標(biāo)號(hào)，然后采用標(biāo)簽傳播的方法更新其余節(jié)點(diǎn)的標(biāo)簽。

在傳統(tǒng)的LPA算法[6]中，節(jié)點(diǎn)標(biāo)簽傳播規(guī)則分為兩步：第一步，將節(jié)點(diǎn)i的標(biāo)簽更新為其鄰居節(jié)點(diǎn)中標(biāo)簽數(shù)目最多的標(biāo)簽；第二步，若其鄰居節(jié)點(diǎn)中標(biāo)簽數(shù)目最多的標(biāo)簽有多個(gè)時(shí)，則隨機(jī)選擇其中一個(gè)作為節(jié)點(diǎn)i的標(biāo)簽。這樣的隨機(jī)操作容易造成算法的不穩(wěn)定，社團(tuán)劃分結(jié)果不夠準(zhǔn)確。因此，本文的標(biāo)簽傳播規(guī)則為：

Step1 將節(jié)點(diǎn)i的標(biāo)簽更新為其鄰居節(jié)點(diǎn)中標(biāo)簽數(shù)目最多的標(biāo)簽；

Step2 若其鄰居節(jié)點(diǎn)中標(biāo)簽數(shù)目最多的標(biāo)簽有多個(gè)時(shí)，選擇其中相關(guān)拓?fù)鋭?shì)最大的作為節(jié)點(diǎn)i的標(biāo)簽。

BITP算法

輸入：無(wú)向無(wú)權(quán)網(wǎng)絡(luò)G=(V,E)，其中，V={1,2,…,n}。

輸出：局部社團(tuán)C={C1,C2,…,Ck}，其中k為局部社團(tuán)數(shù)目。

算法步驟：

(1) 計(jì)算所有節(jié)點(diǎn)相關(guān)拓?fù)鋭?shì)；

(2) 采用貪婪局部搜索的方法尋找網(wǎng)絡(luò)中的局部極大勢(shì)值節(jié)點(diǎn)；

(3) 將這些極值點(diǎn)的標(biāo)簽分別初始化為它們各自的節(jié)點(diǎn)標(biāo)號(hào)，網(wǎng)絡(luò)中的其他節(jié)點(diǎn)的標(biāo)簽初始化為0。

(4) 按照上述標(biāo)簽傳播規(guī)則依次對(duì)網(wǎng)絡(luò)中其余節(jié)點(diǎn)進(jìn)行標(biāo)簽更新。

(5) 標(biāo)簽相同的節(jié)點(diǎn)同屬于同一個(gè)局部社團(tuán)，輸出局部社團(tuán){C1,C2,…,Ck}。

在BITP算法中，計(jì)算節(jié)點(diǎn)的相關(guān)拓?fù)鋭?shì)的時(shí)間復(fù)雜度為O(2n)，n為網(wǎng)絡(luò)中節(jié)點(diǎn)數(shù)；貪婪局部搜索極大值的時(shí)間復(fù)雜度為O(n)，標(biāo)簽更新的時(shí)間復(fù)雜度為O(n)。本文算法總的時(shí)間復(fù)雜度為O(2n+n+n)=O(n)。

3 實(shí)驗(yàn)評(píng)價(jià)標(biāo)準(zhǔn)

3.1 模塊度指標(biāo)

模塊度[3]用來(lái)比較社團(tuán)劃分結(jié)果與隨機(jī)圖之間的差異。定義如下：

(7)

其中，m為網(wǎng)絡(luò)中節(jié)點(diǎn)的數(shù)目；∑in表示一個(gè)社團(tuán)內(nèi)部的連邊數(shù)目；∑tot表示一個(gè)社團(tuán)內(nèi)部所有節(jié)點(diǎn)度的總和。

3.2NMI指標(biāo)

標(biāo)準(zhǔn)化互信息NMI[17](NormalizedMutualInformation)常用來(lái)衡量社團(tuán)劃分結(jié)果與真實(shí)社團(tuán)結(jié)構(gòu)之間的相近程度。定義如下：

(8)

其中，A、B分別為兩個(gè)不同的局部社團(tuán)所代表的向量；I(A,B)是向量A和向量B的互信息；H(A)是向量A的信息熵；H(B)是向量B的信息熵。NMI的取值為[0,1]，NMI值越大說(shuō)明社團(tuán)劃分結(jié)果與真實(shí)社團(tuán)結(jié)構(gòu)越相似，越小則反之。

3.3VI指標(biāo)

信息差異VI[18](VariationofInformation)常用來(lái)衡量社團(tuán)劃分結(jié)果與真實(shí)社團(tuán)結(jié)構(gòu)之間的差異。定義如下：

VI=H(A|B)+H(B|A)

(9)

其中，A、B分別為兩個(gè)不同的局部社團(tuán)所代表的向量；H(A|B)是向量A對(duì)于向量B的條件熵；H(B|A)是向量B對(duì)于向量A的條件熵。VI的取值為[0,log(m)]，m為網(wǎng)絡(luò)中節(jié)點(diǎn)的數(shù)目。VI值越小說(shuō)明社團(tuán)劃分結(jié)果與真實(shí)社團(tuán)結(jié)構(gòu)差異越小，越大則反之。

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

為了驗(yàn)證BITP算法的準(zhǔn)確性與有效性，分別在人工合成網(wǎng)絡(luò)和真實(shí)網(wǎng)絡(luò)上與多種算法進(jìn)行實(shí)驗(yàn)對(duì)比。

4.1 人工合成網(wǎng)絡(luò)

實(shí)驗(yàn)采用LFR(Lancichinetti-Fortunato-Radicchi)[19]基準(zhǔn)網(wǎng)絡(luò)來(lái)生成人工合成網(wǎng)絡(luò)。網(wǎng)絡(luò)中的節(jié)點(diǎn)度和社團(tuán)大小均符合冪律分布。混合參數(shù)μ用來(lái)控制局部社團(tuán)內(nèi)部連接數(shù)與外部連接的比例，取值為[0,1]。其值越小說(shuō)明內(nèi)部連接比較緊密，社團(tuán)結(jié)構(gòu)較強(qiáng)；反之，社團(tuán)結(jié)構(gòu)較弱。本文僅取其值0.1～0.8。根據(jù)μ取值不同對(duì)應(yīng)生成8個(gè)不同的人工合成網(wǎng)絡(luò)，并分別在這些網(wǎng)絡(luò)上多次運(yùn)行GN、CNM、LPA、WALKTRAP、LEC、SPINGLASS、INFOMAP、MULTILEVEL、BTP、BITP等十種社團(tuán)發(fā)現(xiàn)算法。人工合成網(wǎng)絡(luò)具體參數(shù)設(shè)置分別如表1所示。

表1 人工網(wǎng)絡(luò)參數(shù)設(shè)置

為了比較這些算法社團(tuán)劃分結(jié)果與真實(shí)網(wǎng)絡(luò)結(jié)構(gòu)之間差異，分別記錄它們劃分結(jié)果的模塊度指標(biāo)、NMI指標(biāo)和VI指標(biāo)，這些指標(biāo)通過(guò)算法運(yùn)行100次求算術(shù)平均值而來(lái)。圖3反映了十種算法在人工網(wǎng)絡(luò)上劃分結(jié)果的各種指標(biāo)隨μ值變化的對(duì)比情況。

圖3 十種算法在500節(jié)點(diǎn)網(wǎng)絡(luò)上各種指標(biāo)變化曲線圖

總體上，各種算法的模塊度指標(biāo)隨μ值的增大均有所下降。GN、LPA和INFOMAP三種算法尤為明顯，隨μ值增大，模塊度逐漸趨向于零，說(shuō)明這些算法運(yùn)行時(shí)不穩(wěn)定，而其他幾種算法相對(duì)較穩(wěn)定。NMI指標(biāo)和VI指標(biāo)隨μ值的變化，即社團(tuán)結(jié)構(gòu)的不明顯，均呈現(xiàn)出一定程度的波動(dòng)?；谕?fù)鋭?shì)的兩種算法BTP和BITP比其他幾種算法效果好，與真實(shí)網(wǎng)絡(luò)結(jié)構(gòu)更為相近。與BTP算法相比，BITP算法的NMI指標(biāo)較高，VI指標(biāo)較低。這是由于BITP算法考慮到真實(shí)網(wǎng)絡(luò)中節(jié)點(diǎn)的相關(guān)性信息，劃分出來(lái)的社團(tuán)結(jié)構(gòu)要比BTP算法更加合理，與真實(shí)網(wǎng)絡(luò)結(jié)構(gòu)也更為接近，差異也較小。

4.2 真實(shí)網(wǎng)絡(luò)數(shù)據(jù)集

為了進(jìn)一步驗(yàn)證本文算法社團(tuán)劃分的效果，在真實(shí)網(wǎng)絡(luò)數(shù)據(jù)集對(duì)其進(jìn)行測(cè)試，以空手道俱樂(lè)部網(wǎng)絡(luò)[20]和寬吻海豚網(wǎng)絡(luò)[21]為例。

空手道俱樂(lè)部網(wǎng)絡(luò)可表示為G=<34,78>，即網(wǎng)絡(luò)中節(jié)點(diǎn)數(shù)為34、邊的數(shù)目為78。采用BITP算法對(duì)其進(jìn)行社團(tuán)結(jié)構(gòu)挖掘，首先計(jì)算網(wǎng)絡(luò)中所有節(jié)點(diǎn)的相關(guān)拓?fù)鋭?shì)，節(jié)點(diǎn)的相關(guān)拓?fù)鋭?shì)分布如圖4(a)所示。其中，極大勢(shì)值為節(jié)點(diǎn)1和節(jié)點(diǎn)34，分別初始化這兩個(gè)節(jié)點(diǎn)的標(biāo)簽為各自的標(biāo)號(hào)(即標(biāo)簽分別設(shè)為1和34)。然后按照上述標(biāo)簽傳播規(guī)則更新其余節(jié)點(diǎn)的標(biāo)簽。最終社團(tuán)劃分結(jié)果如圖4(b)所示。多次運(yùn)行BITP算法，與真實(shí)網(wǎng)絡(luò)結(jié)構(gòu)相比，均只有節(jié)點(diǎn)3被劃分錯(cuò)誤，準(zhǔn)確率為94.4%，模塊度為0.3600。

圖4 空手道俱樂(lè)部網(wǎng)絡(luò)社團(tuán)結(jié)構(gòu)

寬吻海豚網(wǎng)絡(luò)可表示為G=<62,159>，即網(wǎng)絡(luò)中節(jié)點(diǎn)數(shù)為62、邊的數(shù)目為159。節(jié)點(diǎn)的相關(guān)拓?fù)鋭?shì)分布如圖5(a)所示。極大勢(shì)值為節(jié)點(diǎn)46和節(jié)點(diǎn)58，分別初始化這兩個(gè)節(jié)點(diǎn)的標(biāo)簽為46和58。然后按照上述標(biāo)簽傳播規(guī)則更新其余節(jié)點(diǎn)的標(biāo)簽。最終社團(tuán)劃分結(jié)果如圖5(b)所示。多次運(yùn)行BITP算法，與真實(shí)網(wǎng)絡(luò)結(jié)構(gòu)相比，均只有節(jié)點(diǎn)28和節(jié)點(diǎn)40被劃分錯(cuò)誤，準(zhǔn)確率為93.8%，模塊度為0.3735。

圖5 寬吻海豚網(wǎng)絡(luò)社團(tuán)結(jié)構(gòu)

將BITP算法和其他幾種算法在這兩個(gè)真實(shí)網(wǎng)絡(luò)數(shù)據(jù)集上進(jìn)行社團(tuán)結(jié)構(gòu)挖掘的結(jié)果進(jìn)行對(duì)比分析。表2反映了這幾種算法對(duì)應(yīng)的模塊度指標(biāo)、NMI指標(biāo)和VI指標(biāo)?？梢钥闯觯疚乃惴ㄔ趦蓚€(gè)真實(shí)網(wǎng)絡(luò)數(shù)據(jù)集上的NMI指標(biāo)最高，VI指標(biāo)最低。

表2 幾種算法對(duì)應(yīng)的各種指標(biāo)對(duì)比

5 結(jié) 語(yǔ)

本文提出了一種基于相關(guān)拓?fù)鋭?shì)的社團(tuán)發(fā)現(xiàn)算法。算法將節(jié)點(diǎn)的相關(guān)性引入到拓?fù)鋭?shì)的計(jì)算中，并采用標(biāo)簽傳播的方法控制社團(tuán)規(guī)模。與幾種傳統(tǒng)的社團(tuán)發(fā)現(xiàn)算法在人工合成網(wǎng)絡(luò)和真實(shí)網(wǎng)絡(luò)上進(jìn)行驗(yàn)證，結(jié)果表明本文算法相對(duì)穩(wěn)定且能夠取得較高的社團(tuán)劃分精度。整個(gè)算法時(shí)間復(fù)雜度為O(n)，適合于大規(guī)模復(fù)雜網(wǎng)絡(luò)的社團(tuán)結(jié)構(gòu)挖掘。針對(duì)現(xiàn)有社團(tuán)結(jié)構(gòu)研究大部分針對(duì)無(wú)向無(wú)權(quán)網(wǎng)絡(luò)，下階段考慮將基于拓?fù)鋭?shì)的算法應(yīng)用到加權(quán)網(wǎng)絡(luò)中，并進(jìn)一步提高算法各方面的性能。

[1]GirvanM,NewmanMEJ.Communitystructureinsocialandbiologicalnetworks[J].ProceedingsoftheNationalAcademyofSciencesoftheUnitedStatesofAmerica,2002,99(12):7821-7826.

[2]NewmanMEJ.Detectingcommunitystructureinnetworks[J].TheEuropeanPhysicalJournalB-CondensedMatterandComplexSystems,2004,38(2):321-330.

[3]NewmanMEJ,GirvanM.Findingandevaluatingcommunitystructureinnetworks[J].PhysicalReviewE,2004,69(2):026113.

[4]ClausetA,NewmanMEJ,MooreC.Findingcommunitystructureinverylargenetwork[J].PhysicalReviewE,2004,70(6):066111.

[5]BlondelVD,GuillaumeJL,LambiotteR,etal.Fastunfoldingofcommunitiesinlargenetworks[J].JournalofStatisticalMechanics:TheoryandExperiment,2008(10):P10008.

[6]RaghavanUN,AlbertR,KumaraS.Nearlineartimealgorithmtodetectcommunitystructuresinlarge-scalenetworks[J].PhysicalReviewE,2007,76(3):036106.

[7]PonsP,LatapyM.Computingcommunitiesinlargenetworksusingrandomwalks[C]//Proceedingsofthe20thInternationalSymposiumonComputerandInformationSciences,2005:284-293.

[8]NewmanMEJ.Findingcommunitystructureusingtheeigenvectorsofmatrices[J].PhysicalReviewE,2006,74(3):036104.

[9]GfellerD,DeLRP.Spectralcoarsegrainingandsynchronizationinoscillatornetworks[J].PhysicalReviewLetters,2008,100(17):174104.

[10]RosvallM,BergstromCT.Mapsofrandomwalksoncomplexnetworksrevealcommunitystructure[J].ProceedingsoftheNationalAcademyofSciencesoftheUnitedStatesofAmerica,2008,105(4):1118-1123.

[11] 淦文燕,赫南,李德毅,等.一種基于拓?fù)鋭?shì)的網(wǎng)絡(luò)社區(qū)發(fā)現(xiàn)算法[J].軟件學(xué)報(bào),2009,20(8):2241-2254.

[12] 張健沛,李泓波,楊靜,等.基于拓?fù)鋭?shì)的網(wǎng)絡(luò)社區(qū)節(jié)點(diǎn)重要度排序算法[J].哈爾濱工程大學(xué)學(xué)報(bào),2012,33(6):745-752.

[13] 石立新,張俊星.基于勢(shì)函數(shù)的標(biāo)簽傳播社區(qū)發(fā)現(xiàn)算法[J].計(jì)算機(jī)應(yīng)用,2010,34(3):738-741.

[14] 張桂杰,張健沛,楊靜,等.基于拓?fù)鋭?shì)的局部化重疊社區(qū)識(shí)別[J].吉林大學(xué)學(xué)報(bào):理學(xué)版,2015,53(4):730-738.

[15]ZhangY,WangJ,WangY,etal.Parallelcommunitydetectiononlargenetworkswithpropinquitydynamics[C]//Proceedingsofthe15thACMSIGKDDConferenceonKnowledgeDiscoveryandDataMining,2009:997-1006.

[16]GanWY.Studyontheclusteringproblemindatamining[D].Nanjing:NanjingUniversityofScienceandTechnology,2003.

[17]DanonL,Díaz-GuileraA,DuchJ,etal.Comparingcommunitystructureidentification[J].JournalofStatisticalMechanics:TheoryandExperiment,2005(9):P09008.

[18]Meil?M.Comparingclusteringsbythevariationofinformation[C]//16thAnnualConferenceonLearningTheoryand7thKernelWorkshop,2003:173-187.

[19]LancichinettiA,FortunatoS,RadicchiF.Bechmarkgraphsfortestingcommunitydetectionalgorithms[J].PhysicalReviewE,2008,78(4):046110.

[20]ZacharyWW.Aninformationflowmodelforconflictandfissioninsmallgroups[J].JournalofAnthropologicalResearch,1977,33(4):452-473.

[21]LusseauD,SchneiderK,BoisseauOJ,etal.ThebottlenosedolphincommunityofDoubtfulSoundfeaturesalargeproportionoflong-lastingassociations[J].BehavioralEcologyandSociobiology,2003,54(4):396-405.

COMMUNITY DETECTION ALGORITHM BASED ON INTERRELATED TOPOLOGICAL POTENTIAL

Zhao Wentao1,2Zhao Haohao1Meng Lingjun1

1(SchoolofComputerScienceandTechnology,HenanPolytechnicUniversity,Jiaozuo454000,Henan,China)2(KeyLaboratoryofMineInformationResearchatGeneralUniversitiesinHenanProvince,Jiaozuo454000,Henan,China)

Since the traditional methods obtain low precision in division and low resolution in module function, an algorithm of community detection BITP is proposed based on the interrelated topological potential. The algorithm introduces the interrelated topological potential to evaluate the influence of nodes by considering the correlation factor between nodes. The nodes with extreme potential are searched at first. The sizes of the local communities are controlled by adopting the method of label propagation. The experimental results on synthetic and real-world networks show that the proposed algorithm is relatively stable and achieves higher precision. It is more suitable for detecting community structure in large-scaled and complex networks with a time complexity ofO(n)andnopriorknowledge.

Community structure Complex network Interrelated topological potential Label propagation

2015-09-17。河南省科技攻關(guān)計(jì)劃項(xiàng)目(142102210435)；河南省高等學(xué)校礦山信息化重點(diǎn)學(xué)科開(kāi)放實(shí)驗(yàn)室開(kāi)放基金項(xiàng)目(ky2012-02)。趙文濤，教授，主研領(lǐng)域：數(shù)據(jù)庫(kù)，數(shù)據(jù)挖掘，大數(shù)據(jù)。趙好好，碩士生。孟令軍，碩士生。

TP

ADOI:10.3969/j.issn.1000-386x.2017.01.047