復(fù)雜網(wǎng)絡(luò)社團(tuán)檢測(cè)算法及其應(yīng)用研究.pdf

1、現(xiàn)實(shí)世界中大量復(fù)雜系統(tǒng)可以抽象為復(fù)雜網(wǎng)絡(luò)模型,社團(tuán)結(jié)構(gòu)是復(fù)雜網(wǎng)絡(luò)的關(guān)鍵結(jié)構(gòu)特征,網(wǎng)絡(luò)的整體功能是網(wǎng)絡(luò)中各社團(tuán)相互作用的結(jié)果。因此社團(tuán)結(jié)構(gòu)檢測(cè)是復(fù)雜網(wǎng)絡(luò)研究中的重要內(nèi)容。
　　本文研究復(fù)雜網(wǎng)絡(luò)社團(tuán)檢測(cè)算法及其在生物領(lǐng)域和社會(huì)領(lǐng)域的應(yīng)用,主要包括以下幾點(diǎn):
　　1.在很多真實(shí)網(wǎng)絡(luò)中,由于一個(gè)頂點(diǎn)需要行使不同的功能,該頂點(diǎn)可能同時(shí)屬于多個(gè)社團(tuán),這導(dǎo)致社團(tuán)間存在一定程度的重疊,為了檢測(cè)重疊社團(tuán)結(jié)構(gòu),對(duì)近鄰傳播算法(AP)進(jìn)行改進(jìn),提

2、出一個(gè)重疊社團(tuán)檢測(cè)算法OAP。AP算法檢測(cè)社團(tuán)結(jié)構(gòu)時(shí),先識(shí)別出所有社團(tuán)的中心點(diǎn),再為每個(gè)頂點(diǎn)唯一指派一個(gè)中心點(diǎn),擁有相同中心點(diǎn)的頂點(diǎn)集合就構(gòu)成了一個(gè)社團(tuán)。在中心點(diǎn)指派時(shí),有時(shí)會(huì)出現(xiàn)頂點(diǎn)在多個(gè)中心點(diǎn)間難以選擇的情況,AP通過(guò)擾動(dòng)網(wǎng)絡(luò)避免這種情況發(fā)生,而該現(xiàn)象可以作為識(shí)別重疊點(diǎn)、設(shè)計(jì)OAP算法的重要依據(jù)。OAP先用AP對(duì)網(wǎng)絡(luò)硬劃分,再利用AP的上述特點(diǎn)識(shí)別重疊點(diǎn)的候選集,最后將候選集里那些會(huì)使社團(tuán)變稀疏的頂點(diǎn)作為噪聲過(guò)濾掉,即得到重疊社團(tuán)結(jié)

3、構(gòu)。實(shí)驗(yàn)利用空手道網(wǎng)絡(luò)驗(yàn)證了候選集選擇策略的合理性,利用蛋白質(zhì)相互作用網(wǎng)絡(luò)驗(yàn)證了算法能夠更準(zhǔn)確的檢測(cè)社團(tuán)結(jié)構(gòu),并且檢測(cè)到的社團(tuán)更有意義。實(shí)驗(yàn)結(jié)果說(shuō)明OAP算法是一個(gè)有效的重疊社團(tuán)檢測(cè)算法。
　　2.除了拓?fù)浣Y(jié)構(gòu),網(wǎng)絡(luò)中的頂點(diǎn)還具有屬性信息,為了檢測(cè)拓?fù)浣Y(jié)構(gòu)稠密且屬性信息相似的社團(tuán),提出一個(gè)基于頂點(diǎn)特征的社團(tuán)檢測(cè)算法。首先定義頂點(diǎn)間基于特征子空間的特征相似性,然后結(jié)合頂點(diǎn)特征相似性和拓?fù)湎嗨菩?計(jì)算網(wǎng)絡(luò)中邊的相似性,接著利用單鏈接分

