基于環(huán)路緊密度的復(fù)雜網(wǎng)絡(luò)社區(qū)挖掘方法

劉大有，楊建寧，楊 博，趙學(xué)華，金 弟

（1.吉林大學(xué) 計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院，長春 130012；2.吉林大學(xué) 符號(hào)與知識(shí)工程教育部重點(diǎn)實(shí)驗(yàn)室 長春 130012；3.天津大學(xué) 計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院，天津 300072）

網(wǎng)絡(luò)簇結(jié)構(gòu)是復(fù)雜網(wǎng)絡(luò)最普遍、最重要的拓?fù)浣Y(jié)構(gòu)屬性之一，具有同簇結(jié)點(diǎn)相互連接密集，異簇結(jié)點(diǎn)相互連接稀疏的特點(diǎn)。復(fù)雜網(wǎng)絡(luò)聚類方法旨在揭示出復(fù)雜網(wǎng)絡(luò)中真實(shí)存在的網(wǎng)絡(luò)簇結(jié)構(gòu)［1］。目前已存在很多復(fù)雜網(wǎng)絡(luò)社區(qū)挖掘算法，基本可分為三類：基于啟發(fā)式的社區(qū)挖掘算法［2-7］，基于優(yōu)化的社區(qū)挖掘算法［8-12］和基于概率生成模型的社區(qū)挖掘算法［13-16］?；趩l(fā)式的社區(qū)挖掘算法通常是給出社區(qū)挖掘的啟發(fā)式信息，通過這些啟發(fā)式知識(shí)來劃分社區(qū)。如MFC算法［17］，HITS 算 法［2］，GN 算 法［3］及 多 種 變 種［4-5］以及WH算法［6］。基于優(yōu)化的社區(qū)挖掘算法通常定義劃分社區(qū)的目標(biāo)函數(shù)，并優(yōu)化目標(biāo)函數(shù)使其達(dá)到最大值或接近目標(biāo)函數(shù)的最大值進(jìn)而得到社區(qū)的劃分結(jié)果。如譜方法［8-9］，圖分割 KL算法［10］，F(xiàn)N 算法［11］以及 GA 算法［12］?；诟怕噬赡Ｐ偷姆椒ㄍㄟ^建立網(wǎng)絡(luò)生成模型，并根據(jù)極大似然原理生成模型中的參數(shù)，從而得到網(wǎng)絡(luò)的社區(qū)劃分。典型代表是基于隨機(jī)塊模型（stochastic block model）的方法［14-15，18-19］。

如何合理地確定社區(qū)個(gè)數(shù)是很多復(fù)雜網(wǎng)絡(luò)社區(qū)挖掘方法面臨的難題。如何設(shè)計(jì)出能客觀評價(jià)社區(qū)結(jié)構(gòu)優(yōu)劣的目標(biāo)函數(shù)是現(xiàn)有方法特別是基于優(yōu)化的方法所面臨的另一個(gè)主要問題。Newman等人［20］提出網(wǎng)絡(luò)模塊度Q函數(shù)是最廣泛采用的一種優(yōu)化目標(biāo)，但研究發(fā)現(xiàn)Q函數(shù)存在分辨率極限等問題［21］。

2004年Radicchi等人［4］提出了連接聚類系數(shù)，認(rèn)為簇間邊應(yīng)很少出現(xiàn)在短回路中，否則短回路中其他多數(shù)連接也可能成為簇間連接，從而顯著增加簇間連接密度。文獻(xiàn)［4］將連接聚類系數(shù)定義為包含該鏈接的短回路數(shù)目，并認(rèn)為簇間連接的連接聚類系數(shù)應(yīng)小于簇內(nèi)連接，在算法每次迭代中刪除網(wǎng)絡(luò)中連接系數(shù)最小的連接，直到劃分出合理的社區(qū)。但算法時(shí)間復(fù)雜度較高。

本文屬于基于啟發(fā)式的社區(qū)挖掘算法，所用啟發(fā)性知識(shí)與文獻(xiàn)［4］相同，但提出了更為有效的短回路搜索策略和基于該策略的社區(qū)挖掘方法，并通過實(shí)驗(yàn)對環(huán)路與社區(qū)之間的聯(lián)系做了更為細(xì)致的分析。

