本文選題：復(fù)雜網(wǎng)絡(luò)　切入點：鏈路預(yù)測　出處：《安徽大學(xué)》2017年碩士論文　論文類型：學(xué)位論文

【摘要】：真實世界中的很多研究領(lǐng)域都可以抽象為復(fù)雜網(wǎng)絡(luò),網(wǎng)絡(luò)中的節(jié)點表示對象,邊表示對象之間的關(guān)系。對復(fù)雜網(wǎng)絡(luò)的建模機理和建模過程的深入研究,可以解釋隱藏在自然界、社會界、生物界中的復(fù)雜系統(tǒng)的共同規(guī)律。研究復(fù)雜網(wǎng)絡(luò)對探索網(wǎng)絡(luò)形成及衍化機制有著重要的意義。其中,鏈路預(yù)測作為復(fù)雜網(wǎng)絡(luò)的重要研究方向越來越受到研究者們的關(guān)注。鏈路預(yù)測是指如何通過已知的網(wǎng)絡(luò)節(jié)點以及網(wǎng)絡(luò)結(jié)構(gòu)等信息預(yù)測網(wǎng)絡(luò)中尚未連接的兩個節(jié)點之間產(chǎn)生鏈接的可能性。隨著鏈路預(yù)測研究問題的不斷發(fā)展,很多預(yù)測算法被提出。其中,基于節(jié)點相似性的鏈路預(yù)測算法得到了廣泛的研究。然而,在利用網(wǎng)絡(luò)局部結(jié)構(gòu)信息研究鏈路預(yù)測問題方面的研究還不夠深入。網(wǎng)絡(luò)局部結(jié)構(gòu)對鏈路預(yù)測算法的性能有很大的影響,研究局部結(jié)構(gòu)特征對提升鏈路預(yù)測算法的預(yù)測效果有重大的意義。針對該問題,本文對利用網(wǎng)絡(luò)局部結(jié)構(gòu)信息研究鏈路預(yù)測算法問題進行深入研究,主要內(nèi)容包括以下三個方面:第一,網(wǎng)絡(luò)中的三元閉包結(jié)構(gòu)作為網(wǎng)絡(luò)中最小局部結(jié)構(gòu),具有結(jié)構(gòu)平衡和穩(wěn)定的特征。通過計算出每個節(jié)點在網(wǎng)絡(luò)中所占三元閉包的權(quán)重,并將該權(quán)重用于節(jié)點相似性指標中,提出了 TWCN、TWAA、TWRA三個相似性指標和具有調(diào)節(jié)參數(shù)的三個相似性指標:TWCN*、TWAA*、TWRA*。將新的相似性指標應(yīng)用到預(yù)測算法中,提出了 PWNW算法和PWNW_α算法。采用CN算法、AA算法和RA算法作為對比算法。實驗結(jié)果表明,PWNW-αα算法在預(yù)測精度方面比對比算法更具有優(yōu)勢。這說明利用三元閉包結(jié)構(gòu)信息能夠有效地提高預(yù)測算法的預(yù)測精度。通過分析實驗結(jié)果,發(fā)現(xiàn)了一個現(xiàn)象:在社交網(wǎng)絡(luò)中擁有較多三元閉包的節(jié)點,具有局部穩(wěn)定性,不傾向于建立更多的新鏈接。相反,擁有較少三元閉包的節(jié)點,具有局部不穩(wěn)定性,傾向于建立更多的新鏈接。這種現(xiàn)象也符合社會學(xué)中有關(guān)于新鏈接出現(xiàn)的現(xiàn)象。第二,根據(jù)節(jié)點擁有的三元閉包數(shù)目和節(jié)點度之間的關(guān)系可以計算節(jié)點的聚類系數(shù),該信息體現(xiàn)了節(jié)點的聚集能力。聚類系數(shù)作為重要的節(jié)點拓撲屬性不僅可以很好的體現(xiàn)局部結(jié)構(gòu)的緊密性,同時對產(chǎn)生鏈接也會起到一定的作用。而傳統(tǒng)的鏈路預(yù)測方法通常使用共同鄰居數(shù)目或節(jié)點的度來衡量節(jié)點之間的相似性。然而,節(jié)點之間的關(guān)系不僅與鄰居節(jié)點數(shù)目和度有關(guān),與節(jié)點所處的局部結(jié)構(gòu)有著密切的關(guān)系�；谶@個觀點,提出結(jié)合節(jié)點度和聚類系數(shù)的鏈路預(yù)測算法,簡稱NDCC算法。利用共同鄰居節(jié)點的度和聚類系數(shù)計算被預(yù)測節(jié)點對之間的相似性。不僅充分利用網(wǎng)絡(luò)局部結(jié)構(gòu)信息,還能夠體現(xiàn)出共同鄰居節(jié)點之間存在的差異性。與幾個常用的對比算法的相比,NDCC算法在預(yù)測精度上具有很好的優(yōu)勢。第三,上述兩種預(yù)測算法都只考慮了被預(yù)測節(jié)點對之間的共同鄰居節(jié)點,這種方式只能體現(xiàn)距目標節(jié)點兩步以內(nèi)的網(wǎng)絡(luò)結(jié)構(gòu)。其缺點是對網(wǎng)絡(luò)中不具有共同鄰居節(jié)點的節(jié)點對沒有預(yù)測能力。而新鏈接的產(chǎn)生不會局限于這種鄰居結(jié)構(gòu)。針對該問題,利用社會學(xué)強關(guān)系理論來提升預(yù)測算法的預(yù)測能力。強關(guān)系理論:三步以內(nèi)的關(guān)系都為強關(guān)系,強關(guān)系具有觸發(fā)行為。這種行為可以為未連接的節(jié)點提供更多的相互連接的機會。另外,節(jié)點的度和聚類系數(shù)體現(xiàn)出節(jié)點之間連接緊密程度,對網(wǎng)絡(luò)結(jié)構(gòu)有著很大的影響。結(jié)合這兩個方面,提出結(jié)合節(jié)點拓撲屬性和強關(guān)系的鏈路預(yù)測算法,簡稱TPSR算法。該算法不僅考慮了節(jié)點的拓撲屬性信息——節(jié)點的度和聚類系數(shù),還結(jié)合了強關(guān)系對新鏈接出現(xiàn)的貢獻。充分利用局部結(jié)構(gòu)信息來刻畫節(jié)點之間的相似性。與幾個傳統(tǒng)的算法相比,該算法具有更大的預(yù)測范圍和更強的預(yù)測能力。
[Abstract]:Many research fields in the real world can be abstracted as a complex network, the nodes in the network represent objects, edges represent relationships between objects. The further study of modeling mechanism and modeling process of complex networks, can explain the hidden in the nature, the society, the common law of complex system in the field of Biology. The research on complex networks to explore the mechanism of network formation and evolution has important significance. The link prediction as an important research direction of complex networks has attracted more and more attention of researchers. The link prediction is how to known network nodes and network structure information network connection is not predicted between two nodes have links with continuous possibilities. Research on the issue of link prediction, many prediction algorithm is proposed. Based on the similarity of node link prediction algorithm has been widely studied. However, the research is not deep enough in the use of network prediction of local structure information of link. The local structure of network has great effect on the algorithm performance prediction of link, study on local structure feature is of great significance to enhance the prediction effect of link prediction algorithm. Aiming at this problem, this paper deeply researches the problem of using the network prediction algorithm the local structure information of the link, the main contents include the following three aspects: first, three yuan closure in the network as the network structure has the characteristics of minimal local structure, balance and stability. Through calculating the weight of three yuan for closure of each node in the network, and the weights for node similarity index the TWCN, TWAA, TWRA, three similarity index and adjust the parameters of the three similarity index: TWCN*, TWAA*, TWRA*., the new similarity index is used to The prediction algorithm, PWNW algorithm is proposed and PWNW_ alpha algorithm. Using CN algorithm, AA algorithm and RA algorithm for comparison algorithm. Experimental results show that the PWNW- alpha alpha algorithm in prediction accuracy than the algorithm has more advantages. This shows that the prediction accuracy by three yuan closure structure information can effectively improve the prediction algorithm. Through the analysis of experimental results, found a phenomenon: many nodes have three yuan closure in a social network, with local stability, do not tend to establish a new link more. Instead, nodes have less three yuan closure, with local instability, tend to build more new links. This phenomenon is consistent with the society in a new link phenomenon. Second, clustering coefficient calculation node can according to the relationship between the number of three yuan closure and node degree node has the information, the node can reflect the As the node clustering coefficient. The topology is important not only can well reflect the tightness of the local structure, at the same time will also play a role in generating links. While the traditional link prediction methods usually use common neighbor number or nodes to measure the degree of similarity between nodes. However, the relationship between the nodes not only related with the number of neighbor nodes and the degree, has a close relationship with the local structure of nodes. Based on this point of view, combining with the link node degree and clustering coefficient prediction algorithm, referred to as NDCC algorithm. Computing similarity between pairs of nodes are predicted using the common neighbor node degree and clustering coefficient. Not only make full use of local network structure information, it can reflect the differences between common neighbor nodes. Compared with the comparison of several commonly used algorithms, NDCC algorithm in prediction accuracy is very good Advantage. Third, the above two kinds of prediction algorithms only consider the predicted node common neighbors between pairs of nodes, this way can only reflect the network structure from the target node within step two. The shortcomings of the common node in the network neighbor node does not have to have predictive ability. And not limited to the new link neighborhood structure. Aiming at this problem, the prediction ability of strong sociological relation theory to improve prediction algorithm. The strong relationship between the theory of relationship within step three have strong ties, strong relationship with trigger behavior. This behavior can provide more opportunities for the connected node is not connected. In addition, the degree of the node and cluster the coefficient reflects the degree of close connections between nodes, has a great impact on the network structure. The combination of these two aspects, combined with the proposed link node topology property and the strong relationship between prediction algorithm, referred to as TPS R algorithm. This algorithm considers not only the topological properties of node degree and clustering coefficient of information nodes, combined with a strong relationship between the emergence of the new link contribution. Make full use of local structure information to describe the similarity between nodes. Compared with several traditional algorithms, the algorithm has ability to predict a greater range of prediction and more.

【學(xué)位授予單位】：安徽大學(xué)
【學(xué)位級別】：碩士
【學(xué)位授予年份】：2017
【分類號】：O157.5

【參考文獻】

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

1 呂琳媛;;復(fù)雜網(wǎng)絡(luò)鏈路預(yù)測[J];電子科技大學(xué)學(xué)報;2010年05期

，

本文編號：1645719