王偉欣　劉發(fā)升

摘 要：提出一種基于節(jié)點(diǎn)相似性的社團(tuán)挖掘算法，算法首先根據(jù)節(jié)點(diǎn)的相似度值找出最相似鄰居節(jié)點(diǎn)，合并節(jié)點(diǎn)形成若干個(gè)社團(tuán)，然后優(yōu)化模塊度函數(shù)進(jìn)行社團(tuán)的合并，當(dāng)模塊度值最大時(shí)算法終止。最后，通過Zachary網(wǎng)絡(luò)和Dolphin網(wǎng)絡(luò)進(jìn)行實(shí)驗(yàn)仿真，驗(yàn)證了算法的可行性和精準(zhǔn)性。

關(guān)鍵詞：復(fù)雜網(wǎng)絡(luò)；社團(tuán)結(jié)構(gòu)；節(jié)點(diǎn)相似性；模塊度函數(shù)；聚類

中圖分類號(hào)：TP301.6

現(xiàn)實(shí)世界中的諸多復(fù)雜系統(tǒng)可以抽象表示為復(fù)雜網(wǎng)絡(luò)，如社會(huì)關(guān)系網(wǎng)絡(luò)、生物網(wǎng)絡(luò)、因特網(wǎng)等。研究發(fā)現(xiàn)這些網(wǎng)絡(luò)具有共同的特征：網(wǎng)絡(luò)內(nèi)部存在社團(tuán)結(jié)構(gòu)，即網(wǎng)絡(luò)是由若干“社團(tuán)”構(gòu)成，社團(tuán)內(nèi)部的節(jié)點(diǎn)之間連接稠密，社團(tuán)之間的節(jié)點(diǎn)連接相對(duì)稀疏[1]。社團(tuán)結(jié)構(gòu)研究的科研價(jià)值和實(shí)用價(jià)值已經(jīng)吸引了大量不同領(lǐng)域的研究工作者，并且其研究成果成功地應(yīng)用在蛋白質(zhì)功能檢測、web社區(qū)挖掘、搜索引擎、恐怖組織識(shí)別等眾多領(lǐng)域，社團(tuán)結(jié)構(gòu)已經(jīng)成為信息時(shí)代網(wǎng)絡(luò)研究的一個(gè)熱點(diǎn)。

目前，社團(tuán)劃分方法主要分為兩大類：圖分割法和層次聚類法。圖分割法的兩個(gè)代表算法：Kernighan-Lin算法[2]是一種基于貪婪算法的原理通過優(yōu)化增益函數(shù)從而將網(wǎng)絡(luò)劃分成兩個(gè)大小已知社團(tuán)的二分法；譜平分法[3，4]根據(jù)網(wǎng)絡(luò)的Laplace矩陣的第二小特征值對(duì)網(wǎng)絡(luò)進(jìn)行平分。GN算法和FN算法是層次聚類法的兩個(gè)代表算法。其中，GN算法[5]通過引入邊介數(shù)的概念不斷地對(duì)網(wǎng)絡(luò)中的邊進(jìn)行刪除來得到網(wǎng)絡(luò)的層次結(jié)構(gòu)；FN算法[6]通過不斷合并節(jié)點(diǎn)的方式直接優(yōu)化模塊度值來獲得網(wǎng)絡(luò)的社團(tuán)結(jié)構(gòu)劃分。CNM算法[7]通過使用堆和二叉樹這兩個(gè)新的數(shù)據(jù)結(jié)構(gòu)進(jìn)行節(jié)點(diǎn)信息的存儲(chǔ)對(duì)FN算法進(jìn)行改進(jìn)，算法的計(jì)算效率提高，節(jié)省了節(jié)點(diǎn)的存儲(chǔ)空間。文獻(xiàn)[8]在CNM算法的基礎(chǔ)上提出一種基于局部信息進(jìn)行社團(tuán)劃分的算法。文獻(xiàn)[9]根據(jù)節(jié)點(diǎn)類型提出一種社團(tuán)劃分算法。

