針對檢測網(wǎng)絡(luò)社區(qū)的一種高效、規(guī)則化方法(論文翻譯).docx

針對檢測網(wǎng)絡(luò)社區(qū)的一種高效、規(guī)則化方法Brian Ball,1 Brian Karrer,1 and M. E. J. Newman1, 21Department of Physics, University of Michigan, Ann Arbor, MI 48109, U.S.A.2Center for the Study of Complex Systems, University of Michigan, Ann Arbor, MI 48109, U.S.A.在對網(wǎng)絡(luò)數(shù)據(jù)進(jìn)行分析時面臨的一個基本問題便是如何完成對由高密度互聯(lián)結(jié)點（這些結(jié)點可能重疊或相交）組成的網(wǎng)絡(luò)社區(qū)的檢測。在這里我們描述了一種基于使用生成網(wǎng)絡(luò)模型的規(guī)則化統(tǒng)計方法來尋找重疊社區(qū)的方法。我們將展現(xiàn)這個方法是如何通過使用一種快速的、封閉形式的最大值期望算法來實現(xiàn)網(wǎng)絡(luò)分析的，這種方法使得我們能夠在合理的運行時間內(nèi)完成對于含有百萬數(shù)量級結(jié)點的網(wǎng)絡(luò)進(jìn)行分析。這種方法已經(jīng)在現(xiàn)實世界存在的網(wǎng)絡(luò)和虛擬的基準(zhǔn)測試網(wǎng)絡(luò)中進(jìn)行了實驗，得出的結(jié)論是這種方法對于這兩種類型的網(wǎng)絡(luò)都是適用的。并且利用松弛策略，該算法還可以用來進(jìn)行非重疊的社區(qū)分割，結(jié)果表明這種算法對于解決無重疊網(wǎng)絡(luò)社區(qū)問題也是相對快速和精確的。I引言研究表明，很多網(wǎng)絡(luò)系統(tǒng)（包括生物網(wǎng)絡(luò)和社交網(wǎng)絡(luò)）被自然地劃分為若干模塊（或稱社區(qū)），這些模塊由一組結(jié)點構(gòu)成并且模塊內(nèi)的結(jié)點聯(lián)系緊密而模塊間的聯(lián)系則相對較少。根據(jù)上下文可以判斷出這些結(jié)點或無交集，或相互重疊。在最近的十年里，在網(wǎng)絡(luò)理論研究領(lǐng)域，如何在實驗網(wǎng)絡(luò)數(shù)據(jù)中檢測發(fā)現(xiàn)這樣的結(jié)點信息則成為了一項亟待解決的問題，這個問題也引起了很多研究者的研究熱情。一個優(yōu)良的社區(qū)檢測方案應(yīng)該具有某些理想的性能。首先，它必須是高效的，要能夠精確地分析出社區(qū)結(jié)構(gòu)。例如，社區(qū)結(jié)構(gòu)應(yīng)該能夠廣泛適用于自然存在的和虛擬合成的種種網(wǎng)絡(luò)，并且在其中分析得出適用的結(jié)構(gòu)。其次，基于嚴(yán)格的理論原則依據(jù)的方法要優(yōu)先于那些沒有使用該原則的方法。相比于可通過證明得出或是具有基本數(shù)學(xué)原理的方法相比，那些僅僅依靠純粹直覺去研究事物可能的發(fā)展走向的方法顯然難以讓人信服。最后，這個方法還應(yīng)該具有快速和規(guī)模適中的特點。當(dāng)前科學(xué)研究中的很多網(wǎng)絡(luò)都非常龐大，它們包含百萬甚至千百萬數(shù)量級的結(jié)點。所以我們要優(yōu)先考慮的應(yīng)該是隨網(wǎng)絡(luò)擴(kuò)張運行時間呈線性增長的網(wǎng)絡(luò)算法而非那些呈平方級或立方級增長的算法。本文中我們推導(dǎo)出一個可以找出重疊及非重疊社區(qū)的社區(qū)檢測算法并且證明出其滿足上述所有要求。此算法在標(biāo)準(zhǔn)基準(zhǔn)測試中對于已知社區(qū)結(jié)構(gòu)的檢測上表現(xiàn)出與最佳前向算法相似的性能。此算法是基于已有方法的統(tǒng)計推斷得出的，也就是說它是一個追求極大似然和最大期望并且高效的算法。在其最簡單的表現(xiàn)形式中它僅包含兩組方程的迭代，每種迭代所需時間僅隨系統(tǒng)規(guī)模增大而呈線性增長。在實際應(yīng)用中，此算法能夠在一臺普通的臺式電腦上并且在合理的運行時間里處理擁有百萬級結(jié)點和邊的網(wǎng)絡(luò)。我們已經(jīng)完成分析的最大網(wǎng)絡(luò)擁有400萬結(jié)點和4000萬條邊。我們將尋找重疊社區(qū)作為網(wǎng)絡(luò)檢測問題的出發(fā)點。在社區(qū)檢測問題上最早的努力可以追溯到上個世紀(jì)70年代，當(dāng)時假定社區(qū)是無重疊的或者無交集的。但正如很多研究人員最近這些年爭論的那樣，在實際情形中社區(qū)重疊是普遍存在的。例如在社交網(wǎng)絡(luò)中，一個人常會擁有不止一個熟人圈，諸如家庭，朋友，同事等等。很明顯在這些圈子中存在著至少一個共同成員（也即其本人），也就是說存在著重疊。在生物網(wǎng)絡(luò)中很多結(jié)點可以從屬于不止一個群體。在一個新陳代謝網(wǎng)絡(luò)系統(tǒng)中，一個物種的代謝產(chǎn)物可以在不止一個代謝過程或循環(huán)系統(tǒng)中起作用。在食物鏈中一些物種可以落入兩個毫無交集的子社區(qū)的邊界并且在這兩個子社區(qū)中都起作用。因此解決網(wǎng)絡(luò)社區(qū)檢測問題的一般性方法應(yīng)當(dāng)允許結(jié)點重疊。我們的研究將首先提出一個對于這種一般問題的解決方案，接著我們將展現(xiàn)此方法的一個變體是如何被應(yīng)用到無重疊結(jié)點社區(qū)中的。我們通過將一個隨機(jī)生成的網(wǎng)絡(luò)結(jié)構(gòu)模型應(yīng)用到實際測得的網(wǎng)絡(luò)數(shù)據(jù)中來處理重疊社區(qū)的檢測。這種將統(tǒng)計推斷方法應(yīng)用到網(wǎng)絡(luò)中的方法已經(jīng)被一批學(xué)者探索應(yīng)用于無重疊結(jié)點的網(wǎng)絡(luò)研究中（其中也包含一些數(shù)十年前的工作）。然而將同樣的方法拓展到有重疊的情形則并不容易。一個關(guān)鍵步驟就是發(fā)明一種可以產(chǎn)生與現(xiàn)實中存在網(wǎng)絡(luò)相似的擁有重疊社區(qū)結(jié)構(gòu)網(wǎng)絡(luò)的生成模型。以前被使用的大多數(shù)是一種稱為“混合成員”的模型，這種模型中結(jié)點可以隸屬于多個群組并且擁有超過一個共同群組的兩個結(jié)點更容易產(chǎn)生聯(lián)系。然而這也就意味著兩個社區(qū)的重疊區(qū)要比那些僅落入一個單一社區(qū)的區(qū)域擁有更高平均密度的邊。我們并不清楚這樣的模型是否能夠準(zhǔn)確反映出現(xiàn)實世界中存在的網(wǎng)絡(luò)，但可以肯定的是我們能夠構(gòu)造出這種網(wǎng)絡(luò)結(jié)構(gòu)之外的網(wǎng)絡(luò)。理想情況下，我們更傾向于一種限制少且對于重疊社區(qū)結(jié)構(gòu)少做假設(shè)的模型。另一組檢測重疊社區(qū)的方法是基于本地社區(qū)結(jié)構(gòu)的，這些方法在網(wǎng)絡(luò)中根據(jù)對于本地聯(lián)系模式的分析并且忽略全局網(wǎng)絡(luò)結(jié)構(gòu)來尋找本地群組，而不是一次性將整個網(wǎng)絡(luò)分割成不同社區(qū)。當(dāng)在整個網(wǎng)絡(luò)中生成大量這樣的獨立本地社區(qū)的時候，這樣的方法自然會產(chǎn)生重疊社區(qū)。并且，這樣的社區(qū)更趨向于成為緊縮和互聯(lián)的子圖結(jié)構(gòu)，這種需求并不總是適用于其他方法。與之相對的全局檢測方法則能夠更好地捕捉到大型網(wǎng)絡(luò)結(jié)構(gòu)并且當(dāng)為其加上特別的必須滿足的限制（如必須滿足對于社區(qū)數(shù)量的限制）時更為精確。本文中我們找到一種全局統(tǒng)計的方法用來檢測重疊社區(qū)。這種方法是基于一種已經(jīng)被一批研究物理文學(xué)及機(jī)器學(xué)習(xí)的學(xué)者在各自研究領(lǐng)域獨立提出的連接網(wǎng)絡(luò)的思想。此觀點認(rèn)為在一個網(wǎng)絡(luò)中當(dāng)出現(xiàn)不同類型的邊時社區(qū)就會產(chǎn)生。例如，在社交網(wǎng)絡(luò)中，我們用連接來代表家庭聯(lián)系，友情關(guān)聯(lián)，工作關(guān)系等等。如果我們可以識別出邊的不同類型，我們就能夠識別出上述種種關(guān)系。如果在網(wǎng)絡(luò)中我們不僅將結(jié)點聚集，并且也將邊聚集的話，我們就能夠根據(jù)連接結(jié)點的邊的類型推導(dǎo)出由結(jié)點組成的社區(qū)。在以自然方式（如果一個結(jié)點擁有不止一種類型的邊則其屬于不止一個社區(qū)）產(chǎn)生重疊社區(qū)的時候這種方法表現(xiàn)出與我們關(guān)于社區(qū)結(jié)構(gòu)的起源和本質(zhì)的感性認(rèn)識上很好的一致性。先前發(fā)現(xiàn)連接社區(qū)的方法使用的是一種通過對網(wǎng)絡(luò)中邊的可能劃分進(jìn)行優(yōu)化的啟發(fā)式特征函數(shù)。這樣的特征函數(shù)，尤其是其中的模塊函數(shù)，在過去被用于無重疊社區(qū)的研究中。雖然在實際應(yīng)用中這些函數(shù)往往能夠給出合理的結(jié)果，它們?nèi)匀淮嬖谥恍┤毕荩豪?，模塊不能用于發(fā)現(xiàn)那些很小的社區(qū)，可能產(chǎn)生不唯一的優(yōu)化，從某種形式觀點看有一些不盡如意的地方等等。比爾克和陳（音譯）最近的研究結(jié)果表明這些缺陷可以通過摒棄使用特征函數(shù)方法，取而代之，采用將一個生產(chǎn)模式加入到數(shù)據(jù)中的方法而得以糾正。這也是我們采取的方法，只是對于一個適用于連接社區(qū)的模型的定義需要稍作改動。在結(jié)點社區(qū)的生成模型中可以先將結(jié)點指派群組然后根據(jù)這樣的指派為其分配邊。但是在根據(jù)邊而進(jìn)行劃分的連接社區(qū)的模型中，除非邊已存在，否則我們不可以為群組指派邊。因此邊和它們的群組信息要同時生成。下文中我們將詳述此目標(biāo)是如何實現(xiàn)的。一旦我們獲得這樣的模型，接下的目標(biāo)就將是確定模型中的與觀測到的網(wǎng)絡(luò)最佳匹配的參數(shù)的權(quán)值，并且根據(jù)這些值來確定重疊結(jié)點社區(qū)。本文的結(jié)構(gòu)大致如下：首先我們將定義我們使用的模型然后說明各參數(shù)的最適取值是如何通過使用一個極大似然算法而計算出來的。這個算法在其最簡形式中只是適中快速的，但我們可以證明得出此模型的大量參數(shù)會迅速收斂到平均值，因此可以進(jìn)行剪枝計算。我們?yōu)檫@種剪枝提供了一種解決方案，得出一種適用于特大規(guī)模網(wǎng)絡(luò)的快速算法。我們?yōu)榇罅康默F(xiàn)實世界網(wǎng)絡(luò)以及虛擬構(gòu)造網(wǎng)絡(luò)都提供了應(yīng)用程序示例以證明此算法可以從這些網(wǎng)絡(luò)中發(fā)現(xiàn)已知的重疊社區(qū)。最后，我們通過使用在重疊社區(qū)劃分中為各個節(jié)點僅指定一個其依賴性最強(qiáng)的社區(qū)的技術(shù)來展示這種方法是如何被應(yīng)用于探測無重疊社區(qū)的。我們證明得出對于無連接的社區(qū)而言，這種直覺式啟發(fā)算法可以通過將連接社區(qū)模型看成是一種隨機(jī)障礙模型的松弛這樣的方法得以嚴(yán)格修正。之前提出的適用這種障礙模型的各種算法因它們的運行時間與結(jié)點規(guī)模呈至少平方級增長而只能局限于在一些規(guī)模較小的網(wǎng)絡(luò)上進(jìn)行使用。本文中提出的算法其速度有了顯著提升因此可以用于超大規(guī)模網(wǎng)絡(luò)中無連接社區(qū)的檢測。II一種適用于連接社區(qū)的生成模型首先我們將定義我們即將使用的生成網(wǎng)絡(luò)模型。此模型通過給定結(jié)點數(shù)n、社區(qū)數(shù)以及連接這些社區(qū)的無向邊來生成網(wǎng)絡(luò)。為方便起見，我們用種不同的顏色代表不同的社區(qū)，并且為屬于每個社區(qū)的邊著上各自的顏色，則這個模型就可用一系列的參數(shù)iz，表示結(jié)點i擁有顏色為z的邊的比例。特別的，izjz表示在結(jié)點i和j之間顏色為z的邊的期望值，其平均值服從泊松分布。這意味著技術(shù)上這是一種多重圖（一對結(jié)點之間可以擁有不止一條邊）。而大多數(shù)現(xiàn)實存在的網(wǎng)絡(luò)只擁有單邊，因此從這個角度看這個模型并不現(xiàn)實。然而允許多重邊的存在使得此模型變得極為簡單，在實際運用中iz的值很小因此多重邊的數(shù)量以及引入的誤差都是小規(guī)模的。在大多數(shù)其他隨機(jī)網(wǎng)絡(luò)圖模型（例如，廣泛研究的配置模型）中也進(jìn)行同樣的近似。我們的模型同樣允許自聯(lián)邊，即兩端為同一結(jié)點的邊，其期望值為12iziz，之所以乘以二分之一是為了和之后的結(jié)果保持一致。同樣自聯(lián)邊的出現(xiàn)極大地簡化了邏輯上的拓展并且對于包括配置模型在內(nèi)的隨機(jī)圖模型都具有代表性，盡管在某些情況下這并不現(xiàn)實。正如之前引言中所介紹的那樣，在此定義的模型中連接社區(qū)是隨著網(wǎng)絡(luò)的生成而默認(rèn)生成的，而非顯示定義的。對于一些z擁有較大值iz和jz的兩個結(jié)點i和j，它們被顏色為z的邊連接的可能性也較大，因此包含這樣結(jié)點的群組將被著色為z的邊連接而形成相對稠密的網(wǎng)絡(luò)，而這樣的結(jié)構(gòu)正是我們在一個連接社區(qū)的網(wǎng)絡(luò)中希望看到的。III檢測重疊社區(qū)根據(jù)上述定義的模型，我們可以直接得到生成任意特定網(wǎng)絡(luò)的所應(yīng)用的概率。因為對于兩個相互獨立的泊松分布而言，其參數(shù)之和也服從泊松分布，因此兩結(jié)點i和j之間所有顏色的邊的總數(shù)為zizjz(對于自聯(lián)邊為12Ziziz),，通過此方法得出實際的值是泊松分布的。因而通過一個鄰接矩陣Aij的元素生成圖G的概率是 PG= ijZizjzAijAij!exp-zizjzi12ZizizAii2Aii!exp-12ziziz. 1（對于鄰接矩陣的元素Aij，一般來說，如果i和j之間有一條邊的話取值為1，對于一個自聯(lián)邊而言其值為2，以和上述公式中的12對應(yīng)）我們通過極大化這種可能性（考慮參數(shù)iz或同等地擴(kuò)大它的對數(shù)）而使得這種模型符合已觀測到的網(wǎng)絡(luò)。對公式1取對數(shù)，重新排列，去除附加的和乘倍數(shù)的常量（這些對于最大化的位置沒有影響），我們推出下列對數(shù)概率公式： log PG = ijAijlogzizjz -ijzizjz 2通過對一系列關(guān)于iz非線性隱含方程我們直接最大化這個表達(dá)式，一種簡單的方法如下：首先我們將應(yīng)用以下形式的詹森不等式logzxzzqzlogxzqz (3)xz是任意一組正數(shù)，qz表示概率且滿足zqz=1，注意到存在等式qz= xz/zxz，將公式3帶入到公式2得到log PG ijzAijqijzlogizjzqijz-izjz, 4這里的概率qijz可以任意指定，只要它們滿足zqijz=1。注意到qijz只對網(wǎng)絡(luò)中實際相連的兩結(jié)點i和j有定義（依此有Aij=1），因此它們與測得的邊數(shù)數(shù)量相同。因此，等式可通過選擇一組適當(dāng)?shù)膓ijz而成立，最大化等式4右邊的qijz和iz等效于最大化原始的線性概率，公式2則僅與iz有關(guān)。似乎這并沒有使得最優(yōu)解問題得以簡化，我們僅僅是把一個單點優(yōu)化變成雙點優(yōu)化而已，反而讓人感覺問題變得更加復(fù)雜了。然而值得慶幸的是，事實并不是這樣。這里的雙點優(yōu)化實際上很簡單。根據(jù)iz的值，qijz的最佳值可通過公式qijz=izjzzizjz (5)得到因為這些值使得不等式實際上成為一個等式。當(dāng)給出qijz的最佳值，iz的最佳值可通過區(qū)分公式4得到公式iz=jAijqijziiz 6 在i上對這個表達(dá)式求和并且重新整理的公式iiz2=ijAijqijz (7)然后再與公式(6)結(jié)合得到公式iz=jAijqijzijAijqijz (8)這樣極大化對數(shù)概率就就可簡化為同時求解公式5和8，可以通過選擇一組隨機(jī)的初始值在這兩個公式中反復(fù)迭代來完成。這種方法就是所謂的最大期望算法并且可以證明得出對數(shù)概率在迭代過程中單調(diào)增長，盡管其并不一定會收斂到全域最大值。為預(yù)防其陷入進(jìn)一個局部最大值上，我們將重復(fù)整個計算過程若干次，每次過程的起始條件都是隨機(jī)給定的，我們?nèi)∵@些計算中得出的最大值作為最終的對數(shù)概率。公式5中的qijz的一個物理意義在于，它代表在結(jié)點i和j之間著顏色為z的邊的概率，這也正是我們考量網(wǎng)絡(luò)連接社區(qū)所需的量。注意到qijz對于結(jié)點i和j是對稱的，因此我們多討論的應(yīng)該是一個無向網(wǎng)絡(luò)。這里展示的計算與機(jī)器學(xué)習(xí)中分析文本的方法相近。具體來說，我們可以把這里的模型看成是概率潛在語義分析（一種能在文本資料庫中自動檢測主題的技術(shù)）模型中的一個變體。文本分析和社區(qū)檢測之間的聯(lián)系也曾經(jīng)被一些學(xué)者研究過。其中不可不提的當(dāng)屬Psorakis等人所作的工作。盡管它并不是把連接網(wǎng)絡(luò)作為研究重點，但它應(yīng)用了概率潛在語義分析的另一個變體，同時還使用了一個名為非負(fù)矩陣因子的迭代適應(yīng)算法來尋找有向網(wǎng)絡(luò)中的重疊社區(qū)。同樣值得一提的是Parkinnen等人所作的研究。他們與我們采取同樣的觀點來對待連接社區(qū)，所不同的是他們采取的是一種基于貝葉斯生成模型和馬爾科夫鏈的采用蒙特卡洛技術(shù)的比較算法。有關(guān)文本處理和網(wǎng)絡(luò)分析之間聯(lián)系的詳細(xì)介紹我們在附錄A中給以呈現(xiàn)，在此不再贅述。IV實現(xiàn)上述算法可以作為一個尋找重疊社區(qū)的計算機(jī)算法得以直接實現(xiàn)，并且對于中等規(guī)模大小（擁有成千上萬結(jié)點）的網(wǎng)絡(luò)此算法運行情況良好。對于大型網(wǎng)絡(luò)則將占用大量內(nèi)存，并且運行時間也將變得很長，但這些問題都可以通過使用一種更加精致的實現(xiàn)得以解決，并且使其對于百萬級結(jié)點級別的網(wǎng)絡(luò)的分析成為可能。此算法內(nèi)存的使用主要是用來存儲參數(shù)：參數(shù)iz需要空間n，qijz需要空間m，此處的n和m分別代表網(wǎng)絡(luò)中結(jié)點和邊的數(shù)量。由于通常情況下m要遠(yuǎn)大于n，這意味著內(nèi)存的使用主要由qijz決定。我們可以通過重新構(gòu)造這個算法，使得qijz不需要被存儲，以此來減少內(nèi)存的使用。我們定義平均值kiZ為連接結(jié)點i著顏色為 z的邊的端點數(shù)。kiZ=jAijqijz (9)在此算法的一個給定迭代過程中指定這些量的值，則計算下一次迭代的值的過程如下。首先我們重新定義一組量kiZ用來存儲kiZ的新值，開始我們將這組量都置為0。用kZ來表示所有著顏色為z的結(jié)點的和kiZ=ikiZ (10)則iz可以表示為iz=kiZkZ (11)接著我們遍歷網(wǎng)絡(luò)中的每條邊i,j 計算公式(5)中的分母得到：D=zizjz=zkiZkjZkZ (12)這樣之后將其代入公式(5)我們就將得到qijz=izjzzizjz=kiZkjZDkZ (13)此時我們將它的值代入到量kiZ和kjZ 中，丟棄D和qijz的值，并且對于網(wǎng)絡(luò)中的下一條邊重復(fù)此過程。當(dāng)我們依照這種方法遍歷所有邊后，變量kiZ的值將等價于公式(9)中的值，并將稱為新的kiZ。這種方法只需要存儲kiZ的舊值與新值兩個量，總共有2nK個量，而不是qijz個。因此節(jié)省了大量的內(nèi)存空間。至于運行時間，此算法對每次迭代過程擁有m的計算復(fù)雜度，這里的m仍然是網(wǎng)絡(luò)中邊的數(shù)目?？傔\行時間的主要決定因素是收斂到kiZ的迭代次數(shù)。實際中，我們發(fā)現(xiàn)在很多例子中需要大量的迭代過程，因此影響了此方法的性能。但速度可以通過下述方法得到提高。在這個算法對于網(wǎng)絡(luò)的一個典型運用中，最終結(jié)果是每個結(jié)點僅僅屬于個社區(qū)中的一個子集。換句話說，就是我們期望一大部分參數(shù)kiZ能夠在EM迭代過程中趨于零。從上述方程中可以清楚看到如果某特定kiZ一旦變?yōu)榱?，則其在接下來的迭代中都將保持這個值，這也就意味著它不再需要被更新，我們可以通過將其排除出計算過程而節(jié)省時間。刪減一組變量有兩種策略。一種策略是當(dāng)kiZ低于某個預(yù)定閥值時我們就將其設(shè)置為零，一旦kiZ被設(shè)置為零后，與其相對應(yīng)所有相鄰邊上的qijz也都將被設(shè)置為零，因此也可以不用再計算。因此對于每條邊，我們只需要對于著色為Z的不為零的kiZ和kjZ計算qijz的值。這種策略將帶來速度上的明顯提升。對于較小的網(wǎng)絡(luò)直接計算所有的qijz則更為高效。但是如果kiZ低于預(yù)定閥值我們?nèi)匀粚⑵湓O(shè)置為零，因為這將使得第二次剪枝稱為可能。另一種策略可以與上一種串聯(lián)使用并且對于所有類型的值都將有速度上的顯著提升。其原理是由觀察得出如果對于某特定結(jié)點除一個以外的所有kiZ都被設(shè)置為零的話，則這個結(jié)點的顏色將被設(shè)置為單一值并且不會再改變。如果邊i,j的兩個端點都具有這個性質(zhì)，都收斂到一種單一顏色并且不會改變，則連接它們的邊將不會對于計算有任何影響并且可以將其刪除出網(wǎng)絡(luò)。通過使用這兩種策略我們計算的速度得到可觀的提高。我們發(fā)現(xiàn)在實際計算過程中參數(shù)kiZ的值和邊都將快速收縮，因此主要的迭代僅包含一個子集，通常是那些與社區(qū)屬性不太清楚的結(jié)點連接的邊。如果將閥值設(shè)置為零，則剪枝算法將與原始的EM算法等效。但是即使如此我們也會發(fā)現(xiàn)速度有很大程度的提高。如果設(shè)置為一個很小但非零的值，則我們將在計算中引入一種近似，意味著結(jié)果可能會與原始算法有所不同。然而實際中，這種差別很小，并且非零值會讓性能又有所提升。關(guān)于不同版本算法的運行結(jié)果和運行時間的詳細(xì)比較在附錄B中給出。接下來的計算都使用更快版本的算法，除非特別說明。V結(jié)果我們通過系統(tǒng)生成網(wǎng)絡(luò)和一組現(xiàn)實世界存在的網(wǎng)絡(luò)來測試此算法的性能。系統(tǒng)生成網(wǎng)絡(luò)允許我們在可控條件下測試已知被設(shè)定的社區(qū)結(jié)構(gòu)，而現(xiàn)實世界網(wǎng)絡(luò)則允許我們在實際現(xiàn)實世界的條件下觀測性能。A系統(tǒng)合成網(wǎng)絡(luò)在系統(tǒng)合成網(wǎng)絡(luò)的例子中，我們采用一種經(jīng)典的一致性測試形式。我們通過此算法使用的統(tǒng)一的隨機(jī)模型生成網(wǎng)絡(luò)并且測試其對于不同參數(shù)的值恢復(fù)已知社區(qū)劃分的能力?？梢酝ㄟ^改變變量的值通過單純社區(qū)結(jié)構(gòu)來創(chuàng)建網(wǎng)絡(luò)，或是根本不使用社區(qū)結(jié)構(gòu)。這樣我們可以區(qū)分出此算法帶來的難度上的挑戰(zhàn)。我們測試的網(wǎng)絡(luò)擁有結(jié)點數(shù)n=1000，被分割成兩個重疊社區(qū)。我們將x個結(jié)點僅置于第一個社區(qū)中，表示其只和此社區(qū)中的其他結(jié)點有關(guān)聯(lián)。將y個結(jié)點僅置于第二個社區(qū)中，剩下的z=n-x-y個結(jié)點可置于兩個社區(qū)中。對于各群組中的結(jié)點有相同數(shù)量的連接。我們設(shè)置所有結(jié)點的期望度為k。我們執(zhí)行三組測試。第一組中設(shè)置z=500，x=y=4750，并且通過改變K的值觀察此算法的表現(xiàn)。當(dāng)k0時，網(wǎng)絡(luò)中沒有邊，也就沒有社區(qū)結(jié)構(gòu)，因此此算法會失效。另一方面，當(dāng)k是一個比較大的值時，它應(yīng)該能夠直接得出社區(qū)所在位置。第二個測試我們?nèi)栽O(shè)置z=500，但這次我們將k設(shè)置為10，改變x和y之間結(jié)點的平衡。第三個測試中將k設(shè)置為10，并且限定x和y相等，但允許z值變動。圖1注1），上述三種實驗的結(jié)果。每個數(shù)據(jù)點都是超過100個網(wǎng)絡(luò)的平均值。每個網(wǎng)絡(luò)使用20個隨機(jī)初始變量。每個表中黑色曲線表示結(jié)點分?jǐn)?shù)，它與此算法正確的社區(qū)數(shù)對應(yīng)，而紅色曲線代表重疊區(qū)結(jié)點的Jaccard指數(shù)。在圖表1中我們用黑色曲線表示每個實驗中測量結(jié)點部分，每個點都為100個網(wǎng)絡(luò)的平均值。為了正確考慮劃分，在群組中的一個結(jié)點成員必須通過算法準(zhǔn)確報告。并且對于任一結(jié)點如果當(dāng)最大相似適應(yīng)過程結(jié)束時一個結(jié)點平均至少擁有一條相近顏色的邊則此算法將其當(dāng)做是一個群組的成員。用數(shù)學(xué)術(shù)語表示就是，如果一個結(jié)點對于顏色z的期望度jAijqijz大于一的話，則其屬于社區(qū)z。正如圖表顯示的那樣，對于這三種測試參數(shù)變量在很大范圍內(nèi)變動都可以得到正確的結(jié)果，能夠正確劃分網(wǎng)絡(luò)中的大多數(shù)結(jié)點。正如期望的那樣，第一個測試中精確度隨著K的增加而增加。當(dāng)k大于10時，此算法將快速地識別出已知社區(qū)結(jié)構(gòu)。在另兩個實驗中，實驗精確度隨著兩組的不對稱增強(qiáng)或重疊部分的增加而下降，但當(dāng)二者之一很小時卻能接近100%。為了探測得到算法識別重疊社區(qū)的更多細(xì)節(jié)，對于同樣的實驗我們還測量了Jaccard指數(shù)：如果用S表示在重疊區(qū)中一組結(jié)點，V代表算法識別的在重疊區(qū)的結(jié)點。則可定義Jaccard指數(shù) J=SVSV。此指數(shù)的值在圖表1中用紅色曲線表示?？梢钥闯銎浯笾碌淖呦蚺c正確識別的結(jié)點綜合分?jǐn)?shù)相同。特別地，我們注意到擁有較高平均度K的網(wǎng)絡(luò)J的值趨于1，表示重疊區(qū)可以被較快識別出。B實際網(wǎng)絡(luò)我們同樣也在大量現(xiàn)實世界網(wǎng)絡(luò)中進(jìn)行了測試。這部分我們給出三個具體例子的詳細(xì)結(jié)果。在附錄B中我們給出了一些附加例子的概要結(jié)果。第一個例子是毫無疑問是測試社區(qū)檢測的。由觀測研究得出的表示全球體育俱樂部成員間友好關(guān)系模型的扎卡伊的“空手道俱樂部”網(wǎng)絡(luò)，因在其研究中俱樂部一分為二會造成兄弟鬩墻而引起關(guān)注。已經(jīng)證實，可以僅僅通過網(wǎng)絡(luò)結(jié)構(gòu)的知識就能推斷出其分割線。圖2注2），為“空手道網(wǎng)絡(luò)”中的重疊社區(qū)，(b)為悲慘世界中的人物角色網(wǎng)絡(luò)。對于給定邊，邊的顏色與qijz值最大的z對應(yīng)。對于屬于不止一個社區(qū)的結(jié)點為了清晰表示其在所屬社區(qū)的劃分我們用較大的點表示。圖表2a展示了通過我們的算法得出空手道俱樂部網(wǎng)絡(luò)的兩個重疊群組的分解。圖表中的顏色代表結(jié)點和邊的劃分。俱樂部中兩組間的分割在結(jié)果中涇渭分明地得以表示，并且與實際情況向?qū)?yīng)。但此算法指定了一些同屬于兩個群組的結(jié)點。通過這些重疊結(jié)點表示的個體在兩個俱樂部都有朋友，當(dāng)面對指責(zé)時有可能會產(chǎn)生立場不明的困惑。實際上在對于扎卡伊模型的討論上確實存在這樣的問題。同樣得指出的是，除了確認(rèn)重疊結(jié)點外，我們采用的方法還可以通過餅圖上顏色的多少指明某個結(jié)點屬于一個或另一個社區(qū)的多大部分。通過結(jié)點上每種顏色邊的期望部分可以計算出此分?jǐn)?shù)。第二個例子是另一個社交網(wǎng)絡(luò)，并且其社區(qū)結(jié)構(gòu)之前也被研究過。這個由克努斯編制的網(wǎng)絡(luò)，代表維多克雨果所著小說悲慘世界中那些虛構(gòu)的人物之間的關(guān)系模型。如果兩個人物同時出現(xiàn)在小說的一個章節(jié)中，則就用一條邊將他們連接。圖表2b展示了運用我們的算法將此網(wǎng)絡(luò)劃分為六個重疊社區(qū)的劃分結(jié)果，并且此種劃分大致符合其社會劃分及小說的劇情結(jié)構(gòu)。但此例中最引人入勝的則是那些網(wǎng)絡(luò)核心部分所扮演的角色（那些擁有特別高度數(shù)的結(jié)點所代表的主要人物）。那些擁有如此多聯(lián)系的結(jié)點與網(wǎng)絡(luò)中各個部分都有關(guān)聯(lián)，它們的存在給應(yīng)用傳統(tǒng)的、無重疊社區(qū)檢測的方案帶來困難，因為它們并不是簡單地屬于某一社區(qū)：不管我們?nèi)绾卧O(shè)置這些核心，它都將與很多其他社區(qū)的結(jié)點有聯(lián)系。重疊社區(qū)為此種問題提供了一個優(yōu)雅的解決方案，我們可將核心置于重疊區(qū)。正如圖表2b所示，我們的算法確實是這樣做的。它將網(wǎng)絡(luò)中很多核心人物都放置在兩個以上的社區(qū)中。這樣的指派從小說劇情的角度看來也具有現(xiàn)實意義：核心所代表的主要人物正是那些不止一次出現(xiàn)在小說分劇情中的人物。圖3注3），美國航空乘客網(wǎng)絡(luò)的重疊社區(qū)。這三個社區(qū)大致可分為東海岸、西海岸和阿拉斯加州。在我們的第三個試驗中同樣可看出與上面相似的表現(xiàn)行為。這是一個描述美國各機(jī)場之間航線聯(lián)系的運輸網(wǎng)絡(luò)。在此網(wǎng)絡(luò)中，結(jié)點代表機(jī)場而邊則代表一個定期航班。在此空間網(wǎng)絡(luò)中，有優(yōu)越地理位置的結(jié)點往往與其他與其相近結(jié)點產(chǎn)生聯(lián)系的可能性更大。這也表明如果存在社區(qū)的話，它們將是區(qū)域性的，主要由一些相近結(jié)點的塊組成。在航空網(wǎng)絡(luò)中通過此算法檢測到的社區(qū)遵循這個模式。如圖表3所示，網(wǎng)絡(luò)中所示的三向劃分將此網(wǎng)絡(luò)劃分為東海岸、西海岸和阿拉斯加州。重疊區(qū)部分是由各組間的地理邊界上的結(jié)點組成。但同樣擁有核心結(jié)點。這樣的核心結(jié)點是航空網(wǎng)絡(luò)的經(jīng)紀(jì)人，它們將不同社區(qū)連接，因為它們正是連接兩個遠(yuǎn)距離地點的航班所必經(jīng)的地方。因此將它們看成是多個群組的成員是合適的。在大多數(shù)例子中這些核心結(jié)點更多地屬于它們所在位置的社區(qū)，而非其他社區(qū)。VI無重疊社區(qū)正如我們描述的那樣，我們的算法也可以用來尋找網(wǎng)絡(luò)中無重疊社區(qū)。正如之前一些學(xué)者指出的那樣，一切計算結(jié)點在社區(qū)中所占比例的算法都可以通過將每個結(jié)點指派給它依賴性最強(qiáng)的那個社區(qū)這樣的方法加以改造，用來適應(yīng)無重疊社區(qū)的情況。在我們的例子中，這意味著將指定結(jié)點給擁有最大iz的社區(qū)。通過嚴(yán)格證明得出可以將連接社區(qū)模型看成是一個無重疊度數(shù)校正的隨機(jī)模型的一種松弛表示。和有重疊的情況一樣，我們同樣在系統(tǒng)生成網(wǎng)絡(luò)和現(xiàn)實網(wǎng)絡(luò)中加以測試。對于生成的無權(quán)值的無向網(wǎng)絡(luò)我們使用標(biāo)準(zhǔn)LFR基準(zhǔn)測試。為方便期間。我們采用與Ref31中同樣的參數(shù)表示。將K的值設(shè)為基準(zhǔn)測試網(wǎng)絡(luò)中社區(qū)的數(shù)目。為了量化表示檢測基準(zhǔn)測試網(wǎng)絡(luò)中的已知社區(qū)，我們使用Ref31中測量的不同標(biāo)準(zhǔn)化互信息。我們注意到這個測量方法并不唯一，并且通常會返回不同的結(jié)果。傳統(tǒng)的方法通常用來估計社區(qū)結(jié)構(gòu)，使用這種方法同樣使得我們能夠與Ref31中給出的其他算法所得結(jié)果做直接比較。在基準(zhǔn)測試中，我們發(fā)現(xiàn)通過選擇擁有最大iz值的社區(qū)這種過分簡單化四舍五入式的算法與Ref31中提到的其他算法相比只是取得平均表現(xiàn)性能。然而，對于算法的一個簡單的修改就將產(chǎn)生極大的性能上的提高。首先通過采用四舍五入方法生成一個社區(qū)的候選劃分。接著我們將采用更進(jìn)一步的優(yōu)化措施，我們將在隨機(jī)模型劃分下最大化增加對數(shù)概率的單一結(jié)點從一個社區(qū)轉(zhuǎn)移到另一個社區(qū)。重復(fù)這個過程指導(dǎo)這樣的移動不復(fù)存在。這個過程容易被實現(xiàn)并且與初始劃分相比只需很少的計算開銷，這大大改善了我們的結(jié)果。圖4注4），使用Lancichinetti等人的LFR基準(zhǔn)測試模型生成的網(wǎng)絡(luò)中無重疊社區(qū)算法的測試結(jié)果。上下兩表分別代表不使用和使用后置處理優(yōu)化對數(shù)概率的結(jié)果。對于每個網(wǎng)絡(luò)都使用10個隨機(jī)初始化變量，每個點都是由超過100個網(wǎng)絡(luò)所得的平均值。我們實驗的結(jié)果在圖表4中得以展示。上面的表顯示的是沒有采取附加優(yōu)化步驟的算法的性能，下面的表展示的是采用附加優(yōu)化步驟算法的性能。仔細(xì)檢查這些社區(qū)可以發(fā)現(xiàn)這種方法偶爾會產(chǎn)生社區(qū)分割或是合并?？梢酝ㄟ^一個稍微復(fù)雜的后置處理步驟來優(yōu)化可能性，這也使得更進(jìn)一步提高算法性能成為可能。圖5注5），在美國大學(xué)足球網(wǎng)絡(luò)中得出的無重疊社區(qū)。結(jié)點的聚簇代表由算法得出的社區(qū)，結(jié)點顏色代表大學(xué)被劃分進(jìn)的聯(lián)盟。可以看出，此例中的算法將聯(lián)盟結(jié)構(gòu)完美呈現(xiàn)出來（深紫色結(jié)點代表不屬于任何聯(lián)盟的大學(xué)）。對于現(xiàn)實世界網(wǎng)絡(luò)，在圖表5中我們也給出了其測試結(jié)果。這個例子中我們討論的是Ref1中的大學(xué)足球網(wǎng)絡(luò)。在這個網(wǎng)絡(luò)中結(jié)點代表美國足球中的各大學(xué)球隊，邊代表2000年賽季的比賽時間表，兩隊如果有比賽則用一條邊將其對應(yīng)結(jié)點連接。經(jīng)反復(fù)分析得出這個網(wǎng)絡(luò)的一個聚簇形成的社區(qū)可還原出美國大學(xué)運動的組織單元（即聯(lián)盟），聯(lián)盟中大學(xué)是為了競賽而劃分的。在2000年共有11個聯(lián)盟I-A組成這個網(wǎng)絡(luò)。并且有8支隊伍獨立于任一聯(lián)盟。如圖表5所示，每個單獨屬于一個聯(lián)盟的隊伍被正確的顯示出來。VII結(jié)論本文中我們討論了在無向網(wǎng)絡(luò)中檢測社區(qū)（有重疊和無重疊的）的一種方法。這種方法擁有嚴(yán)格的數(shù)學(xué)基礎(chǔ)作保證。它基于一種連接網(wǎng)絡(luò)的概率模型，容易實現(xiàn)，對于擁有百萬數(shù)量級結(jié)點的網(wǎng)絡(luò)也有極快的速度。并且能夠得到可以與其他算法相媲美的結(jié)果。然而，這種方法并不完美。當(dāng)前其主要的缺陷在于它沒有提供任何準(zhǔn)則以決定我們稱為K的表示網(wǎng)絡(luò)社區(qū)數(shù)的值。這是在各種社區(qū)檢測方法中都普遍存在的問題。一些方法，如模塊最大化方法也提供了解決方案，但是會得出偏頗的答案或者是在一些情形下不連續(xù)的結(jié)論。像貝氏訊息準(zhǔn)則和赤池訊息準(zhǔn)則這樣更嚴(yán)格的方法卻不能在這里運用，這是因為很多模型參數(shù)的值為零，這也就將它們置于參數(shù)空間的邊界上，這將使得源于這些準(zhǔn)則的假設(shè)失效。另一種方法是使用一個較大的K值進(jìn)行計算并且通過一種方法來規(guī)范參數(shù)，如果一些社區(qū)消失則意味著沒有邊與這些社區(qū)相連。例如，Psorakis等人在研究中使用矩陣分解算法，因為包含很多非零參數(shù)它使用前向模型以建立不同社區(qū)間的平衡和網(wǎng)絡(luò)數(shù)據(jù)的擬合優(yōu)度。然而問題在于這種預(yù)先處理本身包含一些未知參數(shù)，它們的值會影響到社區(qū)數(shù)量，因此上面的問題通過這種方法并不能完全得到解決。我們相信應(yīng)用于生成模型的統(tǒng)計模型選擇方法應(yīng)該大體上能夠以一種一致且令人滿意的方式來尋找出社區(qū)的數(shù)量。我們應(yīng)用此方法也進(jìn)行了一些初步試驗，其結(jié)果充滿前景。但是這些方法因為需要大量的計算過程以致于只能在較小的網(wǎng)絡(luò)中加以應(yīng)用。對于當(dāng)今科學(xué)家而言，是否能找出一種可靠穩(wěn)定的方法能夠在合理的運行時間內(nèi)解決大規(guī)模網(wǎng)絡(luò)中的此類問題已成為一類開放問題，并引起他們極大的研究興趣（我們期待著會有更好的研究成果來解決此類問題）。致謝在此衷心感謝Qiaozhu Mei，Cris Moore和Lenka Zdeborova等提出的的寶貴意見。此項工作得到NSA的基金支持，在此一并感謝！參考文獻(xiàn)1 M. Girvan and M. E. J. Newman, Community structure in social and biological networks. Proc. Natl. Acad. Sci. USA 99, 78217826 (2002).2 S. Fortunato, Community detection in graphs. Phys. Rep.486, 75174 (2010).3 L. Danon, J. Duch, A. Diaz-Guilera, and A. Arenas, Comparing community structure identification. J. Stat. Mech. P09008 (2005).4 P. W. Holland, K. B. Laskey, and S. Leinhardt, Stochastic blockmodels: Some first steps. Social Networks 5,109137 (1983).5 Y. J. Wang and G. Y. Wong, Stochastic blockmodels for directed graphs. Journal of American Statistical Association 82, 819 (1987).6 T. A. Snijders and K. Nowicki, Estimation and prediction for stochastic blockmodels for graphs with latent block structure. Journal of Classification 14, 75100 (1997).7 A. Clauset, C. Moore, andM. E. J. Newman, Hierarchical structure and the prediction of missing links in networks. Nature 453, 98101 (2008).8 E. M. Airoldi, D. M. Blei, S. E. Fienberg, and E. P. Xing, Mixed membership stochastic blockmodels. J. Mach. Learn. Res. 9, 19812014 (2008).9 Y.-Y. Ahn, J. P. Bagrow, and S. Lehmann, Link communities reveal multi-scale complexity in networks. Nature 466, 761764 (2010).10 T. S. Evans and R. Lambiotte, Line graphs, link partitions, and overlapping communities. Phys. Rev. E 80, 016105 (2009).11 J. Parkinnen, A. Gyenge, J. Sinkkoken, and S. Kaski, A block model suitable for sparse graphs. In Proceedings of the 7th International Workshop on Mining and Learning with Graphs, Association of Computing Machinery, New York (2009).12 A. Gyenge, J. Sinkkonen, and A. A. Benczur, An efficient block model for clustering sparse graphs. In Proceedings of the 8th International Workshop on Mining and Learning with Graphs, pp. 6269, Association of Computing Machinery, New York (2010).13 M. E. J. Newman and M. Girvan, Finding and evaluating community structure in networks. Phys. Rev. E 69, 026113 (2004).14 S. Fortunato and M. Barthelemy, Resolution limit in community detection. Proc. Natl. Acad. Sci. USA 104, 3641 (2007).15 B. H. Good, Y.-A. de Montjoye, and A. Clauset, Performance of modularity maximization in practical contexts. Phys. Rev. E 81, 046106 (2010).16 X. S. Zhang, R. S. Wang, Y. Wang, J. Wang, Y. Qiu, L. Wang, and L. Chen, Modularity optimization in community detection of complex networks. Europhys. Lett. 87, 38002 (2009).17 P. J. Bickel and A. Chen, A nonparametric view of network models and NewmanGirvan and other modularities. Proc. Natl. Acad. Sci. USA 106, 2106821073 (2009).18 B. Karrer and M. E. J. Newman, Stochastic blockmodels and community structure in networks. Phys. Rev. E 83, 016107 (2011).19 M. Molloy and B. Reed, A critical point for random graphs with a given degree sequence. Random Structures and Algorithms 6, 161179 (1995).20 M. E. J. Newman, S. H. Strogatz, and D. J. Watts, Random graphs with arbitrary degree distributions and their applications. Phys. Rev. E 64, 026118 (2001).21 This is a special case of the general observation that the log of the average of any set of numbers is never less than the average of the log, since the logarithm is concave down. If the numbers in question are xz/qz and the average is taken with weights qz this observation leads immediately to the inequality given.22 I. Psorakis, S. Roberts, and B. Sheldon, Soft partitioning in networks via Bayesian non-negative matrix factorization. In 24th Annual Conference on Neural InformationProcessing Systems, Workshop on Networks Across Disciplines: Theory and Applications (2010).23 If the value of _ is greater than 1/K, then it is possible inadvertently to prune all of the colors from a vertex, leaving it in no community at all. To avoid this, we mustchoose _ 1/K, which we have done in all the calculations presented here. 24 W. W. Zachary, An information flow model for conflict and fission in small groups. Journal of Anthropological Research 33, 452473 (1977).25 D. E. Knuth, The Stanford GraphBase: A Platform for Combinatorial Computing. AddisonWesley, Reading, MA (1993).26 M. T. Gastner and M. E. J. Newman, The spatial structure of networks. Eur. Phys. J. B 49, 247252 (2006).27 M. Barthelemy, Spatial networks. Physics Reports 499, 1101 (2011).28 M. Zarei, D. Izadi, and K. A. Samani, Detecting overlapping community structure of networks based on vertexvertex correlations. J. Stat. Mech. P11013 (2009).29 F. Wang, T. Li, X. Wang, S. Zhu, and C. Ding, Community discovery using nonnegative matrix factorization. Data Mining and Knowledge Discovery 22, 493521 (2011).30 A. Lancichinetti, S. Fortunato, and F. Radicchi, Benchmark graphs for testing community detection algorithms. Phys. Rev. E 78, 046110 (2008).31 A. Lancichinetti and S. Fortunato, Community detection algorithms: A comparative analysis. Phys. Rev. E 80, 056117 (2009).32 T. Hofmann, Probabilistic latent semantic indexing. In Proceedings of the 22nd Annual International ACM Conference on Research and Development in Information Retrieval, pp. 5057, Association of Computing Machinery, New York (1999).33 T. Hofmann, Unsupervised learning by probabilistic latent semantic analysis. Mach. Learn. 42, 177196 (2001).34 T. Hofmann, Latent semantic models for collaborative filtering. ACM Trans. Inf. Syst. 22, 89115 (2004).35 D. D. Lee and H. S. Seung, Learning the parts of objects by nonnegative matrix factorization. Nature 401, 788791 (1999).36 C. Ding, T. Li, andW. Peng, On the equivalence between non-negative matrix factorization and probabilistic latent semantic indexing. Comput. Stat. Data Anal. 52, 39133927 (2008).37 D. M. Blei, A. Y. Ng, and M. I. Jordan, Latent Dirichlet allocation.