基于網(wǎng)絡(luò)中節(jié)點(diǎn)間緊密度的層次聚類社區(qū)發(fā)現(xiàn)算法

1、在網(wǎng)絡(luò)理論研宄屮，數(shù)量巨大的節(jié)點(diǎn)以及節(jié)點(diǎn)之間復(fù)雜的交互關(guān)系構(gòu)成了復(fù) 雜網(wǎng)絡(luò)和復(fù)雜網(wǎng)絡(luò)的網(wǎng)絡(luò)結(jié)構(gòu)。用數(shù)學(xué)語言表達(dá)，即一個(gè)圖有著足夠復(fù)雜的拓?fù)?結(jié)構(gòu)特征1。復(fù)雜網(wǎng)絡(luò)中的一種普遍現(xiàn)象就是社區(qū)現(xiàn)象，它表達(dá)了社區(qū)中的個(gè)體 具有某一方面共同特征的性質(zhì)。社區(qū)發(fā)現(xiàn)在很多學(xué)科有重要應(yīng)用，如在計(jì)算機(jī)學(xué) 科中，增強(qiáng)網(wǎng)絡(luò)銷售功能、提高網(wǎng)絡(luò)服務(wù)質(zhì)量等；在社會(huì)學(xué)中，發(fā)現(xiàn)動(dòng)物社會(huì)組 織結(jié)構(gòu)、揭示政府職能構(gòu)成和運(yùn)行方式、發(fā)現(xiàn)某一領(lǐng)域的科學(xué)家群組等；在生物 學(xué)領(lǐng)域功能基因聚類等。近年來，科學(xué)家們提出了關(guān)于社區(qū)發(fā)現(xiàn)的很多新方法。本文首先介紹了幾種 常見的復(fù)雜網(wǎng)絡(luò)以及其的特性。在此基礎(chǔ)上介紹了基于迭代二分法(iterative b

2、isection)的kernighanlin算法、i普二分法(spectral bisection),棊于去邊方法 的g-n算法、radicchi算法，層次聚類法(hierarchical clustering)和w-h算法。 分析了這些算法的時(shí)間復(fù)雜度等因素，指出了它們的優(yōu)勢(shì)和不足，并且還給出了 這些算法的適用范圍。本文的主要研允內(nèi)容是基于網(wǎng)絡(luò)中節(jié)點(diǎn)間緊密度的層次聚類社區(qū)發(fā)現(xiàn)算法。 在層次聚類算法中，傳統(tǒng)的節(jié)點(diǎn)間緊密度的計(jì)算方法主要是基于網(wǎng)絡(luò)的拓?fù)浣Y(jié) 構(gòu)，如余弦相似性(cosine similarity )、歐拉距離和皮爾遜系數(shù)(pearson correlation coefficient

3、)等。本文節(jié)點(diǎn)間相似度的計(jì)算是基于節(jié)點(diǎn)之間信息交流來往的頻率， 即節(jié)點(diǎn)間邊權(quán)值的大小來衡量節(jié)點(diǎn)的緊密度。兩個(gè)節(jié)點(diǎn)之間交流越頻繁，說明這 兩個(gè)節(jié)點(diǎn)的緊密度就越高，同屬于一個(gè)社區(qū)的可能性就越大。將計(jì)算出來的緊密 度值存儲(chǔ)與緊密度二叉堆中。同時(shí)把節(jié)點(diǎn)之間的相似度計(jì)算擴(kuò)展到社區(qū)之間，更 新緊密度二叉堆中的值，利用二叉堆中的值，合并社區(qū)，直到社區(qū)的合并結(jié)果滿 足某一條件為止。實(shí)驗(yàn)表明，該方法能較好且合理的發(fā)現(xiàn)社區(qū)結(jié)構(gòu)。關(guān)鍵詞：社區(qū)發(fā)現(xiàn)；復(fù)雜網(wǎng)絡(luò)；社區(qū)結(jié)構(gòu)；層次聚類第1章緒論1.1研究背景和意義最近幾年，人多數(shù)國家對(duì)復(fù)雜網(wǎng)絡(luò)的研究都趨于狂熱。隨著計(jì)算機(jī)對(duì)數(shù)據(jù)的 存儲(chǔ)和處理的能力越來越強(qiáng)，以及人規(guī)模系統(tǒng)的數(shù)

4、據(jù)庫的興起，使我們真正認(rèn)識(shí) 了網(wǎng)絡(luò)的特征數(shù)據(jù)，發(fā)現(xiàn)真實(shí)網(wǎng)絡(luò)既不是規(guī)則的，也不是隨機(jī)的，而是復(fù)雜的， 并ii呈現(xiàn)一定規(guī)律的。在信息時(shí)代，網(wǎng)絡(luò)的社區(qū)發(fā)現(xiàn)存在更加普遍，發(fā)現(xiàn)技術(shù)應(yīng)用更加方便，其服 務(wù)價(jià)值和商業(yè)價(jià)值更人。研究在線社會(huì)網(wǎng)絡(luò)離不開社會(huì)網(wǎng)絡(luò)的分析方法，尤其是 社區(qū)可為信息推送、個(gè)性化服務(wù)等提供基本數(shù)據(jù)。所以，在復(fù)雜網(wǎng)絡(luò)屮進(jìn)行社區(qū)發(fā)現(xiàn)意義非比尋常。大量與社區(qū)發(fā)現(xiàn)相關(guān)的論 文都被刊登上丫physical review epnasnaturescience等世界頂級(jí) 的學(xué)術(shù)期刊，www、cikm、sigir、sigkdd、icdm、ecmlpkdd 等著名 的工作組以及越來越多的國際會(huì)議都在研究探

5、討社區(qū)發(fā)現(xiàn)的問題。社區(qū)發(fā)現(xiàn)技術(shù)在數(shù)據(jù)挖掘和探查性分析屮是一種非常重要的技術(shù)。研究大型 復(fù)雜網(wǎng)絡(luò)，更加關(guān)注搜索和發(fā)現(xiàn)潛在的網(wǎng)絡(luò)社區(qū)，這是研究中更重要的方面。主 要涉及的領(lǐng)域有：市場(chǎng)學(xué)、數(shù)據(jù)挖掘、社會(huì)網(wǎng)絡(luò)分析、統(tǒng)計(jì)學(xué)、機(jī)器學(xué)習(xí)、空間 數(shù)據(jù)庫技術(shù)和生物學(xué)等領(lǐng)域，其應(yīng)用非常廣泛。在線社會(huì)網(wǎng)絡(luò)相比其他在線網(wǎng)絡(luò)而言，則是更能影響人們現(xiàn)實(shí)生活關(guān)系的網(wǎng) 絡(luò)。心理學(xué)家和社會(huì)學(xué)家研宄人尺度社會(huì)網(wǎng)因其發(fā)展也有了較人的提高，對(duì)他們 在這些網(wǎng)絡(luò)屮尋找新形式的集體或個(gè)人行為有許多幫助。社會(huì)學(xué)家分析非在線社 會(huì)網(wǎng)絡(luò)會(huì)借鑒在線社會(huì)網(wǎng)絡(luò)，或者研究在線社會(huì)網(wǎng)絡(luò)在新的社會(huì)行為特征，參考 在線社會(huì)網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)研究的基礎(chǔ)。信息社會(huì)的一