本文提出一種局部社團(tuán)劃分的新算法。該算法在CNM的基礎(chǔ)上，首先根據(jù)節(jié)點(diǎn)的相似性產(chǎn)生初始社團(tuán)，即根據(jù)節(jié)點(diǎn)的相似度值找出最相似鄰居節(jié)點(diǎn)，合并節(jié)點(diǎn)形成若干個(gè)小社團(tuán)。然后采用CNM算法的思想根據(jù)模塊度增量進(jìn)行小社團(tuán)之間的聚類，模塊度取得最大值時(shí)算法終止。一方面，由于算法在形成初始社團(tuán)的過程中只需要節(jié)點(diǎn)的局部信息，避免了全部節(jié)點(diǎn)和邊信息的計(jì)算，加快了算法的計(jì)算速度；另一方面，社團(tuán)合并時(shí)模塊度增量的計(jì)算次數(shù)遠(yuǎn)遠(yuǎn)小于節(jié)點(diǎn)個(gè)數(shù)，與CNM算法相比，計(jì)算效率有很大的提高。

1 相關(guān)概念

一個(gè)無權(quán)無向的復(fù)雜網(wǎng)絡(luò)可以用簡單圖G=（V，E）表示，其中V是網(wǎng)絡(luò)的節(jié)點(diǎn)集，E是網(wǎng)絡(luò)的邊集。鄰接矩陣 中的元素 表示網(wǎng)絡(luò)中節(jié)點(diǎn)之間的連接關(guān)系，若節(jié)點(diǎn) 和 互相連接，則 ；若節(jié)點(diǎn) 和 互不連接，則 。

1.1 節(jié)點(diǎn)的相似度矩陣

假設(shè)網(wǎng)絡(luò)中的一對(duì)節(jié)點(diǎn) 和 ， 是節(jié)點(diǎn) 的鄰居集合， 是鄰居集合中節(jié)點(diǎn)的數(shù)目，則 是節(jié)點(diǎn) 和 共同的鄰居個(gè)數(shù)。節(jié)點(diǎn)的鄰居節(jié)點(diǎn)越多，表明它作為其他節(jié)點(diǎn)的鄰居節(jié)點(diǎn)的次數(shù)也就越多，為計(jì)算相應(yīng)的節(jié)點(diǎn)之間的相似性貢獻(xiàn)的力量就會(huì)越小。反之，如果一個(gè)節(jié)點(diǎn)僅有很少的幾個(gè)鄰居節(jié)點(diǎn)， 則為相應(yīng)的節(jié)點(diǎn)對(duì)貢獻(xiàn)的相似性的信息量就會(huì)越大。通過以上的分析，文中節(jié)點(diǎn)的相似度計(jì)算公式定義如下：

式中， 是節(jié)點(diǎn) 的度。度值越大的節(jié)點(diǎn)擁有的鄰居節(jié)點(diǎn)數(shù)就會(huì)越多，式（1.1）中的分母正好消除了這種尺度效應(yīng)，此時(shí) 。 表明節(jié)點(diǎn) 和 不相連。 有兩種情況：一種是節(jié)點(diǎn) 和自身的相似度，即 ；另一種是 且 ，即節(jié)點(diǎn) 和 相連且兩個(gè)節(jié)點(diǎn)均只能有一個(gè)鄰居節(jié)點(diǎn)。

1.2 模塊度函數(shù)

模塊度函數(shù)是Newman和Girvan[10]在2004年提出的用來刻畫社團(tuán)結(jié)構(gòu)強(qiáng)弱的參數(shù)，定義如下：

式中， 表示節(jié)點(diǎn) 所屬的社團(tuán)； 是節(jié)點(diǎn) 的度值； 是網(wǎng)絡(luò)相應(yīng)的鄰接矩陣的元素，節(jié)點(diǎn) ， 相連時(shí) ，節(jié)點(diǎn) ， 不相連時(shí) ；節(jié)點(diǎn) ， 在相同的社團(tuán)時(shí) ，節(jié)點(diǎn) ， 在不同的社團(tuán)時(shí) ； 是網(wǎng)絡(luò)中邊的數(shù)目總和； 指隨機(jī)網(wǎng)絡(luò)中節(jié)點(diǎn) ， 之間可能的邊數(shù)?，F(xiàn)實(shí)網(wǎng)絡(luò)的模塊度函數(shù)的值一般在0.3 ～0.7 之間。

