基于自適應仿射傳播聚類的社團發現求解

穆寶良　李晉

摘 要：本文對復雜網絡的社團發現問題進行研究，分析社團發現問題和聚類問題的相似性，使用自適應仿射傳播聚類算法對社團發現問題進行求解，給出了算法的實例，針對算法中的不同參數進行測試比較。結果表明算法具有較好的準確率和運行效率。

關 鍵 詞：復雜網絡；社團發現；自適應仿射傳播

一、引言

復雜網絡是復雜系統研究的重要領域，取得了大量的研究成果[1-3]。網絡結構的社團劃分是復雜網絡新的研究方向。復雜網絡的社團可以定義為網絡中的一組節點，組內節點之間具有較高的相似度，組間節點具有較低的相似度[4]。社團結構通常對應于網絡中的某一功能單元，例如，萬維網中不同社團代表不同主題的網頁[5]；引文網中不同社團代表了不同的研究領域[6]。

根據社團發現過程中社團形成方式的不同，社團發現大體可以分成四類過程：凝聚過程、分裂過程、搜索過程和其他過程。凝聚過程將網絡中每一個定點設為一個社團，使用設定的度量標準，將相似度高的或相近的社團合并，重新計算，直到所有定點聚集成一個社團。分裂過程與凝聚過程相反，從所有定點組成的大社團出發，進行分裂，直到每個節點組成一個社團。搜索過程是一個逐步優化目標的過程。其他方法主要有譜分析等。本文使用自適應仿射傳播聚類[7]方法求解社團發現問題，相比傳統聚類方法，該方法不需要事先指定分類的個數且具有較快的運行速度。

二、基本定義

社團：目前為止，關于社團還沒有統一的定義。比較常用的有基于鏈接頻度的定義，網絡分組后，即組內的鏈接稠密，組間的鏈接稀疏。還有基于連通性的定義，即將全連通子圖定義為派系，所以也被稱為基于派系的定義，派系的定義也可以通過放寬路徑長度進行弱化。上述兩個定義都是定性的定義，實踐中還有定量的定義，比如使用Girvan和Newman定義的模塊化函數來定義社團。

聚類算法：聚類是一個將數據集分類的過程，是數據挖掘領域中使用的技術，用于發現大規模數據中隱藏的模式和規律。聚類方法融合了多種技術，其應用領域也已超出了數據挖掘的范圍。聚類分析所解決的問題與社團發現問題具有相似的特性，所以社團結構也可以被稱為復雜網絡中的聚類。聚類分析的理論和技術可以應用到復雜網絡社團發現求解的問題中。

相似度：相似度是兩個節點屬性相似的程度。對于網絡中的節點a和b，當以b為聚類中心時，a和b的相似度記為S（a，b）。相似度可以是對稱的，即S（a，b）=S（b，a），也可以是不對稱的，即二者不等。一般可以使用歐式距離來定義相似度，比如。將相似度定義為負值，是因為較大的負值說明二者的距離較小，方便程序的計算。

參考度：節點成為聚類中心的可能性定義為參考度。參考度越大，節點作為聚類中心的可能性也越大。節點a的參考度記為P（a）或S（a，a）。參考度的值會影響聚類的數量，也就是所劃分出的社團的數量。如果初始時對中心點沒有任何限制，可以取所有點的參考度相等，如果取輸入適應度的中值，則社團數量中等。

吸引度：描述使用節點k作為節點i的聚類中心的適合程度，記為R（i，k），為從節點k發送到節點i的消息。

歸屬度：描述節點i選擇節點k作為聚類中心的適合程度，記為A（i，k），為從節點i向節點k發送的消息。

阻尼系數：用來控制迭代過程中的收斂，阻尼系數取不同值時，迭代過程的收斂和振蕩過程也不同。

三、聚類方法

自適應仿射傳播聚類根據輸入數據點之間的相似度進行聚類。設輸入N個數據點，可以將輸入數據點的相似度表示成N×N的矩陣S，S中的值S（i，j）為上面定義的相似度。與傳統的聚類方法不同，算法不需要指定生成聚類的數量，而是使用所有輸入點作為起始聚類，進行求解。相似度矩陣對角線上的值S（k，k）為前面定義的適應度。本文使用節點輸入相似度的中值作為適應度的初始值。算法運行過程中傳遞兩種類型的消息，吸引度和歸屬度。吸引度和歸屬度也以矩陣的形式表示。吸引度大說明節點作為聚類中心的可能性大，歸屬度大說明節點選擇對應節點為聚類中心的可能性大。自適應仿射傳播聚類算法迭代計算所有點的吸引度和歸屬度。直到產生若干個聚類中心，且所有數據點都找到聚類中心為止。

