楊艷新，熊小峰，樂光學(xué)

（1.江西理工大學(xué) 理學(xué)院，江西 贛州 341000；2.嘉興學(xué)院 數(shù)理與信息工程學(xué)院，浙江 嘉興 314000）

基于最短路徑特征的社團(tuán)發(fā)現(xiàn)算法*

楊艷新1,2，熊小峰1，樂光學(xué)1,2

（1.江西理工大學(xué) 理學(xué)院，江西 贛州 341000；2.嘉興學(xué)院 數(shù)理與信息工程學(xué)院，浙江 嘉興 314000）

為了準(zhǔn)確快速地挖掘社團(tuán)結(jié)構(gòu)，提出基于最短路徑特征的社團(tuán)發(fā)現(xiàn)算法SPCDA（Shortest Path feature community discovery algorithm）。該算法是基于最短路徑特征的啟發(fā)，根據(jù)最短路徑數(shù)目的特征計算每個節(jié)點的中介系數(shù)而獲取社團(tuán)中心，并由其長度的特征計算節(jié)點之間的相似度值。然后，取所有節(jié)點的平均相似度值作為劃分社團(tuán)的閾值，構(gòu)成類似于聚類的模型。最后，將與社團(tuán)中心的相似度值大于閾值的節(jié)點進(jìn)行歸類，按照此過程不斷迭代，至節(jié)點集為空。將該算法應(yīng)用于人工合成網(wǎng)絡(luò)和兩個經(jīng)典的真實社會網(wǎng)絡(luò)，并與GN算法和LPA算法進(jìn)行比較，結(jié)果證明SPCDA算法能夠準(zhǔn)確、快速地挖掘隱藏的社團(tuán)結(jié)構(gòu)。

社團(tuán)結(jié)構(gòu)；最短路徑；中介系數(shù)；相似度

0　引 言

隨著經(jīng)濟(jì)的高速發(fā)展，信息技術(shù)日新月異，網(wǎng)絡(luò)使用更加廣泛，信息交流渠道變得多樣化，社交環(huán)境也愈加復(fù)雜化。因此，從復(fù)雜網(wǎng)絡(luò)[1]中挖掘隱藏的社團(tuán)對研究網(wǎng)絡(luò)的結(jié)構(gòu)屬性具有重要意義?，F(xiàn)實世界中，如廣泛使用的Email網(wǎng)絡(luò)、萬維網(wǎng)、遍及全球的Internet、生物系統(tǒng)中的蛋白質(zhì)網(wǎng)絡(luò)、社交網(wǎng)絡(luò)以及無線mesh網(wǎng)絡(luò)[2-3]等，都屬于復(fù)雜網(wǎng)絡(luò)的范疇。挖掘復(fù)雜網(wǎng)絡(luò)潛在的社團(tuán)結(jié)構(gòu)，對于輿情控制、預(yù)防病毒傳播、對未知生物功能的預(yù)測[4-6]等重要重大。

節(jié)點特征屬性的復(fù)雜性、網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)的復(fù)雜性、節(jié)點與結(jié)構(gòu)之間的相互影響以及網(wǎng)絡(luò)之間的相互影響，這都是復(fù)雜網(wǎng)絡(luò)的復(fù)雜性所在。復(fù)雜網(wǎng)絡(luò)中的社團(tuán)結(jié)構(gòu)體現(xiàn)在社團(tuán)內(nèi)部的節(jié)點連接相對緊密，社團(tuán)之間的節(jié)點連接相對稀疏[7]。

近年來，復(fù)雜網(wǎng)絡(luò)中社團(tuán)的挖掘得到了不少專家學(xué)者的關(guān)注。其中，采用層次聚類[8]是一種典型的社團(tuán)挖掘算法。該算法包括分裂式層次聚類和聚合式層次聚類兩種，最具代表性的分裂式層次聚類算法為GN算法[9]。由美國密歇根大學(xué)的Girvan等人提出的基于邊介數(shù)[10]的社團(tuán)發(fā)現(xiàn)算法，則包括最短路徑邊介數(shù)、隨機(jī)游走邊邊介數(shù)以及電流邊邊介數(shù)。隨后，由密歇根大學(xué)的Newman等人提出了社團(tuán)劃分質(zhì)量函數(shù)-模塊度[11]度量，根據(jù)檢測模塊度函數(shù)值大小來選取最佳的社團(tuán)結(jié)構(gòu)。另外，Newman在已有算法的基礎(chǔ)上提出了一種快速社團(tuán)發(fā)現(xiàn)算法——Newman算法[12]。該算法屬于聚合式層次聚類算法，算法起初把網(wǎng)絡(luò)中每一個節(jié)點作為一個獨立的社團(tuán)，每次選擇兩個能使模塊度函數(shù)值Q增加最大的社團(tuán)進(jìn)行合并，直至Q值不再增加為止。

