發(fā)布時(shí)間：2018-06-02 19:10

  本文選題：復(fù)雜網(wǎng)絡(luò) + 鏈路預(yù)測(cè)　； 參考：《蘭州大學(xué)》2017年碩士論文

【摘要】：我們處在一個(gè)由許許多多的復(fù)雜系統(tǒng)所構(gòu)成的世界中,如我們所在的生物圈、我們所在的社會(huì)等等,而滲透在我們生活中的這些復(fù)雜系統(tǒng)都可以被抽象為復(fù)雜網(wǎng)絡(luò),在這個(gè)網(wǎng)絡(luò)中,節(jié)點(diǎn)表示真實(shí)世界中的對(duì)象,邊表示的是它們之間的關(guān)系。網(wǎng)絡(luò)中蘊(yùn)含著大量的信息,而且這些信息會(huì)隨著網(wǎng)絡(luò)的不斷演化而變化,所以在當(dāng)前復(fù)雜網(wǎng)絡(luò)的研究中網(wǎng)絡(luò)的演化是一個(gè)熱點(diǎn),而在網(wǎng)絡(luò)演化的研究中有一個(gè)基本的問題就是網(wǎng)絡(luò)的鏈路預(yù)測(cè)。鏈路預(yù)測(cè)是挖掘網(wǎng)絡(luò)中的隱含信息和預(yù)測(cè)網(wǎng)絡(luò)將要演化的方向。具體的說,就是利用網(wǎng)絡(luò)中的各種信息,對(duì)網(wǎng)絡(luò)中丟失的連邊進(jìn)行尋找和對(duì)目前不存在的連邊進(jìn)行預(yù)測(cè)。處理鏈路預(yù)測(cè)的傳統(tǒng)方法是利用機(jī)器學(xué)習(xí)對(duì)網(wǎng)絡(luò)中的節(jié)點(diǎn)和邊按照它們的屬性進(jìn)行分類。隨著我們進(jìn)入了一個(gè)數(shù)據(jù)爆發(fā)的時(shí)代,網(wǎng)絡(luò)的規(guī)模越來越大,基于機(jī)器學(xué)習(xí)的方法已經(jīng)不能夠提供良好的預(yù)測(cè)準(zhǔn)確性。所以我們將目光轉(zhuǎn)向了利用網(wǎng)絡(luò)的結(jié)構(gòu)信息來進(jìn)行預(yù)測(cè)。目前基于相似性的鏈路預(yù)測(cè)算法是一種受關(guān)注度較高的方向,這種算法往往能帶給我們較好的預(yù)測(cè)結(jié)果以及相對(duì)低的時(shí)間復(fù)雜度。因此本文主要關(guān)注在相似性算法的基礎(chǔ)上如何對(duì)鏈路預(yù)測(cè)的結(jié)果進(jìn)行提升。網(wǎng)絡(luò)的拓?fù)浣Y(jié)構(gòu)是網(wǎng)絡(luò)中所包含的重要結(jié)構(gòu),是網(wǎng)絡(luò)性質(zhì)的決定因素。評(píng)價(jià)網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)的方式有網(wǎng)路聚集系數(shù)和社團(tuán)結(jié)構(gòu)。本文首先將聚集系數(shù)應(yīng)用到相似性指標(biāo)中,來提高預(yù)測(cè)結(jié)果的準(zhǔn)確性。一般來說,聚集系數(shù)較高的網(wǎng)絡(luò),各種相似性指標(biāo)均可以獲得較為理想的結(jié)果,尤其是CN指標(biāo),AA指標(biāo)和RA指標(biāo)。所以我們將節(jié)點(diǎn)的聚集系數(shù)結(jié)合到基于局部結(jié)構(gòu)的相似性指標(biāo)中,并在多個(gè)網(wǎng)絡(luò)上進(jìn)行實(shí)驗(yàn),獲得了良好的預(yù)測(cè)結(jié)果。其次,社團(tuán)結(jié)構(gòu)是網(wǎng)絡(luò)中另一個(gè)重要的拓?fù)浣Y(jié)構(gòu),社團(tuán)結(jié)構(gòu)內(nèi)部節(jié)點(diǎn)之間聯(lián)系緊密,不同社團(tuán)之間節(jié)點(diǎn)的聯(lián)系相對(duì)稀疏,所以社團(tuán)結(jié)構(gòu)的這種特性與節(jié)點(diǎn)之間的相似性有天然的聯(lián)系。因此,我們將社團(tuán)的這種特性結(jié)合到相似性指標(biāo)中,先定義節(jié)點(diǎn)之間的緊密程度,隨后提出基于節(jié)點(diǎn)間緊密度的一類相似性指標(biāo),并在多個(gè)真實(shí)網(wǎng)絡(luò)上進(jìn)行實(shí)驗(yàn),驗(yàn)證了基于社團(tuán)結(jié)構(gòu)的算法的有效性。最后,資源分配的相似性算法是一個(gè)預(yù)測(cè)性能非常好的算法,于是我們它擴(kuò)展到高階的路徑上,提出新的基于路徑的資源分配算法,并驗(yàn)證了它的有效性。本文通過對(duì)所提出的算法進(jìn)行大量實(shí)驗(yàn),結(jié)果表明它們都能在一定程度上提升鏈路預(yù)測(cè)結(jié)果的準(zhǔn)確性,對(duì)未來進(jìn)行網(wǎng)路演化機(jī)制的深入研究具有重要意義。
[Abstract]:We are in a world of many, many complex systems, such as the biosphere we live in, the society we live in, and the complex systems that permeate our lives can be abstracted into complex networks. In this network, nodes represent real-world objects and edges represent their relationships. There are a lot of information in the network, and these information will change with the evolution of the network, so the evolution of the network is a hot spot in the current research of complex network. In the research of network evolution, a basic problem is network link prediction. Link prediction is the direction of mining hidden information and predicting the evolution of network. To be specific, it is to use all kinds of information in the network to search for the missing connected edges in the network and to predict the non-existent connected edges. The traditional method to deal with link prediction is to classify nodes and edges according to their attributes by using machine learning. As we enter an era of data explosion, the scale of the network is becoming larger and larger, and the machine learning method can not provide good prediction accuracy. So we turn our eyes to the use of network structure information to predict. At present, the link prediction algorithm based on similarity is a kind of high attention direction, which can bring us better prediction results and relatively low time complexity. Therefore, this paper focuses on how to improve the results of link prediction based on similarity algorithm. The topological structure of the network is an important structure contained in the network, and it is the decisive factor of the nature of the network. The network topology is evaluated by network aggregation coefficient and community structure. In this paper, the aggregation coefficient is first applied to the similarity index to improve the accuracy of the prediction results. In general, the network with higher aggregation coefficient can obtain satisfactory results, especially CN index AA index and RA index. So we combine the clustering coefficient of nodes into the similarity index based on local structure and experiment on multiple networks and obtain good prediction results. Secondly, the community structure is another important topology in the network. Therefore, this characteristic of community structure has a natural relationship with the similarity between nodes. Therefore, we combine this characteristic of community into similarity index, define the degree of closeness between nodes, then propose a kind of similarity index based on tightness of nodes, and experiment on many real networks. The validity of the algorithm based on community structure is verified. Finally, the similarity algorithm of resource allocation is a very good predictor, so we extend it to higher-order paths, propose a new path-based resource allocation algorithm, and verify its effectiveness. Through a large number of experiments on the proposed algorithms, the results show that they can improve the accuracy of the link prediction results to a certain extent, and it is of great significance to further study the evolution mechanism of the network in the future.
【學(xué)位授予單位】：蘭州大學(xué)
【學(xué)位級(jí)別】：碩士
【學(xué)位授予年份】：2017
【分類號(hào)】：O157.5

