On the Number of Graphs with a Given Histogram
arXiv:2202.01563 · doi:10.1109/TIT.2023.3296827
Abstract
Let be a large (simple, unlabeled) dense graph on vertices. Suppose that we only know, or can estimate, the empirical distribution of the number of subgraphs that each vertex in participates in, for some fixed small graph . How many other graphs would look essentially the same to us, i.e., would have a similar local structure? In this paper, we derive upper and lower bounds on the number of graphs whose empirical distribution lies close (in the Kolmogorov-Smirnov distance) to that of . Our bounds are given as solutions to a maximum entropy problem on random graphs of a fixed size that does not depend on , under global density constraints. The bounds are asymptotically close, with a gap that vanishes with at a rate that depends on the concentration function of the center of the Kolmogorov-Smirnov ball.
arXiv comment40 pages
References in corpus (8)
- Statistical mechanics of complex networks
- Random graphs with clustering
- Estimating and understanding exponential random graph models
- Random graphs containing arbitrary distributions of subgraphs
- Random graphs with a given degree sequence
- Phase transitions in a complex network
- On replica symmetry of large deviations in random graphs
- Higher-order structure and epidemic dynamics in clustered networks