6、些急需回答的問題在社會(huì)網(wǎng)絡(luò) 分析的一些初步應(yīng)用上有了答案。例如：bany在其文獻(xiàn)上用社會(huì)網(wǎng)絡(luò)分析的思 想和方法研究了現(xiàn)代社會(huì)中人際關(guān)系的變化特征。在線社會(huì)網(wǎng)絡(luò)的研究有跟現(xiàn)實(shí) 社會(huì)網(wǎng)絡(luò)密切相關(guān)的動(dòng)力學(xué)，網(wǎng)絡(luò)演化規(guī)律，結(jié)構(gòu)特性等方面的主題。最近幾年，關(guān)于復(fù)雜網(wǎng)絡(luò)的研宂屮，復(fù)雜網(wǎng)絡(luò)社區(qū)發(fā)現(xiàn)算法的研究設(shè)計(jì)己成 為重中之重。首先，社區(qū)發(fā)現(xiàn)技術(shù)的實(shí)用價(jià)值非常重大。例如，在社會(huì)網(wǎng)絡(luò)屮，社區(qū)代表 是真實(shí)的社會(huì)團(tuán)體，社會(huì)團(tuán)體內(nèi)部的每個(gè)人都具有相同或類似的背景和興趣；在 引文網(wǎng)絡(luò)中，若干個(gè)論文的集合組成一個(gè)社區(qū)，ii每個(gè)社區(qū)中的論文代表的是一 個(gè)相同的主題；在萬維網(wǎng)屮，社區(qū)發(fā)現(xiàn)的結(jié)果是一些網(wǎng)站的集合，但是每個(gè)網(wǎng)站

7、 集合討論主題都是相同或類似的23;在電子電路網(wǎng)絡(luò)或者生物化學(xué)網(wǎng)絡(luò)中，社 區(qū)發(fā)現(xiàn)的結(jié)果是一些功能單元，同一類功能單元被劃分到同一個(gè)社區(qū)中4。發(fā)現(xiàn) 這些網(wǎng)絡(luò)中的社區(qū)不僅為個(gè)性化服務(wù)、信息推送，提供基本的理論根據(jù)，而且有 助于加深我們有效的理解和幫助這些網(wǎng)絡(luò)的開發(fā)。在如今的信息時(shí)代，隨著越來 越普遍存在的社區(qū)，以及越來越方便的發(fā)現(xiàn)技術(shù)，社區(qū)發(fā)現(xiàn)技術(shù)的商業(yè)價(jià)值更是 越來越大。其次，社區(qū)發(fā)現(xiàn)技術(shù)的發(fā)展在一定程度上影響了對(duì)復(fù)雜網(wǎng)絡(luò)的研允。在實(shí)際 網(wǎng)絡(luò)世界屮，很多處都有復(fù)雜網(wǎng)絡(luò)，它對(duì)社區(qū)發(fā)現(xiàn)技術(shù)有很多影響。而且復(fù)雜網(wǎng) 絡(luò)和社區(qū)發(fā)現(xiàn)技術(shù)彼此之間存在非常緊密的關(guān)聯(lián)。過去的一些日子里，眾多學(xué)者 發(fā)現(xiàn)這些網(wǎng)絡(luò)都是

8、由若干個(gè)“社區(qū)”構(gòu)成的，經(jīng)過認(rèn)真分析研宂之后，發(fā)現(xiàn)這些 網(wǎng)絡(luò)共同具有一個(gè)性質(zhì)，即這些網(wǎng)絡(luò)具有一定的物理意義和數(shù)學(xué)特性，具體地說 來，雖然社區(qū)之間的節(jié)點(diǎn)連接相對(duì)較少，但是社區(qū)內(nèi)部節(jié)點(diǎn)之間的連接卻十分緊 密。社區(qū)發(fā)現(xiàn)技術(shù)的發(fā)展，使我們對(duì)大型復(fù)雜網(wǎng)絡(luò)有了更加清楚的了解，同時(shí)社 區(qū)發(fā)展技術(shù)也從另外一個(gè)角度推動(dòng)了我們對(duì)復(fù)雜網(wǎng)絡(luò)的研宄。最后，社區(qū)發(fā)現(xiàn)技術(shù)對(duì)于理論研允具有非常高的學(xué)術(shù)價(jià)值。廣義上說，我們 可以通過研宂所發(fā)現(xiàn)的社區(qū)內(nèi)部結(jié)構(gòu)較為緊密的社區(qū)，利用社區(qū)發(fā)現(xiàn)的結(jié)果以及 思路，以不同的眼光去研究其他領(lǐng)域。以專家推薦為例，社區(qū)發(fā)現(xiàn)技術(shù)可以很方 便地幫助我們?cè)谀骋谎绣愁I(lǐng)域找到關(guān)系十分緊密的專家。不過，從發(fā)現(xiàn)

9、的效率、 效果上來看，fi前我們還有很多工作需要去做，因?yàn)槟壳暗纳鐓^(qū)發(fā)現(xiàn)技術(shù)都具有 局限性。特別是最近幾年，許多研宄社區(qū)發(fā)現(xiàn)的技術(shù)和方法都被應(yīng)用到各行各業(yè), 其方法的優(yōu)勢(shì)和劣勢(shì)經(jīng)過實(shí)際的驗(yàn)證之后也被完全地暴露了出來。fi前，社會(huì)領(lǐng) 域中的社區(qū)發(fā)現(xiàn)，在許多國家已經(jīng)成為學(xué)者的研宂重點(diǎn)對(duì)象，因?yàn)樯鐣?huì)網(wǎng)絡(luò)規(guī)模 對(duì)社區(qū)發(fā)現(xiàn)方法的效果和效率有較大影響，網(wǎng)絡(luò)規(guī)模越大，影響也隨之增大。以萬維網(wǎng)為例，我們按照社區(qū)來闡述萬維網(wǎng)的一些優(yōu)點(diǎn)：第一，萬維網(wǎng)中的所有社會(huì)活動(dòng)的代表是社區(qū)，我們通過了解存在于萬維網(wǎng) 屮的知識(shí)信息來深入研究社區(qū)的方式，并了解網(wǎng)絡(luò)信息組織結(jié)構(gòu)的發(fā)展?fàn)顩r；社 區(qū)為內(nèi)聯(lián)網(wǎng)和因特網(wǎng)的相關(guān)服務(wù)提供了很好

10、的門戶。第二，社區(qū)可以為用戶提供一些可靠的有價(jià)值信息。社區(qū)可以幫助用戶挖掘 自己感興趣的信息，通過對(duì)網(wǎng)絡(luò)社區(qū)信息進(jìn)一步挖掘，不僅可以發(fā)現(xiàn)對(duì)我們個(gè)人 推薦的指導(dǎo)，而且還可以使我們可以進(jìn)行方便的智能搜索和瀏覽信息。第三，作為社會(huì)性網(wǎng)絡(luò)的萬維網(wǎng)，社區(qū)代表了萬維網(wǎng)的社會(huì)活動(dòng)。該技術(shù)有 著非常重要的作用，例如在一些特殊的領(lǐng)域，以犯罪偵查為例，從偵查犯罪的視 角出發(fā)，我們可以利用公安機(jī)關(guān)里已經(jīng)記錄的嫌疑人交往數(shù)據(jù)，通過對(duì)這些數(shù)據(jù) 的有機(jī)分析，將犯罪學(xué)的知識(shí)和社區(qū)發(fā)現(xiàn)技術(shù)相結(jié)合，加入一些人工處理過程， 經(jīng)過計(jì)算機(jī)最后的分析，我們就可以得到一些黑社會(huì)組織等犯罪團(tuán)伙的信息，從 而減少了公安機(jī)關(guān)犯罪偵查的工作難度

