基于自適應(yīng)仿射傳播聚類的社團(tuán)發(fā)現(xiàn)求解

穆寶良　李晉

摘 要：本文對(duì)復(fù)雜網(wǎng)絡(luò)的社團(tuán)發(fā)現(xiàn)問(wèn)題進(jìn)行研究，分析社團(tuán)發(fā)現(xiàn)問(wèn)題和聚類問(wèn)題的相似性，使用自適應(yīng)仿射傳播聚類算法對(duì)社團(tuán)發(fā)現(xiàn)問(wèn)題進(jìn)行求解，給出了算法的實(shí)例，針對(duì)算法中的不同參數(shù)進(jìn)行測(cè)試比較。結(jié)果表明算法具有較好的準(zhǔn)確率和運(yùn)行效率。

關(guān) 鍵 詞：復(fù)雜網(wǎng)絡(luò)；社團(tuán)發(fā)現(xiàn)；自適應(yīng)仿射傳播

一、引言

復(fù)雜網(wǎng)絡(luò)是復(fù)雜系統(tǒng)研究的重要領(lǐng)域，取得了大量的研究成果[1-3]。網(wǎng)絡(luò)結(jié)構(gòu)的社團(tuán)劃分是復(fù)雜網(wǎng)絡(luò)新的研究方向。復(fù)雜網(wǎng)絡(luò)的社團(tuán)可以定義為網(wǎng)絡(luò)中的一組節(jié)點(diǎn)，組內(nèi)節(jié)點(diǎn)之間具有較高的相似度，組間節(jié)點(diǎn)具有較低的相似度[4]。社團(tuán)結(jié)構(gòu)通常對(duì)應(yīng)于網(wǎng)絡(luò)中的某一功能單元，例如，萬(wàn)維網(wǎng)中不同社團(tuán)代表不同主題的網(wǎng)頁(yè)[5]；引文網(wǎng)中不同社團(tuán)代表了不同的研究領(lǐng)域[6]。

根據(jù)社團(tuán)發(fā)現(xiàn)過(guò)程中社團(tuán)形成方式的不同，社團(tuán)發(fā)現(xiàn)大體可以分成四類過(guò)程：凝聚過(guò)程、分裂過(guò)程、搜索過(guò)程和其他過(guò)程。凝聚過(guò)程將網(wǎng)絡(luò)中每一個(gè)定點(diǎn)設(shè)為一個(gè)社團(tuán)，使用設(shè)定的度量標(biāo)準(zhǔn)，將相似度高的或相近的社團(tuán)合并，重新計(jì)算，直到所有定點(diǎn)聚集成一個(gè)社團(tuán)。分裂過(guò)程與凝聚過(guò)程相反，從所有定點(diǎn)組成的大社團(tuán)出發(fā)，進(jìn)行分裂，直到每個(gè)節(jié)點(diǎn)組成一個(gè)社團(tuán)。搜索過(guò)程是一個(gè)逐步優(yōu)化目標(biāo)的過(guò)程。其他方法主要有譜分析等。本文使用自適應(yīng)仿射傳播聚類[7]方法求解社團(tuán)發(fā)現(xiàn)問(wèn)題，相比傳統(tǒng)聚類方法，該方法不需要事先指定分類的個(gè)數(shù)且具有較快的運(yùn)行速度。

二、基本定義

社團(tuán)：目前為止，關(guān)于社團(tuán)還沒(méi)有統(tǒng)一的定義。比較常用的有基于鏈接頻度的定義，網(wǎng)絡(luò)分組后，即組內(nèi)的鏈接稠密，組間的鏈接稀疏。還有基于連通性的定義，即將全連通子圖定義為派系，所以也被稱為基于派系的定義，派系的定義也可以通過(guò)放寬路徑長(zhǎng)度進(jìn)行弱化。上述兩個(gè)定義都是定性的定義，實(shí)踐中還有定量的定義，比如使用Girvan和Newman定義的模塊化函數(shù)來(lái)定義社團(tuán)。

聚類算法：聚類是一個(gè)將數(shù)據(jù)集分類的過(guò)程，是數(shù)據(jù)挖掘領(lǐng)域中使用的技術(shù)，用于發(fā)現(xiàn)大規(guī)模數(shù)據(jù)中隱藏的模式和規(guī)律。聚類方法融合了多種技術(shù)，其應(yīng)用領(lǐng)域也已超出了數(shù)據(jù)挖掘的范圍。聚類分析所解決的問(wèn)題與社團(tuán)發(fā)現(xiàn)問(wèn)題具有相似的特性，所以社團(tuán)結(jié)構(gòu)也可以被稱為復(fù)雜網(wǎng)絡(luò)中的聚類。聚類分析的理論和技術(shù)可以應(yīng)用到復(fù)雜網(wǎng)絡(luò)社團(tuán)發(fā)現(xiàn)求解的問(wèn)題中。

