基于信息瓶頸的社區(qū)發(fā)現(xiàn)F

1、基于信息瓶頸的社區(qū)發(fā)現(xiàn)F本研究得到973國家重點(diǎn)基礎(chǔ)研究發(fā)展計(jì)劃的項(xiàng)目（項(xiàng)目編號(hào)：2004CB318109 & 2007CB311100)、微軟亞洲研究院IST2007- Web 2.0社區(qū)發(fā)現(xiàn)與社區(qū)演化研究課題（FY07-RES-THEME-067）的資助。作者簡介：沈華偉，男，1982年生，博士研究生，E-mail：HshenhuaweiH，主要研究方向?yàn)樯鐣?huì)計(jì)算、復(fù)雜網(wǎng)絡(luò)、信息檢索；程學(xué)旗，男，1971年生，博士，研究員，研究領(lǐng)域包括網(wǎng)絡(luò)信息安全、大規(guī)模信息檢索與信息挖掘、P2P計(jì)算等；陳海強(qiáng)，男，1979年生，博士研究生，主要研究方向?yàn)樯鐣?huì)計(jì)算、復(fù)雜網(wǎng)絡(luò)、信息檢索；劉悅，女，1971年

2、生，博士，副研究員，研究領(lǐng)域包括Web搜索和挖掘、復(fù)雜網(wǎng)絡(luò)分析與社會(huì)計(jì)算、分布式系統(tǒng)等。沈華偉1),2) 程學(xué)旗1) 陳海強(qiáng)1),2) 劉悅1)1)（中國科學(xué)院計(jì)算技術(shù)研究所 北京 100080)2)（中國科學(xué)院研究生院 北京 100049）摘 要 本文提出一種映射方法，把單部網(wǎng)絡(luò)變換成二部圖網(wǎng)絡(luò)。針對得到的二部圖網(wǎng)絡(luò)，在信息論的框架下，提出了一種基于信息瓶頸的社區(qū)發(fā)現(xiàn)方法。該方法通過尋找網(wǎng)絡(luò)的最優(yōu)壓縮表示來發(fā)現(xiàn)網(wǎng)絡(luò)的社區(qū)結(jié)構(gòu)，最優(yōu)壓縮表示盡可能多地保留原始網(wǎng)絡(luò)的拓?fù)涮卣?。在真?shí)數(shù)據(jù)集和計(jì)算機(jī)產(chǎn)生的數(shù)據(jù)集上的實(shí)驗(yàn)表明，該方法能夠有效地發(fā)現(xiàn)網(wǎng)絡(luò)的社區(qū)結(jié)構(gòu)。另外，對于有向網(wǎng)絡(luò)的社區(qū)發(fā)現(xiàn)，現(xiàn)有方法忽

3、略有向網(wǎng)絡(luò)中邊的方向而作為無向網(wǎng)絡(luò)來處理，損失了有向的網(wǎng)絡(luò)的方向信息，本文提出的社區(qū)發(fā)現(xiàn)方法能夠很好地解決這一問題，并能從有向網(wǎng)絡(luò)中挖掘出一些現(xiàn)有方法無法發(fā)現(xiàn)的知識(shí)，這一特點(diǎn)使得本文的方法比現(xiàn)有方法更適用于解決像WWW這樣的有向網(wǎng)絡(luò)。同時(shí)，真實(shí)世界的許多網(wǎng)絡(luò)本身就是二部圖網(wǎng)絡(luò)，相對于現(xiàn)有的社區(qū)發(fā)現(xiàn)方法，本文的方法可以直接應(yīng)用于這類網(wǎng)絡(luò)。關(guān)鍵詞社區(qū)發(fā)現(xiàn)；信息瓶頸；聚團(tuán)性中圖法分類號(hào)Information Bottleneck based Community Detection in NetworkSHEN Hua-Wei1),2) CHENG Xue-Qi1) CHEN Hai-Qiang1),

4、2) LIU Yue1)1)（Institute of Computing Technology, Chinese Academy of Sciences, Beijing 100080）2)（Graduate University of Chinese Academy of Sciences, Beijing 100049）Abstract This paper proposes a projection method to transform a unipartite network into a bipartite network. As to the obtained bipartit

5、e network, we present an information-bottleneck-based method for community detection under the information-theoretic framework. This method detects the community structure of networks by finding an efficient compression of the network. The efficient compression holds the regularity of the original n

6、etwork as many as possible. Applications on the computer-generated networks and many real-world networks demonstrate that this method is very effective at community detection of networks. As for the community detection of directed networks, existing methods neglect the direction of edges and treat t

7、hem as undirected networks. The information provided by directionality is lost in this process. Using the projection method proposed in this paper, the direction of edges can be retained and thus our method is more suitable to detect the community structure in directed networks, such as the world-wi

8、de-web. And some new knowledge can be found by our method. In addition, our method can be directly applied to the detection of community structure in bipartite networks, which are common in real world.Keywordscommunity detection; information bottleneck; modularity1 引 言真實(shí)世界中的許多系統(tǒng)可以使用網(wǎng)絡(luò)來表示，例如，Internet

9、、WWW、科技文獻(xiàn)引用關(guān)系網(wǎng)絡(luò)、食物鏈網(wǎng)絡(luò)、社會(huì)關(guān)系網(wǎng)絡(luò)等。一個(gè)網(wǎng)絡(luò)一般由一個(gè)頂點(diǎn)集和一個(gè)邊集構(gòu)成。對于WWW而言，每一個(gè)網(wǎng)頁是一個(gè)頂點(diǎn)，所有網(wǎng)頁構(gòu)成網(wǎng)絡(luò)的頂點(diǎn)集，網(wǎng)頁間的超鏈接是邊，所有超鏈接構(gòu)成這個(gè)網(wǎng)絡(luò)的邊集。近幾年，網(wǎng)絡(luò)統(tǒng)計(jì)特征得到研究人員越來越多的關(guān)注。網(wǎng)絡(luò)的一些統(tǒng)計(jì)特征，像小世界效應(yīng)、頂點(diǎn)度分布、頂點(diǎn)的高聚團(tuán)性等逐漸為研究人員所熟知X1XX2X。但是，目前的研究主要關(guān)注于網(wǎng)絡(luò)的宏觀和微觀結(jié)構(gòu)特征，宏觀特征是基于網(wǎng)絡(luò)整體，微觀特征是基于頂點(diǎn)，介于宏觀和微觀之間的特征卻沒有得到充分的關(guān)注和研究。社區(qū)結(jié)構(gòu)是一種介于宏觀和微觀之間的網(wǎng)絡(luò)特征，是真實(shí)世界中許多復(fù)雜網(wǎng)絡(luò)所具有的一種普遍性質(zhì)X3X

