Discriminative Distance-Based Network Indices and the Tiny-World Property

Mostafa Haghir Chehreghani, Albert Bifet, Talel Abdessalem

Introduction

In the field of network science, understanding the structural importance of nodes is critical for applications ranging from social network analysis to infrastructure planning. Traditionally, distance-based indices such as closeness centrality and eccentricity have served as the primary tools for this task. However, these metrics, which rely solely on the length of the shortest path (geodesic distance), often fail to capture the nuanced connectivity of real-world graphs. This paper introduces a novel metric, Discriminative Distance ($dd$), which incorporates path redundancy to provide a more granular and functionally accurate view of network structure, revealing what the authors term the "tiny-world" property.

The Problem with Traditional Metrics

Traditional distance-based measures suffer from three significant limitations:

  1. Poor Discriminability: In large-scale networks, many nodes often receive identical scores. For instance, in the Yahoo web graph, nearly 30% of nodes share the same eccentricity, making it impossible to rank them effectively.
  2. Ignoring Redundancy: Traditional metrics treat a node connected by a single path the same as a node connected by multiple redundant paths of the same length. Intuitively, a node with more "backup" routes is more accessible and central.
  3. Mathematical Instability: Extending these metrics to directed or disconnected graphs often results in undefined values or requires controversial mathematical workarounds.

The Discriminative Distance Metric

To address these flaws, the authors propose the Discriminative Distance ($dd$). For any two vertices $v$ and $u$, the distance is defined as: $$dd(v, u) = \frac{d(v, u)}{\sigma(v, u)}$$ where $d(v, u)$ is the shortest path length and $\sigma(v, u)$ is the number of shortest paths between them. By dividing the geodesic distance by the number of shortest paths, the metric rewards connectivity redundancy.

Comparison of path redundancy between nodes $v$ and $u$ in different graph structures.

As shown in the figure above, while the geodesic distance between $v$ and $u$ might be the same in both scenarios (a) and (b), the discriminative distance in (a) would be significantly lower due to the multiple available paths. This allows the metric to "break ties" that traditional closeness centrality cannot.

Algorithms for Scale

Calculating all-pairs shortest paths and their counts is computationally intensive ($O(V \cdot E)$). To make this practical for massive datasets, the paper introduces two approaches:

  • DCC (Discriminative Closeness Calculator): An exact algorithm that modifies BFS or Dijkstra’s algorithm to count shortest paths simultaneously with distance calculation.
  • RANDOMADPL: A randomized approximation algorithm that uses uniform sampling to estimate network-wide averages. This allows researchers to achieve high-confidence results using only a fraction (e.g., 0.1%) of the nodes.

Key Insights: The Tiny-World Property

The most significant discovery enabled by this new metric is the "Tiny-World" property. While the well-known "Small-World" property states that average path lengths grow logarithmically with network size, the authors found that the average discriminative path length is often bounded by a tiny constant (typically $\approx 2$), regardless of the network's total size.

A network structure illustrating how multiple shortest paths between $s$ and $t$ contribute to the tiny-world property.

This suggests that real-world networks are functionally much "tinier" than previously thought. The high density of alternative shortest paths in these networks makes nodes exceptionally reachable from one another.

Results and Impact

The authors evaluated their methods on 13 diverse datasets, including social networks like Flickr and web graphs like Stanford.

  • Discriminability Boost: In the flickr dataset, discriminative closeness achieved 92.7% discriminability, a massive improvement over the 4.4% offered by traditional closeness.
  • Efficiency: The RANDOMADPL algorithm proved highly accurate, with relative errors typically under 5% even with very small sample sizes.
  • Accessibility: The metric captures "accessibility" rather than just distance. A node that is slightly further away but reachable via many redundant paths is often more central than a node that relies on a single "bridge" edge.

Conclusion

By factoring in path redundancy, Discriminative Distance provides a more powerful lens for network analysis. It not only solves the tie-breaking problem inherent in traditional metrics but also reveals the "tiny-world" nature of complex systems. Future work may focus on optimizing top-$k$ node identification and further exploring the correlation between discriminative distance and other centrality measures like PageRank.

Summary updated

Abstract

In large networks, using the length of shortest paths as the distance measure has shortcomings. A well-studied shortcoming is that extending it to disconnected graphs and directed graphs is controversial. The second shortcoming is that a huge number of vertices may have exactly the same score. The third shortcoming is that 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. In this paper, first we develop a new distance measure between vertices of a graph that yields discriminative distance-based centrality indices. This measure is proportional to the length of shortest paths and inversely proportional to the number of shortest paths. We present algorithms for exact computation of the proposed discriminative indices. Second, we develop randomized algorithms that precisely estimate average discriminative path length and average discriminative eccentricity and show that they give $(\epsilon,\delta)$-approximations of these indices. Third, we perform extensive experiments over several real-world networks from different domains. In our experiments, we first show that compared to 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). Fourth, in order to better motivate the usefulness of our proposed distance measure, 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 compared to the well-known existing measures.
BibTeX
@misc{chehreghani2017discriminative,
  author = {Mostafa Haghir Chehreghani and Albert Bifet and Talel Abdessalem},
  title = {{Discriminative Distance-Based Network Indices and the Tiny-World Property}},
  year = {2017},
  eprint = {1703.06227},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/1703.06227},
}
Figure