遺傳算法優(yōu)化模塊度的二分網(wǎng)絡(luò)社團檢測方法

卜振興，　洪衛(wèi)軍

(中國人民公安大學， 北京　100038)

遺傳算法優(yōu)化模塊度的二分網(wǎng)絡(luò)社團檢測方法

卜振興，洪衛(wèi)軍

(中國人民公安大學， 北京100038)

摘要目前二分網(wǎng)絡(luò)社團檢測研究處于探索階段，評估標準和檢測方法較少，模塊度值具有局部性且偏差較大，檢測結(jié)果不穩(wěn)定。針對上述問題，提出一種基于遺傳算法優(yōu)化二分網(wǎng)絡(luò)模塊度的檢測方法，依據(jù)節(jié)點相似度初始化染色體，通過不斷改變社團個數(shù)，使用改進的遺傳算法交叉、選擇和變異等因子，遺傳迭代獲得全局模塊度最大值以及對應(yīng)的社團劃分。仿真結(jié)果表明：能夠有效檢測到模塊度全局最大值以及對應(yīng)的社團個數(shù)和社團劃分，社團劃分更加精準，算法具有較強的魯棒性和抗干擾能力。

關(guān)鍵詞復雜網(wǎng)絡(luò)； 二分網(wǎng)絡(luò)； 遺傳算法； 社團結(jié)構(gòu)

0引言

復雜網(wǎng)絡(luò)是一種具有自組織、自相似、吸引子、小世界、無標度中部分或者全部性質(zhì)的網(wǎng)絡(luò)。簡而言之，復雜網(wǎng)絡(luò)呈現(xiàn)了高度的復雜性。

社團結(jié)構(gòu)特性是復雜網(wǎng)絡(luò)中一種介于宏觀和微觀之間的重要性質(zhì)，其典型特征表現(xiàn)為：社團內(nèi)部節(jié)點之間的聯(lián)系較為密切，而社團與社團之間節(jié)點的聯(lián)系相對較少。社團檢測是通過一些算法檢測出網(wǎng)絡(luò)的社團劃分，是分析復雜網(wǎng)絡(luò)的前提和基礎(chǔ)，引起了各個領(lǐng)域研究學者的極大興趣和廣泛關(guān)注。目前已經(jīng)有了很多檢測社團結(jié)構(gòu)的方法，這些方法使得人們在分析各種信息網(wǎng)絡(luò)、生物網(wǎng)絡(luò)以及社會網(wǎng)絡(luò)等的社團結(jié)構(gòu)時更加準確有效，分析的網(wǎng)絡(luò)規(guī)律也越來越大。

二分網(wǎng)絡(luò)是具有兩種節(jié)點類型的網(wǎng)絡(luò)，節(jié)點關(guān)系僅存在于不同類型節(jié)點之間，同類型節(jié)點之間不存在聯(lián)系，如：科學家- 論文、人員- 位置等網(wǎng)絡(luò)都是典型的二分網(wǎng)絡(luò)，生活中普遍存在形形色色的二分網(wǎng)絡(luò)，研究二分網(wǎng)絡(luò)可以了解和解釋網(wǎng)絡(luò)的內(nèi)部特征，掌握節(jié)點之間的規(guī)律，同時可以應(yīng)用于實際。例如：通過分析一個人出現(xiàn)的地點，可以掌握該人的活動規(guī)律；分析一種犯罪的特征，可以挖掘出該類案件的犯罪群體等。因此，研究二分網(wǎng)絡(luò)不僅具有重要的理論意義，更具有廣泛的現(xiàn)實意義，成為學者研究的重點和熱點。