10、。社區(qū)結(jié)構(gòu)和網(wǎng)絡(luò)的功能有著緊密的關(guān)系，像魯棒性、高傳播速度等。發(fā)現(xiàn)網(wǎng)絡(luò)社區(qū)結(jié)構(gòu)是揭示網(wǎng)絡(luò)結(jié)構(gòu)和功能之間關(guān)系的重要基礎(chǔ)。因此，對于網(wǎng)絡(luò)社區(qū)結(jié)構(gòu)的研究開始得到許多領(lǐng)域的學(xué)者日益增加的關(guān)注和研究X4X。社區(qū)沒有一個(gè)明確的定義，一個(gè)被普遍接受的觀點(diǎn)是：一個(gè)社區(qū)是網(wǎng)絡(luò)的一個(gè)子圖，子圖中的頂點(diǎn)更傾向于和子圖內(nèi)的頂點(diǎn)有邊相連。因此，社區(qū)內(nèi)部頂點(diǎn)連邊密度較高，不同社區(qū)之間頂點(diǎn)連邊密度相對較低。對于真實(shí)網(wǎng)絡(luò)，同屬于一個(gè)社區(qū)的頂點(diǎn)更有可能具有相似的性質(zhì)或相近的功能。在WWW網(wǎng)絡(luò)中，同一個(gè)社區(qū)的頁面通常表達(dá)相近的主題；在神經(jīng)網(wǎng)絡(luò)中，一個(gè)社區(qū)通常對應(yīng)一個(gè)功能組，也就是說一個(gè)社區(qū)的頂點(diǎn)有著相近的功能；在科技文獻(xiàn)共同署名

11、網(wǎng)絡(luò)中，同一個(gè)社區(qū)內(nèi)的學(xué)者有著相近的研究興趣。發(fā)現(xiàn)網(wǎng)絡(luò)的社區(qū)結(jié)構(gòu)能夠發(fā)現(xiàn)新的知識(shí)和現(xiàn)象，有助于更深刻地理解和認(rèn)識(shí)網(wǎng)絡(luò)結(jié)構(gòu)和功能之間的關(guān)系。網(wǎng)絡(luò)社區(qū)結(jié)構(gòu)的研究有著很長的歷史。作為網(wǎng)絡(luò)社區(qū)發(fā)現(xiàn)的一個(gè)簡化問題，圖劃分問題幾十年來得到了廣泛和深入的研究。圖劃分問題的一個(gè)典型應(yīng)用是并行計(jì)算中的任務(wù)分配問題。有C個(gè)處理器處理N個(gè)任務(wù)，這些任務(wù)之間在處理過程中可能需要相互通信。為簡單起見，我們假設(shè)，1)每個(gè)任務(wù)都需要相同的處理時(shí)間；2)任何有通信的兩個(gè)任務(wù)之間的通信量都是一樣的。這樣一來，我們就得到了一個(gè)無權(quán)無向簡單圖，N個(gè)頂點(diǎn)代表N個(gè)任務(wù)，邊連接需要通信的任務(wù)。相對于同一處理器上的兩個(gè)任務(wù)之間的通信代價(jià)，

12、不同處理器上兩個(gè)任務(wù)之間通信的代價(jià)是非常高的。因此，為了提高處理的效率，應(yīng)減少不同處理器上的任務(wù)之間的通信。從而，這樣一個(gè)任務(wù)分配問題就變成了一個(gè)典型的圖劃分問題，把圖中的N個(gè)頂點(diǎn)劃分成C個(gè)組（社區(qū)），在平衡各個(gè)處理器的負(fù)載的同時(shí)，使組間的通信盡可能地少。精確求解圖劃分問題是困難的，因此多種啟發(fā)式算法被提出，試圖近似求解圖劃分問題。在很多情況下，這些啟發(fā)式算法能夠得到可以接受的解。在這類算法中，最著名的是由Kernighan-Lin提出的算法X5X，該算法在稀疏圖上的時(shí)間復(fù)雜度可以達(dá)到。和圖劃分問題不同，對于社區(qū)發(fā)現(xiàn)問題，事先并不知道一個(gè)網(wǎng)絡(luò)中有多少個(gè)社區(qū)存在，各個(gè)社區(qū)包含的頂點(diǎn)個(gè)數(shù)也是未知的

13、。這使得社區(qū)發(fā)現(xiàn)問題是一個(gè)比圖劃分更加困難的問題。另外，網(wǎng)絡(luò)的社區(qū)結(jié)構(gòu)通常呈現(xiàn)出層次特征，一個(gè)社區(qū)可以進(jìn)一步劃分成幾個(gè)子社區(qū)；有些頂點(diǎn)出現(xiàn)在不同的社區(qū)中，這使得社區(qū)之間有重疊。這些現(xiàn)象也增加了社區(qū)發(fā)現(xiàn)的難度。目前，已經(jīng)有許多社區(qū)發(fā)現(xiàn)方法提出，分別基于連邊密度X6X、介數(shù)X7X、信息中心度X8X、隨機(jī)行走X9X、譜分析X10X、最優(yōu)化某個(gè)目標(biāo)質(zhì)量函數(shù)X11X等等，最有代表性的一類方法是基于優(yōu)化網(wǎng)絡(luò)聚團(tuán)性(modularity)的方法X11X。ModularityX7X是由M.E.J. Newman提出的，最早是衡量網(wǎng)絡(luò)劃分好壞的一種度量。Modularity值(通常也叫Q值)的計(jì)算方法為，其中，

14、表示社區(qū)和社區(qū)之間的邊數(shù)占總邊數(shù)的比率；表示有一個(gè)端點(diǎn)在社區(qū)中的邊占邊總數(shù)的比率。Modularity的基本思想是：完全隨機(jī)網(wǎng)絡(luò)沒有社區(qū)結(jié)構(gòu)，如果一個(gè)網(wǎng)絡(luò)有良好的社區(qū)結(jié)構(gòu)，就存在一種對該網(wǎng)絡(luò)的劃分，使得這種劃分對應(yīng)一個(gè)較高的Q值。對于真實(shí)世界的網(wǎng)絡(luò)而言，Q的取值一般介于0.30.7之間?；趍odularity的方法大多旨在優(yōu)化Q值，希望找到一種網(wǎng)絡(luò)的劃分，使得這種劃分對應(yīng)的Q值最大。一個(gè)網(wǎng)絡(luò)的所有可能劃分?jǐn)?shù)等于第二類Stirling數(shù)X11X，因此枚舉所有劃分是計(jì)算上不可行的。研究人員提出許多啟發(fā)式方法來優(yōu)化Q值，貪婪方法X12X、模擬退火算法X13X、極值優(yōu)化方法X14X等被用來尋找較優(yōu)的