11、。最后，消費(fèi)者可以輕易地在相關(guān)的銷售商中準(zhǔn)確地找到社區(qū)的概念。我們可 以知道社區(qū)各個(gè)商家感興趣的特定客戶，有利于我們進(jìn)行篩選，通過發(fā)現(xiàn)的社區(qū) 來評(píng)估因特網(wǎng)的社會(huì)性和知識(shí)性，如果用戶對(duì)某個(gè)方面感興趣，也可以研究這些 用戶的組成形式。例如在電信業(yè)務(wù)行業(yè)，我們可以通過社區(qū)挖掘出一些客戶間的 緊密聯(lián)系，并為客戶提供有針對(duì)性的服務(wù)，可以更好地提高企業(yè)的效率?？偠灾鐓^(qū)發(fā)現(xiàn)技術(shù)有著非常重要的研究意義，它已經(jīng)成為社會(huì)網(wǎng)絡(luò)分 析、信息檢索和數(shù)據(jù)挖掘等許多科學(xué)領(lǐng)域關(guān)注的重點(diǎn)。1.2國內(nèi)外研究概況復(fù)雜網(wǎng)絡(luò)中的社區(qū)發(fā)現(xiàn)具有相當(dāng)大的理論和現(xiàn)實(shí)意義，當(dāng)前科學(xué)家已經(jīng)提出 和發(fā)現(xiàn)了許多社區(qū)探測(cè)方法?；趫D論中二分法算法

12、的主要思想是將圖中的節(jié)點(diǎn)劃分為給定數(shù)目的若干 個(gè)子集，要求劃分后各子集間連邊數(shù)目最小，從而使得子集中節(jié)點(diǎn)間連邊數(shù)目最 大。該問題己被證明為np難題，所以人們提出了各種以求得問題的近似解的算 法。任各種算法中，kernighan-lin算法和譜方法(spectral method)是兩種典型的算法。二十世紀(jì)七十年代初期，kemighan和lin提出了采用試探優(yōu)化方法來發(fā)現(xiàn) 網(wǎng)絡(luò)中的社區(qū)結(jié)構(gòu)，該算法基于貪婪算法原理，簡(jiǎn)稱k-l算法算法基木思想 是，引入效益函數(shù)q,計(jì)算交換網(wǎng)絡(luò)中不同社區(qū)之間的節(jié)點(diǎn)或者將節(jié)點(diǎn)劃分到其 他社區(qū)中效益函數(shù)q的值，選取使q值最大的網(wǎng)絡(luò)劃分。如果網(wǎng)絡(luò)中節(jié)點(diǎn)數(shù)量 非常大，則該算

13、法的時(shí)間復(fù)雜度很高。其中，譜方法將社區(qū)劃分問題轉(zhuǎn)化為優(yōu)化二次型問題，通過計(jì)算圖的拉普拉 斯矩陣的第二小特征向量來優(yōu)化預(yù)定義的“截”函數(shù)6。二十世紀(jì)九十年代，pothen 等提出一種劃分網(wǎng)絡(luò)為兩個(gè)社區(qū)的二分法，該方法基于圖的拉普拉斯矩陣的譜特 征算法應(yīng)用第二小特征值所對(duì)應(yīng)的特征向量，將社區(qū)中的節(jié)點(diǎn)根據(jù)特征向量 中每個(gè)值的正負(fù)將對(duì)應(yīng)節(jié)點(diǎn)劃分。girvan和newman2002年在社ix發(fā)現(xiàn)中引入邊介數(shù)的概念，然后基于邊介 數(shù)對(duì)網(wǎng)絡(luò)中節(jié)點(diǎn)進(jìn)行分裂，該算法即為gn算法f71。算法實(shí)現(xiàn)社區(qū)劃分的基本思 想是將網(wǎng)絡(luò)中介數(shù)最大的邊依次移除，通過去邊實(shí)現(xiàn)社區(qū)發(fā)現(xiàn)。2004年newman 將gn算法擴(kuò)展到加權(quán)網(wǎng)

14、絡(luò)|81。newman基于貪婪原理提出一種與去邊方法相對(duì) 的凝聚算法，該算法依次計(jì)算社區(qū)間的模塊度，并使它連續(xù)增大，復(fù)雜度為o(z?z + n)n 稱為快速算法|91。newman、moore 和 clauset 等人基于 newman 快 速算法，提出了一種新的貪婪算法即cnm算法fin1。cnm算法采用二叉堆數(shù)據(jù)結(jié)構(gòu)存儲(chǔ)社區(qū)之間的模塊度值，其復(fù)雜度為121%2 2006年基于模塊度矩陣, newman提出一種譜社區(qū)劃分算法lh1,并于兩年后把該算法擴(kuò)展應(yīng)用到有向網(wǎng)絡(luò) 中。tyler等人在2003年發(fā)現(xiàn)，為提高gn算法的計(jì)算速度，從網(wǎng)絡(luò)中的某個(gè)節(jié) 點(diǎn)集ia)的節(jié)點(diǎn)出發(fā)，然后計(jì)算邊介數(shù)算法速度

15、有明顯提高，進(jìn)而提出了一種更高 效率的算法2003年，wu和huberman將電阻網(wǎng)絡(luò)性質(zhì)應(yīng)用到社ix發(fā)現(xiàn)中，提出w-h算 法，該算法可以確定包含指定節(jié)點(diǎn)的社區(qū)|141。算法將網(wǎng)絡(luò)中的邊想象成導(dǎo)線，導(dǎo) 線以電阻值為單位。在網(wǎng)絡(luò)中任意選擇兩點(diǎn)加上電位差，求解kirchhoff方程， 可以確定某個(gè)電位值處的節(jié)點(diǎn)，然后根據(jù)某個(gè)節(jié)點(diǎn)所處電位的所屬范圍即可確定 所屬社區(qū)。2005年，latapy和pons基于隨機(jī)游走策略提出了一種社區(qū)劃分算法。在該 算法中，規(guī)定初始每個(gè)節(jié)點(diǎn)都為一個(gè)社區(qū)，然后根據(jù)某種游走策略，使節(jié)點(diǎn)逐步 向與其所在社區(qū)之間的平方距離均值最小的社區(qū)游走，劃分到新的社區(qū)，逐步計(jì) 算，逐步更新

16、社區(qū)之間的距離u5j。基于隨機(jī)游走的動(dòng)態(tài)社區(qū)發(fā)現(xiàn)算法，可以借助隨機(jī)游動(dòng)來進(jìn)行|161，提高統(tǒng)計(jì) 結(jié)果的精度。李強(qiáng)等人1171提出：樣本數(shù)據(jù)集(圖頂點(diǎn))可以被看作是隨機(jī)游走的 agent,根據(jù)某些隨機(jī)游走規(guī)則，它每一步移動(dòng)的方向?yàn)樵谒朽徑狱c(diǎn)中隨機(jī)選 取一個(gè)移動(dòng)單位距離a u，圖形的尺寸和形狀會(huì)隨時(shí)間不斷變化。隨著樣木點(diǎn)的 連續(xù)移動(dòng)，同類樣本點(diǎn)逐漸聚集在一起，不用類樣本點(diǎn)彼此遠(yuǎn)離，從而自動(dòng)形成 集群。zhou1181使用隨機(jī)游走來定義節(jié)點(diǎn)對(duì)之間的距離、整體吸引子和局部吸引子 概念，且很明顯社區(qū)一定是最小子圖。這種方法的時(shí)間復(fù)雜度為0(n3)。將算法 應(yīng)用于zachary的空手道俱樂部實(shí)驗(yàn)中，表明

