The Node-Similarity Distribution of Complex Networks and Its Applications in Link Prediction

Cunlai Pu, Jie Li, Jian Wang, Tony Q.S. Quek

研究成果: Article同行評審

1 引文 斯高帕斯(Scopus)


Over the years, quantifying the similarity of nodes has been a hot topic in network science, yet little has been known about the distribution of node-similarity. In this paper, we consider a typical measure of node-similarity called the common neighbor based similarity (CNS). By means of the generating function, we propose a general framework for calculating the CNS distributions of node sets in various networks. Particularly, we show that for the Erdös-Rényi random network, the CNS distribution of node sets of any size obeys the Poisson law. Furthermore, we connect the node-similarity distribution to the link prediction problem, and derive analytical solutions for two key evaluation metrics: i) precision and ii) area under the receiver operating characteristic curve (AUC). We also use the similarity distributions to optimize link prediction by i) deriving the expected prediction accuracy of similarity scores and ii) providing the optimal prediction priority of unconnected node pairs. Simulation results confirm our theoretical findings and also validate the proposed tools in evaluating and optimizing link prediction.

頁(從 - 到)4011-4023
期刊IEEE Transactions on Knowledge and Data Engineering
出版狀態Published - 2022 8月 1

All Science Journal Classification (ASJC) codes

  • 資訊系統
  • 電腦科學應用
  • 計算機理論與數學


深入研究「The Node-Similarity Distribution of Complex Networks and Its Applications in Link Prediction」主題。共同形成了獨特的指紋。