1 環(huán)路緊密度算法（LTA）

1.1 算法基本思想

通過一次遍歷圖中所有的邊（假設(shè)研究的是無權(quán)無向圖），若i結(jié)點(diǎn)到j(luò)結(jié)點(diǎn)有兩條完全不重合的路徑，則說明i，j同屬于一個(gè)環(huán)路。若環(huán)路上結(jié)點(diǎn)的個(gè)數(shù)p小于某個(gè)特定的值α，則認(rèn)為此環(huán)路緊密。認(rèn)為緊密環(huán)路內(nèi)結(jié)點(diǎn)僅包含于一個(gè)社區(qū)，否則環(huán)路內(nèi)大部分邊會(huì)成為社區(qū)間連接，這樣會(huì)大大增加社區(qū)間的連接密度［4］。且認(rèn)為不在同一社區(qū)中的結(jié)點(diǎn)，即使結(jié)點(diǎn)之間存在兩條完全不重合的路徑，但這樣的兩條路徑所構(gòu)成的環(huán)路一般周長較長，即此環(huán)路一般是疏松的。通過合理設(shè)計(jì)算法，可通過一次遍歷網(wǎng)絡(luò)得到網(wǎng)絡(luò)中所有的緊密環(huán)路。表1為算法描述中使用的符號(hào)和定義。

表1 算法描述中用到的符號(hào)及說明Table 1 Symbols and description used in algorithm

步驟一：利用廣度優(yōu)先遍歷算法遍歷全圖。在當(dāng)前訪問結(jié)點(diǎn)集合中選取要訪問的結(jié)點(diǎn)。若結(jié)點(diǎn)之前未被訪問，則將其前向結(jié)點(diǎn)記錄，并將該結(jié)點(diǎn)的鄰居結(jié)點(diǎn)（不包含其前向結(jié)點(diǎn)）加入下次訪問結(jié)點(diǎn)集合，轉(zhuǎn)步驟四；若結(jié)點(diǎn)已被訪問，則必存在至少兩條不同的路徑能訪問到當(dāng)前結(jié)點(diǎn)，故存在環(huán)路，轉(zhuǎn)步驟二。

步驟二：找出遍歷到當(dāng)前結(jié)點(diǎn)的兩條不同的路徑，得到環(huán)路。判斷環(huán)路結(jié)點(diǎn)個(gè)數(shù)p是否滿足條件p≤α，若滿足則環(huán)路足夠緊密，轉(zhuǎn)步驟三；若不滿足條件，轉(zhuǎn)步驟四。

步驟三：若在所有環(huán)路中有兩個(gè)緊密環(huán)路有邊重合，則將兩個(gè)環(huán)路合并，將兩個(gè)環(huán)路合并后稱為一個(gè)核，若是當(dāng)前找到的緊密環(huán)路與某個(gè)核有邊重合，則將該環(huán)路合并到核內(nèi)，若在合并過程中引起某核與核之間有邊重合，同樣進(jìn)行合并。以此類推，得到最終的核；若該緊密環(huán)路不與任何環(huán)路或是核有邊重合，則做為獨(dú)立的核存在。

步驟四：若當(dāng)前訪問結(jié)點(diǎn)集合不空，在當(dāng)前訪問結(jié)點(diǎn)集合中選取一個(gè)結(jié)點(diǎn)做為下一次訪問的結(jié)點(diǎn)，轉(zhuǎn)步驟一；若當(dāng)前訪問結(jié)點(diǎn)集合為空，轉(zhuǎn)步驟五。

步驟五：若待訪問結(jié)點(diǎn)集合為空，算法結(jié)束。轉(zhuǎn)步驟六。

步驟六：最后將不在任何核中的結(jié)點(diǎn)通過計(jì)算其與各個(gè)核的緊密程度，取與各個(gè)核中最為緊密的的核作為其社區(qū)歸屬。

算法只需一次遍歷整個(gè)圖，便可以得到圖中的所有最小環(huán)路，通過合并環(huán)路與環(huán)路、環(huán)路與核、核與核，最終得到核的個(gè)數(shù)作為社區(qū)的個(gè)數(shù)。

