Discriminative Distance-Based Network Indices with Application to Link Prediction - Département Informatique et Réseaux Accéder directement au contenu
Article Dans Une Revue The Computer Journal Année : 2018

Discriminative Distance-Based Network Indices with Application to Link Prediction

Résumé

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.
Fichier principal
Vignette du fichier
1703.06227.pdf (693.31 Ko) Télécharger le fichier
Origine : Fichiers produits par l'(les) auteur(s)

Dates et versions

hal-02287954 , version 1 (31-01-2024)

Identifiants

Citer

Mostafa Haghir Chehreghani, Albert Bifet, Talel Abdessalem. Discriminative Distance-Based Network Indices with Application to Link Prediction. The Computer Journal, 2018, 61 (7), pp.998-1014. ⟨10.1093/comjnl/bxy040⟩. ⟨hal-02287954⟩
43 Consultations
4 Téléchargements

Altmetric

Partager

Gmail Facebook X LinkedIn More