此外，Raghavan等人[13]提出了一種簡單快速的標(biāo)簽傳播算法（Label Propagation Algorithm，LPA）[14]。該算法具有近乎線性的時間和空間復(fù)雜度。Blondel則提出了一種基于貪婪層次聚類的BGLL算法[15]，該算法基于局部模塊度最優(yōu)化思想。還有研究者提出了多種不同的社團(tuán)結(jié)構(gòu)劃分算法[16]，如譜方法[17]、FN算法[18]等。

本文提出一種基于最短路徑特征，根據(jù)最短路徑數(shù)目的特征計算每個節(jié)點的中介系數(shù)而獲取社團(tuán)中心，根據(jù)最短路徑長度的特征計算節(jié)點之間的相似度值，取所有節(jié)點的平均相似度值[19]作為劃分社團(tuán)的閾值，以構(gòu)成類似于聚類[20]的模型，最后將與社團(tuán)中心的相似度值大于閾值的節(jié)點進(jìn)行歸類，按照此過程不斷迭代，至節(jié)點集為空。最后，采用標(biāo)準(zhǔn)化互信息（Normalized Mutual Information，NMI）[21]和模塊度（Modularity）[22]檢測社團(tuán)結(jié)構(gòu)的緊密性。

1　基本概念

為了研究復(fù)雜網(wǎng)絡(luò)的結(jié)構(gòu)屬性，定義了最短路徑特征、相似度和劃分閾值等概念，并提出了中介系數(shù)的定義。

1.1最短路徑特征

基于最短路徑特征的啟發(fā)，定義了兩種不同的概念：一種是最短路徑的數(shù)目特征；另一種是最短路徑的長度特征。其中，最短路徑的數(shù)目特征應(yīng)用于計算中介系數(shù)，而最短路徑的長度特征則應(yīng)用于獲取節(jié)點的相似度。

1.2中介系數(shù)

定義節(jié)點影響力的中介系數(shù)：

式中，pjk表示節(jié)點j和節(jié)點k之間的最短路徑數(shù)目，pijk表示節(jié)點j到節(jié)點k之間的pjk條最短路徑中經(jīng)過節(jié)點i的最短路徑數(shù)目，表示網(wǎng)絡(luò)節(jié)點集內(nèi)每對節(jié)點的最短路徑中實際經(jīng)過節(jié)點i的最短路徑數(shù)目，表示所有網(wǎng)絡(luò)節(jié)點對的最短路徑中可能經(jīng)過節(jié)點i的最短路徑數(shù)目最大值。

1.3節(jié)點相似度

定義網(wǎng)絡(luò)節(jié)點的相似度：

式中，dji、dki為節(jié)點j、k到節(jié)點i的最短路徑長度（連接邊數(shù)），S(j,k)的取值域為（0,1]。

1.4劃分閾值

定義社團(tuán)結(jié)構(gòu)劃分的閾值：

2　算法描述

2.1基本思想

通過網(wǎng)絡(luò)中某個節(jié)點的最短路徑數(shù)目來刻畫節(jié)點在網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)中的重要性和影響力，計算出網(wǎng)絡(luò)中每一個節(jié)點的中介系數(shù)，并由大到小進(jìn)行排序。通過比較網(wǎng)絡(luò)中任意兩個節(jié)點到另外某一個節(jié)點的最短路徑長度差值，來判斷這兩個節(jié)點的相似度。按照聚類的思想，計算節(jié)點對的平均相似度值進(jìn)行社團(tuán)結(jié)構(gòu)的劃分。

