【摘要】：近年來,隨著統(tǒng)計(jì)學(xué)、物理學(xué)、社會學(xué)和計(jì)算機(jī)科學(xué)等多門學(xué)科的交叉性研究的興起,復(fù)雜網(wǎng)絡(luò)分析逐漸成為交叉性科學(xué)研究的熱點(diǎn)。鏈接預(yù)測是根據(jù)網(wǎng)絡(luò)結(jié)構(gòu)屬性預(yù)測網(wǎng)絡(luò)中節(jié)點(diǎn)之間是否存在鏈接的方法和技術(shù)。該技術(shù)作為復(fù)雜網(wǎng)絡(luò)分析的主要研究方向,在模擬網(wǎng)絡(luò)演化、學(xué)習(xí)網(wǎng)絡(luò)表征等理論研究方面,以及推斷信息傳播、提供推薦服務(wù)等應(yīng)用服務(wù)領(lǐng)域均有重要的研究價(jià)值。但是由于數(shù)據(jù)規(guī)模的不斷擴(kuò)大,網(wǎng)絡(luò)結(jié)構(gòu)也日益復(fù)雜,使得已有鏈接預(yù)測算法的有效性大大降低。因此如何充分利用復(fù)雜網(wǎng)絡(luò)結(jié)構(gòu)信息設(shè)計(jì)鏈接預(yù)測算法成為該領(lǐng)域中新的難點(diǎn)和重點(diǎn)。同時(shí)隨著人們對機(jī)器學(xué)習(xí)與數(shù)據(jù)挖掘領(lǐng)域研究的不斷深入,如何學(xué)習(xí)網(wǎng)絡(luò)中的復(fù)雜結(jié)構(gòu)提高鏈接預(yù)測算法的性能也受到極大的關(guān)注。本文以挖掘共鄰節(jié)點(diǎn)貢獻(xiàn)、加權(quán)聚類系數(shù)、影響力節(jié)點(diǎn)和社區(qū)信息等復(fù)雜網(wǎng)絡(luò)結(jié)構(gòu)特征為主線,結(jié)合貝葉斯模型、隨機(jī)塊模型、遷移學(xué)習(xí)等機(jī)器學(xué)習(xí)技術(shù)對基于復(fù)雜網(wǎng)絡(luò)結(jié)構(gòu)的鏈接預(yù)測算法開展了深入細(xì)致的研究,并做出了以下主要貢獻(xiàn):(1)新近提出的基于局部樸素貝葉斯概率模型的鏈接預(yù)測算法能夠度量不同共鄰節(jié)點(diǎn)對潛在節(jié)點(diǎn)對的貢獻(xiàn),實(shí)現(xiàn)簡單且有效。但該算法假定每個(gè)共同鄰居對鏈接的形成產(chǎn)生單獨(dú)作用,并不能反映網(wǎng)絡(luò)各節(jié)點(diǎn)相互連接的圖狀結(jié)構(gòu)特征。針對這一問題,本文提出了一種基于樹狀增強(qiáng)樸素貝葉斯概率模型的鏈接預(yù)測算法。該算法利用互信息來度量共鄰節(jié)點(diǎn)之間的潛在相關(guān)性,有效地解決了其中的獨(dú)立性假設(shè)限制。在對人工網(wǎng)絡(luò)、真實(shí)網(wǎng)絡(luò)的實(shí)驗(yàn)結(jié)果證明了其相對于傳統(tǒng)算法的優(yōu)越性。(2)在加權(quán)網(wǎng)絡(luò)中,基于局部結(jié)構(gòu)的相似度指標(biāo)被廣泛用于加權(quán)復(fù)雜網(wǎng)絡(luò)的鏈接預(yù)測問題。然而此類指標(biāo)忽略了共同鄰居對計(jì)算潛在鏈接相似度產(chǎn)生的不同貢獻(xiàn),也沒有計(jì)算局部結(jié)構(gòu)中共鄰節(jié)點(diǎn)之間鏈接的不同加權(quán)權(quán)重。因此,本文通過引入加權(quán)聚類系數(shù)的概念把無權(quán)的樸素貝葉斯預(yù)測算法拓展到加權(quán)復(fù)雜網(wǎng)絡(luò)的應(yīng)用場景。在真實(shí)加權(quán)網(wǎng)絡(luò)的大量實(shí)驗(yàn)上證明了提出算法的有效性。(3)基于局部結(jié)構(gòu)的預(yù)測指標(biāo)對網(wǎng)絡(luò)中所有可能的鏈接計(jì)算相似度,并無區(qū)分鏈接是否處同一社區(qū)或者不同社區(qū)之間,也沒有區(qū)分處于不同社區(qū)結(jié)構(gòu)下共鄰節(jié)點(diǎn)對預(yù)測節(jié)點(diǎn)對的影響。因此本文通過劃分社區(qū)結(jié)構(gòu)提出了一種差分化處理潛在鏈接和共鄰節(jié)點(diǎn)貢獻(xiàn)的預(yù)測算法。該算法把鏈接劃分成社區(qū)內(nèi)部和社區(qū)間兩類鏈接計(jì)算相似度,同時(shí)提出了共鄰節(jié)點(diǎn)鏈接度和社區(qū)參與度的概念,有效地處理了在社區(qū)劃分下不同共鄰節(jié)點(diǎn)的影響。大量實(shí)驗(yàn)表明算法能夠有效提高鏈接預(yù)測效果并推廣到CN和Jaccard指標(biāo)當(dāng)中。(4)社區(qū)表示在復(fù)雜網(wǎng)絡(luò)中的簇。同一社區(qū)內(nèi)部節(jié)點(diǎn)之間的鏈接比較緊密,而社區(qū)與社區(qū)之間的鏈接比較稀疏。本文借鑒了經(jīng)典的隨機(jī)塊模型和社交圈子發(fā)現(xiàn)算法,提出一種平衡模塊度最大化的鏈接預(yù)測算法(MMLP)。MMLP首先搭建一個(gè)強(qiáng)調(diào)內(nèi)部鏈接的概率生成過程。該過程能夠有效的利用模塊度定義解釋鏈接預(yù)測和社區(qū)發(fā)現(xiàn)之間的聯(lián)系,同時(shí)把集成特征和鏈接相關(guān)聯(lián),從而學(xué)習(xí)不同特征在不同社區(qū)的權(quán)重。大量的實(shí)驗(yàn)表明MMLP比基準(zhǔn)算法取得了更好的預(yù)測效果。(5)面向多維度異構(gòu)網(wǎng)絡(luò)的鏈接預(yù)測算法缺點(diǎn)在于顯式地使用維度間的關(guān)聯(lián)。即在原有的同構(gòu)算法基礎(chǔ)上添加和維度相關(guān)的概率表示,并沒有深入挖掘各維度子網(wǎng)絡(luò)之間的隱含關(guān)系。同時(shí)各種用于計(jì)算相似度的特征均是基于局部結(jié)構(gòu)或者路徑結(jié)構(gòu)的特征,是領(lǐng)域相關(guān)的,并不具備一般性。為了克服這些缺點(diǎn),我們在MMLP的基礎(chǔ)上采用遷移學(xué)習(xí)的思想用源維度子網(wǎng)絡(luò)學(xué)習(xí)的知識幫助目標(biāo)維度子網(wǎng)絡(luò)的預(yù)測,提出一個(gè)社區(qū)層次的內(nèi)部維度間知識遷移的算法(ITLP)。ITLP既保留了MMLP在挖掘社區(qū)變化和鏈接生成之間的關(guān)系的特點(diǎn),更通過遷移學(xué)習(xí)的思想有效地拓展到多維網(wǎng)絡(luò)鏈接預(yù)測中。在真實(shí)多層次數(shù)據(jù)集的實(shí)驗(yàn)證明了ITLP的魯棒性。(6)許多通過共鄰節(jié)點(diǎn)影響權(quán)重定義相似度的預(yù)測算法沒有辦法同時(shí)把網(wǎng)絡(luò)的宏觀(全局)和微觀(局部)兩類特性納入到同一個(gè)算法當(dāng)中。即使部分算法能夠集成上述特性,但運(yùn)算效率低,沒有辦法拓展到較大規(guī)模的密集網(wǎng)絡(luò)當(dāng)中。為了克服這些缺點(diǎn),提出一個(gè)基于全局性影響力節(jié)點(diǎn)識別的鏈接預(yù)測算法。該算法通過引入有影響力節(jié)點(diǎn)識別技術(shù)中的節(jié)點(diǎn)影響力排名得分來定義不同共鄰節(jié)點(diǎn)的貢獻(xiàn),有效集成了局部結(jié)構(gòu)和全局結(jié)構(gòu)的影響。在無權(quán)網(wǎng)絡(luò)和加權(quán)網(wǎng)絡(luò)的大量實(shí)驗(yàn)表明,提出的算法能夠快速并準(zhǔn)確地完成較大規(guī)模具備密集結(jié)構(gòu)網(wǎng)絡(luò)的鏈接預(yù)測任務(wù)。
【圖文】：

