A study on the performance of similarity indices and its relationship with link prediction: a two-state random network case
arXiv:1809.00465 · doi:10.3938/jkps.73.1589
Abstract
Similarity index measures the topological proximity of node pairs in a complex network. Numerous similarity indices have been defined and investigated, but the dependency of structure on the performance of similarity indices has not been sufficiently investigated. In this study, we investigated the relationship between the performance of similarity indices and structural properties of a network by employing a two-state random network. A node in a two-state network has binary types that are initially given, and a connection probability is determined from the state of the node pair. The performance of similarity indices affects the number of links and the ratio of intra-connections to inter-connections. Similarity indices have different characteristics depending on their type. Local indices perform well in small-size networks and do not depend on whether the structure is intra-dominant or inter-dominant. In contrast, global indices perform better in large-size networks, and some such indices do not perform well in an inter-dominant structure. We also found that link prediction performance and the performance of similarity are correlated in both model networks and empirical networks. This relationship implies that link prediction performance can be used as an approximation for the performance of the similarity index when metadata for node types are unavailable. This relationship may help to find the appropriate index for given networks.
arXiv comment17 pages, 8 figures
References in corpus (20)
- Statistical mechanics of complex networks
- The structure and function of complex networks
- Finding community structure in networks using the eigenvectors of matrices
- Cooperative Game Theory Approaches for Network Partitioning
- The structure of scientific collaboration networks
- The diameter of the world wide web
- Hierarchical organization of modularity in metabolic networks
- Link Prediction in Complex Networks: A Survey
- Hierarchical structure and the prediction of missing links in networks
- Evolution of the social network of scientific collaborations
- Clustering and preferential attachment in growing networks
- Hierarchical Structure in Financial Markets
- Structure and tie strengths in mobile communication networks
- Predicting Missing Links via Local Information
- Self-similar community structure in organisations
- Recommender Systems
- Vertex similarity in networks
- Topology of correlation based minimal spanning trees in real and model markets
- The topology of the transcription regulatory network in the yeast, S. cerevisiae
- Accuracy Test for Link Prediction in terms of Similarity Index: The Case of WS and BA Models