17、了該方法的有效性。zhoull9j也提出 了節(jié)點(diǎn)間的相異度度量方法。圖最初是作為一個(gè)單獨(dú)的社區(qū)，相異度小于閾值的 節(jié)點(diǎn)中的被劃分到同一社區(qū)，分區(qū)在劃分的過程中逐漸減小。這個(gè)算法的時(shí)間復(fù) 雜度仍然是0(n3)。hu等人|2()|設(shè)計(jì)了一種基于節(jié)點(diǎn)之間的信號(hào)處理圖聚類技術(shù)，節(jié)點(diǎn)對(duì)應(yīng)于同 一個(gè)社區(qū)的鄰接向量，這些向量由模糊k-means聚類來劃分。最佳聚類為向量在同一個(gè)社區(qū)的平均最短距離何不同的社區(qū)中的平均最長(zhǎng)距離。算法的時(shí)間復(fù)雜度 為o(t(<k+l)n2)，是<k圖屮度的平均值。van dcmgen1211利用markov聚類算法，模擬擴(kuò)散過程。從隨機(jī)矩陣r開始， 元素rij表示隨機(jī)

18、矩陣的i到j(luò)的隨機(jī)游動(dòng)的概率。矩陣r的每一列元素總和為1。 算法每次迭代包括以i兩個(gè)步驟擴(kuò)張和膨脹。若干次迭代后，具有優(yōu)化模塊的矩 陣趨于穩(wěn)定。即使是稀疏圖，進(jìn)過迭代，矩陣也會(huì)變成稠密圖矩陣。該算法的時(shí) 間復(fù)雜度為o (r?)。r前要?jiǎng)澐稚鐓^(qū)的網(wǎng)絡(luò)處理的都是帶正值的網(wǎng)絡(luò)，但是還有些符號(hào)社會(huì)網(wǎng) 絡(luò)，除包含正聯(lián)系外，也含有負(fù)聯(lián)系。1996年，doreian和mrvart在充分研允符 號(hào)后，利用貪婪策略政策和局部搜索方法，提出了一種對(duì)符號(hào)網(wǎng)絡(luò)的社區(qū)發(fā)現(xiàn)方 法22。yang等在2007年，基于代理的啟發(fā)式方法，提出了一種劃分符號(hào)社會(huì)網(wǎng) 絡(luò)的方法，該算法被叫做fec算法無論是運(yùn)用經(jīng)典的圖論方法，還是基于

19、社會(huì)學(xué)分裂、聚類算法，都是將網(wǎng)絡(luò) 中的節(jié)點(diǎn)劃分成不同的社區(qū)，社區(qū)間不存在重疊節(jié)點(diǎn)。但是，在現(xiàn)實(shí)屮，社區(qū)之 間常常存在相互關(guān)聯(lián)，并且有重疊。也就是說，多個(gè)社區(qū)樂意共享相同的節(jié)點(diǎn)。 所以，如果按是否存在重疊節(jié)點(diǎn)來劃分，社區(qū)發(fā)現(xiàn)主要分為非重疊和重疊社區(qū)發(fā) 現(xiàn)兩方面2425。而非重疊社區(qū)發(fā)現(xiàn)的發(fā)展更加相對(duì)成熟，利用非重疊社區(qū)一些 方法進(jìn)行改進(jìn)，進(jìn)而應(yīng)用與重疊的社區(qū)發(fā)現(xiàn)。congal26b重要節(jié)點(diǎn)復(fù)制為多個(gè) 節(jié)點(diǎn)，然后將每個(gè)節(jié)點(diǎn)劃分到合適的社區(qū)，從而發(fā)現(xiàn)重疊社區(qū)結(jié)構(gòu)。baumes等人棊于局部?jī)?yōu)化的思想，給出y些局部?jī)?yōu)化函數(shù)，這些函數(shù)棊 于邊密度評(píng)價(jià)社區(qū)結(jié)構(gòu)，并按照一定策略對(duì)所有社區(qū)進(jìn)行局部?jī)?yōu)化，將最終的

20、優(yōu) 化結(jié)果作為社區(qū)發(fā)現(xiàn)的結(jié)果2728。由于一個(gè)節(jié)點(diǎn)可能通過不同的優(yōu)化過程中加 入社區(qū)，因而可以實(shí)現(xiàn)重疊社區(qū)發(fā)現(xiàn)。palla等人2005年在文獻(xiàn)中提到上述問題；并給出了一種基于派系的重疊社 區(qū)發(fā)現(xiàn)算法(clique percolation method) cpm,該方法可以找到重疊的社區(qū)結(jié)構(gòu)， 并應(yīng)用到蛋白質(zhì)網(wǎng)絡(luò)、通訊網(wǎng)絡(luò)和合著網(wǎng)絡(luò)的結(jié)構(gòu)分析屮29。有學(xué)者很快將派系 過濾算法加工應(yīng)用到二分圖和有向加權(quán)網(wǎng)絡(luò)中在此基礎(chǔ)上kumpula等人 32提出了派系過濾的快速實(shí)現(xiàn)算法。然而，派系過濾算法在實(shí)際應(yīng)用中依賴參數(shù) k的選擇，選取不同的k值得到的網(wǎng)絡(luò)社區(qū)結(jié)構(gòu)具有很大的差別，因此存在一 定的局限性。200

21、7年gregory將gn算法應(yīng)用于點(diǎn)介數(shù)，提出了一種分裂復(fù)制點(diǎn)介數(shù)最高 的節(jié)點(diǎn)的社區(qū)發(fā)現(xiàn)算法conga261,算法在采用傳統(tǒng)的gn算法進(jìn)行社區(qū)發(fā)現(xiàn)的基 礎(chǔ)上，首先分裂復(fù)制出最高點(diǎn)介數(shù)的節(jié)點(diǎn)的多個(gè)副本，社區(qū)發(fā)現(xiàn)完成后再合并分 裂的節(jié)點(diǎn)。由于被分裂的節(jié)點(diǎn)最終劃分到了不同的社區(qū)，從而實(shí)現(xiàn)了重疊社區(qū)的發(fā)現(xiàn)。evans等利用邊圖與點(diǎn)圖相互轉(zhuǎn)化的思想，將初始網(wǎng)絡(luò)屮的邊看做點(diǎn)來處理， 將點(diǎn)圖轉(zhuǎn)換成邊圖，然后進(jìn)行社區(qū)發(fā)現(xiàn)，最后再將邊圖還原成原來的點(diǎn)圖將 邊圖中的節(jié)點(diǎn)還原為邊后，可以發(fā)現(xiàn)不同社區(qū)間的某些邊可能與同一個(gè)節(jié)點(diǎn)有連 接，該節(jié)點(diǎn)可以被認(rèn)為是重疊節(jié)點(diǎn)。文獻(xiàn)28利用邊圖轉(zhuǎn)換的思想采用圖譜分割 的方法同時(shí)得到

