Link prediction based on hyperbolic mapping with community structure for complex networks

Zuxi Wang, Yao Wu, Qingguang Li, Fengdong Jin and Wei Xiong

Physica A: Statistical Mechanics and its Applications, 2016, vol. 450, issue C, 609-623

Abstract: Link prediction is becoming a concerned topic in the complex network field in recent years. However, the existing link prediction methods are unsatisfactory for processing topological information and have high time complexity. This paper presents a novel method of Link Prediction with Community Structure (LPCS) based on hyperbolic mapping. Different from the existing link prediction methods, to utilize global structure information of the network, LPCS deals with the network from an overall perspective. LPCS takes full advantage of the community structure and its hierarchical organization to map networks into hyperbolic space, and obtains the hyperbolic coordinates which depict the global structure information of the network, then uses hyperbolic distance to describe the similarity between the nodes, finally predicts missing links according to the degree of the similarity between unconnected node pairs. The combination of the hyperbolic geometry framework and the community structure makes LPCS perform well in predicting missing links, and the time complexity of LPCS is linear, which makes LPCS can be applied to handle large scale networks in acceptable time. LPCS outperforms many state-of-the-art link prediction methods in the networks obeying power-law degree distribution.

Keywords: Link prediction; Community structure; Hierarchical organization; Hyperbolic geometry; Complex networks (search for similar items in EconPapers)
Date: 2016
References: View references in EconPapers View complete reference list from CitEc
Citations: View citations in EconPapers (7)

Downloads: (external link)
http://www.sciencedirect.com/science/article/pii/S0378437116000182
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:450:y:2016:i:c:p:609-623

DOI: 10.1016/j.physa.2016.01.010

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 ().