【相似文獻(xiàn)】

相關(guān)期刊論文 前10條

1 關(guān)威;扭曲環(huán)帶的直觀拓?fù)湫再|(zhì)[J];自然雜志;1984年05期

2 楊學(xué)鋒;關(guān)于一類臨界點(diǎn)的局部拓?fù)湫再|(zhì)[J];數(shù)學(xué)學(xué)報(bào);1990年01期

3 陳世平;一種介于B－性質(zhì)與P－性質(zhì)之間的拓?fù)湫再|(zhì)[J];四川大學(xué)學(xué)報(bào)(自然科學(xué)版);1996年03期

4 戴保華;關(guān)于∮性質(zhì)的σ-積[J];青海師專學(xué)報(bào);1997年02期

5 周國(guó)平,龔國(guó)勇;淺談模的實(shí)譜的拓?fù)湫再|(zhì)[J];宜春學(xué)院學(xué)報(bào);2003年04期

6 胡傳芳;;移位空間上的拓?fù)湫再|(zhì)[J];中國(guó)科技信息;2008年03期

7 馬銳;關(guān)于模糊關(guān)系的解的拓?fù)湫再|(zhì)(英文)[J];云南師范大學(xué)學(xué)報(bào)(自然科學(xué)版);2003年03期

8 鄧義華;;兩個(gè)集合的復(fù)合的拓?fù)湫再|(zhì)研究[J];長(zhǎng)江大學(xué)學(xué)報(bào)(自科版);2005年10期