2 算法實(shí)現(xiàn)

在復(fù)雜網(wǎng)絡(luò)中，如果在兩個(gè)節(jié)點(diǎn)的相連過程中，對(duì)某個(gè)節(jié)點(diǎn)進(jìn)行相連的次數(shù)越多，說明這兩個(gè)節(jié)點(diǎn)擁有共同的鄰居節(jié)點(diǎn)數(shù)就較多，則認(rèn)為這兩個(gè)節(jié)點(diǎn)是相似的。兩個(gè)節(jié)點(diǎn)的相似度是由他們的鄰居節(jié)點(diǎn)決定的，而與圖中其他節(jié)點(diǎn)無關(guān)。如果兩個(gè)節(jié)點(diǎn)相似度足夠大，它們應(yīng)該被放到一起，這是基于相似網(wǎng)絡(luò)的基本概念。

本文算法的基本思想：首先依據(jù)相似性函數(shù)計(jì)算節(jié)點(diǎn)之間的相似度，找出網(wǎng)絡(luò)中每個(gè)節(jié)點(diǎn)的最近鄰居節(jié)點(diǎn)，這里指在該節(jié)點(diǎn)的鄰居節(jié)點(diǎn)中與該節(jié)點(diǎn)的相似度值最大的節(jié)點(diǎn)。然后把網(wǎng)絡(luò)中的每個(gè)節(jié)點(diǎn)與其最近鄰居節(jié)點(diǎn)一一合并，組成若干個(gè)局部社團(tuán)。在節(jié)點(diǎn)合并的過程中應(yīng)注意節(jié)點(diǎn)的歸屬，這里選取合并的節(jié)點(diǎn)中把含有最優(yōu)相似性節(jié)點(diǎn)個(gè)數(shù)最多的節(jié)點(diǎn)作為社團(tuán)的核心節(jié)點(diǎn)。節(jié)點(diǎn)合并之后形成若干個(gè)小社團(tuán)，此時(shí)小社團(tuán)形成了網(wǎng)絡(luò)的初始社團(tuán)。然后采用CNM算法的思想，把一個(gè)小社團(tuán)全體看作一個(gè)節(jié)點(diǎn)，通過社團(tuán)的合并進(jìn)行模塊度函數(shù)的優(yōu)化，其中小社團(tuán)是沿著模塊度增量 升高的方向進(jìn)行社團(tuán)的整合。當(dāng)模塊度 的值最大時(shí)，終止算法。此時(shí)模塊度 對(duì)應(yīng)的劃分即是待求解網(wǎng)絡(luò)的最佳社團(tuán)劃分。

算法步驟如下：

步驟1 輸入網(wǎng)絡(luò) ，找出網(wǎng)絡(luò)中每個(gè)節(jié)點(diǎn)的鄰居節(jié)點(diǎn)，根據(jù)相似性公式（1.1）計(jì)算每個(gè)節(jié)點(diǎn)與其鄰居節(jié)點(diǎn)的相似度。

步驟2 從相似度矩陣中找出每個(gè)節(jié)點(diǎn)的最相似節(jié)點(diǎn)。節(jié)點(diǎn) 的最相似節(jié)點(diǎn)是指在節(jié)點(diǎn) 鄰居節(jié)點(diǎn)中與該節(jié)點(diǎn)間的最大相似度值的節(jié)點(diǎn)。

步驟3 把具有相同的最相似節(jié)點(diǎn)的節(jié)點(diǎn)進(jìn)行合并，并選取作為最相似節(jié)點(diǎn)次數(shù)最多的節(jié)點(diǎn)作為社團(tuán)核心節(jié)點(diǎn)，并用核心節(jié)點(diǎn)表示該社團(tuán)。