1.2 基本的LTA算法

S表示結(jié)點(diǎn)結(jié)合，Sg表示從S0開始算起，第g代待訪問結(jié)點(diǎn)的集合，即從種子結(jié)點(diǎn)，遍歷g步得到的結(jié)點(diǎn)集合，?i，Si∈S。從V中選取種子結(jié)點(diǎn)seed，把seed加入到S0中。算法的偽代碼如算法1（應(yīng)用于非加權(quán)網(wǎng)絡(luò)）所示。

算法1：

1.3 擴(kuò)展的LTA算法

LTA算法對α值較敏感，若要得到真實(shí)的社區(qū)劃分，需設(shè)定恰當(dāng)?shù)摩林?。把算法擴(kuò)展到有權(quán)無向圖中，使算法的應(yīng)用范圍更廣。

擴(kuò)展后算法的主要目的是尋找在加權(quán)網(wǎng)絡(luò)中的緊密環(huán)路以及各個(gè)社區(qū)的核結(jié)點(diǎn)。其中計(jì)算環(huán)路緊密性包括兩方面：

式（1）與式（2）分別表示加權(quán)圖環(huán)路緊密值和環(huán)路周長。對Cfk，pk限制條件亦改為兩方面：

特別地，當(dāng)圖中邊的權(quán)重都為1（無權(quán)無向圖）時(shí)，Cfk＝pk。

根據(jù)以上內(nèi)容對LTA算法進(jìn)行擴(kuò)展，如算法2（應(yīng)用于加權(quán)網(wǎng)絡(luò)）所示。

算法2：

此修改使得LTA不能找到所有環(huán)路，為找到所有環(huán)路，可采用多次LTA，對每次LTA得到的結(jié)果進(jìn)行合并，亦可達(dá)到很好的效果。例如洪泛得到的兩個(gè)核集分別用X，Y 表示。X中含有個(gè) 核，Y 中 含 有個(gè) 核。則 對 （?i，?j）combine（Xi，Yj）。用cooccuri，j來表示核Xi和核Yj之間共現(xiàn)的結(jié)點(diǎn)數(shù)，若或則執(zhí)行合并Xi和Yj。若Xi和Yj未能執(zhí)行合并操作，則將Xi∩Yj中結(jié)點(diǎn)社區(qū)歸屬均置為空，在1.1節(jié)步驟六中作為未被加入到核結(jié)構(gòu)的結(jié)點(diǎn)做算法后處理。

1.4 算法后處理

通過LTA算法計(jì)算得到C，將C中每個(gè)核作為一個(gè)社區(qū)，而C并不包含圖G中所有的結(jié)點(diǎn)，會(huì)有一些結(jié)點(diǎn)本身就不在環(huán)路中（如該結(jié)點(diǎn)的度為1），此時(shí)要對LTA算法運(yùn)行的結(jié)果進(jìn)行后處理。處理辦法是計(jì)算各社區(qū)中包含該結(jié)點(diǎn)鄰居數(shù)最多的社區(qū)，并將其作為其本身的社區(qū)歸屬，見算法3（LTA的后處理算法）。

算法3：

1.5 算法效率分析

算法利用寬度優(yōu)先遍歷策略遍歷圖中每一條邊，故時(shí)間復(fù)雜度為O（m）；算法在檢測到某結(jié)點(diǎn)存在于環(huán)路中時(shí)，計(jì)算環(huán)路周長以及Cf值的時(shí)間復(fù)雜度為O（αnlog（n））；故總體上算法的時(shí)間復(fù)雜度為：O（m＋αnlog（n）），對于稀疏網(wǎng)絡(luò)為：O（αnlog（n））。

2 實(shí)驗(yàn)與評估

論文中實(shí)驗(yàn)設(shè)備為個(gè)人PC，中央處理器為Intel（R）Core（TM）2Duo CPU E8400 ＠3.00GHz 2.99GHz，內(nèi)存為 4.00GB（3.46GB usable），操作系統(tǒng)為 Windows 732b。所用編程語言是Matlab。

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

