現(xiàn)實(shí)世界的網(wǎng)絡(luò)里自然地包含了很多社團(tuán)結(jié)構(gòu),它們已經(jīng)成為網(wǎng)絡(luò)系統(tǒng)中一個(gè)重要的統(tǒng)計(jì)特征。例如,在社會(huì)網(wǎng)絡(luò)中,它們可能代表著一組俱樂(lè)部成員;生物網(wǎng)絡(luò)里,或許是一組功能相關(guān)的基因組;在語(yǔ)意網(wǎng)絡(luò)中,它們是一些與某個(gè)主題相關(guān)的網(wǎng)頁(yè)。通常來(lái)講,社團(tuán)結(jié)構(gòu)是一些聯(lián)系緊密的實(shí)體,結(jié)構(gòu)內(nèi)部節(jié)點(diǎn)之間的聯(lián)系相對(duì)網(wǎng)絡(luò)中其它節(jié)點(diǎn)更緊密。如何高效地挖掘出這些結(jié)構(gòu)對(duì)理解和分析網(wǎng)絡(luò)結(jié)構(gòu)來(lái)說(shuō)是一個(gè)很重要的問(wèn)題。 盡管在網(wǎng)絡(luò)社團(tuán)的發(fā)現(xiàn)方面已經(jīng)取得不少研究成果,但仍然存在許多問(wèn)題有待解決。比如,有些算法的效率不是很高,社團(tuán)結(jié)構(gòu)的度量機(jī)制不夠完善;很少有工作去關(guān)注重疊的社團(tuán)結(jié)構(gòu),雖然重疊的結(jié)構(gòu)在現(xiàn)實(shí)的網(wǎng)絡(luò)中更普遍存在,也更能反映出真實(shí)世界的本質(zhì)。針對(duì)這些問(wèn)題,本文借助一些經(jīng)典的算法來(lái)產(chǎn)生社團(tuán)結(jié)構(gòu)的種子,然后以拓展種子的方式來(lái)挖掘網(wǎng)絡(luò)中重疊和非重疊的社團(tuán)結(jié)構(gòu)。本文的主要貢獻(xiàn)如下: 1.結(jié)合多層次策略,文中運(yùn)用經(jīng)典的圖譜劃分方法產(chǎn)生了種子集合,并對(duì)種子的特征進(jìn)行了分析。多層次策略使得算法在計(jì)算最粗糙圖的Fiedler向量時(shí)具有很好的劃分速度;譜平分方法幫助算法過(guò)程找到很好的圖劃分線(xiàn)索。這些種子集合抓住了社團(tuán)結(jié)構(gòu)的主體,反映出了目標(biāo)社團(tuán)的特征,具有很好的性能。 在真實(shí)的網(wǎng)絡(luò)數(shù)據(jù)上,文中也對(duì)種子選取的合理性做出了驗(yàn)證。 2.運(yùn)用種子拓展的方式提出了一種新穎的社團(tuán)識(shí)別算法。該算法基于模塊函數(shù)和節(jié)點(diǎn)的傳遞概率。模塊函數(shù)是由Newman和Cirvan來(lái)定義的,它已經(jīng)成為度量社團(tuán)結(jié)構(gòu)的一種主流標(biāo)準(zhǔn)。算法用它的改變值來(lái)評(píng)估新擴(kuò)展節(jié)點(diǎn)對(duì)當(dāng)前種子集合的貢獻(xiàn)。傳遞概率在算法中被用來(lái)推斷相鄰節(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ī)會(huì)。第4章對(duì)算法過(guò)程做出了詳細(xì)的描述,同時(shí)也對(duì)擴(kuò)展過(guò)程中節(jié)點(diǎn)的刪除操作和擴(kuò)展步上逃逸的概率做出了分析。 3.對(duì)網(wǎng)絡(luò)中普遍存在的而又很少被關(guān)注的重疊社團(tuán)結(jié)構(gòu),文中提出一種識(shí)別算法。對(duì)解決重疊問(wèn)題,它開(kāi)辟了一條新的途徑。該算法仍然基于種子擴(kuò)展。在得到種子集合之后,算法結(jié)合隨機(jī)行走技術(shù)給出了一種合理的擴(kuò)展過(guò)程,它用時(shí)間步來(lái)刻化。在擴(kuò)展的每個(gè)時(shí)間步,算法首先計(jì)算出所有標(biāo)準(zhǔn)化后的節(jié)點(diǎn)概率。按照概率值的降序,所有的節(jié)點(diǎn)依次被掃描。然后,確定哪些節(jié)點(diǎn)在接下來(lái)的時(shí)間步里作進(jìn)一步的擴(kuò)展。通過(guò)節(jié)點(diǎn)掃描,算法還要對(duì)新擴(kuò)展的節(jié)點(diǎn)作出是否為當(dāng)前的種子集合貢獻(xiàn)者的判斷。這些判斷主要用于尋找候選社團(tuán)在當(dāng)前時(shí)間步最優(yōu)的結(jié)構(gòu)。運(yùn)用貢獻(xiàn)節(jié)點(diǎn)的性質(zhì),文中給出了一些定理�；谛再|(zhì)定理,一些無(wú)用的擴(kuò)展節(jié)點(diǎn)在尋找候選社團(tuán)的最優(yōu)結(jié)構(gòu)時(shí)可以被安全地刪除。擴(kuò)展過(guò)程執(zhí)行上述步驟直到社團(tuán)結(jié)構(gòu)之間的重疊率超過(guò)了用戶(hù)的忍受范圍或者到達(dá)了隨機(jī)擴(kuò)展的收斂時(shí)間。 第5章不僅介紹了算法步驟,也對(duì)擴(kuò)展過(guò)程給出了理論分析。分析表明,提出的方法使得候選社團(tuán)在每個(gè)時(shí)間步上都能找到最優(yōu)的結(jié)構(gòu),基于懶惰隨機(jī)行走的整個(gè)擴(kuò)展過(guò)程也能給種子集合帶來(lái)好的擴(kuò)展結(jié)構(gòu)。 4.在六個(gè)網(wǎng)絡(luò)數(shù)據(jù)集上,對(duì)上述提出的算法作出了驗(yàn)證。數(shù)據(jù)集來(lái)自真實(shí)的網(wǎng)絡(luò),規(guī)模大小不等,內(nèi)容涉及多個(gè)領(lǐng)域。在實(shí)驗(yàn)分析上,文中從多個(gè)角度運(yùn)用多種機(jī)制來(lái)評(píng)估算法。評(píng)估內(nèi)容包括種子選取方式上的對(duì)比,算法與相關(guān)工作的比較以及時(shí)間分析等。對(duì)重疊的社團(tuán)結(jié)構(gòu),還給出了在著名的網(wǎng)絡(luò)里發(fā)現(xiàn)的實(shí)例。實(shí)驗(yàn)結(jié)果表明文中提出的方法具有一定的優(yōu)越性,同時(shí)也證明了重疊方式對(duì)識(shí)別完善的社團(tuán)結(jié)構(gòu)是非常重要的,讓大家認(rèn)識(shí)到重疊社團(tuán)在真實(shí)網(wǎng)絡(luò)中的研究意義。 綜上所述,本文針對(duì)網(wǎng)絡(luò)中的社團(tuán)發(fā)現(xiàn)問(wèn)題提出了幾種新算法。這些算法采用了種子擴(kuò)展的方式,擴(kuò)展過(guò)程基于隨機(jī)行走技術(shù),擴(kuò)展結(jié)構(gòu)選用了模塊函數(shù)來(lái)度量。文中用理論分析和大量的實(shí)驗(yàn)驗(yàn)證了這些算法。結(jié)果表明提出的方法能識(shí)別出結(jié)構(gòu)完善的社團(tuán)結(jié)構(gòu),具有很好的性能。
【學(xué)位單位】：復(fù)旦大學(xué)
【學(xué)位級(jí)別】：博士
【學(xué)位年份】：2008
【中圖分類(lèi)】：N941.4
【部分圖文】：