2.2算法主要步驟

（1）由式（1）計算網(wǎng)絡(luò)中每個節(jié)點的中介系數(shù)值Bi，并降序排列存儲于一維數(shù)組B[]中。

（2）根據(jù)式（2）獲取網(wǎng)絡(luò)中所有節(jié)點對的相似度值S(j,k)，并存入相似度矩陣S中。

（3）按照式（3）求出社團(tuán)結(jié)構(gòu)的劃分閾值λ。

（4）取一維數(shù)組B[]中最大元素所對應(yīng)的節(jié)點作為社團(tuán)中心。

（5）取網(wǎng)絡(luò)中所有與該社團(tuán)中心的相似度值大于閾值λ的節(jié)點并加入到該社團(tuán)，最后在網(wǎng)絡(luò)節(jié)點集中刪除這些節(jié)點。

（6）判斷網(wǎng)絡(luò)節(jié)點集是否為空，如果為空，則算法結(jié)束；否則重復(fù)步驟（4）至步驟（6）。

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

SPCDA算法的主要時間開銷包括計算網(wǎng)絡(luò)中每個節(jié)點的中介系數(shù)值Bi和計算網(wǎng)絡(luò)中所有節(jié)點對的相似度值S(j,k)。其中，計算網(wǎng)絡(luò)中n個節(jié)點的中介系數(shù)值Bi，有n個網(wǎng)絡(luò)節(jié)點，且每一個節(jié)點都要匹配成節(jié)點對，則需要循環(huán)次，所以這部分的時間復(fù)雜度是O[n(n-1)(n-2)/2]；然后，計算節(jié)點對的相似度，網(wǎng)絡(luò)中有n個節(jié)點，則需要循環(huán)次，因此該部分的時間復(fù)雜度是由此，SPCDA算法的總時間復(fù)雜度為：

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

為了驗證本文提出的SPCDA算法的有效性，將其在人工合成網(wǎng)絡(luò)LFR benchmark和兩個經(jīng)典的真實社會網(wǎng)絡(luò)上進(jìn)行實驗，并與GN算法、LPA算法進(jìn)行比較。仿真實驗環(huán)境：Intel Core i5 2.20 GHz的CPU，8 GB內(nèi)存，1T硬盤容量，Windows 8操作系統(tǒng)；實驗工具為Mysql 5.5和Matlab R2009a。

3.1評價標(biāo)準(zhǔn)

本文采用New-man[12]和Girvan[10]提出的標(biāo)準(zhǔn)化互信息（Normalized Mutual Information）NMI和模塊度函數(shù)Q作為衡量社團(tuán)劃分結(jié)果的標(biāo)準(zhǔn)。

3.1.1標(biāo)準(zhǔn)化互信息NMI

標(biāo)準(zhǔn)化互信息NMI[21]定義如下：

式中，A、B分別表示真實的社團(tuán)集合和通過算法劃分得到的社團(tuán)結(jié)果，I(A,B)是A、B兩個向量的交互信息，H(A)和H(B)分別表示A向量和B向量的標(biāo)準(zhǔn)熵。

3.1.2模塊度函數(shù)

模塊度[22]函數(shù)定義如下：

式中，Ii表示第i個社團(tuán)內(nèi)部邊的數(shù)目，Di表示第i個社團(tuán)中節(jié)點的度之和。

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

在LFR網(wǎng)絡(luò)中，設(shè)置不同的數(shù)據(jù)參數(shù)值分別測試SPCDA、GN、LPA三種算法。其中，S為社團(tuán)的規(guī)模，Smin為社團(tuán)的最小規(guī)模，Smax為社團(tuán)的最大規(guī)模，Dmax為最大節(jié)點度，Dave為平均節(jié)點度，N為網(wǎng)絡(luò)的節(jié)點個數(shù)，度指數(shù)t1=2，社團(tuán)指數(shù)t2=3，γ為混合參數(shù)。LFR人工數(shù)據(jù)集的各種參數(shù)取值如表1所示。

表1　LFR數(shù)據(jù)集參數(shù)值

