【摘要】：隨著信息技術的飛速發(fā)展,復雜系統(tǒng)的大量涌現,網絡科學作為一門新生學科也得到了快速發(fā)展。鏈路預測作為該領域中的一個重要課題,可以根據已有網絡拓撲結構等信息,來發(fā)現網絡中存在但未知的連邊和預測不存在但將來可能形成的連邊。鏈路預測在實踐中,可以在社交網絡中用來推薦好友、在基因調控中用來發(fā)現未知的調控關系;在理論上,則有助于揭示網絡的內部結構特征,促進對復雜系統(tǒng)演化機制的理解。目前的鏈路預測算法主要是根據節(jié)點屬性或者網絡拓撲結構來預測連邊,前者在實踐中存在節(jié)點屬性信息難以獲取、質量難以保證等問題,而后者僅需知道網絡的拓撲結構,但也存在預測精度不高的問題。本文研究屬于后者,即僅根據網絡拓撲結構來進行鏈路預測。本文首先在高階近鄰保持嵌入(High Order Proximity preserved Embedding,HOPE)算法的基礎上,提出了 一種鄰接嵌入(Adjacency Embedding,AE)算法,將網絡中的節(jié)點用低維、實值、稠密的向量進行表征,通過在低維空間中計算這些表征向量之間的距離來推斷節(jié)點的相似性,從而預測其間產生連邊的可能性。通過對10個真實網絡上的實驗分析可以得出,相對于HOPE算法,AE算法在保證預測精度的同時,減小了時間復雜度。其次,基于節(jié)點之間相似性應當可以傳遞的思想,本文提出基于AE算法的轉移相似性(Transferring Similarity Based on Adjacency Embedding,TSBAE)算法,結合各節(jié)點之間的潛在網絡結構相似性,克服了 HOPE算法以及AE算法中由于數據稀疏性導致的相距較遠的節(jié)點之間相似性預測不準確的問題。結果表明,無論是在無向網絡上,還是在有向網絡上,TSBAE算法都比基準算法、AE算法預測精度高。
【學位授予單位】：湖南大學
【學位級別】：碩士
【學位授予年份】：2018
【分類號】：O157.5
【圖文】：

絡結構的研究。本章將會介紹復雜網絡的網絡表示、鏈路預測問題、復雜網絡逡逑拓撲性質、評價指標以及本文實驗部分用作對比分析的基準算法。逡逑．１網絡表示逡逑根據連邊是否有權重，可以將圖分為加權圖和無權圖。在加權圖中，每一條逡逑都有一個權值，而無權圖的連邊不存在權值。本文進行鏈路預測時，只考慮無逡逑網絡。根據連邊是否有方向，可以將圖分為有向圖和無向圖。逡逑在無向無權網絡中，網絡可以由表示，其中ｒ為節(jié)點集，￡為連邊逡逑，其五ＧＧＦ）。節(jié)點對（0和節(jié)點對表示同一條連邊，連邊是逡逑有方向的，邊數Ｍ的最大取值是７Ｖ（ＡＭ）／２。簡單無權無向網絡滿足以下條件：逡逑（１）節(jié)點自己和自己不能連接，即網絡中不存在如的邊；逡逑（２邋）任意兩個節(jié)點之間最多只能有一條連邊；逡逑（３）任意兩個節(jié)點之間的連邊沒有方向性，即當時，五；逡逑（４）連邊之間沒有權重的概念，只代表節(jié)點之間關系的存在性。逡逑

邐（２．２）逡逑：ｅ（ｒ（．ｒ）0ｒ（＞＊））邋１0§欠：逡逑式中ｒ（ｘ）、ｒ00分別表示節(jié)點Ｘ和的鄰居的集合，應用ａ邋ａ方法計算相似性的時逡逑候，需要考慮共同鄰居的度的影響，網絡中節(jié)點Ｚ的度為屹。如圖２．３得到節(jié)點１逡逑的度為３，節(jié)點３的度為４，因此可以得到節(jié)點２和節(jié)點５的相似性為：逡逑_灒擔劍保▆0口３）＋１／（／嘆４戶３．７５６。同理，考慮節(jié)點４和節(jié)點５的ＡＡ相似性時，也需逡逑要考慮其共同鄰居節(jié)點３的度，因此可以得呀口３戶２．０９６。由此可得，逡逑根據ＡＡ相似性的預測方法，節(jié)點２和節(jié)點５之間產生連接的可能性大于節(jié)點４逡逑和節(jié)點５之間產生連接的可能性。逡逑１０逡逑