為了評估算法的有效性，論文利用文獻(xiàn)［22］提出的Lancichinetti model基準(zhǔn)數(shù)據(jù)模型作為數(shù)據(jù)生成器，該模型提供了豐富的網(wǎng)絡(luò)屬性參數(shù)設(shè)置，包括最大度，平均度，度分布，網(wǎng)絡(luò)社區(qū)最大規(guī)模，網(wǎng)絡(luò)社區(qū)最小規(guī)模，網(wǎng)絡(luò)社區(qū)重疊比例，結(jié)點(diǎn)個(gè)數(shù)，網(wǎng)絡(luò)社區(qū)多重度分布和網(wǎng)絡(luò)社區(qū)多重規(guī)模分布的設(shè)置。論文采用normalized mutual information（NMI）對算法挖掘社區(qū)的精度進(jìn)行評估。

采用Lancichinetti model共生成3組數(shù)據(jù)，皆為無權(quán)無向圖。第1組數(shù)據(jù)用來分析環(huán)路結(jié)點(diǎn)個(gè)數(shù)閾值α對社區(qū)挖掘效果的影響。第2組數(shù)據(jù)用來測試算法挖掘網(wǎng)絡(luò)社區(qū)的精度。第3組數(shù)據(jù)用來測試算法挖掘網(wǎng)絡(luò)的效率。

（1）第1組網(wǎng)絡(luò)數(shù)據(jù)。設(shè)置結(jié)點(diǎn)個(gè)數(shù)n為128，社區(qū)最小規(guī)模Cmin為10（網(wǎng)絡(luò)社區(qū)規(guī)模指其中包含的網(wǎng)絡(luò)結(jié)點(diǎn)數(shù)目），網(wǎng)絡(luò)最大規(guī)模Cmax為50，網(wǎng)絡(luò)結(jié)點(diǎn)最大度dmax為20，網(wǎng)絡(luò)結(jié)點(diǎn)平均度davg設(shè)置為4到13，社區(qū)間重疊結(jié)點(diǎn)比例μ設(shè)置為0.05。網(wǎng)絡(luò)結(jié)點(diǎn)度分布指數(shù)τ1設(shè)置為－1，網(wǎng)絡(luò)社區(qū)規(guī)模分布指數(shù)τ2設(shè)置為－1。共10小組不同的設(shè)置，且根據(jù)每小組的數(shù)據(jù)設(shè)置，重復(fù)生成10個(gè)網(wǎng)絡(luò)，共100個(gè)網(wǎng)絡(luò)。

（2）第2組網(wǎng)絡(luò)數(shù)據(jù)。設(shè)置n為128，Cmin為50，Cmax為70，dmax為20，davg為15，τ1為－1，τ2為－1，μ為從0.05到0.5共10小組不同的設(shè)置。特別地，當(dāng)μ設(shè)置為0時(shí)，表示社區(qū)間沒有邊連接，相當(dāng)于各個(gè)社區(qū)是獨(dú)立的連通子圖，其挖掘精準(zhǔn)度應(yīng)為1。且根據(jù)每小組的數(shù)據(jù)設(shè)置重復(fù)生成10個(gè)網(wǎng)絡(luò)，共100個(gè)網(wǎng)絡(luò)。

③第3組網(wǎng)絡(luò)數(shù)據(jù)。n為從500到5000，Cmin為20，Cmax為100，dmax為20，davg設(shè)為15，τ1為－1，τ2為－1，μ為0.05，共10小組不同的數(shù)據(jù)。特別地，當(dāng)n設(shè)置為0時(shí)，表示網(wǎng)絡(luò)沒有結(jié)點(diǎn)，則算法運(yùn)行時(shí)間應(yīng)為0s。

