一種基于節(jié)點相似性的局部社團劃分算法

王偉欣　劉發(fā)升

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

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

中圖分類號：TP301.6

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

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

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

1 相關(guān)概念

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

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

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

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

1.2 模塊度函數(shù)

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

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

2 算法實現(xiàn)

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

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

算法步驟如下：

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

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

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

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

步驟5 根據(jù)式（2.1）計算模塊度增量 。由于在該步驟時，每個節(jié)點對應的是一個社團，此時模塊度的計算公式可表示如下：

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

3 實驗結(jié)果及分析

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

3.1 Zachary網(wǎng)絡

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

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

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

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

3.2 Dolphins網(wǎng)絡

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

4 結(jié)束語

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

參考文獻：

[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].計算機工程，2011，37（7）：12-23.

[9]史偉，趙政，薛桂香.基于節(jié)點類型的復雜網(wǎng)絡模塊探測算法[J].計算機應用，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.