The degree-related clustering coefficient and its application to link prediction

• We propose the degree-related clustering coefficient to estimate the cluster ability of nodes.
• The degree-related clustering coefficient exhibits a high robustness in estimating the cluster ability of nodes when the observed bias of links is considered.
• The DCP algorithm is proposed to achieve high accuracy and robustness on link prediction.
• The discussion about parameter setting improves our algorithm’s efficiency.
• The stability analysis shows that our index is stable when measuring node similarity.

Link prediction plays a significant role in explaining the evolution of networks. However it is still a challenging problem that has been addressed only with topological information in recent years. Based on the belief that network nodes with a great number of common neighbors are more likely to be connected, many similarity indices have achieved considerable accuracy and efficiency. Motivated by the natural assumption that the effect of missing links on the estimation of a node’s clustering ability could be related to node degree, in this paper, we propose a degree-related clustering coefficient index to quantify the clustering ability of nodes. Unlike the classical clustering coefficient, our new coefficient is highly robust when the observed bias of links is considered. Furthermore, we propose a degree-related clustering ability path (DCP) index, which applies the proposed coefficient to the link prediction problem. Experiments on 12 real-world networks show that our proposed method is highly accurate and robust compared with four common-neighbor-based similarity indices (Common Neighbors(CN), Adamic-Adar(AA), Resource Allocation(RA), and Preferential Attachment(PA)), and the recently introduced clustering ability (CA) index.