LTA算法中主要的參數(shù)為α和β，鑒于Lancichinetti model未提供生成加權(quán)人工數(shù)據(jù)的功能，實(shí)驗(yàn)只對α做分析。試驗(yàn)中，α分別取3到9共7個(gè)值?；鶞?zhǔn)網(wǎng)絡(luò)平均度davg為4到13，隨著davg的增加，網(wǎng)絡(luò)稠密度增加，則理論上社區(qū)間連接更加緊密，若要正確挖掘網(wǎng)絡(luò)中的社區(qū)，則對α值的要求應(yīng)愈加嚴(yán)格。如圖1所示。算法在davg分別取4，5和α取3到6時(shí)，算法挖掘社區(qū)的精度均能達(dá)到90%以上，隨著davg的增大，網(wǎng)絡(luò)稠密度增加，社區(qū)挖掘的高精度對α的要求越來越苛刻。所幸的是，在圖1中可以看到當(dāng)α＝3時(shí)，能從容面對davg在所有取值下的人工網(wǎng)絡(luò)。此結(jié)論也從另一方面說明同處于α＝3的緊密環(huán)路的結(jié)點(diǎn)在很大程度上處于同一網(wǎng)絡(luò)社區(qū)。

圖1 不同α取值情況下的NMI變化情況Fig.1 NMI variations in terms ofα

圖2 不同網(wǎng)絡(luò)對應(yīng)的NMI變化情況Fig.2 NMI variations in terms of different networks

利用第2組數(shù)據(jù)進(jìn)行實(shí)驗(yàn)得到的結(jié)果如圖2所示。圖2中y軸表示每小組網(wǎng)絡(luò)執(zhí)行LTA結(jié)果的NMI精度值，x軸表示每小組網(wǎng)絡(luò)對應(yīng)的μ值。圖中紅色曲線表示10組網(wǎng)絡(luò)執(zhí)行結(jié)果NMI精度平均值曲線。從圖2中可知，當(dāng)μ為0、0.05和0.1時(shí)算法挖掘精度接近為1，隨著μ值的增大，網(wǎng)絡(luò)社區(qū)結(jié)構(gòu)越來越不明顯，挖掘精度也隨之下降。算法較適合社區(qū)間連接稀疏的網(wǎng)絡(luò)。

為了更好地對算法的執(zhí)行效率進(jìn)行分析，現(xiàn)對結(jié)點(diǎn)數(shù)目從500到5000的網(wǎng)絡(luò)逐一測試，所得結(jié)果如圖3所示。

圖3 LTA算法運(yùn)行時(shí)間圖Fig.3 Running time of the LTA

2.2 真實(shí)基準(zhǔn)網(wǎng)絡(luò)數(shù)據(jù)集

為了進(jìn)一步驗(yàn)證算法的可行性，算法使用無權(quán)無向圖Dolphin網(wǎng)絡(luò)［23］對LTA進(jìn)行實(shí)驗(yàn)。另采用Karate加權(quán)無向網(wǎng)絡(luò)［24］對擴(kuò)展LTA進(jìn)行實(shí)驗(yàn)。

2.2.1 Dolphin網(wǎng)絡(luò)

圖4中所示的紅色結(jié)點(diǎn)和藍(lán)色結(jié)點(diǎn)分別表示LTA算法找到的兩個(gè)核，白色結(jié)點(diǎn)表示未加入核的結(jié)點(diǎn)。分析發(fā)現(xiàn)結(jié)點(diǎn)dn63在環(huán)內(nèi)，但未被加入到核中，這是因?yàn)槠涮幱趦缮鐓^(qū)邊緣區(qū)域，如前文分析，這種情況的出現(xiàn)對社區(qū)的劃分有促進(jìn)作用，更有助于準(zhǔn)確進(jìn)行社區(qū)挖掘。對圖4中填充色為白色的結(jié)點(diǎn)進(jìn)行后處理，依據(jù)算法GetGroup對圖4中結(jié)果后處理所得結(jié)果如圖5所示。此實(shí)驗(yàn)結(jié)果完全符合Dolphin網(wǎng)絡(luò)的實(shí)際社區(qū)劃分情況。

圖4 Dolphin網(wǎng)絡(luò)的核結(jié)構(gòu)圖Fig.4 The cores structure of the Dolphin network

圖5 Dolphin網(wǎng)絡(luò)的社區(qū)結(jié)構(gòu)圖Fig.5 The communities structure of the Dolphin network

2.2.2 Karate網(wǎng)絡(luò)

