李維勇，孔 楓，張 偉，陳云芳

（1.南京信息職業(yè)技術(shù)學(xué)院網(wǎng)絡(luò)與通信學(xué)院，南京210023；2.南京郵電大學(xué)計(jì)算機(jī)學(xué)院，南京210023）

引 言

近年來，社區(qū)發(fā)現(xiàn)成為復(fù)雜網(wǎng)絡(luò)分析的重要任務(wù)，社區(qū)發(fā)現(xiàn)方法在社交網(wǎng)絡(luò)中受到了極大的關(guān)注。社區(qū)是社交網(wǎng)絡(luò)中的一種普遍現(xiàn)象，在社區(qū)中的許多成員傾向于形成緊密聯(lián)系的群體。在不同的情況下，這些群體可以稱為社區(qū)、集群、內(nèi)聚子團(tuán)或模塊。社區(qū)發(fā)現(xiàn)是通過分析網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)和網(wǎng)絡(luò)節(jié)點(diǎn)的屬性來研究出的某種集群的結(jié)構(gòu)特征從而組成的一種網(wǎng)絡(luò)節(jié)點(diǎn)集合，在該集群中內(nèi)部節(jié)點(diǎn)連接緊密，而外部節(jié)點(diǎn)連接稀疏。顯然，該集群的內(nèi)部節(jié)點(diǎn)之間的交流比外部節(jié)點(diǎn)更加頻繁。

如何在復(fù)雜網(wǎng)絡(luò)中找到社區(qū)結(jié)構(gòu)已經(jīng)成為許多領(lǐng)域的熱門話題，包括社會(huì)學(xué)、生物信息學(xué)和物理學(xué)等。屬于同一個(gè)社區(qū)中的節(jié)點(diǎn)具有更大的可能性有著相同或相似的屬性：例如，在同一個(gè)社交網(wǎng)絡(luò)中的群體［1］更可能具有共同的興趣愛好或者背景；在萬維網(wǎng)中［2-4］形成的社區(qū)結(jié)構(gòu)可能具有共同的主題和相關(guān)的頁面；在細(xì)胞和遺傳相關(guān)的生物或神經(jīng)網(wǎng)絡(luò)中［5-6］，社區(qū)結(jié)構(gòu)的形成可能暗示細(xì)胞存在相似特征。這些網(wǎng)絡(luò)集合可以幫助簡(jiǎn)化整個(gè)網(wǎng)絡(luò)的功能分析。

由于社區(qū)發(fā)現(xiàn)研究具有很重要的意義，目前已有許多社區(qū)發(fā)現(xiàn)方法被提出?，F(xiàn)有的社區(qū)發(fā)現(xiàn)方法大致分為傳統(tǒng)方法、分裂方法、基于模塊的方法、譜方法和動(dòng)態(tài)方法等［7］。分裂算法的思想是檢測(cè)連接不同社區(qū)的頂點(diǎn)的邊并將其刪除，使集群間彼此斷開，其中最受歡迎的算法是Girvan和Newman提出的［8-9］，他們定義了中介性，并引入了模塊度作為網(wǎng)絡(luò)結(jié)構(gòu)的后繼度量，這對(duì)于社區(qū)發(fā)現(xiàn)具有非常重要的意義，并在許多應(yīng)用場(chǎng)合中獲得了成功。模塊度是衡量社區(qū)結(jié)構(gòu)最著名的質(zhì)量函數(shù)，基于模塊度又使用了不同的聚類方法，例如貪心算法［10］、模擬退火方法［11］、外部?jī)?yōu)化方法［12］、譜優(yōu)化方法［13］以最大化模塊度［14］。一些研究人員還提出了改進(jìn)的模塊度測(cè)量方法，例如擴(kuò)展到有向圖，包括有向圖的正邊和負(fù)邊概念。譜方法是根據(jù)圖的特征矩陣、特征向量、特征值來發(fā)現(xiàn)社區(qū)。動(dòng)態(tài)方法則采用圖上的運(yùn)動(dòng)過程，例如旋轉(zhuǎn)-旋轉(zhuǎn)交互，隨機(jī)行走和同步。

最近由社區(qū)發(fā)現(xiàn)算法發(fā)展起來的圖劃分開辟了網(wǎng)絡(luò)分析的新領(lǐng)域。此外，在社區(qū)發(fā)現(xiàn)算法的研究中，SimRank方法被用來推斷網(wǎng)絡(luò)的結(jié)構(gòu)特性，該方法之所以非常適合社區(qū)聚類的原因很明顯：節(jié)點(diǎn)之間會(huì)以更高的概率來吸引和它們具有相同性質(zhì)的節(jié)點(diǎn)。

