發(fā)布時(shí)間：2018-09-07 19:56

【摘要】：近年來(lái),隨著web2.0技術(shù)的迅猛發(fā)展,社會(huì)網(wǎng)絡(luò)的規(guī)模也不斷發(fā)展壯大,復(fù)雜網(wǎng)絡(luò)分析對(duì)研究者們來(lái)說(shuō)成為一項(xiàng)重要的研究任務(wù)。而鏈接預(yù)測(cè)問題作為復(fù)雜網(wǎng)絡(luò)分析的一個(gè)研究分支,其在社會(huì)網(wǎng)絡(luò)、生物信息網(wǎng)絡(luò)、食物網(wǎng)等諸多與人類生活密切相關(guān)的方面都有著廣泛的應(yīng)用價(jià)值。因此,本文深入學(xué)習(xí)了鏈接預(yù)測(cè)問題。在數(shù)據(jù)挖掘領(lǐng)域,鏈接預(yù)測(cè)問題扮演著十分重要的角色,其目的是根據(jù)網(wǎng)絡(luò)已知的各類信息估計(jì)兩個(gè)不相連的節(jié)點(diǎn)存在鏈接的概率。鏈接預(yù)測(cè)作為數(shù)據(jù)挖掘領(lǐng)域的重要研究?jī)?nèi)容,已經(jīng)被研究許多年了。它被分為兩種類型:一預(yù)測(cè)未知鏈接;二預(yù)測(cè)未來(lái)鏈接。第一種致力于挖掘應(yīng)該存在但未被人所知的鏈接,第二種致力于預(yù)測(cè)現(xiàn)有網(wǎng)絡(luò)中不存在但未來(lái)可能發(fā)生的鏈接。本文主要集中于預(yù)測(cè)未知的鏈接。現(xiàn)存的鏈接預(yù)測(cè)算法大體分為四類:一基于拓?fù)浣Y(jié)構(gòu)的鏈接預(yù)測(cè);二基于社會(huì)學(xué)理論的鏈接預(yù)測(cè);三基于機(jī)器學(xué)習(xí)的鏈接預(yù)測(cè);四基于矩陣分析的鏈接預(yù)測(cè)。本文就第一點(diǎn)和第四點(diǎn)展開了深入的研究。提出了以下幾點(diǎn)創(chuàng)新點(diǎn):1.本文針對(duì)基于拓?fù)浣Y(jié)構(gòu)的鏈接預(yù)測(cè)算法進(jìn)行改進(jìn),將CN算法和RA算法結(jié)合在一起,提出一種新的相似度度量方法CN-RA。這種方法不僅考慮社會(huì)網(wǎng)絡(luò)中共同鄰居數(shù)目,還考慮了單個(gè)共同鄰居節(jié)點(diǎn)對(duì)節(jié)點(diǎn)相似度的影響,同CN算法、RA算法和其它基準(zhǔn)的基于拓?fù)浣Y(jié)構(gòu)的算法相比,取得了更好的預(yù)測(cè)效果。2.本文提出一種多特征融合的鏈接預(yù)測(cè)框架。受到已有的基于矩陣填充的鏈接預(yù)測(cè)方法的啟發(fā),我們深入研究了增廣拉格朗日乘子算法-ALM。使用鄰接矩陣表示社會(huì)網(wǎng)絡(luò),由于社會(huì)網(wǎng)絡(luò)鄰接矩陣具有低秩性,因此我們可以使用ALM算法優(yōu)化鄰接矩陣,解決鏈接預(yù)測(cè)問題�；诖朔椒�,本文提出了一種多特征融合的鏈接預(yù)測(cè)框架,將拓?fù)浣Y(jié)構(gòu)特征和低秩特征融合在一起,進(jìn)行了實(shí)驗(yàn)驗(yàn)證。實(shí)驗(yàn)結(jié)果表明,這種框架與傳統(tǒng)基于拓?fù)浣Y(jié)構(gòu)的方法和單獨(dú)使用ALM算法相比,更進(jìn)一步提高了預(yù)測(cè)效果。同時(shí),這個(gè)框架還保證了可擴(kuò)展性,可將其它特征(如節(jié)點(diǎn)屬性信息、社會(huì)學(xué)信息)融合進(jìn)來(lái),進(jìn)一步分析動(dòng)態(tài)網(wǎng)絡(luò)鏈接預(yù)測(cè)問題。為了驗(yàn)證以上兩點(diǎn)的可行性與有效性,本文選取了三個(gè)真實(shí)數(shù)據(jù)集進(jìn)行實(shí)驗(yàn)驗(yàn)證,分別為USAir數(shù)據(jù)集、Net Science數(shù)據(jù)集、Jazz數(shù)據(jù)集,使用CN、AA、PA、RA、Jaccard方法作為基準(zhǔn)方法,使用ROC曲線和AUC值評(píng)估實(shí)驗(yàn)結(jié)果。實(shí)驗(yàn)結(jié)果表明,本文提出的方法得到了預(yù)期的預(yù)測(cè)效果,而結(jié)合了多特征的鏈接預(yù)測(cè)框架更是顯著提高了預(yù)測(cè)效果。
[Abstract]:In recent years, with the rapid development of web2.0 technology, the scale of social network is also growing, complex network analysis has become an important research task for researchers. As a branch of complex network analysis, link prediction is widely used in social network, biological information network, food web and many other aspects closely related to human life. Therefore, this paper delves into the problem of link prediction. In the field of data mining, the problem of link prediction plays a very important role in estimating the probability of the existence of links between two disconnected nodes based on the known information of the network. As an important research content in the field of data mining, link prediction has been studied for many years. It is divided into two types: one predicting unknown links and the other predicting future links. The first is to mine links that should exist but are not known, and the second is to predict links that do not exist in existing networks but may occur in the future. This paper focuses on predicting unknown links. The existing link prediction algorithms are divided into four categories: link prediction based on topology; link prediction based on sociological theory; link prediction based on machine learning; and link prediction based on matrix analysis. In this paper, the first point and the fourth point of the in-depth study. Put forward the following points of innovation: 1. In this paper, the link prediction algorithm based on topology structure is improved, and a new similarity measure method, CN-RA., is proposed by combining CN algorithm with RA algorithm. This method not only considers the number of common neighbors in the social network, but also considers the influence of a single common neighbor node on the node similarity. Compared with the CN algorithm and other benchmark algorithms based on topology structure, this method is more effective than the traditional algorithm. Better prediction effect. 2. 2. In this paper, a link prediction framework based on multi-feature fusion is proposed. Inspired by the existing link prediction methods based on matrix filling, we deeply study the augmented Lagrangian multiplier algorithm-ALM. Because the adjacent matrix of social network is of low rank, we can use ALM algorithm to optimize the adjacent matrix and solve the problem of link prediction. Based on this method, a link prediction framework based on multi-feature fusion is proposed, which combines topology features with low-rank features, and is verified by experiments. The experimental results show that compared with the traditional topology based method and the ALM algorithm alone, the prediction effect of this framework is further improved. At the same time, the framework also ensures scalability, and other features (such as node attribute information, sociological information) can be combined to further analyze the dynamic network link prediction problem. In order to verify the feasibility and validity of the above two points, this paper selects three real data sets for experimental verification, one is the USAir dataset net Science dataset and the other is the CN,AA,PA,RA,Jaccard method. ROC curves and AUC values were used to evaluate the experimental results. The experimental results show that the method proposed in this paper can achieve the expected prediction effect, and the link prediction framework with multiple features can significantly improve the prediction effect.
【學(xué)位授予單位】：吉林大學(xué)
【學(xué)位級(jí)別】：碩士
【學(xué)位授予年份】：2017
【分類號(hào)】：O157.5;TP311.13