步驟4 重新構(gòu)建網(wǎng)絡(luò)。把每個(gè)初始社團(tuán)看作是新的節(jié)點(diǎn)，對(duì)社團(tuán)中的節(jié)點(diǎn)進(jìn)行權(quán)值的合并，并更新鄰接矩陣。

步驟5 根據(jù)式（2.1）計(jì)算模塊度增量 。由于在該步驟時(shí)，每個(gè)節(jié)點(diǎn)對(duì)應(yīng)的是一個(gè)社團(tuán)，此時(shí)模塊度的計(jì)算公式可表示如下：

步驟6 重復(fù)步驟5，直到模塊度 不在增加為止，此時(shí)對(duì)應(yīng)的社團(tuán)結(jié)構(gòu)就是待劃分網(wǎng)絡(luò)的最優(yōu)社團(tuán)結(jié)構(gòu)。

3 實(shí)驗(yàn)結(jié)果及分析

為了測試本論文提出算法的可行性和準(zhǔn)確性，針對(duì)兩個(gè)經(jīng)典的現(xiàn)實(shí)網(wǎng)絡(luò)Zachary網(wǎng)絡(luò)和Dolphins網(wǎng)絡(luò)進(jìn)行實(shí)驗(yàn)仿真。本文算法采用Matlab語言進(jìn)行編譯，實(shí)驗(yàn)結(jié)果證明該算法是可行的，并且準(zhǔn)確性高，能夠較好地完成網(wǎng)絡(luò)社團(tuán)的劃分。

3.1 Zachary網(wǎng)絡(luò)

Zachary網(wǎng)絡(luò)是社會(huì)學(xué)家Zachary在1970至1972年間對(duì)其觀察和研究的空手道俱樂部中成員的社會(huì)關(guān)系構(gòu)建的一個(gè)社會(huì)網(wǎng)絡(luò)，如圖3.1所示。網(wǎng)絡(luò)含有34個(gè)節(jié)點(diǎn)和78條邊，它們分別代表俱樂部成員和成員之間的社會(huì)關(guān)系。在觀察期間，俱樂部主管和校長對(duì)是否需要提高收費(fèi)標(biāo)準(zhǔn)的問題意見不一致，俱樂部分成了兩個(gè)小俱樂部，主管和校長分別是這兩個(gè)小俱樂部的核心人物。在圖3.1中，節(jié)點(diǎn)1表示俱樂部主管，節(jié)點(diǎn)34表示校長。Zachary網(wǎng)絡(luò)是檢驗(yàn)社團(tuán)挖掘算法的三大基準(zhǔn)網(wǎng)絡(luò)之一，用來測試算法僅根據(jù)觀察到的網(wǎng)絡(luò)結(jié)構(gòu)能否對(duì)網(wǎng)絡(luò)做出準(zhǔn)確的劃分。

使用本文算法對(duì)Zachary網(wǎng)絡(luò)進(jìn)行分析，根據(jù)節(jié)點(diǎn)相似度進(jìn)行節(jié)點(diǎn)聚類得到的初始社團(tuán)如表3.1所示。從表中可以看出，經(jīng)過節(jié)點(diǎn)聚類，網(wǎng)絡(luò)中的節(jié)點(diǎn)被劃分為8個(gè)小社團(tuán)。

與CNM算法相比，本文算法由于先對(duì)節(jié)點(diǎn)進(jìn)行了聚類，算法的迭代次數(shù)肯定會(huì)小于網(wǎng)絡(luò)的節(jié)點(diǎn)數(shù)，考慮節(jié)點(diǎn)聚類時(shí)最糟糕的情況，即對(duì)于含有 節(jié)點(diǎn)的網(wǎng)絡(luò)，網(wǎng)絡(luò)中的每個(gè)節(jié)點(diǎn)只能夠和一個(gè)節(jié)點(diǎn)相互成為最相似節(jié)點(diǎn)，則此時(shí)算法的迭代次數(shù)為 次，而CNM算法最多需要比網(wǎng)絡(luò)的節(jié)點(diǎn)總數(shù)減少1的次數(shù)才能夠完成網(wǎng)絡(luò)社團(tuán)的挖掘，此時(shí)迭代次數(shù)為 次。因此，該算法在時(shí)間上是由于CNM算法的。該算法Zachary網(wǎng)絡(luò)劃分結(jié)果如圖4.2所示，可以看出，該算法把Zachary網(wǎng)絡(luò)分成2個(gè)社團(tuán)，與現(xiàn)實(shí)中的