4、層凝聚算法對(duì)邊聚類(lèi),最后提取邊上的公共特征作為社團(tuán)特征。實(shí)驗(yàn)利用Facebook網(wǎng)絡(luò)數(shù)據(jù)驗(yàn)證了算法能夠快速準(zhǔn)確的檢測(cè)出社團(tuán)結(jié)構(gòu),并能很好的解釋社團(tuán)含義。利用酵母 PPI數(shù)據(jù)說(shuō)明算法能夠準(zhǔn)確檢測(cè)到具有生物意義的社團(tuán),并給出該社團(tuán)可能行使功能的時(shí)間。實(shí)驗(yàn)結(jié)果說(shuō)明算法具有普適性,能夠在頂點(diǎn)具有屬性信息的網(wǎng)絡(luò)中識(shí)別有意義的社團(tuán)結(jié)構(gòu)。
　　3.分析動(dòng)態(tài)網(wǎng)絡(luò)不同時(shí)刻間社團(tuán)結(jié)構(gòu)的變化以研究網(wǎng)絡(luò)演化規(guī)律與特點(diǎn)是動(dòng)態(tài)網(wǎng)絡(luò)研究的重點(diǎn)。由于動(dòng)態(tài)網(wǎng)絡(luò)相鄰

5、采樣時(shí)刻網(wǎng)絡(luò)結(jié)構(gòu)一般變化不大,為避免對(duì)相似網(wǎng)絡(luò)重復(fù)聚類(lèi),提出一個(gè)基于橋系數(shù)的靜態(tài)局部社團(tuán)檢測(cè)算法和在此基礎(chǔ)上的增量社團(tuán)檢測(cè)算法。首先利用靜態(tài)算法提取每個(gè)社團(tuán)的最小橋系數(shù)生成樹(shù),最小橋系數(shù)生成樹(shù)的導(dǎo)出子圖就是t?1時(shí)刻的社團(tuán)結(jié)構(gòu),然后通過(guò)橋系數(shù)的變化判斷t時(shí)刻可能出現(xiàn)結(jié)構(gòu)變化的社團(tuán),最后局部調(diào)整這些社團(tuán),以得到符合t時(shí)刻網(wǎng)絡(luò)拓?fù)涞纳鐖F(tuán)結(jié)構(gòu)。實(shí)驗(yàn)利用足球隊(duì)網(wǎng)絡(luò)數(shù)據(jù)驗(yàn)證了靜態(tài)局部社團(tuán)檢測(cè)算法的精確性,利用構(gòu)造數(shù)據(jù)驗(yàn)證了增量算法的精確性,利用D

6、BLP數(shù)據(jù)驗(yàn)證了增量算法的高效性。實(shí)驗(yàn)結(jié)果說(shuō)明算法能夠利用前一時(shí)刻的社團(tuán)結(jié)構(gòu)和增量信息,快速準(zhǔn)確的檢測(cè)當(dāng)前時(shí)刻的社團(tuán)結(jié)構(gòu)。
　　4.蛋白質(zhì)復(fù)合體預(yù)測(cè)對(duì)理解生物體結(jié)構(gòu)與功能之間的關(guān)系具有極其重要的意義。研究發(fā)現(xiàn)蛋白質(zhì)復(fù)合體由一個(gè)核和一些附屬蛋白質(zhì)構(gòu)成,對(duì)復(fù)合體的拓?fù)浣Y(jié)構(gòu)目前沒(méi)有明確的定義,本文從邊的角度刻畫(huà)復(fù)合體的核結(jié)構(gòu),提出一個(gè)基于邊的蛋白質(zhì)復(fù)合體檢測(cè)算法。算法首先識(shí)別出所有的核邊,然后對(duì)核邊聚類(lèi)得到候選核,接下來(lái)過(guò)濾候選核以保證

7、其中不存在重疊程度較高的核,最后檢測(cè)每個(gè)核的附屬蛋白質(zhì),得到蛋白質(zhì)復(fù)合體。實(shí)驗(yàn)利用DIP數(shù)據(jù)庫(kù)中的酵母PPI和文獻(xiàn)中的Gavin PPI數(shù)據(jù),驗(yàn)證了算法的精確性。實(shí)驗(yàn)結(jié)果說(shuō)明算法能夠更準(zhǔn)確的檢測(cè)蛋白質(zhì)復(fù)合體,識(shí)別出位置一致性和語(yǔ)義相似性都更高的復(fù)合體。
　　5.作為溝通和分享信息的平臺(tái),在線社交網(wǎng)絡(luò)已是人們生活中必不可少的一部分,為注冊(cè)用戶推薦朋友是社交網(wǎng)站必須提供的重要服務(wù),為了解決這個(gè)問(wèn)題,提出基于社交圈的朋友推薦算法。算法基