Better ways to count colors and states in complex networks
Spatial Mixing and Deterministic Approximate Counting of Multi-spin Systems beyond Bounded Degree Graphs
Data Structures and Algorithms
Summary
Counting the different ways to arrange colors or states on a network can be very hard, especially when the network is big or irregular. This paper presents a new method that can more efficiently and reliably count these arrangements in certain types of complicated networks, going beyond simple or limited cases. The authors improve previous best results for counting colorings on random graphs and show their approach works under broader conditions than before.
What this means in practice
- •For network algorithm engineers: Provide efficient algorithms for approximate counting of configurations in networks with non-uniform degrees or random sparse topology.
- •For data scientists working on probabilistic models: Enable improved estimations of marginal probabilities in graphical models beyond classical bounded-degree assumptions.
Authors
Zhidan Li, Kuan Yang
Abstract
We develop a framework for deterministic approximate counting of multi-spin systems beyond bounded-degree graphs. The algorithm recursively constructs rational polytopes containing the true marginal vectors and uses linear-fractional programming to obtain certified bounds on marginal ratios. For positive interactions on graphs of polynomial connective constant $D$, we establish strong spatial mixing and a fully polynomial-time approximation scheme (\textbf{FPTAS}) whenever $Dc<1$, where $c$ bounds the Birkhoff contraction coefficients of the interactions. We further extend the framework to proper colorings of sparse Erdős-Rényi random graphs using recursion on permissive blocks. For every fixed $η\in(0,1)$, sufficiently large fixed $d$, and fixed integer $q\ge(2+η)d$, we obtain an \textbf{FPTAS} for counting proper $q$-colorings of $G\sim\mathcal G(n,d/n)$ with high probability over $G$. This improves the leading constant $3$ in the earlier counting guarantee of Yin and Zhang (APPROX/RANDOM, 2016) to $2$, and asymptotically matches the spatial mixing regime established by Yin (ICALP, 2014).