基于節(jié)點動態(tài)連接度的網(wǎng)絡(luò)社團劃分算法

賈 珺，胡曉峰，賀筱媛(國防大學 .信息作戰(zhàn)與指揮訓練教研部; .研究生院，北京 100091)

基于節(jié)點動態(tài)連接度的網(wǎng)絡(luò)社團劃分算法

賈 珺a,b，胡曉峰a，賀筱媛b
(國防大學 a.信息作戰(zhàn)與指揮訓練教研部; b.研究生院，北京 100091)

首先定義了節(jié)點動態(tài)連接度這一概念，然后介紹了基于節(jié)點動態(tài)連接度的網(wǎng)絡(luò)社團劃分算法，之后再對其中相關(guān)參數(shù)的取值范圍和社團劃分結(jié)果之間的關(guān)系進行了分析，并以Zachary網(wǎng)絡(luò)為例驗證了分析結(jié)論。在此基礎(chǔ)上，以dolphins、polbooks和football 3個實際網(wǎng)絡(luò)為對象，進行了社團劃分實驗，證明了本算法可通過動態(tài)調(diào)整參數(shù)實現(xiàn)對不同網(wǎng)絡(luò)的社團劃分。最后將實驗結(jié)果與其他幾種常見的社團劃分算法結(jié)果進行了比較，證明了算法的優(yōu)勢，并對算法中需要注意的一些問題進行了說明。

節(jié)點動態(tài)連接度；社團結(jié)構(gòu)；社團劃分

0 引言

網(wǎng)絡(luò)中的社團結(jié)構(gòu)指的是網(wǎng)絡(luò)中的節(jié)點形成的多個團體，這些團體內(nèi)部之間連接緊密，而團體之間的連接則相對松散[1-2]，具體結(jié)構(gòu)如圖1所示。很多現(xiàn)實中存在的網(wǎng)絡(luò)，都表現(xiàn)出擁有較明顯的社團結(jié)構(gòu)。對于網(wǎng)絡(luò)社團結(jié)構(gòu)，特別是劃分算法的研究，不但在網(wǎng)絡(luò)科學研究方面有重要的理論意義，而且在社會學、計算機學、生物學等領(lǐng)域也都有實際的應(yīng)用價值。

從劃分后的結(jié)果來說，網(wǎng)絡(luò)社團劃分算法主要包括非重疊社團和重疊社團兩大類[3]，其中非重疊社團劃分算法是研究最早也是應(yīng)用最廣的一類算法。這一類算法主要包括最早的試探性算法Kernighan-Lin，它是通過設(shè)置一個增益函數(shù)，利用貪婪算法的原理逐步將網(wǎng)絡(luò)劃分成大小已知的兩個社團的[4]；還包括基于網(wǎng)絡(luò)特定矩陣的譜分析法，其中最典型的是利用圖的拉普拉斯矩陣[5]或標準矩陣[6]進行計算，這一類算法的基本原理是在這類矩陣中，同一社團節(jié)點對應(yīng)的特征分量都近似相等，利用這一原理可以較快速和準確地找到社團[7]。除了以上兩類算法外，在非重疊社團劃分算法中應(yīng)用最廣泛的一類是基于模塊度(Q)的優(yōu)化算法，其中主要包括凝聚、分裂兩種。其中凝聚算法主要是利用自底向上，逐步聚合的思想，讓每次的聚合都向著模塊度增大最大的方向，直至所有邊都合成一個社團為止，過程中最大Q值對應(yīng)的即為社團結(jié)構(gòu)。其中最典型的有Newman快速算法[8]和CNM算法[9]等；分裂算法與凝聚算法的思路相反，它是自頂向下進行的，通過不斷移除網(wǎng)絡(luò)中的邊，向著模塊度減小最大的方向，最終將網(wǎng)絡(luò)中所有點都劃分成獨立社團，過程中最大Q值對應(yīng)的即為社團結(jié)構(gòu)。其中最典型的有Newman最早提出的GN算法[10]以及后來在其上的多種改進和延伸[2，11-12]等。近年來，又出現(xiàn)了幾種其他類型的社團劃分算法。其中一類搜索算法是從網(wǎng)絡(luò)的某些特定節(jié)點開始，以相應(yīng)的標準進行計算，將節(jié)點劃分到不同的網(wǎng)絡(luò)中，這一類算法有一個共同點就是計算復(fù)雜度相對較小，例如利用經(jīng)典的節(jié)點相似性指標以及其他一些自定義指標進行計算的[13-16]；還有一類算法是將模擬退火[17]、遺傳算法[18]等智能優(yōu)化算法引入社團劃分算法中，通過設(shè)定目標函數(shù)，最終得到最優(yōu)或者較優(yōu)的社團劃分結(jié)果。