Ganjaliyev［15］提出了一種通過聚類來識(shí)別網(wǎng)絡(luò)中社區(qū)的方法。在這種方法中，存在一組約束條件，即每個(gè)數(shù)據(jù)對(duì)象正好分配給一個(gè)集群，每個(gè)集群至少包含一個(gè)對(duì)象［16］。選擇一定數(shù)量的集群，并使所選集群的總權(quán)重最大化而使集群之間的相似性最小化。Choudhury等［17］重點(diǎn)研究了一種新的Newman-Girvan算法來檢測(cè)社交網(wǎng)絡(luò)中的社區(qū)和子社區(qū)。該方法已在Zachary空手道俱樂部、Bottlenose海豚網(wǎng)絡(luò)和大學(xué)足球網(wǎng)絡(luò)等真實(shí)的社交網(wǎng)絡(luò)中展開了實(shí)施。Lee和Cunningham［18］描述了在評(píng)估大型數(shù)據(jù)集和小型手工制數(shù)據(jù)集方面的差異，在較小數(shù)據(jù)集上運(yùn)行良好的算法在大型數(shù)據(jù)集上可能運(yùn)行的效果較差，因此，他們引入了一個(gè)框架，在該框架中，社交網(wǎng)絡(luò)數(shù)據(jù)集使用元數(shù)據(jù)進(jìn)行注釋，該框架基于機(jī)器學(xué)習(xí)：假設(shè)如果社區(qū)發(fā)現(xiàn)算法運(yùn)行良好，則分類器應(yīng)該能夠使用發(fā)現(xiàn)的社區(qū)集合來推斷與社區(qū)結(jié)構(gòu)密切相關(guān)的節(jié)點(diǎn)屬性的缺失值，該節(jié)點(diǎn)屬性有兩個(gè)缺陷：不完整和嵌套，他們還解釋了挖掘出的數(shù)據(jù)如何遭受目的收集的數(shù)據(jù)的影響。Muslim［19］討論了4種使用節(jié)點(diǎn)的結(jié)構(gòu)和屬性相似性的社區(qū)結(jié)構(gòu)檢測(cè)方案，每個(gè)方案提供了不同的輸出，可以將其組合然后在社交網(wǎng)絡(luò)中找到社區(qū)。第1種方案使用節(jié)點(diǎn)之間的結(jié)構(gòu)相似性；第2種方案利用節(jié)點(diǎn)之間的屬性相似性；在第3種方案中利用了節(jié)點(diǎn)之間的結(jié)構(gòu)相似性和屬性相似性；在第4種方案中僅考慮使用節(jié)點(diǎn)之間的屬性相似性。Wang等［20］提出了一種基于動(dòng)態(tài)內(nèi)容的網(wǎng)絡(luò)社區(qū)檢測(cè)方法NEI-Walk，該篇文章中提出了一種基于內(nèi)容的網(wǎng)絡(luò)轉(zhuǎn)換為節(jié)點(diǎn)-邊緣交互（Node edge interaction，NEI）網(wǎng)絡(luò)的方法，其中節(jié)點(diǎn)內(nèi)容、邊緣內(nèi)容和鏈接結(jié)構(gòu)被無縫地嵌入。首先，基于內(nèi)容的網(wǎng)絡(luò)被轉(zhuǎn)換為NEI網(wǎng)絡(luò)，即一種多模式網(wǎng)絡(luò)，由2種類型的節(jié)點(diǎn)和3種類型的邊組成，分別稱為n節(jié)點(diǎn)和e節(jié)點(diǎn)，3種類型的邊緣分別表示節(jié)點(diǎn)內(nèi)容相似性，邊內(nèi)容相似性和結(jié)構(gòu)相似性。隨著基于內(nèi)容的網(wǎng)絡(luò)的發(fā)展，提出了一種基于差異活動(dòng)的方法來逐步維護(hù)NEI網(wǎng)絡(luò)，通過在NEI網(wǎng)絡(luò)中應(yīng)用異構(gòu)隨機(jī)游走發(fā)現(xiàn)潛在社區(qū)。Blondel等［21］提出了一種方法，它是一種基于模塊化優(yōu)化的啟發(fā)式方法。以每個(gè)開始節(jié)點(diǎn)作為社區(qū)，并基于模塊度作為來優(yōu)化應(yīng)合并的社區(qū)標(biāo)準(zhǔn)，在一組節(jié)點(diǎn)上重復(fù)此操作幾次，直到無法進(jìn)行進(jìn)一步優(yōu)化為止。然后在社區(qū)圖上整體重復(fù)該過程。Raghavan等［22］提出了一種基于標(biāo)簽傳播的簡(jiǎn)單方法，最初，圖中的每個(gè)節(jié)點(diǎn)都使用唯一的標(biāo)簽進(jìn)行初始化，并且在方法的每個(gè)步驟中，每個(gè)節(jié)點(diǎn)都采用其大多數(shù)鄰居當(dāng)前具有的標(biāo)簽，無法更改標(biāo)簽時(shí)，迭代過程收斂。對(duì)于具有相同標(biāo)簽的每組節(jié)點(diǎn)形成一個(gè)社區(qū)。

