Predicting link directions via a recursive subgraph-based ranking
arXiv:1206.2199 · doi:10.1016/j.physa.2013.03.025
Abstract
Link directions are essential to the functionality of networks and their prediction is helpful towards a better knowledge of directed networks from incomplete real-world data. We study the problem of predicting the directions of some links by using the existence and directions of the rest of links. We propose a solution by first ranking nodes in a specific order and then predicting each link as stemming from a lower-ranked node towards a higher-ranked one. The proposed ranking method works recursively by utilizing local indicators on multiple scales, each corresponding to a subgraph extracted from the original network. Experiments on real networks show that the directions of a substantial fraction of links can be correctly recovered by our method, which outperforms either purely local or global methods.
arXiv comment6 pages, 5 figures; revised arguments for methods section; figures replotted; minor revisions
References in corpus (24)
- Statistical mechanics of complex networks
- The structure and function of complex networks
- Link Prediction in Complex Networks: A Survey
- Hierarchical structure and the prediction of missing links in networks
- Hierarchical Organization in Complex Networks
- Predicting Missing Links via Local Information
- Self-similarity of complex networks
- Hierarchical group dynamics in pigeon flocks
- Leaders in Social Networks, the Delicious Case
- Finding Scientific Gems with Google
- Journal Status
- Diffusion of scientific credits and the ranking of scientists
- Graph Evolution: Densification and Shrinking Diameters
- Maximal planar networks with large clustering coefficient and power-law degree distribution
- Hierarchy measure for complex networks
- Who is the best player ever? A complex network analysis of the history of professional tennis
- Generalized percolation in random directed networks
- Friendship networks and social status
- Potential Theory for Directed Networks
- Identifying the greatest team and captain - A complex network approach to cricket matches
- Mutually-Antagonistic Interactions in Baseball Networks
- Dynamic behaviors in directed networks
- Enhancing synchronization by directionality in complex networks
- Synchronization on Effective Networks
Cited by in corpus (6)
- Progresses and Challenges in Link Prediction
- Predicting missing links and their weights via reliable-route-based method
- Link prediction via linear optimization
- Playing the role of weak clique property in link prediction: A friend recommendation model
- Identifying Communities and Key Vertices by Reconstructing Networks from Samples
- DiffQue: Estimating Relative Difficulty of Questions in Community Question Answering Services