從計算復(fù)雜度角度來說，以上這些算法中利用局部節(jié)點信息的復(fù)雜度總體上要明顯小于利用網(wǎng)絡(luò)全局信息的。但傳統(tǒng)的利用局部節(jié)點信息的算法一般沒有考慮高階鄰居對網(wǎng)絡(luò)社團劃分結(jié)果的影響，導(dǎo)致一些社團結(jié)構(gòu)無法劃分出來；同時原有算法中的劃分標準一般相對固定，對于不同類型的網(wǎng)絡(luò)產(chǎn)生的劃分效果也并不完全相同，算法的通用性方面受到了制約。

為了解決上述問題，本文首先提出了節(jié)點動態(tài)連接度這一概念，根據(jù)節(jié)點的動態(tài)連接度對網(wǎng)絡(luò)進行社團結(jié)構(gòu)的劃分，同時針對不同網(wǎng)絡(luò)動態(tài)調(diào)整節(jié)點連接度中的參數(shù)，以期得到最佳的網(wǎng)絡(luò)社團結(jié)構(gòu)劃分結(jié)果。實驗結(jié)果證明，這一網(wǎng)絡(luò)社團劃分算法復(fù)雜度較低，并且在多種不同類型的網(wǎng)絡(luò)中都能得到較好的社團結(jié)構(gòu)劃分結(jié)果。

1 算法介紹

本算法的核心思想是采用定量化的方式，計算節(jié)點與已有社團之間的關(guān)系，通過這一關(guān)系的數(shù)量值與設(shè)定的閾值進行比較，來確定節(jié)點是否屬于該社團，最終將所有節(jié)點劃分到不同的社團中去，以實現(xiàn)對網(wǎng)絡(luò)的社團結(jié)構(gòu)劃分。其中節(jié)點與社團之間的定量化關(guān)系即為本算法中定義的節(jié)點動態(tài)連接度，在節(jié)點動態(tài)連接度中還設(shè)置了一個可變參數(shù)，以適應(yīng)不同網(wǎng)絡(luò)在劃分中可能產(chǎn)生的差異。

1.1 基本概念與定義

對于一個無向無權(quán)網(wǎng)絡(luò)G(V,E)，其中V=[v1,v2,…,vN]為網(wǎng)絡(luò)的節(jié)點集，E=[e1,e2,…,eM]為網(wǎng)絡(luò)的鏈路集。假設(shè)網(wǎng)絡(luò)中某已知社團為Cm，則可定義網(wǎng)絡(luò)中的任意節(jié)點vi對于社團Cm的動態(tài)連接度為：

其中nvj,Cm為vj與Cm中的節(jié)點之間存在連邊的個數(shù)；kvj為節(jié)點vj的度；α即為節(jié)點連接度中的可變參數(shù)。情況1)指的是若節(jié)點vi的鄰居vj屬于社團Cm，則這個鄰居對于vi節(jié)點動態(tài)連接度的貢獻值為正1；情況2)指的是若節(jié)點vi的鄰居vj不屬于社團Cm，但是由于其只與vi相連，因此它也不可能屬于其他社團，則vj對vi節(jié)點動態(tài)連接度的貢獻值同樣也為1；情況3)指的是若vj不屬于社團Cm，同時其度不等于1，則vj對vi節(jié)點連接度的貢獻值要看它與社團Cm的連接情況，若其沒有連接，則vj的貢獻度為負1。而對于連接情況則主要是通過連接比率與可變參數(shù)α來確定，因此這里設(shè)可變參數(shù)的取值范圍為α≥0。

