Link Prediction with Node Clustering Coefficient

Abstract

Predicting missing links in incomplete complex networks efficiently and accurately is still a challenging problem. The recently proposed CAR (Cannistrai-Alanis-Ravai) index shows the power of local link/triangle information in improving link-prediction accuracy. With the information of level-2 links, which are links between common-neighbors, most classical similarity indices can be improved. Nevertheless, calculating the number of level-2 links makes CAR index not efficient enough. Inspired by the idea of employing local link/triangle information, we propose a new similarity index with more local structure information. In our method, local link/triangle structure information can be conveyed by clustering coefficient of common neighbors directly. The reason why clustering coefficient has good effectiveness in estimating the contribution of a common-neighbor is because that it employs links existing between neighbors of the common-neighbor and these links have the same structural position with the candidate link to this common-neighbor. Ten real-world networks drawn from five various fields are used to test the performance of our method against to classical similarity indices and recently proposed CAR index. Two estimators: precision and AUP, are used to evaluate the accuracy of link prediction algorithms. Generally speaking, our new index only performs competitively with CAR, but it is a good complement to CAR for networks with not very high LCP-corr, which is a measure to estimate the correlation between number of common-neighbors and number of links between common-neighbors. Besides, the proposed index is also more efficient than CAR index.

8 pages, 3 figures

References in corpus (9)

• Hierarchical structure and the prediction of missing links in networks
• Predicting Missing Links via Local Information
• Community Structure in Jazz
• Missing and spurious interactions and the reconstruction of complex networks
• Effective and Efficient Similarity Index for Link Prediction of Complex Networks
• Collective credit allocation in science
• Emergent Complex Network Geometry
• Information filtering based on transferring similarity
• Role-similarity based functional prediction in networked systems: Application to the yeast proteome

Cited by in corpus (7)

• Improving local clustering based top-L link prediction methods via asymmetrical link clustering information
• A comparative study of similarity-based and GNN-based link prediction approaches
• Clustering Coefficient Reflecting Pairwise Relationships within Hyperedges
• Adaptive Similarity Function with Structural Features of Network Embedding for Missing Link Prediction
• A Preference Random Walk Algorithm for Link Prediction through Mutual Influence Nodes in Complex Networks
• Providing a Link Prediction Model based on Structural and Homophily Similarity in Social Networks
• Efficient and Adaptive Estimation of Local Triadic Coefficients