＜ｗ邋＾逡逑圖３．２邋ＨＯＰＥ算法示例圖逡逑圖３．２是ＨＯＰＥ算法學習有向圖示例，左邊是－個有向圖，右邊是左圖的嵌入逡逑向量空間。在左邊的有向圖中，實線農示觀察到的有向邊，虛線丨：的數字足Ｋａｔｚ逡逑相似性值。例如，根據非對稱的傳遞性，對Ｖ；—１（１兩條路輕，圖逡逑中可能存在連ａｖ，—％。根據公式（３．３），計算ｖｊｌｊｖ＾Ｋａｔｚ相似性，即０．０２，邋ｖ＃ｊｖ，Ｊ逡逑Ｋａｔｚ相似性為０．０１。另一方面，因為ｖ６—ｖ，在相反的方向，從ｖ，ｖ＃ｊＫａｔｚ相似性很逡逑小，即０。在嵌入空間中，箭頭表不頂點的嵌入向量，其中向量Ｗ和ｗ丨分別表不ｖ，？的逡逑源向量和目標向量。用邋＜和《；之間的內積（也就是0〃）作為從ｖ，．到．的近似距離，其逡逑２１逡逑

【相似文獻】

相關期刊論文 前10條

1 傅賢超;;基于GPU加速的圖像雙向相似性計算[J];現代計算機;2013年16期

2 馮永;張洋;;基于概念間邊權重的概念相似性計算方法[J];計算機應用;2012年01期

3 魏靜;;基于社交網絡服務位置的用戶相似性計算方法[J];計算機與現代化;2015年07期

4 劉文劍,許之偉,陳在禮;基于事例的工藝設計中形狀相似性計算方法[J];計算機集成制造系統(tǒng)-CIMS;2001年09期

5 艾均;李林志;蘇湛;鄔春學;;基于觀點傳播的改進相似性計算評分預測方法[J];上海理工大學學報;2017年03期

6 滕東興,戴國忠,程成,童秉樞;三維場景間相似性計算初探[J];工程圖學學報;2002年03期

7 王毅;唐歆瑜;謝治華;;基于向量空間模型的畢業(yè)論文相似性辨識研究[J];科學技術與工程;2007年09期

8 陳志敏;李志強;;基于用戶特征和項目屬性的協(xié)同過濾推薦算法[J];計算機應用;2011年07期

9 張東娜;周春光;劉彥斌;郭東偉;;一種基于WordNet和Corpus Statistics的語義相似性計算方法[J];吉林大學學報(理學版);2010年05期

10 宋艷;劉方愛;;綜合顏色與紋理的圖像檢索[J];計算機工程與設計;2007年17期

相關會議論文 前2條

1 朱靖波;陳文亮;姚天順;;面向TDT的主題相似性計算模型[A];語言計算與基于內容的文本處理——全國第七屆計算語言學聯(lián)合學術會議論文集[C];2003年

2 靳宇;蔡康穎;王文成;;基于相似性計算的大型工業(yè)3D模型壓縮算法[A];第18屆全國多媒體學術會議（NCMT2009）、第5屆全國人機交互學術會議（CHCI2009）、第5屆全國普適計算學術會議（PCC2009）論文集[C];2009年

相關博士學位論文 前1條

1 陳秀明;基于多粒度猶豫模糊語言信息的群推薦方法研究[D];合肥工業(yè)大學;2017年

相關碩士學位論文 前10條

1 劉曉鈺;基于網絡嵌入與轉移相似性的鏈路預測研究[D];湖南大學;2018年

2 史同欣;基于功能網絡的microRNA與疾病關聯(lián)預測方法研究[D];黑龍江大學;2017年

3 候冬雪;基于重疊社區(qū)發(fā)現的微博好友推薦系統(tǒng)研究[D];新疆大學;2018年

4 王麗敬;地理案例的空間相似性計算[D];山東科技大學;2010年

5 虞娟;基于集成案例推理的商務智能決策研究[D];合肥工業(yè)大學;2007年

6 雷琨;電子商務個性化推薦系統(tǒng)研究[D];電子科技大學;2012年

7 梁毅芳;支持變型設計的三維產品語義搜索研究[D];桂林電子科技大學;2016年

8 張東娜;基于WordNet的短文本語義相似性計算研究[D];吉林大學;2010年

9 黃偉;文檔的分類與相似性研究及其并行化實現[D];福建師范大學;2016年

10 劉永;數據挖掘在電信產品生命周期管理中的應用研究[D];湖南大學;2008年

本文編號：2751425