二分網(wǎng)絡(luò)社團檢測最初基于映射法來實現(xiàn)，將二分網(wǎng)絡(luò)轉(zhuǎn)換為單分網(wǎng)絡(luò)，使用較為成熟的單分網(wǎng)絡(luò)檢測方法進行檢測。隨著科學的發(fā)展，不少學者提出了直接檢測法，即直接使用二分網(wǎng)絡(luò)模型進行檢測，如：Guimera等人提出了二分模塊度，設(shè)計出對應(yīng)的檢測方法，但是該方法只能每次檢測一種類型的節(jié)點；Barber對Newman單分模塊度進行了拓展，提出自己的二分網(wǎng)絡(luò)模塊度及對應(yīng)的二分網(wǎng)絡(luò)檢測方法BRIM。雖然上述兩種方法都各具優(yōu)點，但都存在著一些問題和難點，使得檢測結(jié)果準確性不夠。其難點可以歸納為：(1)映射法的映射方法不夠精準，造成重要信息丟失，從而使得檢測結(jié)果存在誤差，如何設(shè)計一種更精準的映射方法是該類方法的難點；(2)非映射法由于檢測模型不夠準確和需要額外初始輸入，使得檢測結(jié)果局部最優(yōu)，如何找到全局最優(yōu)檢測方法是此類檢測方法的難點。

為了克服上述問題和難點，本文提出一種新型的基于遺傳算法優(yōu)化二分網(wǎng)絡(luò)模塊度的社團檢測方法，為了得到全局最大模塊度值，最初不限定社團個數(shù)，檢測劃分不同社團個數(shù)時的模塊度局部最大值，逐步改變社團個數(shù)，得到全局最大模塊度值。在每次檢測中，根據(jù)網(wǎng)絡(luò)節(jié)點對的相似度，得到節(jié)點相似度矩陣，根據(jù)矩陣初始化染色體，通過遺傳操作得到局部最大值以及對應(yīng)的社團劃分結(jié)果。

本文方法具有以下優(yōu)點：(1)無需額外輸入?yún)?shù)，通過不斷改變社團個數(shù)，檢測全局模塊度最大值及對應(yīng)的網(wǎng)絡(luò)劃分結(jié)果；(2)根據(jù)單分加權(quán)網(wǎng)節(jié)點相似度初始化染色體序列，避免由于映射信息丟失造成誤差較大的問題；(3)根據(jù)實際要求單獨檢測某一類型節(jié)點的社團劃分，避免同時計算兩類節(jié)點造成的冗余計算，節(jié)省算法時間，提供計算效率。

1二分網(wǎng)絡(luò)相關(guān)原理

1.1　二分網(wǎng)絡(luò)概念

二分網(wǎng)絡(luò)是復雜網(wǎng)絡(luò)中的一種重要表現(xiàn)形式，相對于單分網(wǎng)絡(luò)(節(jié)點類型唯一的網(wǎng)絡(luò))，二分網(wǎng)絡(luò)由兩部分不同類型網(wǎng)絡(luò)節(jié)點構(gòu)成，同一類型網(wǎng)絡(luò)節(jié)點不相連，關(guān)系僅存在于不同類型節(jié)點之間的網(wǎng)絡(luò)，如圖1。

圖1　二分網(wǎng)絡(luò)模型

1.2　節(jié)點相似度

節(jié)點相似度，即為節(jié)點對之間的相似程序，在社團網(wǎng)絡(luò)中，一般按照他們的社會圈的相似性來定義頂點的相似性。例如：兩個人共同的朋友數(shù)。在理論網(wǎng)絡(luò)中，一般定義為兩個節(jié)點具有共同邊的個數(shù)，假如節(jié)點a和b，存在共同的連接節(jié)點集合N，那么N中個數(shù)數(shù)量越大，說明節(jié)點A和B的相似度越高，反之，相似度越低。目前，常用的計算節(jié)點對相似度的公式有：

(1)

(2)

在上面的公式中，Ni表示節(jié)點vi的鄰域，|*|表示集合的勢，即元素個數(shù)。兩種相似度的取值范圍都介于0~1之間。

1.3　二分網(wǎng)絡(luò)模塊度

模塊度Q是由Newman等人為解決衡量復雜網(wǎng)絡(luò)中社團劃分質(zhì)量提出的一種衡量標準，Q值越大，表明該網(wǎng)絡(luò)具有的社團結(jié)構(gòu)越明顯，Q的取值范圍為[0,1]，在實際網(wǎng)絡(luò)中，該值范圍通常介于0.3~0.7之間。