為了驗(yàn)證LTA對加權(quán)圖擴(kuò)展算法的可行性，用加權(quán)Karate網(wǎng)絡(luò)作為測試數(shù)據(jù)。實(shí)驗(yàn)前的鄰接矩陣和結(jié)構(gòu)圖分別如圖6和圖7所示，其中圖6中X軸和Y軸表示對應(yīng)結(jié)點(diǎn)的編號(hào)，藍(lán)色點(diǎn)表示對應(yīng)結(jié)點(diǎn)之間的邊。

執(zhí)行算法LTA，得到網(wǎng)絡(luò)核結(jié)構(gòu)對應(yīng)的鄰接矩陣和結(jié)構(gòu)圖分別如圖8和圖9所示。圖8中紅色（藍(lán)色）正方形內(nèi)中的藍(lán)色點(diǎn)表示得到的一個(gè)核結(jié)構(gòu)所包含的邊集，稱為紅色（藍(lán)色）核。圖9所示為所得兩個(gè)核的結(jié)構(gòu)圖，其中未加入核的結(jié)點(diǎn)未在圖中繪出。

依據(jù)算法GetGroup進(jìn)行后處理所得結(jié)果的鄰接矩陣和結(jié)構(gòu)圖分別如圖10和圖11所示。圖10中紅色（藍(lán)色）正方形中所含邊集對應(yīng)圖8，圖9中的紅色（藍(lán)色）核。圖11表示對應(yīng)的紅色社區(qū)與藍(lán)色社區(qū)結(jié)構(gòu)圖。所得結(jié)果與真實(shí)社區(qū)劃分完全相同。

圖6 Karate網(wǎng)絡(luò)的鄰接矩陣圖Fig.6 The adjacency matrix of Karate network

對于Karate網(wǎng)絡(luò)，其結(jié)構(gòu)圖利用Netdraw工具畫出，且此工具包含對圖的faction分析。其中faction分析包含兩種模式：Quality模式和Speed模式。利用faction分析中的Quality模式分析得到的圖與論文中LTA算法實(shí)驗(yàn)得到的結(jié)果完全相同。而在Speed模式下，結(jié)點(diǎn)16被分到圖中的紅色社區(qū)。仔細(xì)研究結(jié)點(diǎn)16發(fā)現(xiàn)，其處于社區(qū)的邊緣，故將其劃分到任一社區(qū)皆可，其效果如圖12所示。

圖7 Karate網(wǎng)絡(luò)的結(jié)構(gòu)圖Fig.7 The structure of the Karate club network

圖8 Karate網(wǎng)絡(luò)的核鄰接矩陣圖Fig.8 The adjacency matrix of the cores of Karate

圖9 Karate網(wǎng)絡(luò)的核結(jié)構(gòu)圖Fig.9 The cores structure of the Karate club network

圖10 Karate網(wǎng)絡(luò)的社區(qū)鄰接矩陣圖Fig.10 The adjacency matrix of Karate network

圖11 Karate網(wǎng)絡(luò)的核結(jié)構(gòu)圖Fig.11 The communities structure of the Karate club network

圖12 利用Netdraw工具對Karate網(wǎng)絡(luò)的分析結(jié)果Fig.12 The results of using Netdraw to analyze the Karate club network

3 結(jié)束語

針對社區(qū)挖掘問題，研究了網(wǎng)絡(luò)中環(huán)路緊密度與社區(qū)結(jié)構(gòu)的關(guān)系，進(jìn)而提出了基于環(huán)路緊密度的社區(qū)挖掘算法LTA。LTA算法的一個(gè)主要優(yōu)點(diǎn)是不需事先指定社區(qū)個(gè)數(shù)K。實(shí)驗(yàn)結(jié)果表明：LTA算法挖掘精度較高，且算法穩(wěn)定性較好；同時(shí)，還驗(yàn)證了處于同一緊密環(huán)路中的兩個(gè)結(jié)點(diǎn)處于同一社區(qū)的概率較大，處于不同社區(qū)的兩個(gè)結(jié)點(diǎn)處于不同環(huán)路的概率較大這一思想；此外發(fā)現(xiàn)當(dāng)LTA算法將參數(shù)α設(shè)置為3時(shí)，處于同一緊密環(huán)路中的結(jié)點(diǎn)會(huì)以極大概率出現(xiàn)在同一社區(qū)中。

