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

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

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

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

【相似文獻(xiàn)】

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

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

2 馮永;張洋;;基于概念間邊權(quán)重的概念相似性計算方法[J];計算機(jī)應(yīng)用;2012年01期

3 魏靜;;基于社交網(wǎng)絡(luò)服務(wù)位置的用戶相似性計算方法[J];計算機(jī)與現(xiàn)代化;2015年07期

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

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

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

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

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

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

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

相關(guān)會議論文 前2條

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

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

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

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

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

1 劉曉鈺;基于網(wǎng)絡(luò)嵌入與轉(zhuǎn)移相似性的鏈路預(yù)測研究[D];湖南大學(xué);2018年

2 史同欣;基于功能網(wǎng)絡(luò)的microRNA與疾病關(guān)聯(lián)預(yù)測方法研究[D];黑龍江大學(xué);2017年

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

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

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

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

7 梁毅芳;支持變型設(shè)計的三維產(chǎn)品語義搜索研究[D];桂林電子科技大學(xué);2016年

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

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

10 劉永;數(shù)據(jù)挖掘在電信產(chǎn)品生命周期管理中的應(yīng)用研究[D];湖南大學(xué);2008年

本文編號：2751425