復雜網(wǎng)絡中社區(qū)發(fā)現(xiàn)關鍵技術研究.pdf

1、現(xiàn)實世界中的很多復雜系統(tǒng)都可以抽象為一個復雜網(wǎng)絡,如社會系統(tǒng)中的人際關系網(wǎng),生態(tài)系統(tǒng)中的蛋白質(zhì)交互網(wǎng),科技系統(tǒng)中的萬維網(wǎng)等。在這些復雜網(wǎng)絡中,節(jié)點表示個體,節(jié)點之間的邊表示個體之間的聯(lián)系。大量的研究表明,復雜網(wǎng)絡中普遍存在著社區(qū)結構,即社區(qū)內(nèi)部的節(jié)點具有更加密切的聯(lián)系。社區(qū)結構往往代表了具有相同屬性或者扮演相似角色的節(jié)點集合。社區(qū)發(fā)現(xiàn)能夠探究網(wǎng)絡的結構與功能,發(fā)現(xiàn)其中隱藏的規(guī)律及預測其行為,是進行網(wǎng)絡分析的基礎和關鍵,因此具有重要的理論

2、意義和廣泛的應用前景。目前,社區(qū)發(fā)現(xiàn)已成為計算機等眾多領域最具挑戰(zhàn)性的基礎研究課題之一。
　　本課題主要圍繞復雜網(wǎng)絡中的非重疊社區(qū)發(fā)現(xiàn)、重疊社區(qū)發(fā)現(xiàn)、動態(tài)網(wǎng)絡社區(qū)發(fā)現(xiàn)以及局部社區(qū)發(fā)現(xiàn)等四個方面存在的問題進行研究,主要包括以下幾個方面的內(nèi)容:
　　1.大多數(shù)現(xiàn)有的社區(qū)發(fā)現(xiàn)算法都是非監(jiān)督的學習方式,不能充分利用少量的先驗知識以提高社區(qū)發(fā)現(xiàn)的質(zhì)量,為此,提出一種基于快速近鄰傳播的半監(jiān)督網(wǎng)絡社區(qū)發(fā)現(xiàn)算法(SCAN-FAP),該算法主

3、要包括基于約束的SimRank相似度和基于快速近鄰傳播的社區(qū)發(fā)現(xiàn)兩部分,前者用于有效利用已知的先驗知識,后者在前者的基礎上充分利用所得到的相似度并提高社區(qū)發(fā)現(xiàn)的性能。實驗結果表明,SCAN-FAP能夠有效利用少量的先驗知識,顯著提高社區(qū)發(fā)現(xiàn)的質(zhì)量,并且算法的性能優(yōu)于其它幾種代表性的半監(jiān)督聚類算法。
　　2.為了能夠更加有效地探測復雜網(wǎng)絡中的重疊社區(qū)結構,提出一種基于鏈接密度聚類的重疊社區(qū)發(fā)現(xiàn)算法(DBLINK),該算法首先采用基于

4、密度的聚類算法將網(wǎng)絡中的邊集劃分為若干個互不相連的鏈接社區(qū),然后將不屬于任何鏈接社區(qū)的邊孤立出來,只將有效的鏈接社區(qū)轉化為具有重疊性的節(jié)點社區(qū),從而避免了網(wǎng)絡社區(qū)過度重疊的現(xiàn)象發(fā)生,并提高了重疊社區(qū)發(fā)現(xiàn)的質(zhì)量。在模擬網(wǎng)絡和真實網(wǎng)絡上進行了測試,并與幾種代表性的重疊社區(qū)發(fā)現(xiàn)算法進行比較,實驗結果表明了DBLINK的高效性與有效性。
　　3.針對動態(tài)復雜網(wǎng)絡的社區(qū)發(fā)現(xiàn)問題,在基于鏈接密度聚類的重疊社區(qū)發(fā)現(xiàn)算法基礎之上,提出一種基于增量

5、鏈接密度聚類的動態(tài)網(wǎng)絡社區(qū)發(fā)現(xiàn)算法(iDBLINK),該算法通過相鄰時刻邊與邊之間相似度的變化,對當前時刻的局部鏈接社區(qū)進行一定的更新,主要包括鏈接社區(qū)的創(chuàng)建、增長、合并、刪除、收縮以及分裂等。該算法雖然只關注非重疊的鏈接社區(qū)的更新,卻能夠自然地反映出節(jié)點的重疊社區(qū)結構。在模擬網(wǎng)絡和真實網(wǎng)絡上的實驗結果表明,相對于其它幾種代表性的增量社區(qū)發(fā)現(xiàn)算法,iDBLINK能夠更加有效地適應于動態(tài)網(wǎng)絡的社區(qū)發(fā)現(xiàn)。
　　4.現(xiàn)有局部社區(qū)發(fā)現(xiàn)算法

6、容易受到單一源節(jié)點的影響,且不能識別重疊節(jié)點所在的多個局部社區(qū)。針對該問題,提出一種基于節(jié)點極大團擴展的局部社區(qū)發(fā)現(xiàn)算法(LCD-MC),該算法首先找出包含指定節(jié)點的所有極大團的集合,然后在此基礎上將各個未擴展的極大團作為初始局部社區(qū),分別通過貪婪優(yōu)化的算法不斷地進行社區(qū)擴展。LCD-MC不僅能夠得到比較穩(wěn)定和準確的結果,而且當指定節(jié)點為重疊節(jié)點時,能夠有效識別多個局部社區(qū)。在模擬網(wǎng)絡和真實網(wǎng)絡上進行了測試,并與具有代表性的局部社區(qū)發(fā)現(xiàn)