【摘要】：鏈路預測作為復雜網(wǎng)絡重要的研究方向之一,在理論研究和實際應用中都意義重大。目前關于鏈路預測的研究主要是針對靜態(tài)網(wǎng)絡,忽略了網(wǎng)絡的時間演化信息,并且大部分的鏈路預測算法沒有考慮到鄰居節(jié)點之間的差異性,因此存在一定的不足。本文主要從以下幾個方面展開研究:1,在鏈路預測中區(qū)分不同的鄰居節(jié)點;2,利用網(wǎng)絡的歷史信息進行動態(tài)網(wǎng)絡鏈路預測;3,在鏈路預測中考慮節(jié)點中心性的影響。主要工作如下:1、研究了靜態(tài)網(wǎng)絡中基于互信息的鏈路預測算法。為了對不同的鄰居節(jié)點進行有效地區(qū)分,本文在原始互信息算法的基礎上考慮了共同鄰居的度信息,提出了改進的互信息算法。該算法不僅考慮了共同鄰居之間的結構信息,還通過節(jié)點的度信息來區(qū)分不同的鄰居節(jié)點。實驗表明:在靜態(tài)網(wǎng)絡中,區(qū)分不同的鄰居節(jié)點可以提高鏈路預測算法的精確度。2、改進的互信息算法在動態(tài)網(wǎng)絡中的應用。為了充分利用網(wǎng)絡演化過程中的歷史信息,本文利用時間序列模型表示動態(tài)網(wǎng)絡,并將改進的互信息算法與移動平均模型相結合,提出了改進的移動平均互信息算法。該算法不僅利用了網(wǎng)絡的結構信息和節(jié)點的度信息,還考慮了歷史信息對當前時刻的影響。實驗表明,當網(wǎng)絡中存在較多連邊時,改進的移動平均互信息算法在鏈路預測中表現(xiàn)優(yōu)異。3、研究了動態(tài)網(wǎng)絡鏈路預測中節(jié)點中心性的作用�？紤]到不同節(jié)點在網(wǎng)絡中重要性的差異,首先通過節(jié)點中心性方法來衡量節(jié)點的重要性,然后進行歸一化處理,并與已有的鏈路預測算法相結合,將結合后的算法應用于動態(tài)網(wǎng)絡鏈路預測。實驗結果表明,考慮節(jié)點中心性的鏈路預測算法在動態(tài)網(wǎng)絡中有較高的精確度。
【圖文】：

對于復雜系統(tǒng)的描述和研宄一般是通過復雜網(wǎng)絡來實現(xiàn)的。逡逑對復雜網(wǎng)絡的研宄有著悠久的歷史，最初起源于１９３６年歐拉解決的“七橋逡逑問題”。如圖１．１所示，“七橋問題”是指如何從一個地方（Ａ、Ｂ、Ｃ、Ｄ）出逡逑發(fā)，走遍Ａ、Ｂ、Ｃ和Ｄ四個地方，最后回到起點，條件是每座橋走且僅走一逡逑遍［１，２】。歐拉將每個出發(fā)點抽象為圖中的節(jié)點，每座橋可以理想化為一條邊，因逡逑此，該問題就變成了如何通過一筆畫出圖１．１（ｂ）的圖形。逡逑ｘ逡逑（邋Ｂ邐Ａ邐抽象邋＇）Ｂ邋Ｈ邐逡逑Ｄ邐Ｄ逡逑（ａ）邐（ｂ）逡逑圖１．１哥尼斯堡七橋問題逡逑Ｆｉｇ邋１．１邋Ｔｈｅ邋ｐｒｏｂｌｅｍ邋ｏｆ邋ｓｅｖｅｎ邋ｂｒｉｄｇｅｓ邋ｉｎ邋Ｋｏｎｉｇｓｂｅｒｇ逡逑二十世紀六十年代，Ｅｒｄｏｓ和Ｒｅｎｙｉ連續(xù)發(fā)表了三篇文章，從而提出了著名逡逑的隨機圖（ＥＲ）模型［３＿５］，從此復雜網(wǎng)絡理論在數(shù)學領域有了系統(tǒng)化的研宄。逡逑ＥＲ模型的大致含義如下：對于一個節(jié)點數(shù)為Ｎ的網(wǎng)絡，在一定時間內，這Ｎ逡逑個節(jié)點之間隨機相連，其中連接的概率均為；？，，且ｐ是個固定值，由此形成的逡逑網(wǎng)絡叫隨機網(wǎng)絡。該模型的提出極大地促進了復雜網(wǎng)絡的研究進展

Ｆｉｇ邋２．１邋Ｅｘａｍｐｌｅ邋ｏｆ邋ｕｎｄｉｒｅｃｔｅｄ邋ｎｅｔｗｏｒｋ逡逑在無向網(wǎng)絡中，如果0＾ｉ0）ｅ￡，則說明頂點／和頂點＿／之間是相鄰的，即逡逑頂點／是頂點＿／的鄰居，記ｒ（0為頂點／的所有鄰居集合。如圖２．１所示，頂點逡逑６的鄰居有頂點１、頂點３和頂點５，用公式表示為ｒ（６）邋＝邋｛１，３，５｝。如果用鄰接逡逑矩陣來表示圖，則表達式如（２．１）所不：逡逑Ｗ邋Ｗ邋（２，）逡逑Ｉ邋１邐（Ｖｉ，ｖ；）邋ｅ邋Ｅ逡逑９逡逑
【學位授予單位】：中國科學技術大學
【學位級別】：碩士
【學位授予年份】：2018
【分類號】：O157.5;TP301.6

【參考文獻】

相關期刊論文 前5條

1 李靜茹;喻莉;趙佳;;加權社交網(wǎng)絡節(jié)點中心性計算模型[J];電子科技大學學報;2014年03期

2 任曉龍;呂琳媛;;網(wǎng)絡重要節(jié)點排序方法綜述[J];科學通報;2014年13期

3 傅穎斌;陳羽中;;基于鏈路預測的微博用戶關系分析[J];計算機科學;2014年02期

4 付立東;高琳;馬小科;;基于社團檢測的復雜網(wǎng)絡中心性方法[J];中國科學:信息科學;2012年05期

5 呂琳媛;;復雜網(wǎng)絡鏈路預測[J];電子科技大學學報;2010年05期

本文編號：2599849