# Geodesic Length Distribution in Sparse Network Ensembles

arXiv: https://arxiv.org/abs/2111.02330 · HTML: https://mlsanity.com/paper/2111.02330/

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 14 of its 90 references that are in the map.
- First posted on arXiv 3 Nov 2021.

## Builds on (most cited first, 14 of 14)

- [node2vec: Scalable Feature Learning for Networks](https://mlsanity.com/paper/1607.00653/) (2016)
- [Representation Learning on Graphs: Methods and Applications](https://mlsanity.com/paper/1709.05584/) (2017)
- [A Comprehensive Survey of Graph Embedding: Problems, Techniques and Applications](https://mlsanity.com/paper/1709.07604/) (2017)
- [Graph Embedding Techniques, Applications, and Performance: A Survey](https://mlsanity.com/paper/1705.02801/) (2017)
- [Hierarchical Block Structures and High-resolution Model Selection in Large Networks](https://mlsanity.com/paper/1310.4377/) (2013)
- [Structure and inference in annotated networks](https://mlsanity.com/paper/1507.04001/) (2015)
- [Bayesian Models of Graphs, Arrays and Other Exchangeable Random Structures](https://mlsanity.com/paper/1312.7857/) (2013)
- [Sparse graphs using exchangeable random measures](https://mlsanity.com/paper/1401.1137/) (2014)
- [Network structure from rich but noisy data](https://mlsanity.com/paper/1703.07376/) (2017)
- [Network reconstruction and community detection from dynamics](https://mlsanity.com/paper/1903.10833/) (2019)
- [Reconstructing networks with unknown and heterogeneous errors](https://mlsanity.com/paper/1806.07956/) (2018)
- [Properties of Latent Variable Network Models](https://mlsanity.com/paper/1506.07806/) (2015)
- [Community detection in networks without observing edges](https://mlsanity.com/paper/1808.06079/) (2018)
- [A bag-of-paths framework for network data analysis](https://mlsanity.com/paper/1302.6766/) (2013)

## Abstract (arXiv)

A key task in the study of networked systems is to derive local and global properties that impact connectivity, synchronizability, and robustness; computing shortest paths or geodesics yields measures of network connectivity that can explain such phenomena. We derive an analytic distribution of geodesic lengths on the giant component in the supercritical regime -- when the giant component exists -- or on small components in the subcritical regime, of any sparse (and possibly directed) network with conditionally independent edges, in the infinite-size limit. We provide specific results for widely used network models like stochastic block models, dot product graphs, random geometric graphs, and sparse graphons. The survival function of the geodesic length distribution possesses a simple closed-form expression which is asymptotically tight for finite lengths, has a natural interpretation of traversing independent geodesics in the network, and delivers novel insight into the aforementioned network families.