雖然已有許多不同的社區(qū)發(fā)現(xiàn)方法被提出，但還有一些尚未解決的問題：當(dāng)進(jìn)行大規(guī)模的網(wǎng)絡(luò)分析時(shí)，大多數(shù)算法效率低下且時(shí)間復(fù)雜度高。自1998年谷歌網(wǎng)頁排名算法PageRank提出以來，相繼有SimRank［23］、SimFusion［24］、Penetrating-Rank［25］等基于圖拓?fù)浣Y(jié)構(gòu)的相似度計(jì)算模型被提出，其中Sim-Rank被認(rèn)為是一種比較流行的基于有向圖拓?fù)浣Y(jié)構(gòu)的計(jì)算圖節(jié)點(diǎn)相似度的模型。它的主要思想為：如果兩個(gè)對(duì)象（節(jié)點(diǎn)）被相似的對(duì)象引用（即有向圖中不同節(jié)點(diǎn)的入邊鄰節(jié)點(diǎn)相似或相同），那么這兩個(gè)節(jié)點(diǎn)也相似。近年來，基于SimRank的方法被用到了社區(qū)發(fā)現(xiàn)中，使用SimRank方法計(jì)算兩個(gè)節(jié)點(diǎn)之間的相似度，可以計(jì)算出具有相同屬性信息的節(jié)點(diǎn)屬于同一個(gè)社區(qū)的可能性更大，從而可以逐步確定出一個(gè)社區(qū)結(jié)構(gòu)。

然而面對(duì)大規(guī)模網(wǎng)絡(luò)，使用傳統(tǒng)的節(jié)點(diǎn)之間計(jì)算相似度的方法計(jì)算消耗的時(shí)間過長(zhǎng)；但是，對(duì)于具有冪律分布［26-27］的網(wǎng)絡(luò)來說，核心節(jié)點(diǎn)起著非常重要的作用。因此，本文提出了一種基于SimRank的層次社區(qū)發(fā)現(xiàn)算法，該方法有以下3方面創(chuàng)新：

（1）利用自然的冪律分布和網(wǎng)絡(luò)中的社區(qū)結(jié)構(gòu)，本文用核心節(jié)點(diǎn)測(cè)量網(wǎng)絡(luò)中的所有節(jié)點(diǎn)迭代的穩(wěn)定性；

（2）使用SimRank函數(shù)計(jì)算節(jié)點(diǎn)與節(jié)點(diǎn)之間的相似度，通過迭代計(jì)算減少的計(jì)算復(fù)雜度；

（3）迭代計(jì)算后的節(jié)點(diǎn)相似度將社區(qū)聚集在核心節(jié)點(diǎn)周圍，根據(jù)社區(qū)質(zhì)量評(píng)估指標(biāo)，重復(fù)執(zhí)行社區(qū)的合并，以獲得合理的社區(qū)。

本文首先介紹了社區(qū)發(fā)現(xiàn)方法研究的相關(guān)工作；然后介紹相關(guān)的理論基礎(chǔ)和概念。進(jìn)而描述了基于SimRank的全局矩陣平滑收斂的社區(qū)發(fā)現(xiàn)，并展示實(shí)驗(yàn)分析結(jié)果。最后，得出結(jié)論并建議未來研究方向。

1 SimRank的定義

網(wǎng)絡(luò)圖一般使用G=(V，E)來表示，其中V={v1，…，vn}和E={e1，…，en}分別表示節(jié)點(diǎn)集合和邊的集合，圖G的鄰接矩陣為A，其中aij=1表示節(jié)點(diǎn)i和節(jié)點(diǎn)j之間存在連接的邊，aij=0表示不存在連接的邊。在這里圖G被認(rèn)為是無向網(wǎng)絡(luò)圖，所以鄰接矩陣A是對(duì)稱矩陣。表示節(jié)點(diǎn)i的鄰接點(diǎn)的個(gè)數(shù)。