通過定義1中的公式，就可以計算出任意節(jié)點與任意社團之間的連接度。在進行社團劃分時，通過與設(shè)定的閾值相比較，就可以將節(jié)點劃分到不同網(wǎng)絡(luò)中。

對于網(wǎng)絡(luò)社團的劃分情況，本算法中采用模塊度Q來衡量劃分的質(zhì)量[11]。對于模塊度Q的計算，首先要假設(shè)網(wǎng)絡(luò)被劃分成k個社團，則在此基礎(chǔ)上構(gòu)建一個k×k維的對稱矩陣e=(eij)，其中元素eij表示第i個社團和第j個社團之間的邊在所有邊中所占的比率，則模塊度為

1.2 算法流程

本算法首先是通過設(shè)定一個固定的α值，然后選擇起始節(jié)點并進行節(jié)點動態(tài)連接度計算和社團劃分，劃分完畢后計算在此α值下得到的社團劃分模塊度，之后再多次改變α值，最后最大的模塊度所對應(yīng)的即為最佳的網(wǎng)絡(luò)社團劃分結(jié)果。在固定的α值下，具體的一次社團劃分算法主要是從某一個選定的節(jié)點出發(fā)，首先確定一個社團(一般選取網(wǎng)絡(luò)中度最大的點與其鄰居構(gòu)成)。然后以這個社團為起點，計算所有相關(guān)鄰居節(jié)點的節(jié)點連接度，若大于閾值0，則加入社團，否則不加入，重復(fù)這一過程直到?jīng)]有節(jié)點能再加入這一社團為止。然后將劃分好的這一社團從原有網(wǎng)絡(luò)中剔除，再重新選取已有度最大的節(jié)點及其鄰居節(jié)點構(gòu)成初始社團，重復(fù)以上步驟直到所有節(jié)點都劃分完畢為止。在固定的α值下，具體的一次社團劃分算法可用如下幾步表示：

步驟3：計算每個新添加節(jié)點的所有鄰居對于社團Cj的節(jié)點連接度，若大于閾值0，則將這一節(jié)點添加到社團Cj中。

步驟4：重復(fù)步驟3直到?jīng)]有任何節(jié)點可以添加為止，這時的社團Cj即為網(wǎng)絡(luò)G(V,E)中的一個社團。

步驟5：從網(wǎng)絡(luò)G(V,E)中剔除社團Cj相關(guān)所有節(jié)點與邊，形成一個新的網(wǎng)絡(luò)G′(V′,E′)。

步驟6：以新網(wǎng)絡(luò)G′(V′,E′)為初始網(wǎng)絡(luò)，重復(fù)步驟1～步驟5，直到新網(wǎng)絡(luò)G′(V′,E′)沒有節(jié)點為止。這個過程中生成的所有社團集合C=[C1,C2,…,CN]即是網(wǎng)絡(luò)G(V,E)進行社團劃分后的結(jié)果。

通過以上步驟就可以得到一個固定α值下的網(wǎng)絡(luò)社團劃分結(jié)果。對于不同的α值，分別進行劃分并記錄下其模塊度，最大的模塊度所對應(yīng)的既是理論上認為的最佳網(wǎng)絡(luò)社團劃分結(jié)果。

同時需要說明的是，通過定義1中的情況2)，本算法已經(jīng)將可能出現(xiàn)的孤立節(jié)點劃分到了相關(guān)社團中。因此經(jīng)過Step5剔除掉相關(guān)節(jié)點和邊之后，不會出現(xiàn)未劃入社團的孤立節(jié)點。但是有可能出現(xiàn)孤立的節(jié)點群，而這些孤立的節(jié)點群，就是其他還未劃分出來的社團結(jié)構(gòu)。通過算法還可以看到，如果選取的起始節(jié)點不同或者設(shè)定的閾值不同，本算法可能會遇到的情況是在社團交界處的某些節(jié)點可能會同時屬于不同社團。這一問題屬于重疊社團劃分中的情況，傳統(tǒng)的重疊社團處理中，一般都是將交界處節(jié)點同時劃分到不同社團中去。本算法的處理方式是將這種交界處的節(jié)點劃歸到先劃出的社團，因此節(jié)點只會屬于一個社團。