15、Q值，這些方法在許多網(wǎng)絡(luò)上取得了不錯(cuò)的結(jié)果。對于社區(qū)結(jié)構(gòu)的認(rèn)識(shí)，基于modularity的方法認(rèn)為社區(qū)結(jié)構(gòu)是真實(shí)網(wǎng)絡(luò)和隨機(jī)網(wǎng)絡(luò)之間的統(tǒng)計(jì)偏差，社區(qū)發(fā)現(xiàn)的過程是找一種最優(yōu)劃分使這種偏差最大。社區(qū)結(jié)構(gòu)的另一種認(rèn)識(shí)是基于網(wǎng)絡(luò)壓縮的，認(rèn)為社區(qū)結(jié)構(gòu)是網(wǎng)絡(luò)結(jié)構(gòu)規(guī)則性的一種體現(xiàn)，而發(fā)現(xiàn)網(wǎng)絡(luò)中的社區(qū)結(jié)構(gòu)是去掉那些不重要的細(xì)節(jié)而保留網(wǎng)絡(luò)的整體拓?fù)涮卣?，這一過程可以看成是對網(wǎng)絡(luò)拓?fù)涞挠袚p壓縮X15X。基于社區(qū)結(jié)構(gòu)的第二種認(rèn)識(shí)，一些社區(qū)發(fā)現(xiàn)方法被提出X15XX16X,其中，X16X考慮使用信息瓶頸來定義網(wǎng)絡(luò)模塊性并基于這一定義，提出了一種社區(qū)發(fā)現(xiàn)方法?；谏鐓^(qū)結(jié)構(gòu)的第二種認(rèn)識(shí)，本文重新思考社區(qū)發(fā)現(xiàn)問題。社區(qū)發(fā)現(xiàn)轉(zhuǎn)變

16、成尋找網(wǎng)絡(luò)結(jié)構(gòu)的一種高效壓縮表示，這種壓縮能夠盡可能多地反映原始網(wǎng)絡(luò)中的結(jié)構(gòu)規(guī)則性。本文首先提出一種變換方法，把網(wǎng)絡(luò)轉(zhuǎn)換成二部圖網(wǎng)絡(luò)；進(jìn)而，針對該二部圖，在信息論的框架下，提出了一種新的基于信息瓶頸的社區(qū)發(fā)現(xiàn)方法。為驗(yàn)證基于信息瓶頸社區(qū)發(fā)現(xiàn)方法的有效性，本文展示了該方法在計(jì)算機(jī)生成網(wǎng)絡(luò)上的性能，并把該方法應(yīng)用到一些真實(shí)世界的網(wǎng)絡(luò)中，而且與現(xiàn)有方法作了對比。結(jié)果表明，基于信息瓶頸的社區(qū)發(fā)現(xiàn)方法能夠有效地發(fā)現(xiàn)這些網(wǎng)絡(luò)中的社區(qū)結(jié)構(gòu)。本文其它部分的組織結(jié)構(gòu)如下：第二節(jié)簡要敘述了信息瓶頸方法；第三節(jié)給出一種把一般網(wǎng)絡(luò)變換成二部圖網(wǎng)絡(luò)的方法，闡述了如何使用信息瓶頸方法發(fā)現(xiàn)網(wǎng)絡(luò)的社區(qū)結(jié)構(gòu)，給出了基于信息瓶頸

17、社區(qū)發(fā)現(xiàn)方法的一般框架；第四節(jié)把該社區(qū)發(fā)現(xiàn)方法應(yīng)用到計(jì)算機(jī)生成的網(wǎng)絡(luò)和真實(shí)網(wǎng)絡(luò)上，以檢驗(yàn)方法的有效性；第五節(jié)總結(jié)了全文，提出一些有待探討的問題，并對未來工作進(jìn)行了展望。2 信息瓶頸方法在介紹基于信息瓶頸的社區(qū)發(fā)現(xiàn)方法之前，本節(jié)對信息瓶頸方法做一簡單介紹。信息瓶頸方法由Naftali Tishby等人提出X17X。信息瓶頸方法基于下面的基本思想：給定兩個(gè)隨機(jī)變量和的先驗(yàn)聯(lián)合分布，壓縮其中一個(gè)隨機(jī)變量，同時(shí)保證盡可能多地維持兩個(gè)變量的互信息。依據(jù)香農(nóng)信息論，兩個(gè)隨機(jī)變量和的互信息表示它們的聯(lián)合分布關(guān)于各自邊緣分布乘積的相對熵，它反映了變量()包含的關(guān)于變量()的信息量。假定變量壓縮后的表示記為，有

18、。和著名的率失真理論相似，我們要在盡可能壓縮的表示長度和盡可能多地維持關(guān)于的信息之間尋求一個(gè)折中。每一種壓縮對應(yīng)著一種由到的賦值，表示的一個(gè)取值x對應(yīng)中取值的概率。一般情況下，每一個(gè)可以對應(yīng)中多個(gè)甚至所有取值，這種情況下的賦值稱為軟賦值，如果一個(gè)只對應(yīng)唯一一個(gè)，這種賦值為硬賦值。信息瓶頸方法就是找到一種最優(yōu)的賦值，最小化，這里，參數(shù)是拉格朗日乘子，用以保證包含足夠多地關(guān)于的信息。在對先驗(yàn)聯(lián)合分布不作任何假設(shè)的情況下，問題對應(yīng)著一個(gè)精確的最優(yōu)解。這個(gè)最優(yōu)解通過三個(gè)分布給出：第一個(gè)分布是的分布；第二個(gè)分布是由到的賦值；第三個(gè)分布是，它刻化和的關(guān)系。精確解的形式表達(dá)如下：,這里，是歸一化因子，參數(shù)決

19、定了賦值的“軟硬程度”，是和之間的Kullback-Leibler距離，用以度量和在表示時(shí)的偏差。方程組可以通過迭代的方式來求解，迭代是收斂的。當(dāng)參數(shù)時(shí)，我們得到的解對應(yīng)一種硬賦值，也就是說每一個(gè)只對應(yīng)于一個(gè)。此時(shí)，只考慮中的第2項(xiàng)，而忽略了第1項(xiàng)，進(jìn)而方程組可以表示成。方程組可以使用一種簡單的層次聚類方法來求解X18X。初始時(shí)，每一個(gè)單獨(dú)屬于一個(gè)類別，也就是說沒有對進(jìn)行任何壓縮。每一步，我們合并兩個(gè)類別，選擇要合并的兩個(gè)類別時(shí)，依據(jù)局部最小化信息損失的原則，選擇合并后減少最小的兩個(gè)類別進(jìn)行合并。假設(shè)要合并的兩個(gè)類別為和，合并后新生成的類別記為，合并過程可以形式化表示成方程組。合并代價(jià)是指合并