SimRank是Jeh與Widom于2002年提出的通過圖G=(V，E)的拓?fù)浣Y(jié)構(gòu)衡量圖中任意2個(gè)節(jié)點(diǎn)相似度的模型［23］。SimRank計(jì)算滿足以下2條規(guī)則：（1）如果兩個(gè)不同對(duì)象被相似對(duì)象引用，則這兩個(gè)對(duì)象相似（遞歸定義）；（2）每個(gè)對(duì)象與其自身相似度最高（基本情況）。

定義1 SimRank定義的數(shù)學(xué)表達(dá)式為［23］

式中：c為取值0到1之間的阻尼系數(shù)，一般取值范圍0.6～0.8［10］；I(a)為節(jié)點(diǎn)a的入邊鄰節(jié)點(diǎn)集合中元素的數(shù)量。

由于圖G的鄰接矩陣為A，矩陣A的列歸一化矩陣Q，則相似矩陣S根據(jù)定義1可表示為

式中：QT為向后轉(zhuǎn)移矩陣的轉(zhuǎn)置，I表示單位矩陣，即將計(jì)算結(jié)果對(duì)角元素均取值為1。

式（1）可 以 用 來 引 入 迭 代 方 法 來 計(jì) 算：如 果a≠b，則 有s0(a，a)=1和s0(a，b)=0，對(duì) 于k=0，1，2，…，設(shè)（i）sk+1(a，a)=1；（ii）如果I(a)=φ或I(b)=φ，sk+1(a，b)=0；（iii）否則

對(duì)于式（2）可變形為

Jeh和Widom［23］首先提出：每個(gè)節(jié)點(diǎn)與自己相似度為1，設(shè)置初始SimRank矩陣為S0=I；根據(jù)式（4）迭代計(jì)算，直至收斂，并且在文獻(xiàn)［23］中證明了此算法收斂性。

2 SGSC算法

2.1 概覽

在真實(shí)的社交網(wǎng)絡(luò)交往過程中，人們的初始行為通常具有以下特征：存在著隨機(jī)性，但是，隨著時(shí)間的流逝，社會(huì)關(guān)系會(huì)趨于穩(wěn)定狀態(tài)，逐漸形成相對(duì)穩(wěn)定的社會(huì)圈子，通常稱這種現(xiàn)象為社區(qū)。受此現(xiàn)象觀察啟發(fā)，本文采用SimRank全局矩陣平滑收斂的網(wǎng)絡(luò)社區(qū)發(fā)現(xiàn)方法（SimRank global smooth convergence，SGSC）算法來作為衡量社交網(wǎng)絡(luò)節(jié)點(diǎn)的模型，來模擬社交網(wǎng)絡(luò)中關(guān)系的相似性。

由于社交網(wǎng)絡(luò)具有大量節(jié)點(diǎn)，通常時(shí)間復(fù)雜度計(jì)算會(huì)隨網(wǎng)絡(luò)規(guī)模呈指數(shù)增長(zhǎng)。為了降低計(jì)算的復(fù)雜性，本文將從兩方面來進(jìn)行：（1）將社交網(wǎng)絡(luò)視為粗粒度單位而不是細(xì)粒度的單元或節(jié)點(diǎn)，這意味著是可以進(jìn)行社區(qū)聚類的；（2）提出了基于SimRank的矩陣收斂的概念，這是計(jì)算節(jié)點(diǎn)與節(jié)點(diǎn)的相似度所需要的；并且本文提出的方法是不需要設(shè)置初始的社區(qū)數(shù)量，因而對(duì)核心節(jié)點(diǎn)的初始選擇不敏感。

本文算法的主要步驟如下：

步驟1根據(jù)節(jié)點(diǎn)的中心度指標(biāo)選擇初始核心節(jié)點(diǎn)；

步驟2計(jì)算SimRank函數(shù)，利用節(jié)點(diǎn)之間的相似度進(jìn)行矩陣迭代收斂；

步驟3對(duì)于每個(gè)非核心節(jié)點(diǎn)，選擇離的最近的真正核心節(jié)點(diǎn)中的核心節(jié)點(diǎn)，并加入該集合，因此，圍繞核心節(jié)點(diǎn)形成初始社區(qū)；

步驟4重復(fù)此過程以評(píng)估形成的社區(qū)質(zhì)量，并合并緊密的社區(qū)。

2.2 選擇核心節(jié)點(diǎn)