1.3 算法分析

本算法的主要特點是設(shè)置了可調(diào)節(jié)的參數(shù)α，因此α的取值范圍和可能出現(xiàn)的結(jié)果就成為了算法設(shè)計的關(guān)鍵部分。根據(jù)節(jié)點連接度的定義，對于任意一個節(jié)點vi和Cm，其中vi的度為kvi，假設(shè)vi的鄰居集合Γi中屬于Cm的比率為x，則不屬于的為1-x。又由定義可知0≤nvj,Cm/kvj≤1，設(shè)不屬于Cm的節(jié)點其cdj(vj,Cm)的平均取值為β，其可能的取值范圍為β≥-1。則可得到任意節(jié)點的節(jié)點連接度取值范圍為

CD(vi,Cm)=kvi×x+kvi×(1-x)×β=kvi×(x+β-x·β)

(1)

由式(1)可以得到，節(jié)點連接度的正負完全由x+β-x·β確定，其中0≤x≤1。則可設(shè)：

z=x+β-x·β

(2)

由式(2)可以看出，當β≥0時，恒有z≥0。又根據(jù)節(jié)點連接度的定義，可變參數(shù)α與β之間的關(guān)系可表示為

β=m×(y+(1-y)(-1+D×α))

(3)

其中，m=kvi×(1-x)，D為nvj,Cm/kvj的平均值，y為度為1的節(jié)點在所有不屬于Cm的節(jié)點中所占的比率。根據(jù)式(3)可以看出，當D×α≥1時，恒有β≥0。但是對于網(wǎng)絡(luò)劃分來說，只有當β值不是恒大于0時，才可能將網(wǎng)絡(luò)中的節(jié)點分配到不同社團中去。因此對于本算法來說，在數(shù)學分析的基礎(chǔ)上可以得到如下結(jié)論：即通過改變α的值，可得到不同的網(wǎng)絡(luò)結(jié)構(gòu)劃分結(jié)果，而且可以看到，當α值過大時，網(wǎng)絡(luò)會被劃分成單一社團。

本文以Zachary網(wǎng)絡(luò)[19]為實例驗證以上結(jié)論。分別為α取不同的值，然后在不同的α值下依據(jù)前面介紹的算法對Zachary網(wǎng)絡(luò)進行劃分，可以分別得到如下結(jié)果：

圖2中從左到右α的取值依次為0，1，2，3，每個α的對應(yīng)的模塊度如表1所示：

通過圖2表1可以看出，對應(yīng)于不同的α值，網(wǎng)絡(luò)的劃分結(jié)果是完全不相同的。而且對于過大的α值，網(wǎng)絡(luò)最終會被劃分為同一社團。這一實例證明了以上數(shù)學分析的結(jié)論。同時，這一結(jié)論也從另一個側(cè)面說明，對于不同的網(wǎng)絡(luò)，改變α值可以得到相對最優(yōu)的劃分結(jié)果，這種設(shè)置可變參數(shù)的動態(tài)劃分算法是合理的。

同時在算法復(fù)雜度方面，假設(shè)網(wǎng)絡(luò)中有n個節(jié)點和m條邊，對于本論文提出的在固定的α值下具體的一次社團劃分算法，其時間復(fù)雜度約為O(n2)，在稀疏網(wǎng)絡(luò)下約等于O(mn)，可以看出這一復(fù)雜度明顯優(yōu)于傳統(tǒng)的GN算法等。

2 實驗

為了驗證算法的有效性，本論文選取了3個實際網(wǎng)絡(luò)數(shù)據(jù)集，這3個是在網(wǎng)絡(luò)社團劃分實驗中最具有代表性的。通過改變α值，分別找到了3個網(wǎng)絡(luò)相對最優(yōu)的劃分結(jié)果，并對相關(guān)實驗結(jié)果進行了綜合分析。

2.1 實驗結(jié)果

