趙福明，盛桂珍，2

（1.長(zhǎng)春工程學(xué)院，長(zhǎng)春130021；2.吉林建筑大學(xué)城建學(xué)院，長(zhǎng)春130111）

隨著SNS網(wǎng)站的迅速發(fā)展和他們的用戶數(shù)量成倍增加，虛擬社會(huì)的網(wǎng)絡(luò)研究及其應(yīng)用的重要性不容忽視。對(duì)于一個(gè)大型的、連接關(guān)系雜亂無章的虛擬社會(huì)網(wǎng)絡(luò)，了解并分析其結(jié)構(gòu)，將其分解成互相獨(dú)立的集群是至關(guān)重要的。特別是，許多應(yīng)用程序需要在理解抽象模型的組織結(jié)構(gòu)的基礎(chǔ)上，以推斷其拓?fù)浣Y(jié)構(gòu)和它的元素之間的關(guān)系。這一研究也是信息流傳播分析、推薦系統(tǒng)、虛擬社會(huì)影響最大化等的研究基礎(chǔ)。

1 社會(huì)網(wǎng)絡(luò)模型的介紹

在虛擬社區(qū)中，一個(gè)成員與多個(gè)主題的子社區(qū)相關(guān)聯(lián)是非常常見的。由于一個(gè)人可以在現(xiàn)實(shí)世界中有多重身份，我們可以合理地假設(shè)：他／她可能分別加入了代表他／她的朋友、工作伙伴、家庭的子社區(qū)，或者他／她根據(jù)自己的多個(gè)興趣參與了不同的組群。由此帶來的問題是：一個(gè)社會(huì)網(wǎng)絡(luò)里的各個(gè)集群可能或多或少地存在重疊。但是現(xiàn)有的大部分圖聚類文獻(xiàn)均沒有考慮這樣有重疊的社區(qū)。

圖1展示了一個(gè)具有34個(gè)節(jié)點(diǎn)的典型重疊群落模型。在1區(qū)域和3區(qū)域的部分節(jié)點(diǎn)均與2區(qū)域內(nèi)的節(jié)點(diǎn)有鏈接，但在1區(qū)域與2區(qū)域重疊，而3區(qū)域獨(dú)立于2區(qū)域。即使不經(jīng)過計(jì)算，我們也可以直觀地看出1區(qū)域與2區(qū)域有更為緊密的聯(lián)系，而3區(qū)域與后者的關(guān)聯(lián)相對(duì)較弱。

定義1：在對(duì)整個(gè)網(wǎng)絡(luò)進(jìn)行劃分之后，2個(gè)子群體含有相同的節(jié)點(diǎn)被稱為重疊社區(qū)；2個(gè)子群不具有相同的節(jié)點(diǎn)，但在這2個(gè)子群中的節(jié)點(diǎn)有連接關(guān)系被稱為分離社區(qū)；2個(gè)子群沒有相同的節(jié)點(diǎn)且它們之間沒有鏈接被稱為無關(guān)社區(qū)。

定義2：在本文中，包括一個(gè)或多個(gè)重疊社區(qū)的社會(huì)網(wǎng)絡(luò)分割的研究被稱為有重疊社會(huì)網(wǎng)絡(luò)分析。

根據(jù)上述2個(gè)定義，在有重疊的社會(huì)網(wǎng)絡(luò)中，并非任意2個(gè)社區(qū)都必須是重疊的，也就是說，本文的研究并不強(qiáng)制2個(gè)子群具有相同的節(jié)點(diǎn)。這與圖1所描述的網(wǎng)絡(luò)結(jié)構(gòu)相一致。