【相似文獻(xiàn)】

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

1 龔振和;基于矩陣表示和合一操作的并行推理方法[J];計(jì)算機(jī)學(xué)報(bào);1988年02期

2 ;1998年第24期擂臺(tái)賽點(diǎn)評(píng)[J];電腦愛好者;1999年06期

3 郝家欍;矩陣、概率與統(tǒng)計(jì)自學(xué)參考[J];煤礦機(jī)械;1985年03期

4 譚瓊;如何形成網(wǎng)絡(luò)流規(guī)劃中的路矩陣[J];系統(tǒng)工程理論與實(shí)踐;1992年04期

5 王以德,賈力普;快速算法及矩陣的新式分解[J];計(jì)算機(jī)應(yīng)用與軟件;1984年03期

6 黃祿炳,黃顯高;矩陣應(yīng)用中值得注意的問題[J];西安郵電學(xué)院學(xué)報(bào);1997年01期

7 李大農(nóng);漢字鄰接頻率的矩陣表示[J];黃岡師專學(xué)報(bào);1997年01期

8 楊秀文,嚴(yán)尚安,張潔,曾順鵬;可達(dá)矩陣的新求法[J];電子科技大學(xué)學(xué)報(bào);2000年06期

9 樊葆華;竇強(qiáng);張鶴穎;;網(wǎng)絡(luò)演算的矩陣解釋[J];計(jì)算機(jī)學(xué)報(bào);2009年12期

