Spherical law for optimal layouts of random graphs
Abstract
Can the nodes of a random graph be placed in an auxiliary space ℝM so that its connectivity becomes local? The spring electric layout is a standard algorithm to try to find such local graph layouts; we study it as a statistical-physics problem by considering the Gibbs ensemble of spring-electric layouts. For graphs with independent edges we solve the model exactly at large number of nodes N and fixed embedding dimension M. The node positions obey a spherical law: they are uniformly distributed in an M-dimensional ball; for M=2 this is closely related to Girko's circular law. Crucially, the ground state energy is flat across all layouts with that density: an optimal layout for one graph is asymptotically optimal for any other. Optimal layouts of i.i.d. graphs are therefore frustrated liquids, macroscopically constrained but microscopically unoptimizable. We discuss relations to graph-partitioning, Laplacian eigenmaps, and dimensionality reduction, and outline how this harsh result breaks down for correlated graphs.
Related
- R-transforms for non-Hermitian block random matrices: a spherical integral approach
- Scalable quantum-enhanced greedy algorithm for the maximum independent set problems on random regular graphs
- Random Cellular Automata and deBruijn Graphs
- Random layers for quantum optimal control with exponential expressivity
- Fuzzy Erdos-Renyi random graphs: Spectral statistics
BibTeX
@misc{stubenrauch2026spherical,
title = {{Spherical law for optimal layouts of random graphs}},
author = {Jakob Stubenrauch and Christian Keup},
howpublished = {arXiv},
year = {2026},
month = oct,
doi = {10.48550/arxiv.2610.40965},
eprint = {2610.40965},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2610.40965},
}
RIS
TY - UNPB
TI - Spherical law for optimal layouts of random graphs
AU - Jakob Stubenrauch
AU - Christian Keup
PY - 2026
DA - 2026/10/29
PB - arXiv
DO - 10.48550/arxiv.2610.40965
UR - https://arxiv.org/abs/2610.40965
AB - Can the nodes of a random graph be placed in an auxiliary space ℝ^M so that its connectivity becomes local? The spring electric layout is a standard algorithm to try to find such local graph layouts; we study it as a statistical-physics problem by considering the Gibbs ensemble of spring-electric layouts. For graphs with independent edges we solve the model exactly at large number of nodes N and fixed embedding dimension M. The node positions obey a spherical law: they are uniformly distributed in an M-dimensional ball; for M=2 this is closely related to Girko's circular law. Crucially, the ground state energy is flat across all layouts with that density: an optimal layout for one graph is asymptotically optimal for any other. Optimal layouts of i.i.d. graphs are therefore frustrated liquids, macroscopically constrained but microscopically unoptimizable. We discuss relations to graph-partitioning, Laplacian eigenmaps, and dimensionality reduction, and outline how this harsh result breaks down for correlated graphs.
ER -