下面將闡述本文提出的有重疊社會(huì)網(wǎng)絡(luò)模型的意義。首先，對(duì)于在重疊范圍內(nèi)的節(jié)點(diǎn)來說，它將與2個(gè)或以上不同社區(qū)里的節(jié)點(diǎn)有緊密聯(lián)系。而由于這些被劃分出來的社區(qū)不具有必要的或直接的關(guān)系，這意味著他們可能有不同的特點(diǎn)，例如社區(qū)內(nèi)的成員會(huì)關(guān)注不同的主題或者是有不同的組織成員組成。在圖1中，1區(qū)域中的節(jié)點(diǎn)28與2區(qū)域中的節(jié)點(diǎn)1都與重疊區(qū)域中的節(jié)點(diǎn)3相關(guān)聯(lián)，然而節(jié)點(diǎn)28與節(jié)點(diǎn)3并沒有直接的聯(lián)系，暗示著2者可能存在不同的特點(diǎn)，而節(jié)點(diǎn)3將同時(shí)擁有這2種特性。這也就意味著重疊范圍內(nèi)的節(jié)點(diǎn)具有它所在的所有社區(qū)的特點(diǎn)，這與上文中提到的個(gè)體人類在現(xiàn)實(shí)世界中具有多重身份相吻合。其次，有重疊的社會(huì)網(wǎng)絡(luò)分割更有助于社會(huì)網(wǎng)絡(luò)分析的其他研究。對(duì)于單一節(jié)點(diǎn)，尤其是處于重疊區(qū)域的節(jié)點(diǎn)，我們可以更全面地了解它的特點(diǎn)及其與其他節(jié)點(diǎn)的連接關(guān)系。對(duì)于整個(gè)網(wǎng)絡(luò)，直觀來講2個(gè)重疊社區(qū)間信息的傳播會(huì)比2個(gè)分離社區(qū)更快更有影響，有重疊的社會(huì)網(wǎng)絡(luò)研究將有助于我們對(duì)整個(gè)虛擬社會(huì)網(wǎng)絡(luò)結(jié)構(gòu)的理解和分析。

本文主要在現(xiàn)有研究的基礎(chǔ)上，提出一個(gè)改進(jìn)的數(shù)學(xué)模型及算法，以滿足對(duì)社會(huì)網(wǎng)絡(luò)分割提出的要求：適用于處理大型密集網(wǎng)絡(luò)和海量數(shù)據(jù)，具有合理的運(yùn)行效率，適用于已有的網(wǎng)絡(luò)分割質(zhì)量的評(píng)估系統(tǒng)。本文組織如下：第2節(jié)中我們給出分割節(jié)點(diǎn)法的基本模型及基礎(chǔ)理論，以及其在其他數(shù)據(jù)模型中的適用性；第3節(jié)中我們將給出實(shí)驗(yàn)平臺(tái)、實(shí)驗(yàn)數(shù)據(jù)的特點(diǎn)以幫助讀者了解下一章；第4節(jié)給出我們實(shí)驗(yàn)中的細(xì)節(jié)、復(fù)雜度分析與實(shí)驗(yàn)結(jié)果；在最后一節(jié)中，我們提供了我們工作的潛在價(jià)值。

2 社會(huì)網(wǎng)絡(luò)分析的基本概念

定義3：虛擬社會(huì)中某成員的好友，或在其抽象出來的無向圖中與節(jié)點(diǎn)A有連接關(guān)系的點(diǎn)定義為A的鄰接點(diǎn)。A的鄰接點(diǎn)的集合V＝｛v1，v2…vn｝，我們定義為與A的子社區(qū)。

2.1 有重疊社區(qū)的數(shù)學(xué)模型

在具有現(xiàn)實(shí)意義中的重疊社區(qū)內(nèi)，一個(gè)節(jié)點(diǎn)與其關(guān)聯(lián)的子群的原始數(shù)學(xué)模型如圖2（a）所示。然而，由于重疊區(qū)域內(nèi)的點(diǎn)連接多個(gè)子社區(qū)，即A同時(shí)連接與其有關(guān)的4個(gè)集群，使得子社區(qū)之間并不相互獨(dú)立，無法直接應(yīng)用圖的數(shù)據(jù)結(jié)構(gòu)并實(shí)現(xiàn)遍歷等算法，故這個(gè)模型并不方便做進(jìn)一步的數(shù)據(jù)處理和結(jié)果評(píng)估。因此，我們將其轉(zhuǎn)換成圖2（b）的結(jié)構(gòu)，也就是第1節(jié)中提到的分裂節(jié)點(diǎn)法。本文首先將A的鄰接點(diǎn)按它們的連接緊密程度分成幾個(gè)小組，如圖2（a）中成員間具有緊密聯(lián)系的大學(xué)同學(xué)、中學(xué)同學(xué)、同事與家人等。并根據(jù)這個(gè)分組將A賦予不同的編號(hào)。例如，對(duì)于連接A的高中同學(xué)而言將A標(biāo)為A1，對(duì)于大學(xué)同學(xué)標(biāo)為A2，家庭成員標(biāo)為A3，同事標(biāo)為A4。這樣，A1、A2、A3、A4將被視為4個(gè)獨(dú)立的節(jié)點(diǎn)參與后續(xù)的實(shí)驗(yàn)，而有重疊的社會(huì)網(wǎng)絡(luò)模型也被轉(zhuǎn)化為普通的網(wǎng)絡(luò)結(jié)構(gòu)。