a) 完整網(wǎng)絡(luò) b) 訓(xùn)練網(wǎng)絡(luò) c) 待預(yù)測網(wǎng)絡(luò)圖 1-1 鏈接預(yù)測實(shí)驗(yàn)劃分過程示意圖1.2 鏈接預(yù)測接下來將介紹鏈接預(yù)測的基本定義、研究現(xiàn)狀以及相關(guān)檢驗(yàn)指標(biāo)。1.2.1 問題定義給定一個(gè)復(fù)雜網(wǎng)絡(luò)G=(V,E)，其中V和E分別表示節(jié)點(diǎn)或者鏈接的集合。在一個(gè)特定的時(shí)間點(diǎn)t，，鏈接預(yù)測的目的是在某個(gè)未來的時(shí)間點(diǎn) ′(t′>t)判斷尚未產(chǎn)生的鏈接的潛在節(jié)點(diǎn)對（或稱為預(yù)測節(jié)點(diǎn)對）是否會產(chǎn)生新的鏈接，或者在當(dāng)前的網(wǎng)絡(luò)結(jié)構(gòu)下預(yù)測丟失鏈接或者未被發(fā)現(xiàn)的鏈接。由于動態(tài)網(wǎng)絡(luò)數(shù)據(jù)獲取比較困難，因此在目前的主流研究中，一般都假設(shè)網(wǎng)絡(luò)是靜態(tài)的。盡管該研究思路在一定程度上和真實(shí)的復(fù)雜網(wǎng)絡(luò)不符，但是