9 鄭會(huì)梧 ,閔佑林;“關(guān)于析格的兩條拓?fù)湫再|(zhì)”一文的注記[J];九江師專學(xué)報(bào);1988年05期

10 陳煥然;半分離空間的遺傳與拓?fù)湫再|(zhì)[J];吉首大學(xué)學(xué)報(bào)(自然科學(xué)版);1985年02期

相關(guān)會(huì)議論文 前10條

1 王鈺;;非注意狀態(tài)下拓?fù)湫再|(zhì)優(yōu)先加工的電生理學(xué)證據(jù)[A];第十二屆全國(guó)心理學(xué)學(xué)術(shù)大會(huì)論文摘要集[C];2009年

2 朱斌;樊祥;馬東輝;程正東;;窗口大小和權(quán)值模板對(duì)固定權(quán)值背景預(yù)測(cè)算法的影響[A];2006年全國(guó)光電技術(shù)學(xué)術(shù)交流會(huì)會(huì)議文集（D 光電信息處理技術(shù)專題）[C];2006年

3 陳飛;陳增強(qiáng);劉忠信;袁著祉;;一種度指數(shù)與聚集系數(shù)可調(diào)節(jié)的復(fù)雜網(wǎng)絡(luò)模型[A];2006全國(guó)復(fù)雜網(wǎng)絡(luò)學(xué)術(shù)會(huì)議論文集[C];2006年

4 王峰;姬冰輝;李斗;;一種基于混沌理論的自相似業(yè)務(wù)流預(yù)測(cè)算法研究[A];2006北京地區(qū)高校研究生學(xué)術(shù)交流會(huì)——通信與信息技術(shù)會(huì)議論文集（上）[C];2006年

5 錢正祥;徐華;張申浩;;數(shù)字信號(hào)序列的向量預(yù)測(cè)算法[A];第三屆全國(guó)信息獲取與處理學(xué)術(shù)會(huì)議論文集[C];2005年

6 傅曉;田廷劍;王軍;李少謙;;一種新的多用戶MIMO-OFDM資源分配算法[A];2008年中國(guó)西部青年通信學(xué)術(shù)會(huì)議論文集[C];2008年

7 郭景峰;代軍麗;馬鑫;王娟;;針對(duì)通信社會(huì)網(wǎng)絡(luò)的時(shí)間序列鏈接預(yù)測(cè)算法[A];第26屆中國(guó)數(shù)據(jù)庫(kù)學(xué)術(shù)會(huì)議論文集（A輯）[C];2009年