通常網(wǎng)絡(luò)是由一些社區(qū)組成，并且每個(gè)社區(qū)都有一個(gè)核心節(jié)點(diǎn)，在此基礎(chǔ)上提出合理的假設(shè)，只要核心節(jié)點(diǎn)可以到達(dá)其他社區(qū)，就可以考慮一個(gè)社區(qū)的所有節(jié)點(diǎn)可以到達(dá)另一個(gè)社區(qū)的所有節(jié)點(diǎn)，這意味著整個(gè)網(wǎng)絡(luò)都是連接的。這種情況類似于首都和每個(gè)省份的大城市之間都有聯(lián)系，所以全國(guó)各地的所有城市都是相互聯(lián)系。多數(shù)情況下社交網(wǎng)絡(luò)中的節(jié)點(diǎn)遵循冪律分布，因此只有極少數(shù)的節(jié)點(diǎn)互連著其他節(jié)點(diǎn)，稱為核心節(jié)點(diǎn)。選擇初始核心節(jié)點(diǎn)的方法至關(guān)重要，必須避免選擇錯(cuò)誤的核心節(jié)點(diǎn)并不錯(cuò)失真實(shí)的核心節(jié)點(diǎn)。

利用傳統(tǒng)的衡量社交網(wǎng)絡(luò)中節(jié)點(diǎn)重要性的指標(biāo)有以下幾種方法：度中心性、緊密度中心性、中介中心性和特征向量中心性。在本文中，采用度中心性作為最基本的指標(biāo)來識(shí)別網(wǎng)絡(luò)中的社區(qū)。這樣做有2個(gè)原因：（1）計(jì)算度中心性比較簡(jiǎn)單；（2）度中心性和迭代過程中使用的矩陣是一致的。

注意到度中心性不僅反映了每個(gè)節(jié)點(diǎn)和其他節(jié)點(diǎn)的相關(guān)性，并且也與和網(wǎng)絡(luò)規(guī)模相關(guān)，即網(wǎng)絡(luò)中的節(jié)點(diǎn)數(shù)。隨著網(wǎng)絡(luò)大小的增加，度中心性的最大值也可能在增加，為了消除度中心性對(duì)網(wǎng)絡(luò)規(guī)模的影響，定義節(jié)點(diǎn)i的重要性如下

若一節(jié)點(diǎn)i滿足Important(vi)≥τ，通過式（5）選擇出來的節(jié)點(diǎn)集合稱為初始核心節(jié)點(diǎn)，初始核心節(jié)點(diǎn)集合定義為

式中τ為一預(yù)設(shè)閾值。

根據(jù)SimRank的特點(diǎn)，隨著迭代趨于無窮大，矩陣不斷趨于最終的穩(wěn)定值。在迭代過程中，一個(gè)節(jié)點(diǎn)到另一個(gè)節(jié)點(diǎn)的集合在不斷增加或逐漸穩(wěn)定在一個(gè)較大的值，這表明目標(biāo)節(jié)點(diǎn)更具有影響力，因此是真實(shí)的核心節(jié)點(diǎn)。因此，使用經(jīng)典的度中心性進(jìn)行度量，解決選擇初始核心節(jié)點(diǎn)集，如果設(shè)置的閾值更高，初始核心節(jié)點(diǎn)集合相對(duì)??；如果將其設(shè)置為較低，則初始核心節(jié)點(diǎn)集合比較大。但是，此更改對(duì)確定最終的核心節(jié)點(diǎn)影響不大。

2.3 選擇社區(qū)合并

確定迭代的步數(shù)之后，可以確保矩陣迭代的穩(wěn)定性，并且可以確定核心節(jié)點(diǎn)距離每個(gè)最近的非核心節(jié)點(diǎn)，然后將非核心節(jié)點(diǎn)放入其最近的核心節(jié)點(diǎn)所在的社區(qū)中。

最初的社區(qū)圍繞核心節(jié)點(diǎn)形成，算法1中的算法需要進(jìn)一步的聚集才能形成層次結(jié)構(gòu)，涉及兩個(gè)步驟：（1）選擇2個(gè)要合并的社區(qū)并計(jì)算它們的相似性；（2）確定聚類過程是否應(yīng)停止。由于傳統(tǒng)衡量社區(qū)劃分質(zhì)量的指標(biāo)，例如：模塊Q，會(huì)涉及更多的計(jì)算復(fù)雜度。從這個(gè)角度來看，利用社區(qū)緊密度指標(biāo)，以確定兩個(gè)社區(qū)之間的相似性，定義如下