圖 2-1 網(wǎng)絡(luò)局部結(jié)構(gòu)示例圖獨(dú)立的共鄰節(jié)點(diǎn)，兩者均影響藍(lán)色潛在節(jié)點(diǎn)對的形成。在左下角子圖的 TAN 模型說明中，屬性X1在類Y上依賴于X3的值，而左上角子圖的 LNB 模型說明中每個(gè)屬性對Y的影響是獨(dú)立于其他屬性的。顯然LNB并不包括屬性之間的關(guān)系（共鄰節(jié)點(diǎn)之間的關(guān)系），它可能無法反映在局部結(jié)構(gòu)中的“鏈接”結(jié)構(gòu)。相反，TAN 能夠捕獲屬性之間的潛在相關(guān)性并使其在預(yù)測過程中發(fā)揮重要作用[80]。綜上所述，本章節(jié)的貢獻(xiàn)總結(jié)如下： 提出了一個(gè)新穎的基于樹狀增強(qiáng)樸素貝葉斯（TAN）模型的復(fù)雜網(wǎng)絡(luò)鏈接預(yù)測算法。該算法保留了 LNB 的優(yōu)點(diǎn)同時(shí)利用信息熵對共鄰節(jié)點(diǎn)之間的隱含關(guān)系建模，緩解其中的強(qiáng)獨(dú)立假設(shè)限制。 TAN 算法可以擴(kuò)展到其他基于相似度的度量：CN、AA 和 RA。 使用人工和真實(shí)世界的數(shù)據(jù)集進(jìn)行實(shí)驗(yàn)評估，結(jié)果表明提出的算法能夠?qū)侧徆?jié)點(diǎn)之間的相關(guān)性建模，并提高鏈接預(yù)測任務(wù)的精確度。
【學(xué)位授予單位】：華南理工大學(xué)
【學(xué)位級別】：博士
【學(xué)位授予年份】：2018
【分類號】：O157.5;TP301.6

【相似文獻(xiàn)】

中國期刊全文數(shù)據(jù)庫 前10條

1 李經(jīng)安;徐志平;;一種改進(jìn)的鄰節(jié)點(diǎn)發(fā)現(xiàn)算法[J];計(jì)算機(jī)與網(wǎng)絡(luò);2015年12期

2 李瑞睿;鄭相全;王靖;葉久志;;一種基于定向天線的鄰節(jié)點(diǎn)發(fā)現(xiàn)算法[J];現(xiàn)代電子技術(shù);2011年05期

3 楊健敏;喬鋼;聶東虎;馬璐;;基于定向收發(fā)的水聲通信網(wǎng)絡(luò)鄰節(jié)點(diǎn)發(fā)現(xiàn)機(jī)制[J];電子與信息學(xué)報(bào);2018年11期