圖2 現(xiàn)實(shí)中個(gè)體與相關(guān)群體的抽象模型及其變型

2.2 現(xiàn)有的研究成果

根據(jù)各社會(huì)網(wǎng)絡(luò)的不同特性，研究人員一般選用譜分析方法、Kernighan－Lin算法、層次聚類算法這3種經(jīng)典社會(huì)網(wǎng)絡(luò)分析算法。雖然這些經(jīng)典算法并不能直接應(yīng)用于有重疊的社會(huì)網(wǎng)絡(luò)分析，但他們對(duì)本文的研究有非常大的參考價(jià)值。

首次嘗試研究有重疊的社會(huì)網(wǎng)絡(luò)是2005年發(fā)表的［12］，并且他們提出了開放的CFinder算法（http：／／cfinder.org／）。CFinder提供了一個(gè)適用于各種研究領(lǐng)域的快速和有效的圖分割方法，例如應(yīng)用最為廣泛的遺傳網(wǎng)絡(luò)和微陣列數(shù)據(jù)。然而，在分析如本文所選擇的具有上億個(gè)節(jié)點(diǎn)及百億條連接的虛擬社會(huì)網(wǎng)絡(luò)時(shí)，CFinder的運(yùn)行時(shí)間和輸出結(jié)果并不令人滿意。

2.3 經(jīng)典層次聚類算法

上一節(jié)中提到的3種方法在處理網(wǎng)絡(luò)分割時(shí)的思想各不相同，本小節(jié)將詳細(xì)描述本文實(shí)驗(yàn)將要用到的階層式聚類算法，并且為了方便區(qū)分試驗(yàn)組與對(duì)照組，后文將稱其為經(jīng)典階層式聚類算法。

這種方法的首要目標(biāo)是度量在給定的網(wǎng)絡(luò)結(jié)構(gòu)內(nèi)，任意有連接的節(jié)點(diǎn)（i，j）的相似性Xij，也就是人為的計(jì)算網(wǎng)絡(luò)中所有連接的強(qiáng)弱程度。度量的方法之一是應(yīng)用在各個(gè)圖論領(lǐng)域的歐幾里德距離：

其他的度量方法包括曼哈頓距離、最大傳輸距離和余弦相似度。本文中，我們將選取與余弦相似性類似的Jaccard相似系數(shù)來評(píng)價(jià)2個(gè)節(jié)點(diǎn)連接的緊密程度。在取得了兩點(diǎn)的相似性之后，經(jīng)典聚類方法指出根據(jù)網(wǎng)絡(luò)的不同特點(diǎn)，我們可以用最短距離法或其他方法分離出各集群。在一般情況下，聚合式聚類算法的復(fù)雜度是O（n3）。

在本文中，我們將修改層次聚類方法，以降低其算法的復(fù)雜度，并使其適用于密集矩陣。在分割重復(fù)區(qū)域的節(jié)點(diǎn)時(shí)，我們將使用2.4節(jié)中介紹的功能函數(shù)作為分割算法的結(jié)束條件，而不是用經(jīng)典分層聚類算法中提出的兩集群的平均距離。并且為了與對(duì)照組比較，我們將分割過節(jié)點(diǎn)的數(shù)據(jù)與未處理的數(shù)據(jù)通過相同的程序處理，再利用功能函數(shù)評(píng)價(jià)網(wǎng)絡(luò)劃分的結(jié)果。

2.4 對(duì)分裂結(jié)果的評(píng)估

上一節(jié)提到的功能函數(shù)是數(shù)據(jù)挖掘領(lǐng)域中普遍承認(rèn)的一種對(duì)網(wǎng)絡(luò)劃分的結(jié)果進(jìn)行評(píng)價(jià)的方法：