22、了多個(gè)社區(qū)。2009年，v. nicosia等人34擴(kuò)展模塊度的定義到有向網(wǎng)絡(luò)，使模塊度更具有 一般性，得到模塊度為&、，并提出了節(jié)點(diǎn)屬于各個(gè)社區(qū)的隸屬系數(shù)(belonging coefficients),使得重疊社區(qū)的判斷具可行性，但是該方法在共享邊對(duì)各個(gè)社區(qū)的 貢獻(xiàn)權(quán)重的判斷上還存在隨意性。shen hua-wei等棊于凝聚的思想同樣提出一種能夠探測(cè)重疊性和層次性的 方法eaglel35j，該方法凝聚的對(duì)象不是網(wǎng)絡(luò)中的節(jié)點(diǎn)，而是網(wǎng)絡(luò)中的極大團(tuán)。 極大團(tuán)指不能被劃分為子團(tuán)的最大節(jié)點(diǎn)集。lancichinetti等基于適應(yīng)度函數(shù)局部最優(yōu)化的思想，提出一種既可以找到重 疊社區(qū)又可以發(fā)現(xiàn)層

23、次結(jié)構(gòu)的lfk算法l36j。在算法過程中某些節(jié)點(diǎn)可以同時(shí)被 劃到多個(gè)社區(qū)中，從而實(shí)現(xiàn)重疊的發(fā)現(xiàn)，還可以調(diào)整a的大小實(shí)現(xiàn)社區(qū)層次性的 發(fā)現(xiàn)。2010年，王莉提出了一種基于共享鄰居節(jié)點(diǎn)的社區(qū)發(fā)現(xiàn)方法eagle，該方 法可以發(fā)現(xiàn)分層重疊社區(qū)37，方法主要確定的節(jié)點(diǎn)的鄰居域關(guān)系來發(fā)現(xiàn)重疊的社 區(qū)，而不是研宂網(wǎng)絡(luò)屮直接相連的節(jié)點(diǎn)間的關(guān)系。該方法考慮節(jié)點(diǎn)的鄰居域關(guān)系 重疊，因此具有重要的指導(dǎo)意義。在極大團(tuán)思想中，社區(qū)被定義為一系列相鄰的k完全圖的集合，cpm的基 本思想是社區(qū)是由k完全圖在其多個(gè)鄰接k完全圖上滾動(dòng)而來的。kumpula等 人對(duì)cpm進(jìn)行了優(yōu)化，提出了時(shí)序性極大團(tuán)過濾算法(sequentia

24、l cpm, scp)。該方法不僅加速了極大團(tuán)過濾算法，而且成功地將極大團(tuán)思想應(yīng)用到了 加權(quán)網(wǎng)絡(luò)屮。在此棊礎(chǔ)上，shen等人39k4()將極大團(tuán)思想與層次聚類方法相結(jié)合, 提出了 eagle算法。該算法將網(wǎng)絡(luò)中大于某一閾值的k完全圖凝聚為譜系樹, 通過cover評(píng)價(jià)社區(qū)質(zhì)量，選取切割點(diǎn)以得到最佳社區(qū)結(jié)構(gòu)。算法的優(yōu)點(diǎn)是能預(yù) 測(cè)網(wǎng)絡(luò)的動(dòng)態(tài)變化，能找到網(wǎng)絡(luò)屮的重要社區(qū)。缺點(diǎn)是不能揭示網(wǎng)絡(luò)層次結(jié)構(gòu)， 尋找極大團(tuán)復(fù)雜度較高，發(fā)現(xiàn)過多的重疊。層次聚類算法主要是利用相似度計(jì)算進(jìn)行社區(qū)發(fā)現(xiàn)，它認(rèn)為處于同一社區(qū)內(nèi) 的兩節(jié)點(diǎn)應(yīng)該等價(jià)或者相似度很高，因此，如何衡量?jī)蓚€(gè)用戶節(jié)點(diǎn)之間的相似度 成為層次聚類社區(qū)發(fā)現(xiàn)的關(guān)鍵

25、。目前典型的兩種方法是基于節(jié)點(diǎn)屬性相似性社區(qū) 發(fā)現(xiàn)算法和基于共有鄰居相似性社區(qū)發(fā)現(xiàn)算法。文獻(xiàn)42基于“六度分割”理論以及dijkstra算法，提出了一種新的社區(qū)發(fā)現(xiàn) 算法。基于六度分割理論可以保證所找到的兩個(gè)節(jié)點(diǎn)之間的路徑不會(huì)太長(zhǎng)，最大 值為六。首先找到網(wǎng)絡(luò)中兩個(gè)節(jié)點(diǎn)之間的所奮路徑，將找到的所有路徑按從端到 長(zhǎng)的順序進(jìn)行排列，其中根據(jù)dijkstra算法找到的是最短路徑7"6。設(shè)定一個(gè)閥值v,其中小于u + 長(zhǎng)度的路徑中的節(jié)點(diǎn)劃分一個(gè)社區(qū)。此方法的不足，由于此方法是基于“六度分割”假設(shè)原理設(shè)計(jì)的，當(dāng)起始人 和目標(biāo)人為同一個(gè)研究領(lǐng)域的研究員時(shí)，發(fā)現(xiàn)的人群為同一領(lǐng)域的可能性較大， 但當(dāng)研

26、究員從事不同多個(gè)領(lǐng)域研究時(shí)，找到的人當(dāng)然也是“五花八門”此外，如 果數(shù)據(jù)規(guī)模龐大，將所有研究員兩兩組隊(duì)來發(fā)現(xiàn)所有的社區(qū)，那樣工作量是巨大 的。此算法的優(yōu)點(diǎn)是準(zhǔn)確度較高，能揭示網(wǎng)絡(luò)的層次結(jié)構(gòu)，優(yōu)化后可發(fā)現(xiàn)大規(guī)模 網(wǎng)絡(luò)中的重疊社區(qū)。缺點(diǎn)是對(duì)于不好的劃分，不能回溯地進(jìn)行修正。2. 1復(fù)雜網(wǎng)絡(luò)在網(wǎng)絡(luò)理論的研究中，復(fù)雜網(wǎng)絡(luò)是由巨大數(shù)量的節(jié)點(diǎn)和節(jié)點(diǎn)之間復(fù)雜的連結(jié) 關(guān)系共同組成的網(wǎng)絡(luò)結(jié)構(gòu)。用數(shù)學(xué)語言表達(dá)，即一個(gè)圖有足夠復(fù)雜的拓?fù)浣Y(jié)構(gòu)特 征。簡(jiǎn)單網(wǎng)絡(luò)與復(fù)雜網(wǎng)絡(luò)相比，不具備復(fù)雜網(wǎng)絡(luò)的結(jié)構(gòu)特征，并且這些特征經(jīng)常 出現(xiàn)在現(xiàn)實(shí)世界網(wǎng)絡(luò)結(jié)構(gòu)中。復(fù)雜網(wǎng)絡(luò)的研究是現(xiàn)如今科學(xué)研究的一個(gè)熱點(diǎn)，現(xiàn) 實(shí)中各種高復(fù)雜度的系統(tǒng)，如互聯(lián)