式中：Edgesinternal(Ci∪Cj)和Edgesexternal(Ci∪Cj)分別表示新的合并后的社區(qū)的內(nèi)部邊和外部邊，Edgesinternal(Ci)和Edgesexternal(Ci)分別表示Ci社區(qū)的內(nèi)部邊和外部邊，當(dāng)Closeness(Ci，Cj)大于某個(gè)閾值時(shí)，將兩個(gè)社區(qū)進(jìn)行合并，一般將該閾值設(shè)置為1～2之間，根據(jù)不同的網(wǎng)絡(luò)可適當(dāng)調(diào)整該閾值，算法1詳細(xì)給出了SGSC算法的整個(gè)過程。

算法1SGSC

輸入：圖G，核心節(jié)點(diǎn)集合CenterSet，參數(shù)α，迭代次數(shù)k，阻尼系數(shù)c

輸出：社區(qū)劃分集合

1：fork：

2：計(jì)算S=（c·QTSQ）+（1-c）·I直至收斂

3：end for

4：ifS＞α：

5：CenterSet=［vi］

6：for i in CenterSet：

7：for j in圖G中除核心節(jié)點(diǎn)外的每個(gè)節(jié)點(diǎn)vj：

8：計(jì)算Closeness（Ci，Cj）直至無法計(jì)算

9：end for

9：if Closeness（Ci，Cj）＞ω：

10： 將相應(yīng)的社區(qū)節(jié)點(diǎn)進(jìn)行合并

11：返回初始社區(qū)劃分集合C

12：for社區(qū)C中的任意兩個(gè)社區(qū)Ci，Cj

13：重復(fù)執(zhí)行8到10

14：返回社區(qū)劃分集合

2.4 驗(yàn)證指標(biāo)

為了評(píng)估不同算法的有效性，本文采用Newman-Girvan模塊度這個(gè)指標(biāo)來評(píng)估網(wǎng)絡(luò)中社區(qū)的結(jié)構(gòu)強(qiáng)度：對(duì)于整個(gè)網(wǎng)絡(luò)來說，cp為通過某種算法事先得到的社交網(wǎng)絡(luò)劃的社區(qū)劃分。cp的Newman-Girvan模塊度定義為［8］

在本文中節(jié)點(diǎn)v和節(jié)點(diǎn)w的值avw=1表示有向圖中的權(quán)值，如果δ(Cv，Cw)=1表示節(jié)點(diǎn)v和節(jié)點(diǎn)w屬于同一個(gè)社區(qū)，如果δ(Cv，Cw)=0則不屬于同一個(gè)社區(qū)。Cv和Cw分別代表節(jié)點(diǎn)v和節(jié)點(diǎn)w屬于的社區(qū)。表示節(jié)點(diǎn)i的終端和另一個(gè)社區(qū)j相連的邊緣分?jǐn)?shù)。是連接到社區(qū)i中節(jié)點(diǎn)的邊的比例。

3 實(shí)驗(yàn)分析

為了驗(yàn)證SGSC算法在不同類型的網(wǎng)絡(luò)中的性能，本文使用了3個(gè)數(shù)據(jù)集進(jìn)行分析：American College Football網(wǎng)絡(luò)［28］、Facebook網(wǎng)絡(luò)［29］以及歐洲D(zhuǎn)eezer社 交 網(wǎng) 絡(luò)［29］，如 表1所 示。American College Football網(wǎng)絡(luò)是具有115個(gè)節(jié)點(diǎn)和613條邊的小組織的網(wǎng)絡(luò)；Facebook網(wǎng)絡(luò)包含來自Facebook的“圈子”（或“朋友列表”），它是由4 039個(gè)節(jié)點(diǎn)和88 234條邊組成的中等規(guī)模的社交網(wǎng)絡(luò)；Deezer用戶的社交網(wǎng)絡(luò)的節(jié)點(diǎn)是來自歐洲國(guó)家的Deezer用戶，邊緣是他們之間的相互關(guān)注者關(guān)系，它是由28 281個(gè)節(jié)點(diǎn)和92 752條邊組成的大規(guī)模網(wǎng)絡(luò)。通過實(shí)驗(yàn)，將提出的SGSC算法和GN［8］以及Newman快速算法［10］進(jìn)行比較。

表1 測(cè)試數(shù)據(jù)集Table 1 Test datasets

本文使用的是Intel Pentium四核處理器，帶有8 GB DDR3內(nèi)存，Windows 10操作系統(tǒng)和Python3的Numpy圖分析工具和Matplotlib數(shù)據(jù)分析工具。

3.1 初始核心節(jié)點(diǎn)的選擇