SPCDA、GN、LPA三種算法分別劃分LFR人工網(wǎng)絡(luò)，實驗得到的標(biāo)準(zhǔn)化互信息NMI隨混合參數(shù)γ的變化曲線如圖1所示。取四組不同的參數(shù)，分別得到圖1（a）、圖1（b）、圖1（c）、圖1（d）四個子圖。

圖1　LFR數(shù)據(jù)集NMI值對比

其中，圖1（a）設(shè)置的最小社團(tuán)規(guī)模為10，最大規(guī)模為50，平均節(jié)點個數(shù)為20，最大節(jié)點個數(shù)為50，此時SPCDA算法劃分LFR人工網(wǎng)絡(luò)的NMI值介于GN和LPA之間；圖1（b）設(shè)置的最小社團(tuán)規(guī)模為20，最大規(guī)模為100，平均節(jié)點個數(shù)和最大節(jié)點個數(shù)與圖1（a）圖相同，在混合參數(shù)γ為0.5時，SPCDA算法劃分LFR網(wǎng)絡(luò)的效果開始略有降低，均低于另兩種算法；圖1（c）設(shè)置的社團(tuán)規(guī)模與圖1（a）圖相同，但平均節(jié)點個數(shù)為40，最大節(jié)點個數(shù)為50，此時SPCDA算法劃分LFR人工網(wǎng)絡(luò)的效果接近GN算法，兩者的效果均遠(yuǎn)優(yōu)于LPA算法；圖1（d）設(shè)置的社團(tuán)規(guī)模與圖1（b）相同，但平均節(jié)點個數(shù)和最大節(jié)點個數(shù)與圖1（c）圖相同，在混合參數(shù)γ為0.1到0.3之間時，GN算法和SPCDA算法的劃分效果相接近；在混合參數(shù)γ處于0.3至0.7之間時，SPCDA算法劃分LFR人工網(wǎng)絡(luò)的效果最佳。分析圖1結(jié)果表明：SPCDA算法劃分社團(tuán)精度介于LPA與GN之間，但針對算法時間復(fù)雜度分析，SPCDA算法時間復(fù)雜度更低，這也將在真實社會網(wǎng)絡(luò)中得以驗證。

3.3真實社會網(wǎng)絡(luò)

在真實社會網(wǎng)絡(luò)中，選取具有代表性的Zachary俱樂部網(wǎng)絡(luò)和美國大學(xué)足球聯(lián)盟網(wǎng)絡(luò)進(jìn)行實驗。

3.3.1Zachary俱樂部網(wǎng)絡(luò)

Zachary空手道俱樂部網(wǎng)絡(luò)由34個節(jié)點78條邊組成。一個節(jié)點對應(yīng)一個成員，一條邊對應(yīng)成員之間的社交關(guān)系。由于就是否提高俱樂部收費的問題導(dǎo)致俱樂部主管和校長之間發(fā)生矛盾，從而形成了分別以主管和校長為中心的兩個不同的社團(tuán)。根據(jù)本文提出的SPCDA算法，由式（1）計算出Zachary網(wǎng)絡(luò)的中介系數(shù)。其中，中介系數(shù)最大的節(jié)點為節(jié)點1，B1=0.835；其次是節(jié)點34，B34=0.799。網(wǎng)絡(luò)中節(jié)點的平均相似度值λ=0.428，Zachary空手道俱樂部網(wǎng)絡(luò)實驗劃分結(jié)果如圖2所示。

圖2　Zachary俱樂部網(wǎng)絡(luò)劃分結(jié)果

本文算法與LPA、GN算法在Zachary空手道俱樂部網(wǎng)絡(luò)進(jìn)行實驗比較。其中，SPCDA算法在劃分社團(tuán)數(shù)目為2時到達(dá)最大模塊度，即社團(tuán)數(shù)目為2時，該社團(tuán)的結(jié)構(gòu)最清晰。在社團(tuán)數(shù)目為2時，SPCDA算法劃分該社團(tuán)的平均模塊度Qave=0.4109，得到最佳社團(tuán)結(jié)構(gòu)的耗時T=54.3 ms；GN算法劃分社團(tuán)的平均模塊度Qave=0.4133，耗時T=150.4 ms；LPA算法劃分社團(tuán)的平均模塊度Qave=0.340 7，耗時T=52.7 ms。劃分Zachary俱樂部網(wǎng)絡(luò)的社團(tuán)結(jié)構(gòu)比較結(jié)果如圖3所示。

