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

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

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

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

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

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

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