20、所帶來的互信息的減少量，定義為。通過一些簡單的代數(shù)變換，得到，這里，函數(shù)是Jensen-Shannon(JS)距離，計(jì)算方法為。對于我們的問題，有。JS距離是非負(fù)的，當(dāng)且僅當(dāng)兩個(gè)參數(shù)是一致的時(shí)候才取值為0，上界是1，且是對稱的。值得注意的是，合并代價(jià)可以看成參加合并“元素”的權(quán)重與其JS距離的乘積。3 基于信息瓶頸的社區(qū)發(fā)現(xiàn)方法3.1 圖的變換給定一個(gè)無向圖，假定變換后的二部圖記為。變換規(guī)則如下：1) 對于中的任意一個(gè)頂點(diǎn)，在中對應(yīng)兩個(gè)頂點(diǎn)和；2) 如果在G中頂點(diǎn)，對應(yīng)中兩條邊和；3)邊和的權(quán)重等于的權(quán)重。圖1是一個(gè)無向圖變換成二部圖的例子。對于有向圖，假定變換后的二部圖記為。變換規(guī)則為：1)

21、 對于中的任意一個(gè)頂點(diǎn)，在中對應(yīng)兩個(gè)頂點(diǎn)和；2) 如果在中頂點(diǎn)，對應(yīng)B中一條邊，這里使用尖括號(hào)表示邊是有向邊；3) 邊的權(quán)重等于的權(quán)重。圖1是一個(gè)有向圖變換成二部圖的例子。5353553353u1u2u3w1w2w3原始無向圖二部圖v2v3v2v3w3w2w1u1u2u3原始有向圖二部圖圖1 圖變換成二部圖的例子3.2 基于信息瓶頸的社區(qū)發(fā)現(xiàn)對于變換得到的二部圖網(wǎng)絡(luò)，其矩陣表示記為，矩陣的行對應(yīng)二部圖的左部，列對應(yīng)就二部圖的右部。矩陣元素表示邊或的權(quán)重，如果和之間沒有邊相連，權(quán)重為0。把二部圖的左部看成是隨機(jī)變量，右部看成是隨機(jī)變量，和的聯(lián)合分布可以由二部圖對應(yīng)的矩陣表示直接構(gòu)造出來。構(gòu)造方法

22、為對的所有元素均除以，是中所有元素之和，也是所有邊的權(quán)重之和（Total Weight）。對于無向網(wǎng)絡(luò)，原始網(wǎng)絡(luò)的頂點(diǎn)集和二部圖網(wǎng)絡(luò)任意一部的頂點(diǎn)集是完全一樣的。二部圖任意一部的壓縮表示均對應(yīng)著原始網(wǎng)絡(luò)的一種壓縮表示，而原始網(wǎng)絡(luò)的壓縮表示包含著原始網(wǎng)絡(luò)的社區(qū)結(jié)構(gòu)的全部知識(shí)。而且，無向網(wǎng)絡(luò)對應(yīng)的二部圖網(wǎng)絡(luò)是左、右部對稱的。因此，我們可以通過壓縮二部圖網(wǎng)絡(luò)的任意一部來達(dá)到發(fā)現(xiàn)原始網(wǎng)絡(luò)的社區(qū)結(jié)構(gòu)的目的。對于有向網(wǎng)絡(luò)，所得到二部圖的左部和右部從入邊和出邊兩個(gè)不同的角度來表現(xiàn)原始網(wǎng)絡(luò)的結(jié)構(gòu)特征。和無向網(wǎng)絡(luò)一樣，壓縮該二部圖的任意一部可以得到原始網(wǎng)絡(luò)的社區(qū)結(jié)構(gòu)。和無向網(wǎng)絡(luò)不同的是，壓縮左部和壓縮右部所得到

23、的社區(qū)結(jié)構(gòu)是不一樣的，兩種壓縮分別從入邊和出邊這兩個(gè)角度反映原始網(wǎng)絡(luò)的社區(qū)結(jié)構(gòu)特征。X表1X給出了一個(gè)有向網(wǎng)絡(luò)，該網(wǎng)絡(luò)共有12個(gè)結(jié)點(diǎn)，標(biāo)號(hào)為1-12，頂點(diǎn)1-6的出邊指向頂點(diǎn)1-3和7-9，頂點(diǎn)7-12的出邊指向頂點(diǎn)4-6和10-12，其它頂點(diǎn)之間沒有邊相連。對于這樣一個(gè)網(wǎng)絡(luò)，按照本文的變換方法得到一個(gè)二部圖網(wǎng)絡(luò)。如果壓縮其左部，得到的社區(qū)結(jié)構(gòu)反映了原始網(wǎng)絡(luò)的出邊特征，得到的社區(qū)為(1-6)和(7-12)；如果壓縮其右部，得到的社區(qū)結(jié)構(gòu)反映了原始網(wǎng)絡(luò)的入邊特征，得到的社區(qū)為(1-3,7-9)和(4-6,10-12)。相比于現(xiàn)有的方法，本文下面提出的基于信息瓶頸的方法可以很好地解決這一問題。表1

24、 有向網(wǎng)絡(luò)的一個(gè)例子 InOut1-37-94-610-121-6YesNo7-12NoYes現(xiàn)在介紹基于信息瓶頸的社區(qū)發(fā)現(xiàn)方法的一般框架。假設(shè)我們選擇壓縮二部圖網(wǎng)絡(luò)的左部，的壓縮會(huì)使和二部圖網(wǎng)絡(luò)的右部的互信息減少，需要在盡可能壓縮和盡可能多地維持關(guān)于的信息之間做折中。我們使用第二章介紹的信息瓶頸方法來完成這一折中任務(wù)。本文使用信息瓶頸方法的一種簡單實(shí)現(xiàn)層次聚類方法，這種方法對應(yīng)參數(shù)，得到的解是一種硬賦值，是對原始網(wǎng)絡(luò)的一種劃分。算法的基本思想是：初始時(shí)，每個(gè)頂點(diǎn)被看成是一個(gè)社區(qū)，然后逐步合并各個(gè)社區(qū)，每次合并選擇合并代價(jià)最小的兩個(gè)社區(qū)進(jìn)行合并，合并過程直到只有一個(gè)社區(qū)時(shí)停止。合并代價(jià)是基于第

25、二章介紹信息瓶頸方法時(shí)所使用的合并代價(jià)。算法輸出結(jié)果是一個(gè)dendrogram，這是一個(gè)有層次結(jié)構(gòu)的樹圖（圖4是一個(gè)例子），從每一層對該樹圖進(jìn)行切分都對應(yīng)原始網(wǎng)絡(luò)的一種劃分。選擇在哪一層進(jìn)行切分是一個(gè)重要的問題。我們使用modularity值來衡量一種劃分的質(zhì)量，選擇modularity值最大的那個(gè)劃分作為原始網(wǎng)絡(luò)的最終的劃分。X表2X給出了算法的具體實(shí)現(xiàn)。在計(jì)算時(shí)，只有當(dāng)之間有邊相連時(shí)，才需要計(jì)算，因?yàn)楹喜]有邊相連的和是沒有意義的。這樣大大減少了運(yùn)算次數(shù)，提高了算法的計(jì)算效率。表2 基于信息瓶頸社區(qū)發(fā)現(xiàn)方法的具體實(shí)現(xiàn)步驟輸入：一個(gè)網(wǎng)絡(luò)輸出：網(wǎng)絡(luò)的一種劃分初始化：1 把輸入網(wǎng)絡(luò)變換成二部圖網(wǎng)

