基于改進資源分配的鏈接預測算法

杜翠鳳 陳少權 蔣仕寶

【摘 要】共同鄰居的數量、共同鄰居的度數、節(jié)點之間的路徑長度等傳統(tǒng)鏈接預測忽視鄰居之間的關系以及節(jié)點本身的拓撲結構，導致其無法解決核心節(jié)點與周圍節(jié)點鏈接強度不同的問題。采用鄰域“結構洞”理論，并且結合節(jié)點本身拓撲結構以及共同鄰居的拓撲結構的影響來實現網絡的鏈接預測，提出基于改進資源分配的鏈接預測算法。實驗證明，該算法不僅更加準確地反映了動態(tài)網絡的拓撲結構，還能更加準確地預測節(jié)點之間是否存在鏈接關系。

【關鍵詞】鏈接預測；鄰域“結構洞”；資源強度；拓撲結構

Link Prediction Algorithm based on Improved Resource Allocation

DU Cuifeng， CHEN Shaoquan， JIANG Shibao

[Abstract] Traditional link prediction， such as the number of common neighbors， the degree of common neighbors and the path length between nodes， ignores the relationship between neighbors and the topological structure of nodes themselves. Thus， the different link intensity between the core node and surrounding nodes can not be solved. Using the theory of "structure hole" of the neighborhood， the link prediction of the network is realized by combining the topological structure of nodes themselves with the topological structure of the common neighbors. A link prediction algorithm based on improved resource allocation was proposed in this paper. Experimental results show that the algorithm not only reflects the topological structure of dynamic network more accurately， but also predicts more accurately whether there is a link between nodes.

[Key words]link prediction； "structure hole" of the neighborhood； resource intensity； topological structure

1 引言

在現實中，很多數據如移動通信網絡數據、社會關系數據以及生物學數據都能夠通過網絡進行描述。因此，鏈接預測有廣泛的應用前景[1]：通過分析移動用戶的通信社會網絡，引入時間序列算法，實現用戶鏈接的動態(tài)預測[2]；基于位置社交網絡的朋友關系預測研究；結合網絡鏈接和內容的局部社區(qū)發(fā)現研究；利用鏈路預測推斷中國航空網絡演化機制。因此，設計具有擴展性強的網絡鏈接預測模型，并用于社會網絡結構變化預測和社會網絡節(jié)點關系預測具有重要的意義。關于鏈接預測，以往的大多數研究主要建立在靜態(tài)社會網絡結構基礎上，這種靜態(tài)的研究大多數利用社會網絡鏈接之間的結構信息進行用戶關系以及網絡結構變化的預測。如基于劃分社區(qū)和差分共鄰節(jié)點貢獻的鏈路預測算法[3]；……