［1］楊博，劉大有，Liu Ji－ming，等.復(fù)雜網(wǎng)絡(luò)聚類方法［J］.軟件學(xué)報(bào)，2009，20（1）：54－66.Yang Bo，Liu Da－you，Liu Ji－ming，et al.Complex network clustering algorithms［J］.Journal of Software，2009，20（1）：54－66.

［2］Kleinberg J M.Authoritative sources in a hyperlinked environment［J］.Journal of the ACM （JACM），1999，46：604－632.

［3］Girvan M，Newman M E J.Community structure in social and biological networks［J］.Proceedings of the National Academy of Sciences，2002，99：7821.

［4］Radicchi F，Castellano C，Cecconi F，et al.Defining and identifying communities in networks［J］.Proceedings of the National Academy of Sciences of the United States of America，2004，101：2658.

［5］Tyler J R，Wilkinson D M，Huberman B A.Email as spectroscopy：Automated discovery of community structure within organizations［J］.The Information Society，2005，21（2）：143－153.

［6］Wu F，Huberman B A.Finding communities in linear time：aphysics approach［J］.The European Physical Journal B－Condensed Matter and Complex Systems，2004，38：331－338.

［7］Yang B，Cheung W K，Liu J.Community mining from signed social networks［J］.IEEE Transactions on.Knowledge and Data Engineering，2007，19：1333－1348.

［8］Pothen A，Simon H D，Liou K P.Partitioning sparse matrices with eigenvectors of graphs［J］.Siam J Matrix Anal Applic，1990，11：430－452.

［9］Fiedler M.Algebraic connectivity of graphs［J］.Czech－oslovak Mathematical Journal，1973，23：298－305.

［10］Kernighan B W，Lin S.An efficient heuristic procedure for partitioning graphs［J］.Bell System Technical Journal，1970，49：291－307.

［11］Newman MEJ.Fast algorithm for detecting community structure in networks［J］.Physical Review E，2004，69：066133.

［12］Guimera R，Amaral L A N.Functional cartography of complex metabolic networks［J］.Nature 2005，433：895－900.

［13］Xing E P，Jordan M I，Russell S.A Generalized Mean Field Algorithm for Variational Inference in Exponential Families.Uncertinty in AI 2003.

［14］Fu W，Song L，Xing E P.Dynamic mixed membership blockmodel for evolving networks［C］∥In Proceedings of the 26th Annual International Conference on Machine learning，2009：329－336.

［15］Airoldi E M，Blei D M，F(xiàn)ienberg S E，et al.Mixed membership stochastic blockmodels［J］.The Journal of Machine Learning Research，2008，9：1981－2014.

［16］Wang Y J，Wong G Y.Stochastic blockmodels for directed graphs［J］.Journal of the American Statistical Association，1987：8－19.

［17］Flake G W，Lawrence S，Giles C L，et al.Self－organization and identification of web communities［J］.Computer，2002；35：66－70.

［18］Hofman J M，Wiggins C H.Bayesian approach to network modularity［J］.Physical Review Letters，2008，100：258701.

［19］Holland P W，Leinhardt S.Local structure in social networks［J］.Sociological methodology 1976，7：1－45.

［20］Newman M E J，Girvan M.Finding and evaluating community structure in networks［J］.Physical Review E，2004，69（2）：026113.

［21］Guimera R，Sales－Pardo M，Amaral L A N.Modularity from fluctuations in random graphs and complex networks［J］.Physical Review E，2004，70：025101.

［22］Lancichinetti A，F(xiàn)ortunato S.Benchmarks for testing community detection algorithms on directed and weighted graphs with overlapping communities［J］.Physical Review E，2009，80：016118.

［23］Lusseau D，Schneider K，Boisseau O J，et al.The bottlenose dolphin community of doubtful sound features a large proportion of long－lasting associations［J］.Behavioral Ecology and Sociobiology，2003，54：396－405.

［24］Zachary W W.An information flow model for conflict and fission in small groups［J］.Journal of Anthropological Research，1977：452－473.