26、絡(luò)，并表示成兩個(gè)隨機(jī)變量X和Y的聯(lián)合分布p(x, y)。2 構(gòu)建一個(gè)隨機(jī)變量3 對于任意的，計(jì)算循環(huán)：For - 找出最小的- 把合并成- 從C中刪除，并把加入到C中- 更新和相關(guān)的- 計(jì)算當(dāng)前的modularity值，記錄下來 End輸出結(jié)果：1 找出最大的modularity值2 輸出對應(yīng)的各個(gè)社區(qū)下面分析算法的時(shí)間復(fù)雜度。假設(shè)網(wǎng)絡(luò)的頂點(diǎn)個(gè)數(shù)為，邊的個(gè)數(shù)為。初始化階段，計(jì)算一個(gè)的時(shí)間復(fù)雜度為，由于只需要計(jì)算有邊相連的對應(yīng)的，那么初始化階段的總體時(shí)間復(fù)雜度為。循環(huán)階段，共循環(huán)了次，每次循環(huán)中，尋找最小的時(shí)間復(fù)雜度為，合并和刪除的時(shí)間復(fù)雜度為，更新時(shí)只更新了和相關(guān)的，因此時(shí)間復(fù)雜度不超過，計(jì)算

27、modularity值的時(shí)間復(fù)雜度也不超過。輸出結(jié)果的時(shí)間復(fù)雜度小于循環(huán)階段的時(shí)間復(fù)雜度。因此整個(gè)算法的時(shí)間復(fù)雜度取決于循環(huán)階段的時(shí)間復(fù)雜度，為。但這只是最壞情況下的時(shí)間復(fù)雜度，通常情況下算法的時(shí)間復(fù)雜度要比分析的低。在下一節(jié)的實(shí)驗(yàn)中，我們把該算法應(yīng)用到有5000多個(gè)頂點(diǎn)的網(wǎng)絡(luò)中，在幾分鐘內(nèi)便得到輸出結(jié)果。另外，這個(gè)算法是可以優(yōu)化的，這在我們以后的工作中解決。4 實(shí)驗(yàn)結(jié)果與分析本節(jié)分別在計(jì)算機(jī)生成的網(wǎng)絡(luò)和真實(shí)世界的網(wǎng)絡(luò)上驗(yàn)證基于信息瓶頸社區(qū)發(fā)現(xiàn)方法的有效性和適用性。4.1 計(jì)算機(jī)生成的網(wǎng)絡(luò)上的實(shí)驗(yàn)為了測試方法的有效性，使用計(jì)算機(jī)生成有已知社區(qū)結(jié)構(gòu)的網(wǎng)絡(luò)，在這樣的網(wǎng)絡(luò)上實(shí)驗(yàn)，測試我們的方法能否發(fā)

28、現(xiàn)或抽取出這些已知的社區(qū)結(jié)構(gòu)。4.1.1 網(wǎng)絡(luò)的生成使用計(jì)算機(jī)生成一系列有已知社區(qū)結(jié)構(gòu)的網(wǎng)絡(luò)X7X。每個(gè)網(wǎng)絡(luò)有128頂點(diǎn)，這些頂點(diǎn)分別屬于4個(gè)已知的社區(qū)中。頂點(diǎn)之間的邊是隨機(jī)添加的，同一個(gè)社區(qū)的兩個(gè)頂點(diǎn)之間有邊相連的概率是，不同社區(qū)的兩個(gè)頂點(diǎn)之間有邊相連的概率是。的選擇要保證頂點(diǎn)和其它社區(qū)頂點(diǎn)之間邊的總數(shù)為某個(gè)指定的值，的選擇保證頂點(diǎn)的度數(shù)等于16。隨著由0逐漸增大，社區(qū)結(jié)構(gòu)變得越來越模糊，社區(qū)發(fā)現(xiàn)變得越發(fā)困難。4.1.2 評測方法由于網(wǎng)絡(luò)中的“真實(shí)”社區(qū)結(jié)構(gòu)是已知的，給出一個(gè)社區(qū)劃分后，我們就有可能度量有多少個(gè)頂點(diǎn)是正確劃分的。比較發(fā)現(xiàn)的社區(qū)和網(wǎng)絡(luò)中已知的社區(qū)，對于發(fā)現(xiàn)的社區(qū)，把它和各個(gè)已知

29、社區(qū)進(jìn)行比較，找出重疊度最大的那個(gè)，和重疊的頂點(diǎn)認(rèn)為是正確劃分的頂點(diǎn)。對發(fā)現(xiàn)的各個(gè)社區(qū)都做類似的處理，從而得到正確劃分的頂點(diǎn)總數(shù)占所有頂點(diǎn)數(shù)的比率FVIC（Fraction of Vertices Identified Correctly）。對于每一個(gè)，我們可以得到一個(gè)FVIC，從而得到一個(gè)FVIC關(guān)于的函數(shù)。但是，當(dāng)發(fā)現(xiàn)的社區(qū)個(gè)數(shù)和已知的社區(qū)個(gè)數(shù)不一致時(shí)，上述度量方法存在不小的偏差。例如，如果已知社區(qū)個(gè)數(shù)為4個(gè)，而實(shí)際發(fā)現(xiàn)的社區(qū)個(gè)數(shù)遠(yuǎn)多于4個(gè)，且實(shí)際發(fā)現(xiàn)的社區(qū)都是已知社區(qū)的子集時(shí)，所有的頂點(diǎn)都被認(rèn)為是正確劃分的，但這個(gè)結(jié)果并不是我們希望的。這里我們還使用了一種更合適的度量方法歸一化后的互信息