在單分網(wǎng)絡(luò)中，我們假設(shè)網(wǎng)絡(luò)可以劃分為k個社團，M定義為網(wǎng)絡(luò)中邊的數(shù)量，V定義為網(wǎng)絡(luò)中所有節(jié)點的集合，Vi和Vm定義為兩個社團，A為網(wǎng)絡(luò)的鄰接矩陣。那么我們可以定義θim為社團Vi到社團Vm的所有連接占整個網(wǎng)絡(luò)邊的比例。

(3)

我們進一步定義大小為kk的矩陣E，其中E中元素表示為eij，矩陣中每行的和定義為ai:

(4)

在網(wǎng)絡(luò)中，當不考慮定點所屬的社團，在保持網(wǎng)絡(luò)節(jié)點度序列不變的情況下，進行隨機連接時，我們可以得到eij=aiaj因此，網(wǎng)絡(luò)模塊度Q可以表示為：

(5)

給定一個網(wǎng)絡(luò)劃分時，假設(shè)網(wǎng)絡(luò)劃分為k個社團，我們建立一個k*k的鄰接矩陣E，其中eij表示節(jié)點分別處于社團i和j的邊占網(wǎng)絡(luò)總邊的比例，eij表示位于同一社團i內(nèi)的邊占網(wǎng)絡(luò)總邊數(shù)的比例，ai表示的是在保持網(wǎng)絡(luò)節(jié)點度序列不變的情況下，邊進行隨機連接后得到的網(wǎng)絡(luò)中社團i的內(nèi)部邊數(shù)占總邊數(shù)的比例的期望值。一般來說，Q值越大，對應(yīng)的社團結(jié)構(gòu)越明顯，目前大家公認的是如果網(wǎng)絡(luò)的劃分具有的最大Q值大于0.3，表明該網(wǎng)絡(luò)具有明顯的社團結(jié)構(gòu)。

目前，對于單分網(wǎng)絡(luò)模塊度研究較為成熟，二分網(wǎng)絡(luò)模塊度尚處于探索階段，Guimera和Barber分別推廣和拓展了Newman的單分模塊度得到自己的二分網(wǎng)絡(luò)模塊度公式。Guimera的二分網(wǎng)絡(luò)模塊度表示為：

(6)

其中，X和Y是類型節(jié)點集合，s是X類節(jié)點的一個社團，NM的X類節(jié)點的社團個數(shù)，a是Y類節(jié)點的一個社團，ma是連接社團a中的邊的個數(shù)，cij是Y類節(jié)點的社團個數(shù)，節(jié)點i和j是連通的，ti和tj分別是Y中連接到節(jié)點i和j的社團總數(shù)。

Barber的二分網(wǎng)絡(luò)模塊度表示為：

(7)

其中，A為二分網(wǎng)絡(luò)的鄰居矩陣，0i×j是i行j列全零矩陣，P為網(wǎng)絡(luò)對應(yīng)隨機模型的連接概率期望矩陣，所謂隨機網(wǎng)絡(luò)模型下的連接概率定義為網(wǎng)絡(luò)中隨機生成一條連接指定頂點的概率。

1.4　二分網(wǎng)絡(luò)常用檢測方法分析

目前常用的二分網(wǎng)絡(luò)社團檢測方法大致分為兩種：映射法和非映射法。

映射法首先將二分網(wǎng)絡(luò)映射為傳統(tǒng)的單分網(wǎng)絡(luò)，然后使用較為成熟的單分網(wǎng)絡(luò)社團檢測方法進行社團結(jié)構(gòu)劃分如圖2。

圖2　二分網(wǎng)絡(luò)映射為單分網(wǎng)絡(luò)

