Navigability evaluation of complex networks by greedy routing efficiency

Alessandro Muscoloni, Carlo Vittorio CannistraciarXiv 2019 · DOI · OpenReview

Abstract

Network navigability is a key feature of complex networked systems. For a network embedded in a geometrical space, maximization of greedy routing (GR) measures based on the node geometrical coordinates can ensure efficient greedy navigability. In PNAS, Seguin et al. (PNAS 2018, vol. 115, no. 24) define a measure for quantifying the efficiency of brain network navigability in the Euclidean space, referred to as the efficiency ratio, whose formula exactly coincides with the GR-score (GR-efficiency) previously published by Muscoloni et al. (Nature Communications 2017, vol. 8, no. 1615). In this Letter, we point out potential flaws in the study of Seguin et al. regarding the discussion of the GR evaluation. In particular, we revise the concept of GR navigability, together with a careful discussion of the advantage offered by the new proposed GR-efficiency measure in comparison to the main measures previously adopted in literature. Finally, we clarify and standardize the GR-efficiency terminology in order to simplify and facilitate the discussion in future studies.

Introduction

In many complex networks, such as the internet or neural circuits, nodes are embedded within a geometric space. To move information efficiently without a global map, these systems often employ greedy routing (GR): a protocol where a packet is passed to whichever neighbor is geometrically closest to the destination. Evaluating how well a network supports this process is critical for understanding its functional efficiency.

Historically, researchers have relied on two distinct and often conflicting metrics to evaluate GR:

  1. Success Ratio: The percentage of packets that successfully reach their destination.
  2. Stretch: The ratio of the greedy path length to the theoretical shortest path length, calculated only for successful deliveries.

This paper addresses the inherent "selection bias" of the stretch metric—which can make a poorly navigable network appear efficient simply because it fails on difficult paths—and advocates for a unified metric: the GR-score (or GR-efficiency).

Methods and Datasets

The authors define the GR-score as the average ratio of the shortest path length to the greedy routing path length across all node pairs. By treating unsuccessful paths as having infinite length (a ratio of 0), the GR-score naturally penalizes both delivery failures and inefficient routing in a single, robust value.

To demonstrate this, the study utilizes artificial networks generated via the nonuniform popularity-similarity optimization (nPSO) model. These synthetic models allow for the creation of specific structural properties to test navigability metrics in "conflict scenarios" where traditional measures provide ambiguous results.

Visualization of a synthetic network (Network 1) generated using the nPSO model to test navigability metrics.

Key Results: Resolving Metric Conflicts

Using two synthetic 100-node networks, the authors illustrate how traditional metrics can lead to contradictory conclusions. As shown in the comparison below, Network 1 appears superior if one only considers "Stretch," as its successful paths are shorter. However, Network 2 has a significantly higher Success Ratio.

Comparison of Success ratio, Stretch, and GR-score for two synthetic networks. While traditional metrics (Success ratio and Stretch) provide conflicting signals, the GR-score identifies Network 2 as the more navigable architecture overall.

The GR-score provides a unique solution to this tie-break, identifying Network 2 as the more navigable architecture. It quantifies that the ~12% gain in successful deliveries far outweighs the minor ~2% loss in path efficiency (stretch).

Standardizing Terminology

A primary goal of this Letter is to correct the scientific record and standardize terminology. The authors point out that the "efficiency ratio" recently introduced in brain network research (Seguin et al., 2018) is mathematically identical to their previously published GR-score. They argue for the adoption of the term "GR-efficiency" to clarify that the metric is specific to the greedy routing protocol and to prevent the redundant "reinvention" of metrics in future network science and neuroscience studies.

Conclusion

The GR-score offers a comprehensive framework for evaluating network navigability by integrating success rates and path efficiency. By adopting the standardized "GR-efficiency" terminology, the research community can more accurately compare diverse network architectures—from the human connectome to global infrastructure—using a single, unbiased metric.

Summary updated

Abstract

Network navigability is a key feature of complex networked systems. For a network embedded in a geometrical space, maximization of greedy routing (GR) measures based on the node geometrical coordinates can ensure efficient greedy navigability. In PNAS, Seguin et al. (PNAS 2018, vol. 115, no. 24) define a measure for quantifying the efficiency of brain network navigability in the Euclidean space, referred to as the efficiency ratio, whose formula exactly coincides with the GR-score (GR-efficiency) previously published by Muscoloni et al. (Nature Communications 2017, vol. 8, no. 1615). In this Letter, we point out potential flaws in the study of Seguin et al. regarding the discussion of the GR evaluation. In particular, we revise the concept of GR navigability, together with a careful discussion of the advantage offered by the new proposed GR-efficiency measure in comparison to the main measures previously adopted in literature. Finally, we clarify and standardize the GR-efficiency terminology in order to simplify and facilitate the discussion in future studies.
BibTeX
@misc{muscoloni2019navigability,
  author = {Alessandro Muscoloni and Carlo Vittorio Cannistraci},
  title = {{Navigability evaluation of complex networks by greedy routing efficiency}},
  year = {2019},
  eprint = {1901.07909},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/1901.07909},
}
Figure