30、(NMI)X4X。定義一個(gè)混淆矩陣，矩陣的每一行對應(yīng)一個(gè)“真實(shí)”的社區(qū)，每一列對應(yīng)一個(gè) “發(fā)現(xiàn)”的社區(qū)。的元素表示“真實(shí)”社區(qū)和發(fā)現(xiàn)的社區(qū)重合的頂點(diǎn)個(gè)數(shù)。矩陣第行的元素之和記為，矩陣第列的元素之和記為，的所有元素之和記為。我們用CR表示“真實(shí)”社區(qū)的個(gè)數(shù)，用CF表示發(fā)現(xiàn)的社區(qū)個(gè)數(shù)。基于信息論，我們得到發(fā)現(xiàn)的社區(qū)劃分F和真實(shí)的社區(qū)劃分R之間相似度一種度量當(dāng)發(fā)現(xiàn)的劃分和網(wǎng)絡(luò)的真實(shí)劃分一致時(shí)，NMI取值為1。如果發(fā)現(xiàn)的劃分和網(wǎng)絡(luò)的真實(shí)劃分完全獨(dú)立時(shí)，NMI取值為0。在下面的實(shí)驗(yàn)中，我們同時(shí)使用FVIC和NMI兩種評測方法來度量一種劃分的好壞。4.1.3 實(shí)驗(yàn)結(jié)果實(shí)驗(yàn)時(shí)，的取值由0到8，對于的任意一個(gè)

31、取值，為了降低偶然性帶來的影響，我們生成100個(gè)網(wǎng)絡(luò)，對每個(gè)網(wǎng)絡(luò)使用我們的方法發(fā)現(xiàn)其中的社區(qū)結(jié)構(gòu)，計(jì)算FVIC值和NMI值，然后求各自的平均值，得到對應(yīng)這個(gè)的平均FVIC值和平均NMI值。從圖2中，當(dāng)我們可以看出，當(dāng)不大于6時(shí)，我們的方法能正確劃分95%以上的頂點(diǎn)，相應(yīng)的NMI值也高達(dá)0.90以上；當(dāng)取值為7時(shí)，也能保證有80%以上的頂點(diǎn)被正確劃分；取8時(shí)，此時(shí)一個(gè)頂點(diǎn)和社區(qū)內(nèi)部頂點(diǎn)的連邊數(shù)等于它和社區(qū)外部頂點(diǎn)的連邊數(shù)，此時(shí)網(wǎng)絡(luò)的社區(qū)結(jié)構(gòu)變得模糊和難以識(shí)別。另外，為了說明本文所提方法的有效性，本文和Newman Fast方法X11X進(jìn)行了對比，Newman Fast方法是目前廣泛使用且效果較好

32、的社區(qū)發(fā)現(xiàn)方法之一。從圖2可以看出，使用FVIC和NMI中任一種評測方法，在大部分情況下，我們的方法都比Newman Fast算法要好。這說明，對于有已知社區(qū)結(jié)構(gòu)的網(wǎng)絡(luò)，我們的方法能很好地發(fā)現(xiàn)網(wǎng)絡(luò)的社區(qū)結(jié)構(gòu)。圖2 FVIC和NMI關(guān)于的變化曲線圖, NF表示Newman Fast算法11，IB表示本文的方法4.2 在真實(shí)網(wǎng)絡(luò)上的實(shí)驗(yàn)在上一小節(jié)中，在計(jì)算機(jī)產(chǎn)生的網(wǎng)絡(luò)上測試了本文方法的性能，這一節(jié)，我們將該方法應(yīng)用到一些真實(shí)的網(wǎng)絡(luò)上，驗(yàn)證方法的適用性。首先，我們在一個(gè)小規(guī)模的網(wǎng)絡(luò)上實(shí)驗(yàn)，驗(yàn)證方法的有效性；然后在一個(gè)有5000多個(gè)頂點(diǎn)的網(wǎng)絡(luò)上實(shí)驗(yàn)，驗(yàn)證方法的適用性。4.2.1 Zachary（圣扎伽

33、利）空手道俱樂部網(wǎng)絡(luò)Zachary空手道俱樂部網(wǎng)絡(luò)（圖3）是社會(huì)網(wǎng)絡(luò)分析的一個(gè)經(jīng)典例子。該網(wǎng)絡(luò)取材于美國一所大學(xué)的一個(gè)空手道俱樂部，俱樂部共有34個(gè)成員。Wayne Zachary通過兩年的觀察，獲取了34個(gè)成員的社會(huì)交往關(guān)系，從而得到了一個(gè)網(wǎng)絡(luò)。在這個(gè)網(wǎng)絡(luò)中，每個(gè)成員代表一個(gè)頂點(diǎn)，如果兩個(gè)成員在俱樂部內(nèi)或在俱樂部外有社會(huì)交往關(guān)系，這兩個(gè)成員對應(yīng)的頂點(diǎn)之間有一條邊相連。后來，俱樂部的管理者和老師之間就是否提高俱樂部的費(fèi)用發(fā)生了爭論，結(jié)果俱樂部分成了兩個(gè)分別以管理者和老師為中心的俱樂部。圖3中，圓形頂點(diǎn)和方形頂點(diǎn)分別代表俱樂部分開后形成的兩個(gè)新俱樂部的成員。圖3 Zachary空手道俱樂部網(wǎng)絡(luò)圖

34、4展示了我們的方法在Zachary空手道俱樂部網(wǎng)絡(luò)中所發(fā)現(xiàn)的社區(qū)結(jié)構(gòu)。圖的下半部分是一個(gè)dendrogram，展現(xiàn)了頂點(diǎn)的合并過程，圖的上半部分表述了合并過程中相應(yīng)的modularity值的變化趨勢。共發(fā)現(xiàn)了5個(gè)社區(qū)，對應(yīng)的modularity值為0.392，而俱樂部的實(shí)際拆分卻只有兩個(gè)部分，但是拆分成兩個(gè)部分所對應(yīng)的modularity值并不是最優(yōu)的。造成算法發(fā)現(xiàn)的劃分和實(shí)際劃分不一致另有原因，俱樂部的實(shí)際劃分是一種指定社區(qū)劃分個(gè)數(shù)的社區(qū)發(fā)現(xiàn)，而我們的算法卻是在事先不知道社區(qū)個(gè)數(shù)的情況下進(jìn)行社區(qū)發(fā)現(xiàn)的。從圖4中，可以看出，如果限定社區(qū)個(gè)數(shù)為2，我們的算法所發(fā)現(xiàn)的劃分和實(shí)際的劃分是幾乎一致的，