網(wǎng)絡(luò)系統(tǒng)的概念已被引入到多個(gè)領(lǐng)域{1。2，3，4，5，6，7}，如社會(huì)網(wǎng)絡(luò)【8，9}、萬(wàn)維網(wǎng)[10， 1112，14，15」、生物網(wǎng)絡(luò)【16，33」、經(jīng)濟(jì)學(xué)網(wǎng)絡(luò){18，19}、科研合作網(wǎng)絡(luò){2�！�、世界的航空運(yùn)輸網(wǎng)絡(luò)【39」、食物網(wǎng)絡(luò)【36，37}等等。圖1.1到圖1.4展示了其中幾種網(wǎng)絡(luò)實(shí)例。這些復(fù)雜的網(wǎng)絡(luò)，是重要的信息資源載體，包含著豐富的內(nèi)容，并且內(nèi)容之間的關(guān)系也極其錯(cuò)綜復(fù)雜。面對(duì)如此龐大繁瑣的網(wǎng)絡(luò)，人們迫切需要挖掘海量數(shù)據(jù)中隱藏的有用信息。網(wǎng)絡(luò)圖中包含著什么特征?網(wǎng)絡(luò)元素之間的復(fù)雜關(guān)聯(lián)又蘊(yùn)含著什么意義?如何從這些網(wǎng)絡(luò)圖里快速有效地挖掘出有意義的信息?解決這些問(wèn)題對(duì)理解網(wǎng)絡(luò)結(jié)構(gòu)和分析網(wǎng)絡(luò)特性具有很大的幫助。網(wǎng)絡(luò)元素可作為圖中的節(jié)點(diǎn)，元素之間的聯(lián)系作為圖的邊。用圖的節(jié)點(diǎn)和邊來(lái)存儲(chǔ)一些附加信息，以圖的方式!咧對(duì)網(wǎng)絡(luò)建模。這樣就可以借助圖挖掘的方式來(lái)分析網(wǎng)絡(luò)中有趣的元素和數(shù)據(jù)元素之間的關(guān)聯(lián)。社團(tuán)結(jié)構(gòu)是網(wǎng)絡(luò)圖中呈現(xiàn)出的一個(gè)重要特征一一每個(gè)社團(tuán)內(nèi)部節(jié)點(diǎn)之間的聯(lián)系相對(duì)圖中其它節(jié)點(diǎn)更緊密「 2125)。這些節(jié)點(diǎn)通常是圖中具有相同屬性或者扮演相似角色的一組集合，所以社團(tuán)又被稱(chēng)為類(lèi)，模塊，粘在一起的子圖。圖1.5和圖1.6展示了兩個(gè)實(shí)例，它們分別代表了非重疊和重疊的社團(tuán)結(jié)構(gòu)。在網(wǎng)絡(luò)中識(shí)別或發(fā)現(xiàn)這些社團(tuán)結(jié)構(gòu)具有重要的實(shí)用價(jià)值。屬于同一個(gè)緊密相連社團(tuán)中的節(jié)點(diǎn)更加可能在其它方面上具有相同或相近的性質(zhì)。如社會(huì)網(wǎng)絡(luò)中的社團(tuán)可能是根據(jù)共同興趣或背景而形成的社會(huì)團(tuán)體;萬(wàn)維網(wǎng)里，社團(tuán)結(jié)構(gòu)或許代表著有與某個(gè)共同主題相關(guān)的網(wǎng)頁(yè)!10

某個(gè)工作組內(nèi)elllail通信構(gòu)成的網(wǎng)絡(luò)

圖1.1:與某個(gè)站點(diǎn)相關(guān)的網(wǎng)頁(yè)書(shū)今.二二裊翻..-.二一.臼份:，.侶今.，.::..…::銘不令...……圖1.2:某個(gè)工作組內(nèi)elllail通信構(gòu)成的網(wǎng)絡(luò)尹

【引證文獻(xiàn)】

相關(guān)碩士學(xué)位論文 前3條

1 劉微;復(fù)雜網(wǎng)絡(luò)中社團(tuán)結(jié)構(gòu)的發(fā)現(xiàn)[D];遼寧師范大學(xué);2011年

2 彭玲;基于主題及核心人物的郵件網(wǎng)絡(luò)社區(qū)發(fā)現(xiàn)研究[D];蘇州大學(xué);2010年

3 許沖沖;基于偶圖分解的電壓控制區(qū)域劃分[D];華北電力大學(xué);2012年

本文編號(hào)：2830012