該方法的優(yōu)點是實現(xiàn)簡單且較為成熟，缺點是在單分映射過程中會丟失一些重要的網(wǎng)絡(luò)信息，無法保證劃分的嚴謹性。因此，如果能找到一種方法使得在映射過程中盡量保留原本信息，則可以更加有效、精準地檢測出二分網(wǎng)絡(luò)社團結(jié)構(gòu)。

非映射方法即直接在原始網(wǎng)絡(luò)上劃分社團結(jié)構(gòu)，可以最大程度上保留原有網(wǎng)絡(luò)的信息。目前常用的非映射法主要是基于Barber的BRIM，但該方法僅適用于檢測小型二分網(wǎng)絡(luò)，且在檢測初始階段需要額外的輸入，使得在檢測應(yīng)用時有較大的局限性。

2遺傳算法優(yōu)化二分網(wǎng)絡(luò)模塊度檢測方法

為了克服以往算法的缺點和局限性，得到全局模塊度Q最大值，本文使用改進的遺傳算法，在不斷改變社團個數(shù)的情況下，通過遺傳算法優(yōu)化二分網(wǎng)絡(luò)模塊度Q值，獲得模塊度全局最大值，從而得到更加有效精準的社團劃分。

2.1　算法總體框架

本算法主要涉及到群體編碼及初始化、適應(yīng)度的評價、選擇算子、交叉算子、變異算子等概念。本文提出來的二分網(wǎng)絡(luò)社團檢測方法，是以二分網(wǎng)絡(luò)模塊度為優(yōu)化函數(shù)，使用遺傳算法對二分網(wǎng)絡(luò)模塊度Q最為適應(yīng)度函數(shù)，通過選擇、交叉和變異操作進行優(yōu)化，以求得最大值檢測社團結(jié)構(gòu)，該算法的基本框架為：

準備工作：將二分網(wǎng)絡(luò)映射單分無向加權(quán)網(wǎng)，得到對應(yīng)矩陣，并計算節(jié)點對的相似度；

輸入：無向加權(quán)網(wǎng)對應(yīng)矩陣，節(jié)點對相似度；

輸出：模塊度最大值Q及其對應(yīng)的社團劃分。

算法主要步驟：

(1)初始化與編碼。進化代數(shù)計數(shù)器t=0，最大進化代數(shù)T，初始社團個數(shù)k=2，最大社團個數(shù)K(默認為節(jié)點個數(shù))，根據(jù)節(jié)點相似度生成M個染色體作為初始群體P(t)；

(2)計算群體P(t)中每個個體的適應(yīng)度值Q；

(3)選擇運算。根據(jù)pi=Qi/∑Q計算每個個體概率分布，通過生成范圍[0,1]的均勻隨機數(shù)s，將s作為選擇指針確定被選個體；

(4)交叉運算。通過生成范圍[0,1]的均勻隨機數(shù)c，若c小于交叉概率pc，選擇兩個個體進行交叉操作；

(5)變異運算。隨機生成范圍[0,1]的隨機數(shù)m，若m小于變異概率pm，則隨機選取某一位置進行變異。群體P(t)經(jīng)過選擇、交叉和變異操作后，產(chǎn)生新一代群體P(t+1)；

(6)遺傳終止條件判斷。若t=T，則進化結(jié)束，取遺傳過程中Q最大值的個體作為局部最優(yōu)結(jié)果；否則，繼續(xù)從2)開始；

(7)算法終止條件判斷。若k達到最大值K，則整個算法終止，取局部最優(yōu)結(jié)果最大值對應(yīng)的社團個數(shù)k和劃分最為結(jié)果輸出；否則，重新設(shè)置k的值，繼續(xù)從1)開始遺傳操作。

2.2　初始化與編碼

編碼是遺傳算法中最基本的一步操作，針對復雜網(wǎng)絡(luò)社團檢測問題，編碼即將社團按照序號從小到大進行編號，將不同的節(jié)點對應(yīng)到不同的序號，表示該節(jié)點屬于某個序號的社團。具體的染色體編碼如圖3所示。

圖3　染色體編碼