27、網(wǎng)網(wǎng)絡(luò)，祌經(jīng)網(wǎng)絡(luò)和社會(huì)網(wǎng)絡(luò)都與復(fù)雜網(wǎng)絡(luò)的 研究有著密不可分的關(guān)系。2. 1.2復(fù)雜網(wǎng)絡(luò)的重要性有許多科學(xué)家感興趣的系統(tǒng)是有多個(gè)獨(dú)立的部分或成分組成的。如由數(shù)據(jù)把 電腦連接起來的因特網(wǎng)，由認(rèn)識(shí)和社會(huì)關(guān)系連接的人組成的社會(huì)網(wǎng)絡(luò)。這些系統(tǒng)的很多方而都值得學(xué)習(xí)。有些人關(guān)注的是其中單個(gè)成分的本質(zhì)，如 一臺(tái)電腦是怎樣工作的，或者一個(gè)人是怎樣感覺并反應(yīng)的。而有些人關(guān)注個(gè)體之 間的連接或交集的本質(zhì)，如互聯(lián)網(wǎng)使用的通信協(xié)議，人類友情的不斷變化等。這 些相互影響相互作用的群體還有第三個(gè)方而，這方而經(jīng)常被忽略但是對(duì)于研宄系 統(tǒng)的行為表現(xiàn)來說又是最總要的，即在系統(tǒng)內(nèi)成分間的連接的模式。網(wǎng)絡(luò)是把一個(gè)系統(tǒng)精簡(jiǎn)成一個(gè)抽象的

28、結(jié)構(gòu)，這個(gè)結(jié)構(gòu)僅僅體現(xiàn)y這個(gè)網(wǎng)絡(luò)的 基本連接模式，它是顯示網(wǎng)絡(luò)的簡(jiǎn)化。網(wǎng)絡(luò)中的結(jié)點(diǎn)和邊可以用附加的信息來表 示，如名字或強(qiáng)度，可以用來獲得系統(tǒng)更多的細(xì)節(jié)。但是在簡(jiǎn)化的過程中，會(huì)丟 掉很多信息，這既有它的壞處也有它的好處。過去很多年，許多領(lǐng)域的科學(xué)家開發(fā)了一系列的工具如數(shù)學(xué)的、計(jì)算機(jī)的、統(tǒng)計(jì)學(xué)的來分析、建模以及理解這些網(wǎng)絡(luò)。這些工具在網(wǎng)絡(luò)的簡(jiǎn)化抽象形式下進(jìn) 行分析和計(jì)算，理論上可以應(yīng)用于任何代表了一個(gè)系統(tǒng)的網(wǎng)絡(luò)圖中。因此如果有 一個(gè)你感興趣的系統(tǒng)，并且可以被轉(zhuǎn)換成網(wǎng)絡(luò)的形式，那么就有上百種已經(jīng)開發(fā) 好并且為人所熟悉的方法可以用來分析這個(gè)系統(tǒng)。當(dāng)然并不是所有的方法都能得 出有效的結(jié)果，這取決于要分

29、析的系統(tǒng)和要分析的特定問題。但是，毫無疑問一 個(gè)試定的網(wǎng)絡(luò)系統(tǒng)問題己經(jīng)存在了一種方法解決。2.3復(fù)雜網(wǎng)絡(luò)分析復(fù)雜網(wǎng)絡(luò)有若干統(tǒng)計(jì)特征。其中包括小世界效應(yīng)，小世界效應(yīng)兵有大的簇系 數(shù)和小的平均距離，網(wǎng)絡(luò)中節(jié)點(diǎn)之間的平均距離對(duì)數(shù)依賴于網(wǎng)絡(luò)中的節(jié)點(diǎn)數(shù)。無 標(biāo)度性質(zhì)，即網(wǎng)絡(luò)中節(jié)點(diǎn)度服從冪率分布，具備冪函數(shù)或指數(shù)函數(shù)的形式，冪函 數(shù)曲線具有右偏性，網(wǎng)絡(luò)中節(jié)點(diǎn)度的分布區(qū)間非常小，所有節(jié)點(diǎn)與節(jié)點(diǎn)度均值相 差不大。網(wǎng)絡(luò)的聚集性或網(wǎng)絡(luò)傳遞性，是指兩個(gè)節(jié)點(diǎn)是同一個(gè)節(jié)點(diǎn)的相鄰節(jié)點(diǎn)， 那么它們有較大概率仍然是和鄰節(jié)點(diǎn)。2. 3. 1中心性在網(wǎng)絡(luò)屮節(jié)點(diǎn)的度是指連接它的邊的數(shù)目。如在一個(gè)關(guān)于友誼的社會(huì)網(wǎng)絡(luò) 中，一個(gè)單獨(dú)個(gè)體

30、的度是他在這個(gè)網(wǎng)絡(luò)中朋友的數(shù)目；在因特網(wǎng)屮，度可能是一 臺(tái)電腦的數(shù)據(jù)連接數(shù)，如路由器或其他設(shè)備等。在很多情況下，一個(gè)網(wǎng)絡(luò)中擁冇 最高度數(shù)的節(jié)點(diǎn)，即擁有最大連接數(shù)的節(jié)點(diǎn)往往在這個(gè)系統(tǒng)屮扮演丫很重要的角 色，因此關(guān)注網(wǎng)絡(luò)中節(jié)點(diǎn)的度能引導(dǎo)我們發(fā)現(xiàn)這個(gè)系統(tǒng)很多重要的特征。(1) 度在社會(huì)網(wǎng)絡(luò)文學(xué)中冇吋候叫做度中心性，強(qiáng)調(diào)它作為中心性度量的用 處。例如，在社會(huì)網(wǎng)絡(luò)屮，一個(gè)人與很多人有聯(lián)系，我們自然而然的就會(huì)覺得他 有很大的影響力，能更接近與某些信息，更有權(quán)威。(2) 簡(jiǎn)單的度中心性的自然延伸為特征向量中心性。我們可以把度中心作為 對(duì)每一個(gè)節(jié)點(diǎn)的鄰居節(jié)點(diǎn)都有的“屮心性點(diǎn)”。但并不是所有的鄰居都是等價(jià)的。

31、在許多情況k,網(wǎng)絡(luò)屮的節(jié)點(diǎn)的重要性被連接到它的網(wǎng)絡(luò)屮的本身很重要的其他 頂點(diǎn)增加了。這久是特征向量中心性的意義。例如：一個(gè)節(jié)點(diǎn)p有三個(gè)朋友，h 他的三個(gè)朋友比較重要，另一個(gè)節(jié)點(diǎn)q也有三個(gè)朋友，但他的三個(gè)朋友重要性都 比較低，所以，p的特征向量屮心性比q高。在一個(gè)網(wǎng)絡(luò)屮，很多情況下，一個(gè) 節(jié)點(diǎn)的重要性與它所連接的自身重要的節(jié)點(diǎn)冇關(guān)。(3) 中心地位的一個(gè)非常不同的概念是中介中心，用于衡量一個(gè)頂點(diǎn)位于其 他頂點(diǎn)之間的路徑的程度。屮介屮心性高的節(jié)點(diǎn)，在網(wǎng)絡(luò)屮憑借自己對(duì)節(jié)點(diǎn)之間 傳遞的信息的控制，可能有相當(dāng)高的影響力。具有高中介中心性的節(jié)點(diǎn)的移除， 將切斷許多其他頂點(diǎn)之間的通信，因?yàn)樗鼈兾挥诤芏喙?jié)點(diǎn)之