本論文選取的數(shù)據(jù)集dolphins最早是由Lusseau博士在其2003年的文章中使用的，主要通過寬吻海豚相互間的聲音研究了其社團情況[20]；數(shù)據(jù)集polbooks主要記錄的是2004年美國大選期間，在Amazon上與政治相關(guān)書籍的售賣情況，其中點為書籍，邊代表了兩個書籍被同一人購買過，這其中的社團主要表現(xiàn)的是購買行為的分類；數(shù)據(jù)集football最早則是由M. Girvan 和M. Newman在其2002年文章中使用過，主要描述的是美國大學生足球在2000年秋天整個賽季的比賽情況，其中節(jié)點表示不同的隊伍，而邊表示的則是不同隊伍之間的比賽，其中的社團代表的是不同的聯(lián)盟[10]。以上這些數(shù)據(jù)集的基本參數(shù)如表2所示。

表1 不同α值下Zachary網(wǎng)絡(luò)社團劃分模塊度Tab.1 different modularity of Zachary in different α

表2 網(wǎng)絡(luò)數(shù)據(jù)集基本參數(shù)Tab.2 the basic parameters’ value of the three networks

在本次實驗中α的取值從0開始，每次增加0.5，記錄下每次劃分結(jié)果的模塊度值，直到網(wǎng)絡(luò)被劃分為一個社團、模塊度降為0為止。通過多次實驗，這3個數(shù)據(jù)集的社團數(shù)量劃分數(shù)量和模塊度值的結(jié)果如圖3～5所示。

由圖3可以看到，本算法對應(yīng)的社團劃分數(shù)量隨著α值的增大，是呈階梯狀單調(diào)遞減的，這是由算法本身的性質(zhì)決定的。而相對應(yīng)的模塊度結(jié)果如圖4所示：

由圖4可以看到，模塊度的變化卻并非是單調(diào)遞減的。這個結(jié)果也可由模塊度計算公式推導(dǎo)而出，即并非社團數(shù)量越多，模塊度越高。綜合以上的實驗結(jié)果數(shù)據(jù)可以得到：數(shù)據(jù)集dolphins最大模塊度為0.584，對應(yīng)的α值為{0.5,1.0}，社團數(shù)量為4；數(shù)據(jù)集polbooks最大模塊度為0.563，對應(yīng)的α值為{0}，社團數(shù)量為5；數(shù)據(jù)集football最大模塊度為0.644，對應(yīng)的α值為{2.5,3.0}，社團數(shù)量為11；具體的社團劃分結(jié)果如圖5所示。

從理論上來說，可以認為圖5中表示的是3個網(wǎng)絡(luò)的最優(yōu)社團劃分結(jié)果。

2.2 結(jié)果分析

在利用本算法進行實際的網(wǎng)絡(luò)社團劃分時，一般是通過改變算法中可變參數(shù)α的值，來獲得盡量貼近于預(yù)期的社團劃分結(jié)果和相對更高的模塊度值，以這種方式實現(xiàn)算法對不同網(wǎng)絡(luò)的最優(yōu)劃分。因此α值的確定方式就成為了提高算法有效性和效率的關(guān)鍵因素之一。由之前實驗結(jié)果的圖3中可以看到，隨著α值的增大，網(wǎng)絡(luò)社團的劃分數(shù)量是單調(diào)遞減的，但同時從圖4中又可以看出，社團結(jié)果的模塊度卻不是單調(diào)遞減，例如dolphins的最大模塊度對應(yīng)的α值為{0.5,1.0}，football的最大模塊度對應(yīng)的α值為{2.5,3.0}。而且隨著網(wǎng)絡(luò)節(jié)點規(guī)模的增大，網(wǎng)絡(luò)最大模塊度對應(yīng)的α值可能會越來越大。因此本算法在實際網(wǎng)絡(luò)的應(yīng)用中，對于α值的確定，可以利用折半查找等策略，快速搜索到可能的最大模塊度對應(yīng)的α值，以提高算法的整體效率。同時如果在進行社團劃分前已知網(wǎng)絡(luò)的社團數(shù)量，就可以利用社團數(shù)量和α值快速找到相對應(yīng)的最大模塊度，這時對應(yīng)的就是理論上最佳的社團劃分結(jié)果。