如前文所述，選擇初始核心節(jié)點(diǎn)的方法是使用度中心性閾值的標(biāo)準(zhǔn)化公式，該值的范圍為0.0～1.0，0.0表示與任何節(jié)點(diǎn)都沒有聯(lián)系（例如一個(gè)孤點(diǎn)），1.0表示與每一個(gè)節(jié)點(diǎn)都有直接聯(lián)系。在社會(huì)網(wǎng)絡(luò)中，標(biāo)準(zhǔn)化的行為人的度中心性測(cè)量行為人在諸多關(guān)系中的參與程度，得到高分的行為人是網(wǎng)絡(luò)中最顯眼的參與者。如果標(biāo)準(zhǔn)化度中心性值越接近1.0，那么行為人在關(guān)系網(wǎng)絡(luò)中的參與度越高。在American College Football網(wǎng)絡(luò)中使用該方法確定了初始核心節(jié)點(diǎn)設(shè)置為｛1，0，3，2，5，6，7，15，53，67，82，88，104，43｝，根據(jù)不同的閾值設(shè)定，雖然選出的核心節(jié)點(diǎn)個(gè)數(shù)不一樣，但是，經(jīng)過多步驟迭代，真正的核心節(jié)點(diǎn)仍然是節(jié)點(diǎn)7、51、18和節(jié)點(diǎn)43。盡管未選擇節(jié)點(diǎn)51和節(jié)點(diǎn)18作為初始核心迭代計(jì)算后，但是經(jīng)過迭代之后，真正的核心節(jié)點(diǎn)仍然節(jié)點(diǎn)7、51、18和節(jié)點(diǎn)43。表2記錄了選擇不同的閾值對(duì)應(yīng)的核心節(jié)點(diǎn)的個(gè)數(shù)以及最終確定的核心節(jié)點(diǎn)。

表2 閾值的選擇對(duì)于核心節(jié)點(diǎn)的影響（American College Football網(wǎng)絡(luò)）Table 2 Effect of the threshold value on core nodes（American College Football network）

對(duì)于中等規(guī)模的網(wǎng)絡(luò)Facebook網(wǎng)絡(luò)來說，重復(fù)同樣的方式進(jìn)行測(cè)試，表3記錄了不同閾值的選擇對(duì)于核心節(jié)點(diǎn)的影響，盡管初始核心節(jié)點(diǎn)不一樣，但得到的最終核心節(jié)點(diǎn)始終是｛8，0，58，351，688，107，726，1 022，1 375，1 394，348，1 594，1 609，1 680，351，171，2 068，2 427，2 618，2 727，352，3 226，3 303，3 334，3 405，1 821，1 825，2 087，2 088，3 486，3 559，3 573，3 582，3 626，3 639，3 645，3 687，3 697，3 703，3 712，3 804，3 926，3 955，1 827，1 830，3 985，3 996，3 998，4 000，4 001，4 002，4 015，4 018，4 024，4 028，4 031，1 858，1 902，1 915，1 973，1 978，1 831，1 993，2 001，1 843，2 031｝，從實(shí)驗(yàn)的結(jié)果來看，本文提出的SGSC算法對(duì)于最終的核心節(jié)點(diǎn)的確認(rèn)是不會(huì)受到任何影響的。

表3 閾值的選擇對(duì)于核心節(jié)點(diǎn)的影響（Facebook網(wǎng)絡(luò)）Table 3 Effect of the threshold value on core nodes（Facebook network）

3.2 精確度

本文還設(shè)計(jì)了一個(gè)實(shí)驗(yàn)來評(píng)估算法的社區(qū)發(fā)現(xiàn)的能力，使用0，1，2，3，…作為American College Football網(wǎng)絡(luò)、Facebook網(wǎng)絡(luò)以及歐洲D(zhuǎn)eezer社交網(wǎng)絡(luò)節(jié)點(diǎn)的編號(hào)，根據(jù)提出的SGSC算法，可以將該網(wǎng)絡(luò)劃分成12個(gè)社區(qū)，｛3，5，10，11，40，52，72，74，81，84，98，102，107｝，｛0，4，9，16，23，41，90，93，104｝，｛1，25，33，37，45，89，103，105，109｝，｛12，14，18，26，31，34，36，38，42，43，54，61，71，85，99｝，｛46，49，53，67，73，83，88，110，114｝，｛6，13，15，47｝，｛44，48，57，66，75，86，91，92，97，112｝，｛17，20，27，56，58，59，62，63，65，70，76，87，95，96，113｝，｛24，28，69｝，｛7，8，21，22，50，51，68，77，78，108，111｝，｛19，29，30，35，55，79，80，82，94，101｝，和｛2，32，39，60，64，100，106｝，和真實(shí)的American College Football網(wǎng)絡(luò)社區(qū)劃分相比，SGSC算法對(duì)于社區(qū)的劃分個(gè)數(shù)完全一致，并且對(duì)于相應(yīng)的節(jié)點(diǎn)屬于相應(yīng)的社區(qū)也是劃分一致。