32、間的通訊路徑上。如 果一個(gè)節(jié)點(diǎn)處在其他越多節(jié)點(diǎn)的通訊路徑上，則該點(diǎn)的中介中心度就越高。(4) 網(wǎng)絡(luò)的另一個(gè)重要的中心性是接近中心性。它測(cè)量了一個(gè)節(jié)點(diǎn)到其他節(jié) 點(diǎn)的平均距離。當(dāng)一個(gè)節(jié)點(diǎn)與其他節(jié)點(diǎn)的平均最短路徑很短時(shí)，接近中心性是一 個(gè)比較小的值。這樣的頂點(diǎn)可能更容易獲取其他頂點(diǎn)屮的信息或?qū)ζ渌?jié)點(diǎn)有更 直接的影響力。在一個(gè)社會(huì)網(wǎng)絡(luò)中，例如，一個(gè)人用與他人之間有較小的平均距 離，別人可能會(huì)發(fā)現(xiàn)，他的意見在社會(huì)上會(huì)比別人意見更迅速地傳達(dá)給他人。無標(biāo)度模型有albert-laszlo baradasi和reka albert在1999年首次提出，現(xiàn) 實(shí)網(wǎng)絡(luò)的無標(biāo)度特性源于眾多網(wǎng)絡(luò)所共有的兩種生成機(jī)制：

33、(1) 網(wǎng)絡(luò)通過添加新節(jié)點(diǎn)而連續(xù)擴(kuò)張；(2) 新節(jié)點(diǎn)擇優(yōu)連接到具有大量連接的節(jié)點(diǎn)上；3.1引言網(wǎng)絡(luò)一個(gè)實(shí)用的價(jià)值就是網(wǎng)絡(luò)中的簇或者社區(qū)。我們大多數(shù)人都非常熟悉網(wǎng) 絡(luò)中己經(jīng)存在的社區(qū)，比如天涯社區(qū)，某大學(xué)的論壇等，在實(shí)際生活中還要很多 看不見的社區(qū)存在，如在大的松散的網(wǎng)絡(luò)中緊密聯(lián)系的朋友群。朋友網(wǎng)中，可能 存在派系、朋友圈、或者各種各樣的朋友幫派，在這些組織之內(nèi)成員之間聯(lián)系緊 密，但在組織之間聯(lián)系很弱或者兒乎不聯(lián)系。如果是包含明顯的劃分或興趣愛好 的社區(qū)，我們想要了解這些社區(qū)，最好的做法就是把它們看成一個(gè)網(wǎng)絡(luò)，劃分社 區(qū)。一個(gè)大的網(wǎng)絡(luò)劃分成多個(gè)社區(qū)的過程涉及不同的社區(qū)層次，劃分社區(qū)的依據(jù) 是網(wǎng)絡(luò)

34、中的數(shù)據(jù)，劃分出的社區(qū)能幫助我們了解整個(gè)網(wǎng)絡(luò)的結(jié)構(gòu)組成。圖分割或社區(qū)發(fā)現(xiàn)都是指將網(wǎng)絡(luò)中的節(jié)點(diǎn)按照網(wǎng)絡(luò)中邊的類型劃分為組、簇 或社區(qū)。但進(jìn)行的劃分都是組內(nèi)節(jié)點(diǎn)緊密連接，組建只有很少幾條邊連接。圖分 割從十九世紀(jì)六十年代開始一直就是計(jì)算機(jī)科學(xué)的一個(gè)經(jīng)典問題。這個(gè)問題就是 把一個(gè)網(wǎng)絡(luò)中的節(jié)點(diǎn)劃分成給定數(shù)目的非重疊組，使組之間邊的數(shù)目最小。社區(qū)發(fā)現(xiàn)用來搜索網(wǎng)絡(luò)中自然存在的分組，不論它們的數(shù)量或大小，是主要 用來發(fā)現(xiàn)和理解大規(guī)模網(wǎng)絡(luò)的結(jié)構(gòu)的一種工具。社區(qū)發(fā)現(xiàn)最普遍的應(yīng)用就是作為 分析和理解網(wǎng)絡(luò)中節(jié)點(diǎn)的工具。社ix發(fā)現(xiàn)的目標(biāo)是找到網(wǎng)絡(luò)的自然分割。分組的 大小不確定，在原則上從一個(gè)分組到另一個(gè)可能變化很大。

35、一個(gè)給定的網(wǎng)絡(luò)可能 分成幾個(gè)大組，很多小組，或很多不同大小的混合物。在復(fù)雜網(wǎng)絡(luò)中發(fā)現(xiàn)社區(qū)， 實(shí)用價(jià)值重大。如在網(wǎng)絡(luò)圖屮的節(jié)點(diǎn)的集群可能表明相關(guān)網(wǎng)頁群體；在代謝網(wǎng)絡(luò) 中節(jié)點(diǎn)的集群可能表示網(wǎng)絡(luò)內(nèi)的功能單元。3.2 迭代二分法(iterative bisection)在實(shí)踐中，大多數(shù)圖的分割方法基于迭代二分法。下面介紹兩種迭代二分法， 其中一個(gè)為基于貪婪算法的kernighan-lin算法。該算法為達(dá)到較優(yōu)的網(wǎng)絡(luò)劃分， 對(duì)所劃分的子網(wǎng)內(nèi)和子網(wǎng)間的邊數(shù)進(jìn)行優(yōu)化。3. 2. 1 kernighanlin 算法kernighan一lin 由 brian kernighan 和 shen lin 在 197

36、0 年提出，是最簡(jiǎn)單且最有名的圖二分啟發(fā)式算法。k-l算法的主要思想是：首先將網(wǎng)絡(luò)劃分成給定大 小的兩個(gè)組，交換滿足條件的不同組間的節(jié)點(diǎn)對(duì)，使得組間連接最稀疏，組內(nèi)連 接最緊密。3. 2. 2 譜二分法(spectrai bisection)從式3.2可以看出laplace矩陣中所有行元素與列元素的和都為0,因此， 該矩陣總有一個(gè)特征值為0,且其對(duì)應(yīng)的特征向量1。此時(shí)對(duì)應(yīng)的分割粒徑：(3.4)n 拉普拉斯算子的第二特征值兒不為0,當(dāng)且僅當(dāng)前網(wǎng)絡(luò)是連通連接的。第二 特征值4基于這個(gè)原因，有時(shí)稱為網(wǎng)絡(luò)的代數(shù)連通度(algebratic connectivity) 4m71o如果網(wǎng)絡(luò)沒有連通，且第二

37、特征值人為零，在這種情況下，兩個(gè)最小特 征值是相同的，并且對(duì)應(yīng)的特征向量是不確定的，任何兩個(gè)特征向量具有相同的 特征值的混合也是一個(gè)特征向量。然而這并不是一個(gè)嚴(yán)重的問題。如果網(wǎng)絡(luò)不是 連接的，有不止一個(gè)分組，那么通常我們對(duì)分割一個(gè)特定組件比較感興趣，如最 大的組成部分，或者將所有分組獨(dú)立劃分。根據(jù)人中的值，所有正值對(duì)應(yīng)的節(jié)點(diǎn)屬于一個(gè)社區(qū)，所有負(fù)值對(duì)應(yīng)的節(jié)點(diǎn) 屬于一個(gè)社區(qū)，據(jù)此將網(wǎng)絡(luò)的節(jié)點(diǎn)劃分為兩個(gè)社區(qū)。因?yàn)閺睦碚撋峡梢宰C明，同 一分組內(nèi)的節(jié)點(diǎn)對(duì)應(yīng)于凡中的值近似相等。148,49代數(shù)連通度人是對(duì)切割尺寸的 一個(gè)直接測(cè)量，.h.正比于它。代數(shù)連通度是網(wǎng)絡(luò)容易劃分程度的的測(cè)量。如果網(wǎng)絡(luò)具有良好的切割