圖3　三種算法劃分的社團(tuán)數(shù)目對應(yīng)的模塊度變化

其中，SPCDA、GN、LPA三種算法劃分Zachary俱樂部網(wǎng)絡(luò)的模塊度函數(shù)Q值均在社團(tuán)數(shù)目為2時達(dá)到最大，并在之后開始逐漸減小。LPA算法減小的幅度較大，而GN算法與SPCDA算法減小幅度較平緩。在社團(tuán)數(shù)目為5時，GN算法和SPCDA算法的模塊度函數(shù)Q值幾乎相等。在社團(tuán)數(shù)目為7時，GN算法減小的幅度加劇，且低于SPCDA算法的劃分精度。通過對比分析劃分社團(tuán)的個數(shù)、模塊度、運(yùn)行時間三個方面的實驗結(jié)果，可見SPCDA算法在時間復(fù)雜度和準(zhǔn)確性上進(jìn)行了有效權(quán)衡，可以用較少的時間來準(zhǔn)確劃分社團(tuán)。

3.3.2美國大學(xué)足球聯(lián)盟網(wǎng)絡(luò)

美國大學(xué)足球聯(lián)盟網(wǎng)絡(luò)由115個節(jié)點和616條邊組成，其中網(wǎng)絡(luò)中的節(jié)點對應(yīng)球隊，邊對應(yīng)兩個球隊之間的比賽聯(lián)系。根據(jù)SPCDA算法對美國大學(xué)足球聯(lián)盟網(wǎng)絡(luò)進(jìn)行社團(tuán)劃分，得到如圖4所示的實驗結(jié)果。

圖4　美國大學(xué)足球聯(lián)盟網(wǎng)絡(luò)社團(tuán)劃分結(jié)果

其中，SPCDA算法劃分美國大學(xué)足球聯(lián)盟網(wǎng)絡(luò)實驗結(jié)果詳情如表2所示。

表2　美國大學(xué)足球聯(lián)盟網(wǎng)絡(luò)社團(tuán)劃分結(jié)果詳情

本文算法劃分美國大學(xué)足球聯(lián)盟網(wǎng)絡(luò)得到10個社團(tuán)。此時的社團(tuán)結(jié)構(gòu)最清晰，劃分該社團(tuán)的平均模塊度Qave=0.5962，得到最佳社團(tuán)結(jié)構(gòu)的耗時T=464.4 ms。GN算法平均模塊度Qave=0.6001，耗時T=5812.8 ms；LPA算法劃分的平均模塊度Qave=0.5879，耗時T=419.7 ms。具體的，與GN、LPA算法在劃分社團(tuán)結(jié)構(gòu)上的實驗結(jié)果如圖5所示。

圖5　三種算法劃分的社團(tuán)數(shù)目對應(yīng)的模塊度變化

其中，在社團(tuán)數(shù)目為10時，SPCDA、GN、LPA三種算法均取得最大模塊度函數(shù)Q值。此后，GN算法劃分美國大學(xué)足球聯(lián)盟網(wǎng)絡(luò)的模塊度函數(shù)Q值大幅度降低，而SPCDA算法和LPA算法均直到社團(tuán)數(shù)目為12之后才開始下降，并在社團(tuán)數(shù)目為10至12之間，其模塊度函數(shù)Q值幾乎維持不變。在社團(tuán)數(shù)目增長到12時，LPA算法也開始出現(xiàn)大幅度降低的現(xiàn)象，而SPCDA算法依然保持小幅度下降，直至社團(tuán)數(shù)目為14時，才開始加劇下降幅度。通過實驗結(jié)果分析，本文算法劃分社團(tuán)的準(zhǔn)確度比LPA算法更高，接近GN算法，而運(yùn)行時間比GN算法更少。由此可知，本文算法在劃分社團(tuán)的精度和時間復(fù)雜度這兩個衡量指標(biāo)上的綜合，得到了有效提高。

4　結(jié) 語