35、只有一個(gè)頂點(diǎn)3被錯(cuò)誤劃分，從圖4中還可以看出，事實(shí)上，頂點(diǎn)3和實(shí)際劃分的每個(gè)部分聯(lián)系緊密程度差不多。另外，當(dāng)社區(qū)個(gè)數(shù)限定為2時(shí)，算法發(fā)現(xiàn)的劃分所對應(yīng)的modularity值為0.360，這個(gè)值與算法發(fā)現(xiàn)的最優(yōu)值差別并不大。圖4 對Zachary空手道俱樂部網(wǎng)絡(luò)，使用我們的方法得到的樹圖(dendrogram)4.2.2 詞聯(lián)想網(wǎng)絡(luò)詞聯(lián)想網(wǎng)絡(luò)F The University of South Florida word association, rhyme, and word fragment norms. /FreeAssociation/.F(Word Asso

36、ciation Network)是美國南佛羅里達(dá)大學(xué)(University of South Florida)收集的詞自由聯(lián)想網(wǎng)絡(luò)，該網(wǎng)絡(luò)通過問卷調(diào)查獲得。共對5019個(gè)詞進(jìn)行了調(diào)查，共有6000人參與了此次調(diào)查。調(diào)查時(shí)，對于每個(gè)詞，要求參與者寫出和該詞關(guān)系最密切的詞。調(diào)查共收到近75萬個(gè)的針對這5019個(gè)詞的應(yīng)答。被調(diào)查的詞稱為“提示詞”，用戶提供的對提示詞的應(yīng)答稱為“目標(biāo)詞”。設(shè)為任意一個(gè)提示詞，為任意一個(gè)目標(biāo)詞，#G表示作為提示詞出現(xiàn)的次數(shù)，#P表示作為提示詞的目標(biāo)詞而出現(xiàn)的次數(shù)，那么提示詞到目標(biāo)詞的前向強(qiáng)度為，如果同時(shí)也是一個(gè)提示詞，那么到的后向強(qiáng)度(BSG)等于到的前向強(qiáng)度。目標(biāo)詞不

37、一定在5019個(gè)提示詞中出現(xiàn)，我們這里只保留在提示詞集合中出現(xiàn)的目標(biāo)詞，這樣一來，每一個(gè)詞既是提示詞，又是目標(biāo)詞。我們定義詞和詞的關(guān)聯(lián)強(qiáng)度為到的前向強(qiáng)度（等于到的后向強(qiáng)度）加上到的后向強(qiáng)度（等于到的前向強(qiáng)度）。5019個(gè)詞看成是5019個(gè)頂點(diǎn)，如果兩個(gè)詞之間的關(guān)聯(lián)強(qiáng)度大于某個(gè)閾值（本文取值為0.025），這兩個(gè)詞對應(yīng)的頂點(diǎn)存在一條邊。這樣我們就得到了一個(gè)有5019個(gè)頂點(diǎn)的無向無權(quán)簡單圖。我們的方法共發(fā)現(xiàn)了18個(gè)社區(qū)(圖5-a)，此時(shí)對應(yīng)的modularity值為0.423，這表明詞聯(lián)想網(wǎng)絡(luò)具有良好的社區(qū)結(jié)構(gòu)。其中有一個(gè)社區(qū)只包含一個(gè)頂點(diǎn)(未在圖5-a中畫出)，分析詞聯(lián)想網(wǎng)絡(luò)，發(fā)現(xiàn)這個(gè)頂點(diǎn)是一個(gè)

38、孤立頂點(diǎn)，因此它單獨(dú)構(gòu)成一個(gè)社區(qū)是合適的。為了更清晰地分析各個(gè)社區(qū)的內(nèi)部結(jié)構(gòu)，使用第三節(jié)中的方法，進(jìn)一步分別對17個(gè)社區(qū)(只包含一個(gè)頂點(diǎn)的社區(qū)除外)進(jìn)行了社區(qū)發(fā)現(xiàn)。圖5-b展示了其中一個(gè)社區(qū)的內(nèi)部結(jié)構(gòu)，對這個(gè)社區(qū)進(jìn)行重新社區(qū)發(fā)現(xiàn)時(shí)，我們得到的modularity值高達(dá)0.691，這說明這個(gè)社區(qū)內(nèi)部具有非常明顯的社區(qū)結(jié)構(gòu)。事實(shí)上，17個(gè)社區(qū)都具有明顯的社區(qū)結(jié)構(gòu)，這表明詞聯(lián)想網(wǎng)絡(luò)的社區(qū)結(jié)構(gòu)是有層次性的。不同層次的社區(qū)對應(yīng)著網(wǎng)絡(luò)不同粒度的劃分。圖5-c向我們展示了其中一個(gè)社區(qū)內(nèi)部的子社區(qū)所包含的各個(gè)詞，這些詞大多是和天文學(xué)有關(guān)的。其它各個(gè)子社區(qū)所包含的詞也具有明顯的類別特征,這里不一一列舉。值得一提

39、的是，我們發(fā)現(xiàn)的社區(qū)大小不滿足power-law規(guī)則X1XX2X。經(jīng)過分析，我們發(fā)現(xiàn)5019個(gè)頂點(diǎn)所構(gòu)成的詞聯(lián)想網(wǎng)絡(luò)的頂點(diǎn)度分布呈泊松分布，而一般情況下，復(fù)雜網(wǎng)絡(luò)的頂點(diǎn)度分布是滿足power-law規(guī)則的，這可能是造成所發(fā)現(xiàn)的社區(qū)大小不滿足power-law規(guī)則的原因。本文提出的方法能夠發(fā)現(xiàn)詞聯(lián)想網(wǎng)絡(luò)中不同粒度的社區(qū)，且這些社區(qū)都是有明確意義的社區(qū)，這對我們理解詞聯(lián)想網(wǎng)絡(luò)的結(jié)構(gòu)是非常重要的，而理解詞聯(lián)想網(wǎng)絡(luò)的結(jié)構(gòu)對使用詞聯(lián)想網(wǎng)絡(luò)是非常有意義的。5 結(jié)論和下一步的工作本文從一個(gè)新的角度重新思考社區(qū)發(fā)現(xiàn)問題，認(rèn)為社區(qū)結(jié)構(gòu)是網(wǎng)絡(luò)結(jié)構(gòu)規(guī)則性的一種體現(xiàn)，而發(fā)現(xiàn)網(wǎng)絡(luò)中的社區(qū)結(jié)構(gòu)是去掉那些不重要的細(xì)節(jié)而保留

40、網(wǎng)絡(luò)的整體拓?fù)涮卣?，這一認(rèn)識(shí)是本文的基礎(chǔ)?；谏鲜稣J(rèn)識(shí)，社區(qū)發(fā)現(xiàn)問題可以看成是對網(wǎng)絡(luò)拓?fù)涞挠袚p壓縮。社區(qū)發(fā)現(xiàn)目標(biāo)是尋找一種網(wǎng)絡(luò)結(jié)構(gòu)的高效壓縮表示，這種壓縮能夠盡可能多地反映原始網(wǎng)絡(luò)中的結(jié)構(gòu)規(guī)則性。進(jìn)而，本文在信息論的框架下，提出了一種基于信息瓶頸的社區(qū)發(fā)現(xiàn)方法。該方法從信息論的角度為社區(qū)發(fā)現(xiàn)問題提供了一種理論解釋，即網(wǎng)絡(luò)社區(qū)結(jié)構(gòu)的最優(yōu)表示是原始網(wǎng)絡(luò)的壓縮比和反映原始網(wǎng)絡(luò)結(jié)構(gòu)規(guī)則之間的最優(yōu)折中。對于有向網(wǎng)絡(luò)的社區(qū)發(fā)現(xiàn)，現(xiàn)有的社區(qū)發(fā)現(xiàn)方法是忽略網(wǎng)絡(luò)中邊的方向，進(jìn)而使用無向網(wǎng)絡(luò)社區(qū)發(fā)現(xiàn)的方法來解決。事實(shí)上，這種做法損失了原始有向網(wǎng)絡(luò)的許多信息，邊的方向自身向我們提供了網(wǎng)絡(luò)結(jié)構(gòu)的一種反映?；诒疚氖褂?/p>

