A Sublinear Algorithm for Approximate Shortest Paths in Large Networks
<|reference_start|>A Sublinear Algorithm for Approximate Shortest Paths in Large Networks: Computing distances and finding shortest paths in massive real-world networks is a fundamental algorithmic task in network analysis. There are two main approaches to solving this task. On one hand are traversal-based algorithms like bidirectional breadth-first search (BiBFS) with no preprocessing step and slow individual distance inquiries. On the other hand are indexing-based approaches, which maintain a large index. This allows for answering individual inquiries very fast; however, index creation is prohibitively expensive. We seek to bridge these two extremes: quickly answer distance inquiries without the need for costly preprocessing.   In this work, we propose a new algorithm and data structure, WormHole, for approximate shortest path computations. WormHole leverages structural properties of social networks to build a sublinearly sized index, drawing upon the explicit core-periphery decomposition of Ben-Eliezer et al. Empirically, the preprocessing time of WormHole improves upon index-based solutions by orders of magnitude, and individual inquiries are consistently much faster than in BiBFS. The acceleration comes at the cost of a minor accuracy trade-off. Nonetheless, our empirical evidence demonstrates that WormHole accurately answers essentially all inquiries within a maximum additive error of 2. We complement these empirical results with provable theoretical guarantees, showing that WormHole requires $n^{o(1)}$ node queries per distance inquiry in random power-law networks. In contrast, any approach without a preprocessing step requires $n^{\Omega(1)}$ queries for the same task.   WormHole does not require reading the whole graph. Unlike the vast majority of index-based algorithms, it returns paths, not just distances. For faster inquiry times, it can be combined effectively with other index-based solutions, by running them only on the sublinear core.<|reference_end|>
@article{basu2024a,
    title={A Sublinear Algorithm for Approximate Shortest Paths in Large Networks},
    author={Sabyasachi Basu, Nadia K=oshima, Talya Eden, Omri Ben-Eliezer, C.
  Seshadhri},
    journal={arXiv preprint arXiv:2406.08624},
    year={2024},
    archivePrefix={arXiv},
    eprint={2406.08624},
    primaryClass={cs.DS cs.DM cs.SI}
}