式中：m為網(wǎng)絡(luò)中原有的連接數(shù)；k為整個(gè)網(wǎng)絡(luò)劃分的集群的個(gè)數(shù)；li為第i個(gè)集群中的連接數(shù)，要求與該連接有關(guān)的2個(gè)節(jié)點(diǎn)都在第i個(gè)集群中；di為第i個(gè)集群中的節(jié)點(diǎn)數(shù)。

功能函數(shù)衡量了分割得到的子社區(qū)與相對(duì)應(yīng)的隨機(jī)社區(qū)在連接程度上的差異。隨機(jī)社區(qū)在這里定義為與得到的第i個(gè)子社區(qū)有相同的節(jié)點(diǎn)數(shù)，但是節(jié)點(diǎn)之間有隨機(jī)鏈接。對(duì)于分割完成的社會(huì)網(wǎng)絡(luò)的Q值，如果大于0，這意味著分割的子社區(qū)有著比其隨機(jī)社區(qū)節(jié)點(diǎn)之間更緊密的聯(lián)系。反之，如果Q小于0，這意味著社區(qū)節(jié)點(diǎn)之間的連接比較松散，分割的結(jié)果并不理想。

雖然重疊的社區(qū)抽象模型是不同于一般的圖結(jié)構(gòu)，但我們將節(jié)點(diǎn)如圖2（b）那樣分割成互相獨(dú)立的節(jié)點(diǎn)。因此，該函數(shù)仍可直接用于對(duì)本文算法的評(píng)估。

基于上述對(duì)功能函數(shù)的分析，我們可以定性地討論有重疊的社區(qū)研究的優(yōu)勢(shì)。對(duì)比節(jié)點(diǎn)只能屬于一個(gè)集群和節(jié)點(diǎn)可以出現(xiàn)在多個(gè)集群的數(shù)學(xué)模型，以下2種情況最有可能發(fā)生。其中一種是2個(gè)或2個(gè)以上的團(tuán)體由于中間節(jié)點(diǎn)的連接而不能在社區(qū)劃分的過程中被分離開。另一種是這個(gè)節(jié)點(diǎn)不會(huì)出現(xiàn)在所有與它有關(guān)的群體中。在這2種情況下，非重疊社會(huì)模型的功能函數(shù)中的di都將比又重疊的高，進(jìn)而使得功能函數(shù)的結(jié)果降低。當(dāng)然，第1種情況的發(fā)生對(duì)功能函數(shù)的結(jié)果影響更大一些。即使是在分裂節(jié)點(diǎn)后會(huì)使節(jié)點(diǎn)的數(shù)量增加，其影響力相比上文中的變化仍是微不足道的。4.3節(jié)2組實(shí)驗(yàn)的結(jié)果對(duì)比將證明上述分析。

3 實(shí)驗(yàn)準(zhǔn)備及數(shù)據(jù)獲得

本節(jié)將介紹實(shí)驗(yàn)的技術(shù)平臺(tái)及數(shù)據(jù)特點(diǎn)，并將簡(jiǎn)單介紹數(shù)據(jù)預(yù)處理的方法及其必要性。

3.1 實(shí)驗(yàn)平臺(tái)

本文主系統(tǒng)，包括網(wǎng)絡(luò)機(jī)器人、節(jié)點(diǎn)相似度計(jì)算、節(jié)點(diǎn)分割與結(jié)果評(píng)估等，均由Java程序開發(fā)。主要是因?yàn)镴ava有豐富的處理網(wǎng)頁內(nèi)容和連接數(shù)據(jù)庫庫函數(shù)，并且非常適合于編寫嵌套次數(shù)較多的循環(huán)函數(shù)。對(duì)于實(shí)驗(yàn)數(shù)據(jù)，已有的一些社會(huì)網(wǎng)絡(luò)數(shù)據(jù)，如美國(guó)橄欖球俱樂部成員關(guān)系網(wǎng)絡(luò)，和網(wǎng)絡(luò)上的虛擬社會(huì)網(wǎng)絡(luò)數(shù)據(jù)，如“臉書”上的好友關(guān)系，都是可用的。在本文的實(shí)驗(yàn)中，我們利用Http Client和HTMLParser從互聯(lián)網(wǎng)上獲得實(shí)驗(yàn)數(shù)據(jù)。另一個(gè)非常有用的工具是ODBC，是用于訪問數(shù)據(jù)庫管理系統(tǒng)（DBMS）的標(biāo)準(zhǔn)軟件接口。

