NetSRE: Link predictability measuring and regulating

摘要

Link prediction is an elemental issue for network-structured data mining, which has already found a wide range of applications. The organization of real-world networks usually embodies both regularities and irregularities, and the precision of link prediction algorithms coincides with the portion of a network being categorized as regular. Quantifying and controlling how well an unobserved link can be predicted is a fundamental problem in link prediction. This paper proposes a structural regularity-exploring architecture, called NetSRE, for measuring and regulating link predictability of networks. The proposed NetSRE assumes that there are consistent interaction patterns across the local subgraphs of networks and one of them can be represented by a linear summation of the others, and thus, link predictability can be characterized by the self-representation degree of network structures. Specifically, NetSRE includes (1) a low Frobenius norm pursuit-based self-representation network model for predicting the “true” underlying networks, (2) a “structural regularity” index for measuring the link predictability of networks, i.e., the inherent difficulty of link prediction independent of specific algorithms, and (3) an importance measuring method for structural role exploration of network links and a link-based structure perturbation algorithm for link predictability regulation. Experimental results on real-world networks validate the performance of our method. It is found that real-world networks have various structural regularities and link predictability can be estimated based on structure mining directly. We show that network heterogeneity provides a way to intrinsically segregate network links into qualitatively distinct groups, which have different influences on the link predictability of networks.