SPCDA算法是基于最短路徑特征的啟發(fā)，每次選取節(jié)點集合中中介系數(shù)最大的節(jié)點作為社團(tuán)中心。根據(jù)最短路徑的相關(guān)概念計算節(jié)點之間的相似度值，取所有節(jié)點的平均相似度值作為劃分社團(tuán)的閾值。將與社團(tuán)中心的相似度值大于閾值的節(jié)點進(jìn)行歸類，按照此過程不斷迭代，至節(jié)點集為空。通過仿真實驗結(jié)果可知，SPCDA算法能夠有效發(fā)現(xiàn)社團(tuán)結(jié)構(gòu)，并且劃分社團(tuán)的準(zhǔn)確度較高，算法的時間復(fù)雜度較低。

[1] 賴大榮.復(fù)雜網(wǎng)絡(luò)社團(tuán)結(jié)構(gòu)分析方法研究[D].上海:上海交通大學(xué),2011. LAI Da-rong.Study on the Analysis Method of Complex Network Community Structure[D].Shanghai:Shanghai Jiao Tong University,2011.

[2] Kun Xie,Xin Wang,Jigang Wen,et al. Cooperative Routing with Relay Assignment in Multi-radio MultihopWireless Networks[J]. IEEE/ACM Transactions on Networking (TON), 2016,24(02): 859-872.

[3] Jigang Wen,Jiannong Cao,Kun Xie,et al.User Density Sensitive P2P Streaming in Wireless Mesh Networks[J].Journal of Parallel and Distributed Computing,2011,71(04):573-583.

[4] Spirin V,Mirny L A.Protein Complexes and Functional Modules in Molecular Networks[C].Haetwell Proceedings of the National Academy of Science.New York:The National Academy of Sciences of the USA,2003:12123-12128.

[5] Wilkinson M D,Huberma A B.A Method for Finding Community of Related Genes[A]//Mill R.Proceedings of the National Academy of Sciences[C].Palo Alto:Chemical Abstracts,2007:5241-5248.

[6] Guimera R,Amara A L.Functional Cartography of Complex Metabolic Networks[J].Nature,2005,433(07):895-900.

[7] 劉瑤.社會網(wǎng)絡(luò)特征分析與社團(tuán)結(jié)構(gòu)挖掘[D].成都:電子科技大學(xué),2013. LIU Yao.Characteristics of Social Network and Community Structure Mining[D].Chengdu: University of Electronic Science and Technology,2013.

[8] Brodka P,Saganowski S,Kazienko P.Group Evolution Discovery in Social Networks[A].Kazien-ko P.Proceedings of International Conference on Advances in Social Networks Analysis and Mining[C].New York:IEEE Computer Society,2011:247-253.

[9] 胡芳.復(fù)雜網(wǎng)絡(luò)節(jié)點中心性多元評估與社團(tuán)探測新算法研究[D].武漢:華中師范大學(xué),2015. HU Fang.Research on the New Algorithm of Multi Evaluation and Community Detection in Complex Network Nodes[D].Wuhan:Huazhong Normal University,2015.

[10] Girvan M,Newman M E J.Community Structure in Social and Biological Networks[J].Proceeding of the National Academy of Sciences of the United States of America,2002,9(12):7821-7826.

[11] Jin J,Liu Y,Xu k,et al.Novel Dynamic Evolution Model based on Improved Cellular Auto mata in Hierarcal Complex Networks[J].Journal of Communicatio ns,2013,8(12):862-869.

[12] Newman M E J.Fast Algorithm for Detecting Community Structure in Networks[J].Physical review E,2004,69(06):066133.

[13] Raghavan U N,Albert R,Kumara S.Near Linear Time Algorithm to Detect Community Structures in Large Scale Networks[J].Physical Review E,2007,76(03):036106.

[14] 劉攻申,張浩霖,孟魁等.非隨機(jī)的標(biāo)簽傳播社區(qū)劃分算法[J].上海交通大學(xué)學(xué)報,2015,49(08):1168-1173. LIU Gong-shen,ZHANG Hao-lin,MENG Kui,et al.A Non Random Label Propagation Algorithm[J].Journal of Shanghai Jiao Tong University,2015,49(08):1168-1173.