對(duì)于中等規(guī)模的Facebook網(wǎng)絡(luò)和大規(guī)模的歐洲的Deezer社交網(wǎng)絡(luò)，表4，5記錄了這3種算法的社區(qū)劃分結(jié)果以及模塊度。通過對(duì)這2種網(wǎng)絡(luò)的聚類出的社區(qū)模塊度的比較，從表4，5中可以看出，隨著網(wǎng)絡(luò)規(guī)模的增長(zhǎng)，SGSC算法表現(xiàn)出明顯的優(yōu)越性，GN算法則在中等規(guī)模和大規(guī)模的網(wǎng)絡(luò)中已經(jīng)無法得出聚類的結(jié)果。由于GN算法是一種性能不太好的基礎(chǔ)算法，因而尤其不適合處理大規(guī)模的真實(shí)社交網(wǎng)絡(luò)。

表4 Facebook網(wǎng)絡(luò)中社區(qū)劃分結(jié)果以及模塊度Table 4 Community division results and modularity of the divided communities（Facebook network）

表5 Deezer社交網(wǎng)絡(luò)中社區(qū)劃分結(jié)果以及模塊度Table 5 Community division results and modularity of the divided communities（Deezer social network）

同時(shí)，本文還比較了3種不同的網(wǎng)絡(luò)中社區(qū)劃分的模塊度值，圖1記錄了在3種不同的網(wǎng)絡(luò)中社區(qū)劃分的模塊度值比較，可以發(fā)現(xiàn)GN算法在Facebook網(wǎng)絡(luò)中已經(jīng)無法聚類出社區(qū)，因而它的社區(qū)模塊度為0，對(duì)于大規(guī)模Deezer社交網(wǎng)絡(luò)的社區(qū)模塊度也同樣為0。因此可以看出無論是在小規(guī)模American College Football網(wǎng)絡(luò)中還是在大規(guī)模的Deezer社交網(wǎng)絡(luò)中，本文所提出算法劃分出的社區(qū)模塊度均優(yōu)于GN算法和Newman快速算法。

雖然本文提出的算法最終對(duì)于社區(qū)劃分的模塊度的值不是非常理想，但從圖2還是可明顯看出，由于GN算法在中等規(guī)模的Facebook網(wǎng)絡(luò)中和Deezer網(wǎng)絡(luò)中已無法聚類出社區(qū)，所以GN算法運(yùn)行的時(shí)間必然超過10 000 s，雖然在小規(guī)模網(wǎng)絡(luò)中，Newman快速算法的運(yùn)行時(shí)間復(fù)雜度和本文提出的SGSC算法幾乎相差不大，但隨著網(wǎng)絡(luò)規(guī)模的增大，本文算法的優(yōu)勢(shì)逐漸體現(xiàn)，在大規(guī)模Deezer社交網(wǎng)絡(luò)中，本文提出的SGSC算法明顯優(yōu)于Newman快速算法。

圖1 不同的網(wǎng)絡(luò)中社區(qū)劃分的模塊度Fig.1 Modularity of the divided communities in different networks

圖2 不同的網(wǎng)絡(luò)中各算法運(yùn)行的時(shí)間Fig.2 Comparisons of complexity

4 結(jié)束語

本文中提出了一種基于SimRank的全局矩陣平滑收斂的社區(qū)發(fā)現(xiàn)算法，利用SimRank的方法計(jì)算節(jié)點(diǎn)與節(jié)點(diǎn)之間的相似性而非傳統(tǒng)計(jì)算節(jié)點(diǎn)相似度的方法，SGSC方法基于矩陣的迭代收斂聚類出所有的初始社區(qū)，最初的社區(qū)劃分利用核心節(jié)點(diǎn)代表全局結(jié)構(gòu)信息。作為最初的社區(qū)，僅僅通過合并核心節(jié)點(diǎn)周圍的節(jié)點(diǎn)，直接使用局部信息以迅速形成小型社區(qū)，無需重新計(jì)算節(jié)點(diǎn)屬于哪個(gè)社區(qū)，從而大大改善算法的效率。今后將重點(diǎn)研究如何確定SimRank的迭代停止條件并結(jié)合真實(shí)的社交網(wǎng)絡(luò)的特征信息以更好地進(jìn)行社區(qū)聚類。