染色體的長度取決于節(jié)點的個數(shù)，染色體的編碼代表每個節(jié)點所屬的社團編號。如圖中所示，第一個節(jié)點和最后一個節(jié)點分別屬于編號為4和2的社團。

初始化的過程是將每個染色體節(jié)點隨機分配一個社團ID，為了避免無效劃分，盡可能得到最優(yōu)解和減少迭代次數(shù)，在本文初始化過程中，我們加入一些約束條件，即節(jié)點之間聯(lián)系密切的節(jié)點對盡可能分配同一社團ID，對于不存在任何聯(lián)系的節(jié)點，可以隨機分配一個社團ID。

在本文的初始化過程中，我們首先將二分網(wǎng)絡(luò)映射為單分加權(quán)網(wǎng)絡(luò)，使用單分網(wǎng)絡(luò)節(jié)點相似度函數(shù)計算二分網(wǎng)絡(luò)節(jié)點對的相似度，根據(jù)將節(jié)點相似度大的節(jié)點盡可能分配同一社團ID。本文采用Jaccard公式1計算單分網(wǎng)絡(luò)節(jié)點對的相似度，得到節(jié)點相似度矩陣。

2.3　個體適應(yīng)度計算

使用單分網(wǎng)絡(luò)模塊度Q原理，推導二分加權(quán)網(wǎng)絡(luò)模塊度Qw，使用Qw計算每個個體的適應(yīng)度值，作為評價社團劃分質(zhì)量的標準。

(8)

公式(8)中，W為單分加權(quán)網(wǎng)絡(luò)的鄰接矩陣，其中元素W為節(jié)點之間權(quán)值，當節(jié)點之間存在連接，則Wij>0，否則Wij=0。

2.4　選擇運算

遺傳算法的原理從本質(zhì)上說基于達爾文的自然選擇學說。選擇提高了遺傳算法的驅(qū)動力。Holland提出的輪盤選擇是最為知名的選擇方式，其基本原理是根據(jù)每個染色體適應(yīng)值的比列來確定該個體的選擇概率或者保留概率。因此，在每一代種群中，根據(jù)適應(yīng)度函數(shù)，計算每個染色體(即每個個體)的適應(yīng)度概率，根據(jù)適應(yīng)度概率進行排序，通過建立一個輪盤模型來表示這些概率。選擇的過程就是旋轉(zhuǎn)輪盤若干次(次數(shù)等于社團的個數(shù))，每次為新種群選出一個個體作為優(yōu)秀個體參與下一代的遺傳操作。輪盤這種選擇方法的特點就是隨機采樣過程。

2.5　交叉運算

交叉算子根據(jù)交叉概率將種群中的兩個染色體隨機交換部分基因產(chǎn)生新的染色體，期望將有益基因組合在一起。目前，最常用的交叉運算是單點交叉，所謂單點交叉，即在染色體中隨機設(shè)置一個交叉點，互換該點前或后的個體對的部分結(jié)構(gòu)，從而產(chǎn)生新的個體對。在本算法過程中，染色體上的每個節(jié)點代表該節(jié)點所屬的社團，為了防止交叉過程中，出現(xiàn)父代信息的丟失，本文交叉采用單向交叉，即個體A、B交叉過程中，A中的某些節(jié)點替換B中的相應(yīng)節(jié)點，A中節(jié)點內(nèi)容保持不變，如圖4所示。

圖4　交叉算子

2.6　變異運算

變異同交叉一樣，也是遺傳算法中的核心內(nèi)容。所謂變異，即單個個體是遺傳過程中，由于環(huán)境等某些原因，造成個體自己上的某些節(jié)點以變異概率Pm發(fā)生變異。隨機生成范圍[0,1]的隨機數(shù)m，若m小于變異概率pm，則隨機選取某一位置進行變異。至此，產(chǎn)生新一代群體P(t+1)。

3仿真結(jié)果與分析

為了驗證本算法的有效性，將本算法應(yīng)用于在數(shù)據(jù)集Southern Women Data上對本文算法進行試驗分析。本文所有實驗均在Windows環(huán)境下，使用matlab7編程計算和繪圖。