[15] Blondel V D,Lambiotee R,lefebvre E,et al.Fast Unfolding of Communities in Large Networks[J].Journal of Statistical Mechanics,2008,2(25):1000-1008.

[16] 駱志剛,蔣曉舟.復(fù)雜網(wǎng)絡(luò)社團(tuán)發(fā)現(xiàn)算法研究新進(jìn)展[J].國防科技大學(xué)學(xué)報,2011,33(01):47-52. LUO Zhi-gang,JIANG Xiao-zhou.New Progress in the Study of Complex Network Community Discovery Algorithm [J].Journal of National University of Defense Technology,2011,33(01):47-52.

[17] 周繼超,劉建生.確定FCM聚類中心的自動譜聚類社團(tuán)發(fā)現(xiàn)算法[J].江西理工大學(xué)學(xué)報,2016,1(37):80-86. ZHOU Ji-chao,LIU Jian-sheng.An Algorithm for Automatic Spectral Clustering in the Determination of FCM Clustering Center[J].Journal of Jiangxi University of Science and Technology,2016,1(37):80-86.

[18] Zhang Y P,Wang Y,Zhao S,et al.Community Detection Algorithm base on Cover[J].Journal of Nanjing University(Natural Sciences),2013,49(05):539-545.

[19] 梁宗文,楊帆,李建平.基于節(jié)點相似性度量的社團(tuán)結(jié)構(gòu)劃分方法[J].計算機(jī)應(yīng)用研究,2015,35(05):1213-1217. LIANG Zong-wen,YANG Fan,LI Jian-ping.A Method for the Division of Community Structure based on the Similarity Measure of Nodes[J].Computer Application Research,2015,35(05):1213-1217.

[20] 楊博,劉大友,金博等.復(fù)雜網(wǎng)絡(luò)聚類方法[J].軟件學(xué)報,2009,20(01):54-66. YANG Bo,LIU Da-you,JIN Bo,et al.Complex Network Clustering Method[J].Journal of Software,2009,20 (01):54-66.

[21] Luo Z G,Jiang X Z.New Progression Community Detection in Complex network [J].Journal of National University of Defense Technology,2011,33(01):47-52.

[22] Newan M E J,Girvan M.Finding and Evaluating Community Structure in Networks[J].Physical Review E,2004, 69(02):026113.

楊艷新（1989—），男，碩士研究生，主要研究方向為計算機(jī)網(wǎng)絡(luò)、數(shù)值分析；

熊小峰（1965—），男，碩士，教授，主要研究方向為數(shù)學(xué)建模及應(yīng)用，數(shù)值計算與數(shù)值分析；

樂光學(xué)（1963—），男，博士，教授，主要研究方向為計算機(jī)網(wǎng)絡(luò)與分布式系統(tǒng)、無線Mesh網(wǎng)絡(luò)技術(shù)。

Community Discovery Algorithm based on Shortest Path Feature

YANG Yan-xin1,2, XIONG Xiao-feng1, YUE Guang-xue1,2
（1.School of Science, Jiangxi University of Science and Technology, Ganzhou Jiangxi 341000，China；2.College of Mathematic Physics and Information Engineering, Jiaxing University, Jiaxing Zhejiang 314000，China）

For quickly and accurately mining community structure the community discovery algorithm SPCDA(Shortest Path feature community discovery algorithm) based on the shortest path feature is proposed. This algorithm, based on the enlightenment of shortest path feature and the number of shortest path, calculates the intermidiary coefficient of each node and captures the community center, and in accordance with the shortest path calculates the similarity of between the nodes, then taking the average similarity of all nodes as the threshold value for dividing social community,constructs a model similar to clustering, and finally the community centers with the similarity value greater than the threshold value of the node are classified, and the algorithm continues this iterative process until the node set becomes empty. The algorithm is applied to the artificially synthetic networks and two classic real social networks. Comparison with GN algorithm and LPA algorithm, indicates that SPCDA algorithm could more accurately and quickly mine the hidden community structure.

community structure; shortest path; intermediary coefficient; similarity

TP301.6

A

1002-0802(2016)-08-01034-07

10.3969/j.issn.1002-0802.2016.08.015

2016-04-20;

2016-07-19

date:2016-04-20;Revised date:2016-07-19