結(jié)果相同，具有很高的準(zhǔn)確性，此時(shí)網(wǎng)絡(luò)的模塊度 的值為0.381。

3.2 Dolphins網(wǎng)絡(luò)

海豚關(guān)系網(wǎng)也是用于檢驗(yàn)網(wǎng)絡(luò)社團(tuán)挖掘算法的一個(gè)常用的基準(zhǔn)網(wǎng)絡(luò)。Lusseau等人花費(fèi)多年時(shí)間觀察生活在新西蘭的一個(gè)海豚群體，海豚群體中包含兩個(gè)子群，其中較大的子群中包含42只海豚，而較小的子群中只有20只海豚。通過觀察研究得出如圖5.4所示的Dolphins網(wǎng)絡(luò)圖，網(wǎng)絡(luò)中的每只海豚對(duì)應(yīng)圖中的一個(gè)節(jié)點(diǎn)，如果兩個(gè)節(jié)點(diǎn)有邊相連接，則表明節(jié)點(diǎn)對(duì)應(yīng)的兩只海豚之間有互動(dòng)關(guān)系。Dolphins網(wǎng)絡(luò)中共有62個(gè)節(jié)點(diǎn)、159條邊。

4 結(jié)束語

本文提出一種基于節(jié)點(diǎn)相似性的局部劃分的新算法，該算法是結(jié)合節(jié)點(diǎn)的局部信息和全局模塊聚類的思想，在CNM算法的基礎(chǔ)上改進(jìn)的一種算法。算法充分利用了節(jié)點(diǎn)之間的關(guān)系——相似度，也采用了模塊度函數(shù)作為社團(tuán)凝聚時(shí)的判斷標(biāo)準(zhǔn)，可以說既考慮了網(wǎng)絡(luò)的局部結(jié)構(gòu)，又考慮了網(wǎng)絡(luò)的整體結(jié)構(gòu)。從實(shí)驗(yàn)仿真分析，算法能夠很好地完成網(wǎng)絡(luò)的劃分，具有較高的準(zhǔn)確性和計(jì)算效率。

參考文獻(xiàn)：

[1]Newman M E J. Detecting community structure in networks[J].The European Physical Journal B，2004，38（2）：321-330.

[2]Kernighan B W，Lin S.An efficient heuristic procedure for partitioning graphs[J].Bell System Technical Journal，1970，49（2）：291-307.

[3]Fiedler M.Algebraic connectivity of graphs[J]. Czechoslovak Mathematical Journal，1973，23（2）：298-305.

[4]Pothen A，Simon H，Liou K P.Partitioning sparse matrices with eigenvectors of graphs[J].SIAM J.Matrix Anal.Appl，1990，11：430.

[5]Girvan M，Newman M E J.Community structure in social and biological networks[J].Proc of the National Academy of Science，2002，99（12）：7821-7826.

[6]Newman M E J.Fast algorithm for detecting community structure in networks[J].Physical Review E，2004，69（6）：66-133.

[7]Clauset A，Newman M E J，Moore C.Finding community structure in very large networks[J].Physical Review E.2004，70：06611.

[8]任永功，孫宇奇，呂朕.一種基于局部信息的社區(qū)發(fā)現(xiàn)方法[J].計(jì)算機(jī)工程，2011，37（7）：12-23.

[9]史偉，趙政，薛桂香.基于節(jié)點(diǎn)類型的復(fù)雜網(wǎng)絡(luò)模塊探測算法[J].計(jì)算機(jī)應(yīng)用，2008，28（10）：2590-2593.

[10]Newman M E J，Girvan M.Finding and evaluating community structure in networks[J].Physical Review E，2004，69：26-113.