【摘要】：近年來,隨著web2.0技術的迅猛發(fā)展,社會網(wǎng)絡的規(guī)模也不斷發(fā)展壯大,復雜網(wǎng)絡分析對研究者們來說成為一項重要的研究任務。而鏈接預測問題作為復雜網(wǎng)絡分析的一個研究分支,其在社會網(wǎng)絡、生物信息網(wǎng)絡、食物網(wǎng)等諸多與人類生活密切相關的方面都有著廣泛的應用價值。因此,本文深入學習了鏈接預測問題。在數(shù)據(jù)挖掘領域,鏈接預測問題扮演著十分重要的角色,其目的是根據(jù)網(wǎng)絡已知的各類信息估計兩個不相連的節(jié)點存在鏈接的概率。鏈接預測作為數(shù)據(jù)挖掘領域的重要研究內容,已經(jīng)被研究許多年了。它被分為兩種類型:一預測未知鏈接;二預測未來鏈接。第一種致力于挖掘應該存在但未被人所知的鏈接,第二種致力于預測現(xiàn)有網(wǎng)絡中不存在但未來可能發(fā)生的鏈接。本文主要集中于預測未知的鏈接�，F(xiàn)存的鏈接預測算法大體分為四類:一基于拓撲結構的鏈接預測;二基于社會學理論的鏈接預測;三基于機器學習的鏈接預測;四基于矩陣分析的鏈接預測。本文就第一點和第四點展開了深入的研究。提出了以下幾點創(chuàng)新點:1.本文針對基于拓撲結構的鏈接預測算法進行改進,將CN算法和RA算法結合在一起,提出一種新的相似度度量方法CN-RA。這種方法不僅考慮社會網(wǎng)絡中共同鄰居數(shù)目,還考慮了單個共同鄰居節(jié)點對節(jié)點相似度的影響,同CN算法、RA算法和其它基準的基于拓撲結構的算法相比,取得了更好的預測效果。2.本文提出一種多特征融合的鏈接預測框架。受到已有的基于矩陣填充的鏈接預測方法的啟發(fā),我們深入研究了增廣拉格朗日乘子算法-ALM。使用鄰接矩陣表示社會網(wǎng)絡,由于社會網(wǎng)絡鄰接矩陣具有低秩性,因此我們可以使用ALM算法優(yōu)化鄰接矩陣,解決鏈接預測問題�；诖朔椒�,本文提出了一種多特征融合的鏈接預測框架,將拓撲結構特征和低秩特征融合在一起,進行了實驗驗證。實驗結果表明,這種框架與傳統(tǒng)基于拓撲結構的方法和單獨使用ALM算法相比,更進一步提高了預測效果。同時,這個框架還保證了可擴展性,可將其它特征(如節(jié)點屬性信息、社會學信息)融合進來,進一步分析動態(tài)網(wǎng)絡鏈接預測問題。為了驗證以上兩點的可行性與有效性,本文選取了三個真實數(shù)據(jù)集進行實驗驗證,分別為USAir數(shù)據(jù)集、Net Science數(shù)據(jù)集、Jazz數(shù)據(jù)集,使用CN、AA、PA、RA、Jaccard方法作為基準方法,使用ROC曲線和AUC值評估實驗結果。實驗結果表明,本文提出的方法得到了預期的預測效果,而結合了多特征的鏈接預測框架更是顯著提高了預測效果。
[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.
【學位授予單位】：吉林大學
【學位級別】：碩士
【學位授予年份】：2017
【分類號】：O157.5;TP311.13

【相似文獻】

相關期刊論文 前10條

1 龔振和;基于矩陣表示和合一操作的并行推理方法[J];計算機學報;1988年02期

2 ;1998年第24期擂臺賽點評[J];電腦愛好者;1999年06期

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

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

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

6 黃祿炳,黃顯高;矩陣應用中值得注意的問題[J];西安郵電學院學報;1997年01期

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

8 楊秀文,嚴尚安,張潔,曾順鵬;可達矩陣的新求法[J];電子科技大學學報;2000年06期

9 樊葆華;竇強;張鶴穎;;網(wǎng)絡演算的矩陣解釋[J];計算機學報;2009年12期

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

相關會議論文 前2條

1 楊偉;;模糊軟矩陣及其格結構[A];中國運籌學會模糊信息與模糊工程分會第五屆學術年會論文集[C];2010年

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

相關重要報紙文章 前1條

1 金_g;IT自考學習資源大搜索（一）[N];中國電腦教育報;2002年

相關博士學位論文 前9條

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

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

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

4 韓曦;基于多維矩陣的移動通信信號檢測及參數(shù)估計技術研究[D];北京郵電大學;2013年

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

6 方茂中;關于矩陣填充和非負矩陣的研究[D];華東師范大學;2008年

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

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

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

相關碩士學位論文 前10條

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

2 吳曼;SDN在IP網(wǎng)絡的流量調度應用研究[D];電子科技大學;2015年

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

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

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

6 白平;基于拓展全息矩陣的變胞機構創(chuàng)新設計研究[D];武漢輕工大學;2015年

7 吳越;Vandermonde矩陣的理論與應用研究[D];安徽大學;2016年

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

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

10 陳露;關于矩陣運算的公開可驗委托計算的研究與分析[D];蘇州大學;2016年

，

本文編號：2229264