Prediction of missing links based on multi-resolution community division

Jingyi Ding, Licheng Jiao, Jianshe Wu, Yunting Hou and Yutao Qi

Physica A: Statistical Mechanics and its Applications, 2015, vol. 417, issue C, 76-85

Abstract: The investigation of link prediction in networks is an important issue in many disciplines. The research of prediction algorithms which required short time but high accuracy is still a challenging task. Most of the existing algorithms are based on the topological information of the networks, including the local or global similarity indices. It is found that the hierarchical organization and community structure information may indeed provide insights for link prediction. In this paper, we propose a simple link prediction method, which fully explore the community structure information of the networks. Firstly, the community structure of the networks under different resolutions is extracted. Then, a simple frequency statistical model is applied to calculate how many times that a pair of nodes divided into the same community under different resolutions. Finally, the probability of the missing links is calculated. The performance of our algorithm is demonstrated by comparing with other seven well-known methods on two kinds of networks in different scales. The results indicate that our approach not only has a good performance on the accuracy, but also has a lower time complexity than any other algorithms which are based on hierarchical structure of the network.

Keywords: Modularity density; Community detection; Multi-resolution; Link prediction (search for similar items in EconPapers)
Date: 2015
References: View references in EconPapers View complete reference list from CitEc
Citations: View citations in EconPapers (5)

Downloads: (external link)
http://www.sciencedirect.com/science/article/pii/S0378437114007638
Full text for ScienceDirect subscribers only. Journal offers the option of making the article available online on Science direct for a fee of $3,000

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:eee:phsmap:v:417:y:2015:i:c:p:76-85

DOI: 10.1016/j.physa.2014.09.005

Access Statistics for this article

Physica A: Statistical Mechanics and its Applications is currently edited by K. A. Dawson, J. O. Indekeu, H.E. Stanley and C. Tsallis

More articles in Physica A: Statistical Mechanics and its Applications from Elsevier
Bibliographic data for series maintained by Catherine Liu ().