41、的網(wǎng)絡(luò)變換方法，可以方便地把有向網(wǎng)絡(luò)轉(zhuǎn)換成一個(gè)二部圖網(wǎng)絡(luò)，該二部圖網(wǎng)絡(luò)的左部反映有向網(wǎng)絡(luò)的出邊特征，右部反映有向網(wǎng)絡(luò)的入邊特征。然后，使用本文提出基于信息瓶頸的社區(qū)發(fā)現(xiàn)方法，可以很方便地發(fā)現(xiàn)分別基于出邊或入邊特征的社區(qū)結(jié)構(gòu)。真實(shí)世界中有許多網(wǎng)絡(luò)自身就是一個(gè)二部圖網(wǎng)絡(luò)，和現(xiàn)有方法相比，本文提出的方法可以很方便地應(yīng)用到這類網(wǎng)絡(luò)的社區(qū)發(fā)現(xiàn)中。另外，許多網(wǎng)絡(luò)中存在不止一類頂點(diǎn)，頂點(diǎn)之間也存在不止一種關(guān)系，這種網(wǎng)絡(luò)被稱為異質(zhì)網(wǎng)絡(luò)。例如，在文獻(xiàn)及其作者構(gòu)成的網(wǎng)絡(luò)中，存在文獻(xiàn)和作者兩類頂點(diǎn)，也存在文獻(xiàn)和作者之間有署名關(guān)系，文獻(xiàn)之間有引用關(guān)系。對于這種異質(zhì)網(wǎng)絡(luò)，如何發(fā)現(xiàn)其中的社區(qū)結(jié)構(gòu)是一個(gè)有著重要研究意義和應(yīng)

42、用價(jià)值的問題。我們下一步的工作將主要致力于解決這一問題。致 謝中國科學(xué)院計(jì)算技術(shù)研究所信息智能與信息安全中心社會(huì)計(jì)算與P2P課題組的呂建明、陳國耀、陳友等同事對本文的完成提出了很多有益的建議，互聯(lián)網(wǎng)挖掘與搜索組的杜偉夫?qū)Ρ疚牡男薷奶峁┝藥椭?，在此一并表示感謝。最后，特別感謝評審老師細(xì)致耐心的審查。圖5 左邊的(a)圖展示詞聯(lián)想網(wǎng)絡(luò)的社區(qū)結(jié)構(gòu)， 共有18個(gè)社區(qū)(其中一個(gè)社區(qū)只包含一個(gè)頂點(diǎn)，未在圖中畫出）。中間的(b)圖展示了其中一個(gè)社區(qū)內(nèi)部的社區(qū)結(jié)構(gòu)，該社區(qū)內(nèi)部共有13個(gè)子社區(qū)。最后，右邊的圖給出了13個(gè)子社區(qū)中其中一個(gè)子社區(qū)所包含的各個(gè)詞。圓圈內(nèi)的數(shù)字表示社區(qū)的大小(也就是社區(qū)所包含的頂點(diǎn)個(gè)數(shù)

43、)，圓圈的大小也反映了社區(qū)的大小。參 考 文 獻(xiàn)1 Albert R, Barabsi A-L. Statistical mechanics of complex networks. Rev. Mod. Phys., 2002, 74: 47-972 Newman M E J The structure and function of complex networks. SIAM Review, 2003, 45: 167-2563 Newman M E J Detecting community structure in networks. Eur. Phys. J. B, 2004, 38

44、: 321-3304 Danon L, Daz-Guilera A, Duch J, Arenas A. Comparing community structure identification. J. Statistical. Mechanics, 2005, P090085 Kernighan B W, Lin S. An efficient heuristic procedure for partitioning graphs. Bell System Technical Journal, 1970, 49: 291-3076 Palla G, Dernyi I, Farkas I, T

45、. Vicsek T. Uncovering the overlapping community structure of complex networks in nature and society. Nature, 2005, 435: 814-8187 Newman M E J, Girvan M. Finding and evaluating community structure in networks. Phys. Rev. E, 2004, 69: 0261138 Fortunato S, Latora V, Marchiori M. A method to find commu

46、nity structures based on information centrality. Phys. Rev. E, 2004, 70: 0561049 Pons P, Latapy M. Computing communities in large networks using random walks/Proceedings of the 20th International Symposium on Computer and Information Sciences, volume 3733 of Lecture Notes in Computer Science, Spring

47、er, New York, 2005: 284-29310 Newman M E J. Finding community structure in networks using the eigenvectors of matrices. Phys. Rev. E, 2006, 74: 03610411 Newman M E J. Fast algorithm for detecting community structure in networks. Phys. Rev. E, 2004, 69: 06613312 Clauset A, Newman M E J, Moore C. Find

48、ing community structure in very large networks. Phys. Rev. E, 2004, 70: 06611113 Reichardt J, Bornholdt S. Statistical mechanics of community detection. Phys. Rev. E, 2006, 74: 01611014 Duch J, Arenas A. Community detection in complex networks using extremal optimization. Phys. Rev. E, 2005, 72: 027

49、10415 Rosvall M, Bergstrom C T. An information-theoretic framework for resolving community structure in complex networks. Proc. Natl. Acad. Sci. USA, 2007, 104: 7327-733116 Ziv E, Middendor M, Wiggins C. An information-theoretic approach to network modularity. Phys. Rev. E, 2005, 71: 04611717 Tishby

50、 N, Pereira F C, Bialek W. The information bottleneck method, 1999, HarXiv:physics/0004057v118 Slonim N, Tishby N. Agglomerative information bottleneck/Proceedings of Neural Information Processing Systems (NIPS-99), 1999: 617-623SHEN Hua-Wei, born in 1982, Ph. D. candidate. His research interests in

51、clude social computing, complex networks, information retrieval.CHENG Xue-Qi, born in 1971, Ph. D. , professor. His research interests include network information security, large-scale information retrieval and knowledge mining, peer-to-peer computing .CHEN Hai-Qiang, born in 1979, Ph. D. candidate.

52、 His research interests include social computing, complex networks, information retrieval.LIU Yue, born in 1971, Ph. D. , associate professor. His research interests include Web search and mining, analysis on complex networks and social computing, distributed system.BackgroundResearch on complex networks attracts considerable attentions from many scientific fields. The main focus is on three aspects: the statistical properties of complex networks, the model of the evolution of complex networks, t