相似度：相似度是兩個(gè)節(jié)點(diǎn)屬性相似的程度。對(duì)于網(wǎng)絡(luò)中的節(jié)點(diǎn)a和b，當(dāng)以b為聚類中心時(shí)，a和b的相似度記為S（a，b）。相似度可以是對(duì)稱的，即S（a，b）=S（b，a），也可以是不對(duì)稱的，即二者不等。一般可以使用歐式距離來(lái)定義相似度，比如。將相似度定義為負(fù)值，是因?yàn)檩^大的負(fù)值說(shuō)明二者的距離較小，方便程序的計(jì)算。

參考度：節(jié)點(diǎn)成為聚類中心的可能性定義為參考度。參考度越大，節(jié)點(diǎn)作為聚類中心的可能性也越大。節(jié)點(diǎn)a的參考度記為P（a）或S（a，a）。參考度的值會(huì)影響聚類的數(shù)量，也就是所劃分出的社團(tuán)的數(shù)量。如果初始時(shí)對(duì)中心點(diǎn)沒(méi)有任何限制，可以取所有點(diǎn)的參考度相等，如果取輸入適應(yīng)度的中值，則社團(tuán)數(shù)量中等。

吸引度：描述使用節(jié)點(diǎn)k作為節(jié)點(diǎn)i的聚類中心的適合程度，記為R（i，k），為從節(jié)點(diǎn)k發(fā)送到節(jié)點(diǎn)i的消息。

歸屬度：描述節(jié)點(diǎn)i選擇節(jié)點(diǎn)k作為聚類中心的適合程度，記為A（i，k），為從節(jié)點(diǎn)i向節(jié)點(diǎn)k發(fā)送的消息。

阻尼系數(shù)：用來(lái)控制迭代過(guò)程中的收斂，阻尼系數(shù)取不同值時(shí)，迭代過(guò)程的收斂和振蕩過(guò)程也不同。

三、聚類方法

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

吸引度和歸屬度如下公式計(jì)算：

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

根據(jù)上面公式，當(dāng)參考度較大使得R（k， k）較大時(shí)， 計(jì)算所得的歸屬度A（i， k） 的值相應(yīng)較大， 增加了k作為聚類中心的可能性； 具有較大參考度值的節(jié)點(diǎn)越多，聚類的數(shù)量也越多。所以，初始參考度值的大小最終聚類的數(shù)量有較大的影響。

自適應(yīng)仿射傳播聚類算法計(jì)算過(guò)程可以描述如下：

1.初始化：計(jì)算相似度矩陣S，計(jì)算參考度P。設(shè)置最大迭代次數(shù)。轉(zhuǎn)步驟2。

2.計(jì)算歸屬度矩陣R值和吸引度A的值，迭代次數(shù)加1，如果達(dá)到最大迭代次數(shù)，轉(zhuǎn)步驟3，否則繼續(xù)步驟2。

3.使用R（k，k）+A（k，k）的值來(lái)判斷是否為聚類中心。如果所計(jì)算的值大于0，則K點(diǎn)為聚類中心。

四、社團(tuán)發(fā)現(xiàn)求解算法

使用上面的算法，可以求解社團(tuán)發(fā)現(xiàn)問(wèn)題，求解過(guò)程中我們使用阻尼系數(shù)lam更新吸引度和歸屬度，公式如下：

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

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

算法輸入：

節(jié)點(diǎn)相似度s（i，k）

節(jié)點(diǎn)的參考度p（k）：

算法輸出：

社團(tuán)的個(gè)數(shù)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，

//計(jì)算責(zé)任度

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；//責(zé)任度

//計(jì)算合適度

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語(yǔ)言實(shí)現(xiàn)了上述算法，使用二維空間中20個(gè)隨機(jī)生成的數(shù)據(jù)點(diǎn)，將P值設(shè)置為S矩陣的中值，最大迭代次數(shù)設(shè)置成1000，以社團(tuán)發(fā)現(xiàn)求解算法進(jìn)行計(jì)算，最終分類結(jié)果如圖1所示。

算法運(yùn)行過(guò)程中，我們針對(duì)不同的阻尼系數(shù)lam進(jìn)行了實(shí)驗(yàn)，發(fā)現(xiàn)當(dāng)lam值較小時(shí)會(huì)得到較快的收斂速度，但是具有比較大的振蕩；當(dāng)lam值較大時(shí)具有較小的振蕩，但是具有較慢的收斂速度。

五、結(jié)語(yǔ)

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

參考文獻(xiàn)

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

[2] 吳金閃，狄增如.從統(tǒng)計(jì)物理看復(fù)雜網(wǎng)絡(luò)研究[J].物理學(xué)進(jìn)展.2004，24 （1）：18-45.

[3] 周濤，等.復(fù)雜網(wǎng)絡(luò)研究概述[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.