吸引度和歸屬度如下公式計算：

R（i，k）=S（i，k）-max{A（i，j）+S（i，j）} j≠k

R（k，k）=P（k）-max{A（k，j）+S（k，j）} j≠k

A（i，k）=min{0，R（k，k）+ j≠i且j≠k

根據上面公式，當參考度較大使得R（k， k）較大時， 計算所得的歸屬度A（i， k） 的值相應較大， 增加了k作為聚類中心的可能性； 具有較大參考度值的節點越多，聚類的數量也越多。所以，初始參考度值的大小最終聚類的數量有較大的影響。

自適應仿射傳播聚類算法計算過程可以描述如下：

1.初始化：計算相似度矩陣S，計算參考度P。設置最大迭代次數。轉步驟2。

2.計算歸屬度矩陣R值和吸引度A的值，迭代次數加1，如果達到最大迭代次數，轉步驟3，否則繼續步驟2。

3.使用R（k，k）+A（k，k）的值來判斷是否為聚類中心。如果所計算的值大于0，則K點為聚類中心。

四、社團發現求解算法

使用上面的算法，可以求解社團發現問題，求解過程中我們使用阻尼系數lam更新吸引度和歸屬度，公式如下：

Ri=（1-lam）* Ri+lam *Ri-1

Ai=（1-lam） * Ai+lam * Ai-1

算法輸入：

節點相似度s（i，k）

節點的參考度p（k）：

算法輸出：

社團的個數M

算法偽代碼：

N←size（S，1）；A←zeros（N，N）；R←zeros（N，N）；//初始化信息

S=S+1e-12*randn（N，N）*（max（S（：））-min（S（：）））；

lam←0.5；

for iter←l：100，

//計算責任度

Rold←R；

AS←A+S；[Y，I]←max（AS，[]，2）；

for i←l：N，AS（i，I（i））←-realmax；end；

[Y2，I2]←max（AS，[]，2）；

R←S-repmat（Y，[l，N]）；

for i←l：N，R（i，I（i））←S（i，I（i））-Y2（i）；end；

R←（1-1am）*R+lam*Rold；//責任度

//計算合適度

Aold←A；

Rp←max（R，O）；for k←l：N，Rp（k，k）←R（k，k）；end；

A←repmat（sum（Rp，1），[N，1]）-Rp；

dA←diag（A）；A←min（A，O）；for k←l：N，A（k，k）←dA（k）；end；

A←（1-1am）*A+lam*Aold；//合適度

end；

E←R十A；

I←find（diag（E）>O）；M←length（I）；//聚類中心

[tmp c]←max（S（：，I），[]，2）；c（I）←1：M；idx←I（c）；

我們使用Java語言實現了上述算法，使用二維空間中20個隨機生成的數據點，將P值設置為S矩陣的中值，最大迭代次數設置成1000，以社團發現求解算法進行計算，最終分類結果如圖1所示。

算法運行過程中，我們針對不同的阻尼系數lam進行了實驗，發現當lam值較小時會得到較快的收斂速度，但是具有比較大的振蕩；當lam值較大時具有較小的振蕩，但是具有較慢的收斂速度。

五、結語

本文使用自適應仿射傳播聚類算法進行社團發現問題的求解，給出了算法的描述和完整的實現。自適應仿射傳播聚類方法具有較快的計算速度，對噪聲不敏感，不需要事先設定社團的數量，能夠較好的解決社團發現問題。實際的求解過程中，相似度的選擇，阻尼系數的設定，都是需要解決的問題，社團求解過程中的重疊問題也是需要處理的重要問題，這些都是下一步的研究方向。

參考文獻

[1] NewmanM E J.The structure and function of comp lex networks[J]. SIAM Review.2003，45（2）：167-256.

[2] 吳金閃，狄增如.從統計物理看復雜網絡研究[J].物理學進展.2004，24 （1）：18-45.

[3] 周濤，等.復雜網絡研究概述[J].物理.2005，34 （1）：31-36.

[4] GirvanM，NewmanM E J.Community structure in social and biological networks.Proc Natl Acad Sci USA[J].2002，99：7821-7826.

[5] Adamic A L，Adar E.Friends and neighbors on the web[J].SocialNetworks.2003，25（3）：211-230.

[6] Redner S.How popular is your paper？ An emp irical study of the citation distribution[J].Eur Phys J B.1998，4：131-134.

[7] Frey B J，Dueck D. Clustering by passing messages between data points[J].Science.2007，315（5814）：972-976.