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

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

Research output: Contribution to journalArticlepeer-review

1 Citation (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.

Original languageEnglish
Pages (from-to)4011-4023
Number of pages13
JournalIEEE Transactions on Knowledge and Data Engineering
Issue number8
Publication statusPublished - 2022 Aug 1

All Science Journal Classification (ASJC) codes

  • Information Systems
  • Computer Science Applications
  • Computational Theory and Mathematics


Dive into the research topics of 'The Node-Similarity Distribution of Complex Networks and Its Applications in Link Prediction'. Together they form a unique fingerprint.

Cite this