GN算法Newman快速算法LPA算法文獻[16]算法本文算法dolphins0．5190．4890．5110．550．584polbooks0．5160．5020．515-0．535football0．5990．5770．5970．5690．636

在算法的有效性方面，以算法劃分網(wǎng)絡(luò)后所求得的最大模塊度值來說，本算法與其他經(jīng)典算法的結(jié)果比較如表3所示。

由表3可以看到，本算法對于不同網(wǎng)絡(luò)所能求得的最大模塊度明顯優(yōu)于傳統(tǒng)的經(jīng)典算法。這是由于通過α值的變化，可以使算法更加適應(yīng)目標網(wǎng)絡(luò)，從而求得更好的社團劃分結(jié)果。同時從前面的分析也可以看出，本算法的時間復(fù)雜度約為O(n2)，這在所有的社團劃分算法中也屬于較低層次，因此本算法從效率上來說也適用于大規(guī)模網(wǎng)絡(luò)。

但同時也應(yīng)該看到，本算法在計算過程中還需要特別注意的是算法中閾值的設(shè)定會影響到最終劃分結(jié)果。以前面算法分析中用到的Zachary網(wǎng)絡(luò)為例：當α=1時，與已知的實際社團結(jié)果相比，若算法中的閾值設(shè)定為0，則可得到的最優(yōu)社團劃分結(jié)果將節(jié)點3錯誤劃分到了另一個社團；但是如果將算法中的閾值設(shè)定為大于0并小于1的任意值，本算法就可以找到與實際情況完全一致的社團劃分結(jié)果(即可將節(jié)點3劃分到正確的社團中去)，如圖6所示。

因此對于不同的網(wǎng)絡(luò)，可以在現(xiàn)有算法的基礎(chǔ)上給閾值增加一個微小的擾動，以期獲得最優(yōu)的劃分結(jié)果。同時還應(yīng)該看到，本算法在利用經(jīng)典的模塊度進行社團劃分結(jié)果的選擇時，是存在一定局限性的。即最大的模塊度對應(yīng)的社團劃分結(jié)果與實際已知的社團結(jié)構(gòu)之間存在差異。例如dolphins實際應(yīng)為兩個社團，但是當社團數(shù)量為2時，對應(yīng)的模塊度并非最大，這是由于模塊度本身的局限以及數(shù)據(jù)可能存在的缺陷導(dǎo)致的。在運用算法進行社團劃分時，必須要注意這一問題。

3 結(jié)論

本算法在傳統(tǒng)局部信息算法基礎(chǔ)上，考慮了二階鄰居對于社團劃分結(jié)果的影響，提高了算法的精度；通過設(shè)置動態(tài)可調(diào)整的參數(shù)，改變了傳統(tǒng)算法難以適應(yīng)不同網(wǎng)絡(luò)的問題，提高了算法的動態(tài)可適應(yīng)性；同時這一算法與很多傳統(tǒng)算法相比，計算復(fù)雜度也屬于較低范圍，因此可應(yīng)用于大規(guī)模網(wǎng)絡(luò)的社團劃分計算中。

下一步可以通過大量實驗，研究參數(shù)α與模塊度之間可能存在的邏輯關(guān)系，為更好地設(shè)定參數(shù)提供依據(jù)；或者可以研究在算法中引入回饋機制，將計算結(jié)果與算法中設(shè)置的動態(tài)參數(shù)以及閾值之間建立對應(yīng)關(guān)系，利用機器學習等智能算法在進行社團劃分時自動快速收斂到最佳結(jié)果區(qū)間，進一步提高算法的計算效率和結(jié)果。

[1]Wasserman S, Faust K. Social Network Analysis: Methods and Applications [M]. Cambridge：Cambridge University Press, 1994.

[2]Radicchi F, Castellano C, Cecconi F, et al, Defining and identifying communities in networks [J]. Proc Natl Acad Sci,2004,101(9):2658-2663.