美國南部Davis俱樂部數(shù)據(jù)是由Stephen提出的一個美國婦女參與活動的二分網(wǎng)絡(luò)，該網(wǎng)絡(luò)由18位婦女和14個活動組成，節(jié)點代表婦女，邊代表婦女參與的活動。

在本實驗中，染色體的長度設(shè)置為婦女總數(shù)18，并根據(jù)節(jié)點對之間的相似度和社團個數(shù)進行編碼，初始化社團個數(shù)為2個，遺傳代數(shù)為20次，隨機生成20個個體做為遺傳群體，交叉概率設(shè)為0.6，變異概率設(shè)為0.002。對于不同的社團個數(shù)，得到的最優(yōu)結(jié)果是不確定的，因此本實驗從劃分2個社團開始，逐步增加社團的個數(shù)，從中選擇使得模塊度最大的作為最優(yōu)解。

在該二分網(wǎng)絡(luò)中，每個活動節(jié)點的度中心性排列見表1。

表1　In-degree centrality

每個婦女節(jié)點的度中心性排列見表2。

表2　Out-degree centrality

運用本文的遺傳算法優(yōu)化二分網(wǎng)絡(luò)模塊度方法對南部婦女Davis數(shù)據(jù)進行社團結(jié)構(gòu)劃分，算法開始設(shè)置初始劃分社團個數(shù)為2個，每次遺傳迭代結(jié)束后，通過不斷改變社團個數(shù)，得到對應(yīng)的模塊度Q值。算法流程如圖5所示。

圖5　本文算法流程圖

結(jié)果顯示：當網(wǎng)絡(luò)被劃分為2個社團時，模塊度Q值最大約0.32，此時所有節(jié)點具有較好的社團結(jié)構(gòu)如圖6所示。

圖6　Q隨社團個數(shù)變化值

由圖6可以看出：當模塊度最大時，網(wǎng)絡(luò)被劃分為兩個社團。其中紅色節(jié)點代表婦女，藍色節(jié)點代表參與的活動，其中紅色婦女節(jié)點1~9被劃分一個社團，紅色婦女節(jié)點10~15被劃分為一個社團，節(jié)點16~18由于跟其他節(jié)點連接較少，處于游離狀態(tài)。該結(jié)果與使用Fast-Newman方法檢測的結(jié)果相差無幾，也進一步說明了本方法的有效性和準確性如圖7。

圖7　本文算法劃分結(jié)果

為了進一步驗證本算法的穩(wěn)定性，對同一數(shù)據(jù)集重復20次仿真實驗，仿真得到不同群體個數(shù)對應(yīng)的Q均值與單次仿真曲線圖擬合程度較高。

綜合仿真實驗結(jié)果表明：本文算法在單次仿真實驗中得出的結(jié)果較之以往算法更加精準，多次重復仿真實驗的結(jié)果與單次結(jié)果對比總體趨勢相同。因此，本算法更加精準，具有較強的魯棒性和抗干擾能力。

4結(jié)語

本文對復雜網(wǎng)絡(luò)進行了詳細的闡述，對二分網(wǎng)絡(luò)相關(guān)原理進行了介紹，提出了基于改進的遺傳算法和無向加權(quán)網(wǎng)絡(luò)模塊度劃分二分網(wǎng)絡(luò)的社團檢測方法。目前對二分網(wǎng)絡(luò)的社團檢測大多基于單分網(wǎng)絡(luò)，二分網(wǎng)絡(luò)在轉(zhuǎn)換為單分網(wǎng)絡(luò)時，會因為一些數(shù)據(jù)的丟失造成社團檢測分析出現(xiàn)誤差，因此，直接基于原始二分網(wǎng)絡(luò)的分析方法會成為后期研究的主要內(nèi)容。

參考文獻

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

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

[3]Guimera R, Ameral L A N. Functional cartography of complex metabolic networks[J]. Nature,2005,433(7028):895-900.

