基于圖挖掘的網(wǎng)絡社團結(jié)構(gòu)發(fā)現(xiàn).pdf

1、現(xiàn)實世界的網(wǎng)絡里自然地包含了很多社團結(jié)構(gòu),它們已經(jīng)成為網(wǎng)絡系統(tǒng)中一個重要的統(tǒng)計特征。例如,在社會網(wǎng)絡中,它們可能代表著一組俱樂部成員;生物網(wǎng)絡里,或許是一組功能相關(guān)的基因組:在語意網(wǎng)絡中,它們是一些與某個主題相關(guān)的網(wǎng)頁。通常來講,社團結(jié)構(gòu)是一些聯(lián)系緊密的實體,結(jié)構(gòu)內(nèi)部節(jié)點之間的聯(lián)系相對網(wǎng)絡中其它節(jié)點更緊密。如何高效地挖掘出這些結(jié)構(gòu)對理解和分析網(wǎng)絡結(jié)構(gòu)來說是一個很重要的問題。
　　 盡管在網(wǎng)絡社團的發(fā)現(xiàn)方面已經(jīng)取得不少研究成果,但

2、仍然存在許多問題有待解決。比如,有些算法的效率不是很高,社團結(jié)構(gòu)的度量機制不夠完善;很少有工作去關(guān)注重疊的社團結(jié)構(gòu),雖然重疊的結(jié)構(gòu)在現(xiàn)實的網(wǎng)絡中更普遍存在,也更能反映出真實世界的本質(zhì)。針對這些問題,本文借助一些經(jīng)典的算法來產(chǎn)生社團結(jié)構(gòu)的種子,然后以拓展種子的方式來挖掘網(wǎng)絡中重疊和非重疊的社團結(jié)構(gòu)。本文的主要貢獻如下:
　　 1.結(jié)合多層次策略,文中運用經(jīng)典的圖譜劃分方法產(chǎn)生了種子集合,并對種子的特征進行了分析。多層次策略使得算法

3、在計算最粗糙圖的Fiedler向量時具有很好的劃分速度;譜平分方法幫助算法過程找到很好的圖劃分線索。這些種子集合抓住了社團結(jié)構(gòu)的主體,反映出了目標社團的特征,具有很好的性能。
　　 在真實的網(wǎng)絡數(shù)據(jù)上,文中也對種子選取的合理性做出了驗證。
　　 2.運用種子拓展的方式提出了一種新穎的社團識別算法。該算法基于模塊函數(shù)和節(jié)點的傳遞概率。模塊函數(shù)是由Newman和Girvan來定義的,它已經(jīng)成為度量社團結(jié)構(gòu)的一種主流標準。算法

4、用它的改變值來評估新擴展節(jié)點對當前種子集合的貢獻。傳遞概率在算法中被用來推斷相鄰節(jié)點之間的聯(lián)系,反映擴展到新節(jié)點的權(quán)重。傳遞概率的源頭是種子集合中節(jié)點的初始概率(初始權(quán)重)。新節(jié)點得到的概率決定了計算節(jié)點貢獻值的次序,貢獻值又決定了節(jié)點是否具有進一步擴展的機會。第4章對算法過程做出了詳細的描述,同時也對擴展過程中節(jié)點的刪除操作和擴展步上逃逸的概率做出了分析。
　　 3.對網(wǎng)絡中普遍存在的而又很少被關(guān)注的重疊社團結(jié)構(gòu),文中提出一種

5、識別算法。對解決重疊問題,它開辟了一條新的途徑。該算法仍然基于種子擴展。在得到種子集合之后,算法結(jié)合隨機行走技術(shù)給出了一種合理的擴展過程,它用時間步來刻化。在擴展的每個時間步,算法首先計算出所有標準化后的節(jié)點概率。按照概率值的降序,所有的節(jié)點依次被掃描。然后,確定哪些節(jié)點在接下來的時間步里作進一步的擴展。通過節(jié)點掃描,算法還要對新擴展的節(jié)點作出是否為當前的種子集合貢獻者的判斷。這些判斷主要用于尋找候選社團在當前時間步最優(yōu)的結(jié)構(gòu)。運用貢獻

6、節(jié)點的性質(zhì),文中給出了一些定理。基于性質(zhì)定理,一些無用的擴展節(jié)點在尋找候選社團的最優(yōu)結(jié)構(gòu)時可以被安全地刪除。擴展過程執(zhí)行上述步驟直到社團結(jié)構(gòu)之間的重疊率超過了用戶的忍受范圍或者到達了隨機擴展的收斂時間。
　　 第5章不僅介紹了算法步驟,也對擴展過程給出了理論分析。分析表明,提出的方法使得候選社團在每個時間步上都能找到最優(yōu)的結(jié)構(gòu),基于懶惰隨機行走的整個擴展過程也能給種子集合帶來好的擴展結(jié)構(gòu)。
　　 4.在六個網(wǎng)絡數(shù)據(jù)集上,

7、對上述提出的算法作出了驗證。數(shù)據(jù)集來自真實的網(wǎng)絡,規(guī)模大小不等,內(nèi)容涉及多個領(lǐng)域。在實驗分析上,文中從多個角度運用多種機制來評估算法。評估內(nèi)容包括種子選取方式上的對比,算法與相關(guān)工作的比較以及時間分析等。對重疊的社團結(jié)構(gòu),還給出了在著名的網(wǎng)絡里發(fā)現(xiàn)的實例。實驗結(jié)果表明文中提出的方法具有一定的優(yōu)越性,同時也證明了重疊方式對識別完善的社團結(jié)構(gòu)是非常重要的,讓大家認識到重疊社團在真實網(wǎng)絡中的研究意義。
　　 綜上所述,本文針對網(wǎng)絡中的