3.2 所選社會(huì)網(wǎng)絡(luò)的特性

我們選擇www.renren.com進(jìn)行我們的研究主要是基于以下3個(gè)原因。1）它是一個(gè)實(shí)名的大學(xué)生交友網(wǎng)站，因此，我們不僅可以通過函數(shù)評(píng)估實(shí)驗(yàn)結(jié)果，也可以通過對(duì)現(xiàn)實(shí)中的成員關(guān)系的調(diào)研來評(píng)估。2）renren.com用戶的連接圖是一個(gè)典型的稠密矩陣。我們有2 095個(gè)成員節(jié)點(diǎn)和63 819個(gè)好友關(guān)系，雖然成員的ID僅有8～9位數(shù)字，但是數(shù)據(jù)占用75.3Mb的存儲(chǔ)空間。在我們所研究的部分虛擬網(wǎng)絡(luò)中，一個(gè)成員的好友數(shù)超過23人，就意味著其關(guān)系矩陣將是一個(gè)相對(duì)密集的大型矩陣。稀疏矩陣的特點(diǎn)是邊數(shù)E≈節(jié)點(diǎn)數(shù)，N≈2個(gè)節(jié)點(diǎn)之間最短路徑長(zhǎng)度L。與稀疏矩陣相比，該矩陣具有邊數(shù)E?節(jié)點(diǎn)數(shù)N，以及2個(gè)節(jié)點(diǎn)之間最短路徑長(zhǎng)度L?邊數(shù)E的特點(diǎn)。因此，我們?cè)谙挛闹袝?huì)重點(diǎn)討論算法復(fù)雜度的問題。最后因?yàn)樵摼W(wǎng)絡(luò)中2個(gè)成員的好友關(guān)系是對(duì)等的，并沒有指向性，所以該社會(huì)網(wǎng)絡(luò)抽象模型是一個(gè)無向圖，并且其關(guān)系矩陣是對(duì)稱矩陣。這將大大簡(jiǎn)化實(shí)驗(yàn)需要考慮的問題，但是本文所提出的分割節(jié)點(diǎn)法同時(shí)適用于有向網(wǎng)絡(luò)的分析。

定義4：實(shí)驗(yàn)中，數(shù)據(jù)準(zhǔn)備的過程中獲取過其所有好友關(guān)系的節(jié)點(diǎn)被稱為準(zhǔn)備好節(jié)點(diǎn)。若某節(jié)點(diǎn)的所有鄰接點(diǎn)都是準(zhǔn)備好節(jié)點(diǎn)，則這個(gè)節(jié)點(diǎn)稱為一級(jí)節(jié)點(diǎn)。除一級(jí)節(jié)點(diǎn)之外的準(zhǔn)備好節(jié)點(diǎn)稱為二級(jí)節(jié)點(diǎn)。

在本次實(shí)驗(yàn)的數(shù)據(jù)中，我們選擇10個(gè)一級(jí)節(jié)點(diǎn)，他們將是第4節(jié)實(shí)驗(yàn)過程中的論述重點(diǎn)。

4 實(shí)驗(yàn)過程

本節(jié)將給出實(shí)驗(yàn)過程及實(shí)現(xiàn)算法中的具體細(xì)節(jié)，并將重點(diǎn)分析節(jié)點(diǎn)相似度的計(jì)算方法、節(jié)點(diǎn)分裂數(shù)目、循環(huán)算法的邊界條件等。

4.1 實(shí)驗(yàn)步驟

圖3中，實(shí)線所標(biāo)示的是分裂節(jié)點(diǎn)算法的實(shí)驗(yàn)流程，虛線是經(jīng)典階層式聚類算法實(shí)驗(yàn)步驟。經(jīng)典階層式聚類算法采用傳統(tǒng)的無重疊的社會(huì)網(wǎng)絡(luò)模型進(jìn)行分析，并將作為本次實(shí)驗(yàn)的對(duì)照實(shí)驗(yàn)，以輔助對(duì)分裂算法的評(píng)估。評(píng)估將根據(jù)上文中提到的，以功能函數(shù)和基于事實(shí)的兩種方法進(jìn)行。

