Discriminative Distance-Based Network Indices with Application to Link Prediction. (25th April 2018)

• Record Type: Journal Article
• Authors: Haghir Chehreghani, Mostafa; Bifet, Albert; Abdessalem, Talel
• Is Part Of: Computer journal. Volume 61:Number 7(2018)
• Page Start: 998
• Page End: 1014
• Publication Date: 2018-04-25
• Subjects: social network analysis -- distance-based network indices -- discriminative indices -- closeness centrality -- eccentricity -- average path length -- the tiny-world property -- link prediction; Computers -- Periodicals; 005.1
• DOI: 10.1093/comjnl/bxy040
• Languages: English
• ISSNs: 0010-4620

Abstract

Abstract: In distance-based network indices, the distance between two vertices is measured by the length of shortest paths between them. A shortcoming of this measure is that when it is used in real-world networks, a huge number of vertices may have exactly the same closeness/eccentricity scores. This restricts the applicability of these indices as they cannot distinguish vertices. Furthermore, in many applications, the distance between two vertices not only depends on the length of shortest paths but also on the number of shortest paths between them. In this paper, first we develop a new distance measure, proportional to the length of shortest paths and inversely proportional to the number of shortest paths, that yields discriminative distance-based centrality indices. We present exact and randomized algorithms for computation of the proposed discriminative indices. Then, by performing extensive experiments, we first show that compared with the traditional indices, discriminative indices have usually much more discriminability. Then, we show that our randomized algorithms can very precisely estimate average discriminative path length and average discriminative eccentricity, using only few samples. Then, we show that real-world networks have usually a tiny average discriminative path length, bounded by a constant (e.g. 2). We refer to this property as the tiny-world property . Finally, we present a novel link prediction method that uses discriminative distance to decide which vertices are more likely to form a link in future, and show its superior performance.