[3]駱志剛,丁凡,蔣曉舟,等.復(fù)雜網(wǎng)絡(luò)社團發(fā)現(xiàn)算法研究新進展[J].國防科技大學學報, 2011,33(1):47-52. Luo Zhigang, Ding Fan, Jiang Xiaozhou, et al. New progress on community detection in complex networks [J]. Journal of National University of Defense Technology, 2011, 33(1): 47-52.

[4]Kernighan B W, Lin S. An efficient heuristic procedure for partitioning graphs[J]. Bell system technical journal, 1970, 49(2): 291-307.

[5]Pothen A, Simon H D, Liou K P. Partitioning sparse matrices with eigenvectors of graphs[J]. SIAM Journal on Matrix Analysis and Applications, 1990, 11(3): 430-452.

[6]Capocci A, Servedio V D P, Caldarelli G, et al. Detecting communities in large networks[J]. Physica A: Statistical Mechanics and Its Applications, 2005, 352(2): 669-676.

[7]Newman M E J. Finding community structure in networks using the eigenvectors of matrices[J]. Physical Review E, 2006, 74(3): 036104.

[8]Newman M E J. Fast algorithm for detecting community structure in networks[J]. Physical Review E, 2004, 69(6): 066133.

[9]Clauset A, Newman M E J, Moore C. Finding community structure in very large networks[J]. Physical Review E, 2004, 70(6): 066111.

[10] Girvan M, Newman M E J. Community structure in social and biological networks [J]. Proceedings of the National Academy of Sciences, 2002, 99(12): 7821-7826.

[11] Newman M E J, Girvan M. Finding and evaluating community structure in networks[J]. Physical Review E, 2004, 69(2): 026113.

[12] Fortunato S, Latora V, Marchiori M. Method to find community structures based on information centrality[J]. Phys Rev E, 2004, 70(5): 056104.

[13] Pan Y, Li D H, Liu J G, et al. Detecting community structure in complex networks via node similarity [J]. Physica A: Statistical Mechanics and Its Applications, 2010, 389(14): 2849-2857.

[14] 袁超, 柴毅. 基于簇相似度的網(wǎng)絡(luò)社團結(jié)構(gòu)探測算法[J]. 物理學報, 2012, 61(21): 539-547. Yuan Chao, Chai Yi. Group similarity based algorithm for network community structure detection [J]. Acta Phys Sin, 2012,61(21):539-547.

[15] 王興元,趙仲祥.基于節(jié)點間依賴度的社團結(jié)構(gòu)劃分方法[J].物理學報， 2014， 63(17): 178901. Wang Xingyuan, Zhao Zhongxiang. Partitioning community structure in complex network based on node dependent degree [J]. Acta Phys Sin,2014,63(17): 178901.

(責任編輯 耿金花)

訂 正

本刊2016年第13卷第1期第64頁頁腳基金項目中“國家統(tǒng)計科學研究項目(2015LZ497)”更正為“國家統(tǒng)計科學研究項目(2015LZ49)”；2016年第13卷第3期第33頁頁腳基金項目中“國家統(tǒng)計科學研究項目(2015LZ249)”更正為“國家統(tǒng)計科學研究項目(2015LZ49)”。

Finding Community Structure in Networks Using Node’s Dynamic Connection Degree

JIA Jun, HU Xiaofeng, HE Xiaoyuan

(a.The Department of Information Operation Command Training,b.The Department of Graduate,National Defense University,Beijing 100091,China)

This paper gives the definition of node’s dynamic connection degree at first, and then introduces the algorithm of finding the community structure by the node’s dynamic connection degree. After that, it analyzes the range of parameter’s value in node’s connection degree and proves it by experimenting on the Zachary network. On this basis, it experiments on three real networks which are dolphins, polbooks and football. The result proves that this algorithm can find different network’s community structure correctly by adjust its parameter’s value. At last, it compares the result with some other common algorithms’ and illustrates some matters that need attention.

node′s dynamic connection degree； community structure； finding community

10.13306/j.1672-3813.2016.04.008

2015-07-06;

2015-09-23

國家自然科學基金(U1435218, 61174035, 61273189, 61374179)

賈珺(1981-)，男，陜西西安人，博士研究生，助理研究員，主要研究方向為軍事運籌學。

TP391.9

A