圖3 實(shí)驗(yàn)流程圖

4.2 根據(jù)相似度分裂一級(jí)節(jié)點(diǎn)

在本次實(shí)驗(yàn)中，將采用最常用的相似度算法之一，Jaccard相似度度量2個(gè)節(jié)點(diǎn)的緊密程度：

上述相似度計(jì)算公式最大的優(yōu)勢(shì)是相對(duì)較低的時(shí)間復(fù)雜度和空間復(fù)雜度。對(duì)于單一節(jié)點(diǎn)算法的時(shí)間復(fù)雜度和空間復(fù)雜度分別是O（n）和O（1），對(duì)于整個(gè)網(wǎng)絡(luò)是O（n2）和O（n）。

除了采用較簡(jiǎn)單的相似度計(jì)算方法，將數(shù)據(jù)放在內(nèi)存中，也可以在很大程度上提高計(jì)算速度。根據(jù)上述計(jì)算結(jié)果，我們刪除圖中最小相似度值的2個(gè)節(jié)點(diǎn)的連接，也就是刪除虛擬社會(huì)網(wǎng)絡(luò)中關(guān)系最不緊密的好友關(guān)系。

圖4顯示刪除某一個(gè)一級(jí)節(jié)點(diǎn)的子社區(qū)中最低相似度的邊，并將這個(gè)子社區(qū)分割為分立社區(qū)時(shí)，作用在其子社區(qū)上的功能函數(shù)的趨勢(shì)圖。

定義5：我們定義圖4顯示刪除一級(jí)節(jié)點(diǎn)A的子社區(qū)中最低相似度的邊并將這個(gè)子社區(qū)分割為分立社區(qū)時(shí)，作用在其子社區(qū)上的功能函數(shù)的曲線為A的Q曲線。

圖4 1號(hào)節(jié)點(diǎn)的Q曲線

在大多數(shù)的一級(jí)節(jié)點(diǎn)，節(jié)點(diǎn)的Q曲線上與圖4類似。整體來看該曲線像二次曲線那樣上升和下降的過程，并有峰值。但與二次曲線不同的是，Q曲線并不是單調(diào)上升或下降的。在其上升或下降的過程中，也會(huì)出現(xiàn)很多小峰尖，一般出現(xiàn)在新的分立社區(qū)性成的時(shí)候。在這個(gè)實(shí)驗(yàn)中，當(dāng)Q曲線達(dá)到最高點(diǎn)時(shí)我們停止刪除邊的循環(huán)算法，如圖2所示。由于Q曲線并不是單調(diào)上升或下降的，故在循環(huán)程序運(yùn)行到圖中所示的功能函數(shù)最大值的時(shí)候，并不能直接判斷是否已經(jīng)到達(dá)最大值，我們需要繼續(xù)運(yùn)行程序，直到Q曲線衰減到一定程度時(shí)，本實(shí)驗(yàn)選取Q曲線已出現(xiàn)的最大值的0.8倍作為刪除連接函數(shù)的截止條件。在圖4中虛線所標(biāo)記的Q曲線最大值處，該子圖中的任意2個(gè)1號(hào)的鄰接點(diǎn)的相似度最小值是0.091 65，最終1號(hào)節(jié)點(diǎn)的子社區(qū)分隔成3個(gè)分離社區(qū)，進(jìn)而1號(hào)節(jié)點(diǎn)被分割為3個(gè)不同標(biāo)記的節(jié)點(diǎn)。

4.3 2組實(shí)驗(yàn)的結(jié)果對(duì)比