[4]White S, Smyth P. A spectral clustering approach to finding communities in graphs. 5th SIAM International Conference on Data Mining, Society for Industrial and Applied Mathematics, Philadelphia, 2005:274-285.

[5]Fortunato S, Barthelemy M. Resolution limit in community detection[J]. Proceedings of the National Academy of the United States of America, 2007,104(1):36-41.

[6]Sun Y, Danila B, Josic K, et al. Improved community structure detection using a modified fine-tuning strategy[J].Europhysics Letters, 2009,86(2), 28004.

[7]Good B H, DE Montjoye Y A, Clauset A. The performance of modularity maximization in practical contexts[J]. Physical Review E, 2010,81(4):046106.

[8]Li Z P, Zhang S H, Wang R S, et al. Quantitative function for community detection[J]. Physical Review E, 2008,77(3):036109.

[9]Wang G X, Shen Y, Ouyang M. A vector partitioning approach to detecting community structure in complex networks[J]. Computer & Mathematics with Applications, 2008,55(12):2746-2752.

[10]Ma X K, Gao L, Xuerong Y, et al. Semi-supervised clustering algorighm for community structure detection in complex networks[J]. Physical A: A Statistical Mechanics and its Applications, 2010,389(1):187-197.

[11]Newman M E J. Modularity and community structure in networks[J]. Proceedings of the National Academy of the United States of America, 2006,103(23):8577-8582.

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

[13]Fortunato S. Community detection in grahps[J]. Physics Reports, 2010,486(3):486-174.

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

[15]Radicchi F, Castellano C, Cecconi F, et al. Defining and identifying communities in networks[J]. Proceedings of the National Academy of the United States of America, 2004,101(9):2658-2663.

[16]Duch J, ARENAS A. Community detection in complex networks using extreme optimization[J]. Proceedings of the National Academy of Sciences of the United States of America, 2005,72(2):027104.

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

[18]Rosvall M, Bergstrom C T. A information theoretic framework for resolving community structure in complex networks[J]. Procceedings of the National Academy of the United States of America, 2007,104(18):7327-7331.

[19]Palla G, Dermyi I, Farkas I, et al. Uncovering the overlapping community structure of complex networks in nature and society[J]. Nature, 2005,435(7043):814-818.

[20]楊樹忠. 復雜網(wǎng)絡(luò)中的社團檢測問題研究[D]. 北京：北京交通大學, 2009, 3-4.

[21]Scott J. Social network analysisc: a handbook[M]. London: Sage Publications, 2000, 113-152.

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

[23]Boccaletti S, Latora V, Moreno Y, et al. Complex networks:structure and dynamics[J]. Physics Reports, 2006, 424(4):175-308.

[24]Ergun G. Human sexual contact network as a bipartite graph[J]. Physica A, 2002, 308:483-488.

[25]Newman M E J. Finding community strcture in networks using the eigenvectors of matrices. Physical Review E, 74:036104, 2006.

[26]Newman M E J. Detecting community structure in networks. The European Physical Journal B, 2004,38(2):321-330.

[27]Guimera R, Sales-pardo M, Amaral L A. Module identification in bipartite and directed network[J]. Physical Review E, 2007,76:036102.

[28]Barber M J. Modularity and community detection in bipartite networks[J]. Physical Review E, 76, 066102, 2007:1-9.

[29]Li Zhen ping, Zhang Shi hua, Wang Rui sheng, et al. Quantitative function for community detection[J]. Physical Review E, 2008, 77(3):109-117.

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

[31]Palla G, Barabasi A-L, Vicsek T. Quantifying social group evolution. Nature, 2007, 446:664-667.

[32]Michael J.Barber. Modularity and community detection in bipartite networks. Physical Review E.

(責任編輯陳小明)

作者簡介卜振興(1982—)，男，山東濟寧人，博士。研究方向為安全防范技術(shù)與工程。

基金項目社會安全基礎(chǔ)工作對象信息采集與提取技術(shù)研究(2013BAK02B01)。

中圖分類號D035.393