Reachability Does Not Imply Searchability in Expanding Networks
Abstract
Routing and search respond in opposite ways to rapid network expansion. Short graph distances make a known destination easy to reach, while the neighborhood accessible within a few hops can be vastly larger than any finite inspection budget. We show that this tension imposes an algorithm-independent constraint on sparse search. If mq relevant nodes are placed without structural information among N nodes and at most M nodes can be inspected, any target-blind exploration protocol has success probability at most Mmq/N, irrespective of correlations between successive inspections, of revisits, and of any structural preference the exploration rule may have. Geometry determines when this constraint becomes relevant: a target becomes accessible with order-one probability when the graph-distance ball volume satisfies V(Rc)∼ N/mq. At this scale, any inspection mechanism achieving a fixed success probability δ>0 must enrich the probability of inspecting relevant nodes by at least order N/(Mmq) relative to the neutral target density. For uniformly searched candidate sets, this entails a vanishing visible fraction of the accessible region. Thus rapidly expanding networks can make rare targets geometrically close while target-blind search remains ineffective. Numerical results on Krioukov hyperbolic random graphs and two-dimensional lattices show that this separation can arise within only a few hops in the rapidly expanding case, while the lattice accessibility radius grows algebraically.
Related
- Bell nonlocality does not imply violation of nonlocal games
- Does a pole in the self-energy imply a violation of the Luttinger theorem?
- Equivalence of maximal and generic reachability for non-universal Variational Quantum Circuits
- Optimizing quantum encodings for analog simulation through dynamical algebra reachability
- Advances in Stereotactic Body Radiation Therapy: Expanding Clinical Applications and Improving Treatment Precision
BibTeX
@misc{scala2026reachability,
title = {{Reachability Does Not Imply Searchability in Expanding Networks}},
author = {Antonio Scala},
howpublished = {arXiv},
year = {2026},
month = sep,
doi = {10.48550/arxiv.2609.31042},
eprint = {2609.31042},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2609.31042},
note = {CC BY-NC-ND 4.0},
}
RIS
TY - UNPB
TI - Reachability Does Not Imply Searchability in Expanding Networks
AU - Antonio Scala
PY - 2026
DA - 2026/09/25
PB - arXiv
DO - 10.48550/arxiv.2609.31042
UR - https://arxiv.org/abs/2609.31042
AB - Routing and search respond in opposite ways to rapid network expansion. Short graph distances make a known destination easy to reach, while the neighborhood accessible within a few hops can be vastly larger than any finite inspection budget. We show that this tension imposes an algorithm-independent constraint on sparse search. If m_q relevant nodes are placed without structural information among N nodes and at most M nodes can be inspected, any target-blind exploration protocol has success probability at most Mm_q/N, irrespective of correlations between successive inspections, of revisits, and of any structural preference the exploration rule may have. Geometry determines when this constraint becomes relevant: a target becomes accessible with order-one probability when the graph-distance ball volume satisfies V(R_c)∼ N/m_q. At this scale, any inspection mechanism achieving a fixed success probability δ>0 must enrich the probability of inspecting relevant nodes by at least order N/(Mm_q) relative to the neutral target density. For uniformly searched candidate sets, this entails a vanishing visible fraction of the accessible region. Thus rapidly expanding networks can make rare targets geometrically close while target-blind search remains ineffective. Numerical results on Krioukov hyperbolic random graphs and two-dimensional lattices show that this separation can arise within only a few hops in the rapidly expanding case, while the lattice accessibility radius grows algebraically.
ER -