圖5中1線是所有一級(jí)節(jié)點(diǎn)經(jīng)過分割處理后應(yīng)用經(jīng)典聚類方法對(duì)整個(gè)虛擬社會(huì)網(wǎng)絡(luò)進(jìn)行處理時(shí)功能函數(shù)的變化曲線，2線是一般的階層式聚類算法對(duì)網(wǎng)絡(luò)處理時(shí)函數(shù)的變化曲線。根據(jù)該圖，我們可以看出應(yīng)用分割節(jié)點(diǎn)法時(shí)的功能函數(shù)值大于經(jīng)典聚類方法的功能函數(shù)值，在統(tǒng)計(jì)分析的意義上，分割的節(jié)點(diǎn)法得到比經(jīng)典聚類方法更理想的結(jié)果。但由于在上圖中2曲線有大致相同的變化速率，所以分裂節(jié)點(diǎn)的方法并不能加快處理的速度，也就是說，分裂節(jié)點(diǎn)法并不能提高得到最佳社會(huì)網(wǎng)絡(luò)分割的算法效率，它只是優(yōu)化了算法結(jié)果。

當(dāng)我們應(yīng)用分裂節(jié)點(diǎn)所得的結(jié)果進(jìn)行實(shí)際情況抽樣調(diào)查時(shí)，分割方法在分割節(jié)點(diǎn)時(shí)所得到的子社區(qū)分割結(jié)果也基本與事實(shí)相符。例如4.2節(jié)中提到的1號(hào)節(jié)點(diǎn)的子社區(qū)中，在這3個(gè)社區(qū)的成員大多分別是1號(hào)節(jié)點(diǎn)在小學(xué)、高中和大學(xué)的同學(xué)。

圖5 應(yīng)用分裂節(jié)點(diǎn)法（▲）與經(jīng)典階層式聚類算法（■）的功能函數(shù)變化曲線

［1］Duch J，Arenas A.Community detection in complex networks using extremely optimization［J］.Physical Review E，2005，72（2）.

［2］Flake G W，Lawrence S，Giles C L，et al.Self－organization and identi？cation of Web communities［J］.IEEE Computer，2002，35（2）：66－70.

［3］Baum’s J，Goldberg M.K，Krishnamoorthy M S，et al.Finding communities by clustering agraph into overlapping sub graphs［C］／／IADIS AC.IADIS，2005：97－104.

［4］Padrol－Sureda A，Perarnau－Llobet G，Pfeifle J，et al.Overlapping community search for social networks［C］／／Data Engineering（ICDE），2010IEEE 26th International Conference on.Long Beach，CA：IEEE，2010：992－995.

［5］Chung F.Spectral Graph Theory［M］.American Mathematical Society，1997.

［6］Newman M E J.Detecting community structure in networks［J］.The European Physical Journal B，2004，38（2）：321－330.

［7］Goldberg Mark，Kelley Stephen，Magdon－Ismail，et al.Finding overlapping communities in social networks［C］／／IEEE Second International Conference on Social Computing.IEEE，2010：104－113.

［8］Cazabet Remy，Amblard Frederic，Hanachi Chihab.Detection of overlapping communities in dynamical social networks［C］／／Social Computing （SocialCom），2010 IEEE Second International Conference on.IEEE，2010：309－314.

［10］Steve Gregory.An algorithm to find overlapping community structure in networks［C］／／Knowledge discovery in databases：PKDD 2007.Warsaw，Poland：Springer Berlin Heidelberg，2007：91－102.

［11］Jeffrey Baumes，Goldberg Mark，Magdon－Ismail Malik.Efficient identification of overlapping communities［C］／／Intelligence and Security Informatics.Atlanta，GA，USA：Springer Berlin Heidelberg，2005：27－36.

［12］王陸.虛擬學(xué)習(xí)社區(qū)社會(huì)網(wǎng)絡(luò)中的凝聚子群［J］.中國(guó)電化教育.2009（8）：22－28.

［13］唐常杰，劉威，溫粉蓮，等.社會(huì)網(wǎng)絡(luò)分析和社團(tuán)信息挖掘的三項(xiàng)探索——挖掘虛擬社團(tuán)的結(jié)構(gòu)，核心和通信行為［J］.計(jì)算機(jī)應(yīng)用，2006，26（9）：20－23.

［14］王陸.典型的社會(huì)網(wǎng)絡(luò)分析軟件工具及分析方法［J］.中國(guó)電化教育，2009（4）：95－100.

［15］石劍飛，閆懷志，牛占云.基于凝聚的層次聚類算法的改進(jìn)［J］.北京理工大學(xué)學(xué)報(bào)，2008，28（1）：66－69.