資源描述：
《基于自適應(yīng)仿射傳播聚類社團發(fā)現(xiàn)求解》由會員上傳分享，免費在線閱讀，更多相關(guān)內(nèi)容在工程資料-天天文庫。
1、基于自適應(yīng)仿射傳播聚類社團發(fā)現(xiàn)求解摘要：本文對復(fù)雜網(wǎng)絡(luò)的社團發(fā)現(xiàn)問題進行研究，分析社團發(fā)現(xiàn)問題和聚類問題的相似性，使用自適應(yīng)仿射傳播聚類算法對社團發(fā)現(xiàn)問題進行求解，給出了算法的實例，針對算法中的不同參數(shù)進行測試比較。結(jié)果表明算法具有較好的準確率和運行效率。關(guān)鍵詞：復(fù)雜網(wǎng)絡(luò)；社團發(fā)現(xiàn)；自適應(yīng)仿射傳播一、引言復(fù)雜網(wǎng)絡(luò)是復(fù)雜系統(tǒng)研究的重要領(lǐng)域，取得了大量的研究成果［1-3］o網(wǎng)絡(luò)結(jié)構(gòu)的社團劃分是復(fù)雜網(wǎng)絡(luò)新的研究方向。復(fù)雜網(wǎng)絡(luò)的社團可以定義為網(wǎng)絡(luò)中的一組節(jié)點，組內(nèi)節(jié)點之間具有較高的相似度，組間節(jié)點具有較低的相似度［4］
2、。社團結(jié)構(gòu)通常對應(yīng)于網(wǎng)絡(luò)中的某一功能單元，例如，萬維網(wǎng)中不同社團代表不同主題的網(wǎng)頁［5］；引文網(wǎng)中不同社團代表了不同的研究領(lǐng)域［6］。根據(jù)社團發(fā)現(xiàn)過程中社團形成方式的不同，社團發(fā)現(xiàn)大體可以分成四類過程：凝聚過程、分裂過程、搜索過程和其他過程。凝聚過程將網(wǎng)絡(luò)中每一個定點設(shè)為一個社團，使用設(shè)定的度量標準，將相似度高的或相近的社團合并，重新計算，直到所有定點聚集成一個社團。分裂過程與凝聚過程相反，從所有定點組成的大社團出發(fā)，進行分裂，直到每個節(jié)點組成一個社團。搜索過程是一個逐步優(yōu)化目標的過程。其他方法主要有譜分析等。
3、本文使用自適應(yīng)仿射傳播聚類[7]方法求解社團發(fā)現(xiàn)問題，相比傳統(tǒng)聚類方法，該方法不需要事先指定分類的個數(shù)且具有較快的運行速度。二、基本定義社團：目前為止，關(guān)于社團還沒有統(tǒng)一的定義。比較常用的有基于鏈接頻度的定義，網(wǎng)絡(luò)分組后，即組內(nèi)的鏈接稠密，組間的鏈接稀疏。還有基于連通性的定義，即將全連通子圖定義為派系，所以也被稱為基于派系的定義，派系的定義也可以通過放寬路徑長度進行弱化。上述兩個定義都是定性的定義，實踐中還有定量的定義，比如使用Girvan和Newman定義的模塊化函數(shù)來定義社團。聚類算法：聚類是一個將數(shù)據(jù)集分
4、類的過程，是數(shù)據(jù)挖掘領(lǐng)域中使用的技術(shù)，用于發(fā)現(xiàn)大規(guī)模數(shù)據(jù)中隱藏的模式和規(guī)律。聚類方法融合了多種技術(shù)，其應(yīng)用領(lǐng)域也已超出了數(shù)據(jù)挖掘的范圍。聚類分析所解決的問題與社團發(fā)現(xiàn)問題具有相似的特性，所以社團結(jié)構(gòu)也可以被稱為復(fù)雜網(wǎng)絡(luò)中的聚類。聚類分析的理論和技術(shù)可以應(yīng)用到復(fù)雜網(wǎng)絡(luò)社團發(fā)現(xiàn)求解的問題中。相似度：相似度是兩個節(jié)點屬性相似的程度。對于網(wǎng)絡(luò)中的節(jié)點a和b,當以b為聚類中心時，a和b的相似度記為S(a,b)o相似度可以是對稱的，即S(a,b)=S(b,a),也可以是不對稱的，即二者不等。一般可以使用歐式距離來定義相似度
5、，比如。將相似度定義為負值，是因為較大的負值說明二者的距離較小，方便程序的計算。參考度：節(jié)點成為聚類中心的可能性定義為參考度。參考度越大，節(jié)點作為聚類中心的可能性也越大。節(jié)點a的參考度記為P(a)或S(a,a)0參考度的值會影響聚類的數(shù)量，也就是所劃分出的社團的數(shù)量。如果初始時對中心點沒有任何限制，可以取所有點的參考度相等，如果取輸入適應(yīng)度的中值，則社團數(shù)量中等。吸引度：描述使用節(jié)點k作為節(jié)點i的聚類中心的適合程度，記為R(i,k),為從節(jié)點k發(fā)送到節(jié)點i的消息。歸屬度：描述節(jié)點i選擇節(jié)點k作為聚類中心的適合程
6、度，記為A(i,k),為從節(jié)點i向節(jié)點k發(fā)送的消息。阻尼系數(shù)：用來控制迭代過程中的收斂，阻尼系數(shù)取不同值時，迭代過程的收斂和振蕩過程也不同。三、聚類方法自適應(yīng)仿射傳播聚類根據(jù)輸入數(shù)據(jù)點之間的相似度進行聚類。設(shè)輸入N個數(shù)據(jù)點，可以將輸入數(shù)據(jù)點的相似度表示成NXN的矩陣S,S中的值S(i,j)為上面定義的相似度。與傳統(tǒng)的聚類方法不同，算法不需要指定生成聚類的數(shù)量，而是使用所有輸入點作為起始聚類，進行求解。相似度矩陣對角線上的值S(k,k)為前面定義的適應(yīng)度。本文使用節(jié)點輸入相似度的中值作為適應(yīng)度的初始值。算法運行過
7、程中傳遞兩種類型的消息，吸引度和歸屬度。吸引度和歸屬度也以矩陣的形式表示。吸引度大說明節(jié)點作為聚類中心的可能性大，歸屬度大說明節(jié)點選擇對應(yīng)節(jié)點為聚類中心的可能性大。自適應(yīng)仿射傳播聚類算法迭代計算所有點的吸引度和歸屬度。直到產(chǎn)生若干個聚類中心，且所有數(shù)據(jù)點都找到聚類中心為止。吸引度和歸屬度如下公式計算：R(i,k)二S(i,k)-max{A(i,j)+S(i,j)}jHkR(k,k)=P(k)-max{A(k,j)+S(k,j)}jHkA(i,k)=min{0,R(k,k)+jHi且jHk根據(jù)上面公式，當參考度較
8、大使得R(k,k)較大時，計算所得的歸屬度A(i,k)的值相應(yīng)較大，增加了k作為聚類中心的可能性；具有較大參考度值的節(jié)點越多，聚類的數(shù)量也越多。所以，初始參考度值的大小最終聚類的數(shù)量有較大的影響。自適應(yīng)仿射傳播聚類算法計算過程可以描述如下：1?初始化：計算相似度矩陣S,計算參考度Po設(shè)置最大迭代次數(shù)。轉(zhuǎn)步驟2。2.計算歸屬度矩陣R值和吸引度A的值，迭代次數(shù)加1,如果達到最大迭代次數(shù)，轉(zhuǎn)
