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

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

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

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

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

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

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