4 劉麗;;基于偽最近鄰節(jié)點(diǎn)的異構(gòu)無線網(wǎng)絡(luò)組網(wǎng)實(shí)現(xiàn)及仿真[J];吉林工程技術(shù)師范學(xué)院學(xué)報(bào);2014年03期

5 朱清超;;多跳吞吐量分析及鄰節(jié)點(diǎn)實(shí)時(shí)估計(jì)算法設(shè)計(jì)[J];計(jì)算機(jī)應(yīng)用;2017年09期

6 劉靖永;李樂民;景小榮;;多跳無線網(wǎng)絡(luò)中無需鄰節(jié)點(diǎn)信息的空間覆蓋廣播算法[J];電子與信息學(xué)報(bào);2010年10期

7 張?bào)?李穎;;移動Ad Hoc網(wǎng)絡(luò)中定向發(fā)送與接收算法的改進(jìn)[J];計(jì)算機(jī)工程;2009年05期

8 伍國華;馬滿好;;路徑交叉檢測與消除方法和鄰節(jié)點(diǎn)置換方法改進(jìn)TSP的解[J];計(jì)算機(jī)應(yīng)用研究;2011年02期

9 張遠(yuǎn);郭虹;劉洛琨;;AODV協(xié)議中擴(kuò)展環(huán)搜索與鄰節(jié)點(diǎn)列表的實(shí)現(xiàn)[J];計(jì)算機(jī)工程;2006年10期

10 高輝;劉靜;徐友云;;Ad hoc網(wǎng)絡(luò)中一種基于鄰節(jié)點(diǎn)時(shí)間安排的多址接入?yún)f(xié)議[J];上海交通大學(xué)學(xué)報(bào);2008年07期

中國重要會議論文全文數(shù)據(jù)庫 前2條

1 董朝平;郭龍祥;殷敬偉;生雪莉;;基于Mamdani推理的水下數(shù)據(jù)轉(zhuǎn)發(fā)機(jī)制研究[A];中國聲學(xué)學(xué)會2017年全國聲學(xué)學(xué)術(shù)會議論文集[C];2017年

2 魏遠(yuǎn)倫;滕丁;;TD小區(qū)H載波不能被占用的原因分析與解決[A];四川省通信學(xué)會2014年學(xué)術(shù)年會論文集[C];2014年

中國博士學(xué)位論文全文數(shù)據(jù)庫 前3條

1 伍杰華;基于復(fù)雜網(wǎng)絡(luò)結(jié)構(gòu)的鏈接預(yù)測[D];華南理工大學(xué);2018年

2 張遠(yuǎn);基于距離和角度信息的無線傳感網(wǎng)節(jié)點(diǎn)定位問題研究[D];山東大學(xué);2012年

3 顧德;無線傳感器網(wǎng)絡(luò)拓?fù)溥吔缗c瓶頸辨識[D];浙江大學(xué);2012年

中國碩士學(xué)位論文全文數(shù)據(jù)庫 前10條

1 韓琳;基于定向天線的自組織網(wǎng)絡(luò)鄰節(jié)點(diǎn)發(fā)現(xiàn)機(jī)制研究[D];西安電子科技大學(xué);2017年

2 高輝;分布式網(wǎng)絡(luò)中基于鄰節(jié)點(diǎn)調(diào)度的多址接入?yún)f(xié)議的研究[D];上海交通大學(xué);2008年

3 楊巧;基于改進(jìn)相似度的社會網(wǎng)絡(luò)鏈接預(yù)測研究[D];華南理工大學(xué);2015年

4 肖瓏;基于鄰節(jié)點(diǎn)殘存率和雙路徑的回退路由算法[D];天津大學(xué);2012年

5 鄭果;移動自組網(wǎng)拓?fù)涔芾碥浖难芯颗c設(shè)計(jì)[D];復(fù)旦大學(xué);2009年

6 賀瑛;面向城市場景的車輛自組織網(wǎng)絡(luò)路由協(xié)議研究[D];西安電子科技大學(xué);2014年

7 姜男瀾;WSN定位問題的研究[D];杭州電子科技大學(xué);2014年

8 劉金定;基于鄰節(jié)點(diǎn)殘存率的AODV路由協(xié)議優(yōu)化研究[D];南京理工大學(xué);2009年

9 王冠;基于費(fèi)舍爾信息的協(xié)作定位算法研究[D];重慶郵電大學(xué);2017年

10 O詞つ

本文編號：2626377