38、，則它較??；如果沒有，則較大。3. 3. 2 rad i cch i 算法該算法與g-n算法原理和同，都是基于去邊，與g-n算法不同的是，raciddhi算法引進(jìn)/邊聚集系數(shù)(edge clustering coefficient)指標(biāo)。radichhi提出了關(guān)于 基于中介性的算法的變形。算法的基木原理是一樣的，都是識(shí)別除社區(qū)之間的邊， 并且移除它們來得到社區(qū)結(jié)構(gòu)。radichhi發(fā)現(xiàn)位于很少連接的社區(qū)之間的邊屬于 邊組成的環(huán)的概率非常小，所以要求兩條臨近的邊屬于同一個(gè)分組中。因此識(shí)別 網(wǎng)絡(luò)中社區(qū)之間的邊的一種方法就是尋找屬于數(shù)目非常小的短循環(huán)的邊。r發(fā)現(xiàn) 長(zhǎng)度為3或者4的環(huán)能得出最好的結(jié)果。

39、重復(fù)去除屬于很小數(shù)目的這種循環(huán)的邊， 最終能發(fā)現(xiàn)網(wǎng)絡(luò)中含的社區(qū)。因此，將1條邊的邊聚集系數(shù)定義為包含該邊的 三角環(huán)所占比例：150j其中&表示節(jié)點(diǎn)z*的度，minc. -l,kj -1)表示節(jié)點(diǎn)y的度,(3.6)表示網(wǎng)絡(luò)中包含該邊的三角環(huán)的個(gè)數(shù)。式3.6中的的分母表示包含該邊的最大可能的三角環(huán)的個(gè)數(shù)。這個(gè)算法很好的一個(gè)特性是它的速度。計(jì)算一條邊所屬的短循環(huán)是在局部范 圍內(nèi)，并且對(duì)于所有的邊來說進(jìn)行這種計(jì)算的范圍也就是整個(gè)網(wǎng)絡(luò)的大小。因此， 在最壞情況下，算法的時(shí)間復(fù)雜度為02)，比基于邊介數(shù)的g-n算法快了一 個(gè)數(shù)量級(jí)。該算法的不足是算法的計(jì)算依賴于網(wǎng)絡(luò)中邊所在的三角環(huán)，對(duì)于一個(gè)三角環(huán)

40、 很少的網(wǎng)絡(luò)，算法實(shí)驗(yàn)結(jié)果比較差。經(jīng)實(shí)證研究，非社會(huì)網(wǎng)絡(luò)中三角環(huán)數(shù)量較社 區(qū)網(wǎng)絡(luò)較少，因此，radicchi算法更適合應(yīng)用于社會(huì)網(wǎng)絡(luò)。3. 4 層次聚類法(h i erarch i ca i clustering)層次聚類是社會(huì)學(xué)家研究社區(qū)發(fā)現(xiàn)所采用的的主要方法之一。算法首先定義 一個(gè)相似度依次計(jì)算網(wǎng)絡(luò)中每對(duì)節(jié)點(diǎn)之間;的值，依據(jù)；值的大小，在網(wǎng)絡(luò)屮的節(jié)點(diǎn)間依次加上一條邊。在此需指出，初始網(wǎng)絡(luò)結(jié)構(gòu)影響節(jié)點(diǎn)對(duì)間相似度 的計(jì)算，而算法所加上的邊與有關(guān)。層次聚類并不是有很多變量和可選結(jié)果的一個(gè)算法種類。層次聚類是一種凝聚技術(shù)，算法從網(wǎng)絡(luò)中獨(dú)立的節(jié)點(diǎn)開始，將它們組合起來形成群組。這跟前而講 的幾種社區(qū)發(fā)

41、現(xiàn)算法完全相反，前幾種算法都是分裂方法，我們從整體視覺看待 網(wǎng)絡(luò)，然后將它分成幾部分。層次聚類的基本思想是基于網(wǎng)絡(luò)結(jié)構(gòu)，定義節(jié)點(diǎn)之間的相似度或連接強(qiáng)度， 然后將距離最近的或最相似的節(jié)點(diǎn)組合成分組。下面看幾種從不同角度定義網(wǎng)絡(luò) 中節(jié)點(diǎn)之間相似度的方法。3. 5w-h算法將網(wǎng)絡(luò)中的每條邊想象成電阻為單位值的導(dǎo)線，且在網(wǎng)絡(luò)中任意選擇的2個(gè) 節(jié)點(diǎn)上加上單位值的電位差，通過求解kirchhoff方程，可以得到每個(gè)節(jié)點(diǎn)處的 電位值。wu和huberman認(rèn)為，如果網(wǎng)絡(luò)可以被分解成2個(gè)社ix，選定的2個(gè) 節(jié)點(diǎn)屬于不同的社區(qū)，所以潛在的電位波譜在連接2個(gè)社區(qū)的兩端，將產(chǎn)生一個(gè) 較大的差距。因此，我們首先確定一

42、個(gè)潛在的最大間隙電位波譜的價(jià)值，然后根 據(jù)各個(gè)節(jié)點(diǎn)的電位值決定節(jié)點(diǎn)所屬社區(qū)。3.6網(wǎng)絡(luò)分析評(píng)價(jià)上幾節(jié)所介紹的集屮網(wǎng)絡(luò)劃分算法均無法自己停止，即無法判斷算法進(jìn)行到 哪個(gè)步驟所得的網(wǎng)絡(luò)劃分結(jié)果是最好的。為此girvan和newman5l定義了一個(gè)評(píng) 價(jià)網(wǎng)絡(luò)分解滿意度的指標(biāo)，稱為模塊度(modularity)。模塊度是用來衡量一個(gè) 網(wǎng)絡(luò)所劃分社區(qū)之間連接程度的指標(biāo)。嚴(yán)格來說，模塊度的值耍比1小，且為正 值。類似于k-l算法，可以利用網(wǎng)絡(luò)的模塊度來設(shè)計(jì)出網(wǎng)絡(luò)分解的貪婪算法52。網(wǎng)絡(luò)一個(gè)實(shí)用的價(jià)值就是網(wǎng)絡(luò)屮的簇或者社區(qū)。我們大多數(shù)人都非常熟悉網(wǎng) 絡(luò)中己經(jīng)存在的社區(qū)，比如天涯社區(qū)，某大學(xué)的論壇等，在實(shí)際生活中還要很多 看不見的社區(qū)存在，如在大的松散的網(wǎng)絡(luò)中緊密聯(lián)系的朋友群。朋友網(wǎng)中，可能 存在派系、朋友圈、或者各種各樣的朋友幫派，在這些組織之a(chǎn)成員之間聯(lián)系緊 密，但在組織之間聯(lián)系很弱或者幾乎不聯(lián)系。如果是包含明顯的劃分或興趣愛好 的社區(qū)，我們想要了解這些社區(qū)，最好的做法就是把它們看成一個(gè)網(wǎng)絡(luò)，劃分社 區(qū)。一個(gè)大的網(wǎng)絡(luò)劃分成多個(gè)社區(qū)的過程涉及不同的社區(qū)層次，劃分社區(qū)的依據(jù) 是網(wǎng)絡(luò)中的數(shù)據(jù)，劃分出的社區(qū)能幫助我們了