10 馮春生;;2維空間填充曲線的塊矩陣迭代法[J];計(jì)算機(jī)工程與應(yīng)用;2011年12期

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

1 楊偉;;模糊軟矩陣及其格結(jié)構(gòu)[A];中國(guó)運(yùn)籌學(xué)會(huì)模糊信息與模糊工程分會(huì)第五屆學(xué)術(shù)年會(huì)論文集[C];2010年

2 陳文康;姚陳;;對(duì)Bond變換的若干思考[A];中國(guó)地球物理·2009[C];2009年

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

1 金_g;IT自考學(xué)習(xí)資源大搜索（一）[N];中國(guó)電腦教育報(bào);2002年

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

1 賀楊成;半監(jiān)督低秩矩陣學(xué)習(xí)及其應(yīng)用[D];上海交通大學(xué);2015年

2 陳梅香;廣義二次矩陣的若干研究[D];福建師范大學(xué);2016年

3 郝曉麗;粒度格矩陣空間模型及其應(yīng)用研究[D];太原理工大學(xué);2009年

4 韓曦;基于多維矩陣的移動(dòng)通信信號(hào)檢測(cè)及參數(shù)估計(jì)技術(shù)研究[D];北京郵電大學(xué);2013年

5 張芬;基于低秩矩陣填充的相位檢索方法研究[D];安徽大學(xué);2015年

6 方茂中;關(guān)于矩陣填充和非負(fù)矩陣的研究[D];華東師范大學(xué);2008年

7 陳娜;矩陣恢復(fù)算法及誤差分析[D];華中科技大學(xué);2012年

8 耿娟;低秩矩陣與張量完整化問題的算法研究[D];中國(guó)農(nóng)業(yè)大學(xué);2014年

9 田貴賢;圖譜理論和幾類矩陣的譜與組合特征研究[D];電子科技大學(xué);2009年

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

1 崔翔;基于卷積壓縮感知的確定性測(cè)量矩陣研究[D];北京化工大學(xué);2015年

2 吳曼;SDN在IP網(wǎng)絡(luò)的流量調(diào)度應(yīng)用研究[D];電子科技大學(xué);2015年

3 王浩;帶噪聲抑制的流量矩陣估計(jì)方法研究[D];電子科技大學(xué);2015年

4 張婷婷;基于低秩矩陣填充與恢復(fù)的圖像去噪方法研究[D];河北工業(yè)大學(xué);2015年

5 鄧愛淘;基于LDPC碼的壓縮感知測(cè)量矩陣研究[D];湘潭大學(xué);2015年

6 白平;基于拓展全息矩陣的變胞機(jī)構(gòu)創(chuàng)新設(shè)計(jì)研究[D];武漢輕工大學(xué);2015年

7 吳越;Vandermonde矩陣的理論與應(yīng)用研究[D];安徽大學(xué);2016年

8 曹萌;幾類Bezout矩陣的研究[D];安徽大學(xué);2016年

9 唐云;基于Spark的大規(guī)模分布式矩陣運(yùn)算算法研究與實(shí)現(xiàn)[D];南京大學(xué);2016年

10 陳露;關(guān)于矩陣運(yùn)算的公開可驗(yàn)委托計(jì)算的研究與分析[D];蘇州大學(xué);2016年

，

本文編號(hào)：2229264