8 曲樺;梁思遠(yuǎn);趙季紅;;基于容量的相對(duì)最小影響資源分配算法[A];中國(guó)通信學(xué)會(huì)通信軟件技術(shù)委員會(huì)2009年學(xué)術(shù)會(huì)議論文集[C];2009年

9 李強(qiáng);梁煒;;面向無線HART網(wǎng)絡(luò)的動(dòng)態(tài)資源分配算法研究[A];2008’“先進(jìn)集成技術(shù)”院士論壇暨第二屆儀表、自動(dòng)化與先進(jìn)集成技術(shù)大會(huì)論文集[C];2008年

10 程尊水;;時(shí)滯復(fù)雜網(wǎng)絡(luò)的分岔與控制[A];中國(guó)力學(xué)學(xué)會(huì)學(xué)術(shù)大會(huì)'2009論文摘要集[C];2009年

相關(guān)重要報(bào)紙文章 前2條

1 記者 陳瑜邋唐婷;人的左右大腦在認(rèn)知上有何不同？[N];科技日?qǐng)?bào);2008年

2 鄭千里;破解蜜蜂分辨圖形之謎[N];科技日?qǐng)?bào);2003年

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

1 王志宙;一維周期系統(tǒng)中波動(dòng)傳播拓?fù)湫再|(zhì)的研究[D];燕山大學(xué);2016年

2 嚴(yán)俊坤;認(rèn)知雷達(dá)中的資源分配算法研究[D];西安電子科技大學(xué);2015年

3 馬玉韜;基于濾波理論和特征統(tǒng)計(jì)的蛋白質(zhì)編碼區(qū)預(yù)測(cè)算法研究[D];天津大學(xué);2013年

4 李楠;基于火焰自由基成像的NO_x排放預(yù)測(cè)算法研究[D];華北電力大學(xué)(北京);2017年

5 金慈航;OFDM系統(tǒng)中基于對(duì)偶分解理論的資源分配算法[D];中國(guó)科學(xué)技術(shù)大學(xué);2008年

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

1 楊釗;基于網(wǎng)絡(luò)拓?fù)湫再|(zhì)和路徑的鏈路預(yù)測(cè)算法[D];蘭州大學(xué);2017年

2 張維偉;歇后語(yǔ)的拓?fù)浣馕鯷D];哈爾濱理工大學(xué);2017年

3 朱博堯;基于結(jié)構(gòu)特性的復(fù)雜網(wǎng)絡(luò)鏈路預(yù)測(cè)研究[D];浙江大學(xué);2017年

4 閆潤(rùn)珍;基于譜分析方法的鏈路預(yù)測(cè)算法研究[D];蘭州大學(xué);2017年

5 吳智勇;學(xué)術(shù)論文排序預(yù)測(cè)算法研究[D];內(nèi)蒙古大學(xué);2015年

6 張勇攀;針對(duì)殘缺IP網(wǎng)絡(luò)的鏈路預(yù)測(cè)技術(shù)研究[D];哈爾濱工業(yè)大學(xué);2015年

7 應(yīng)超;博物館移動(dòng)導(dǎo)覽中的遠(yuǎn)程展示技術(shù)研究及系統(tǒng)實(shí)現(xiàn)[D];浙江大學(xué);2015年

8 常艷華;基于數(shù)據(jù)驅(qū)動(dòng)模擬電路故障預(yù)測(cè)算法實(shí)現(xiàn)與軟件開發(fā)[D];電子科技大學(xué);2015年

9 閆青;基于預(yù)測(cè)算法的快速多尺度金字塔時(shí)空特征點(diǎn)計(jì)算算法研究[D];青島科技大學(xué);2016年

10 錢呂見;復(fù)雜網(wǎng)絡(luò)中基于角色傳遞性和對(duì)稱性的鏈接預(yù)測(cè)算法研究[D];蘭州大學(xué);2016年

，

本文編號(hào)：1969870