Concentration of Multilinear Functions of the Ising Model with Applications to Network Data
This provides improved theoretical tools for analyzing network data, particularly for social networks, though it appears incremental in advancing concentration bounds.
The paper proves near-tight concentration bounds for polynomial functions of Ising models under high temperature, showing exponential tails scaling as exp(-r^{2/d}) at radius r = Ω̃_d(n^{d/2}), which improves previous results by polynomial factors in spin count. It demonstrates these polynomial functions as effective statistics for testing interaction strengths in social networks using synthetic and real data.
We prove near-tight concentration of measure for polynomial functions of the Ising model under high temperature. For any degree $d$, we show that a degree-$d$ polynomial of a $n$-spin Ising model exhibits exponential tails that scale as $\exp(-r^{2/d})$ at radius $r=\tildeΩ_d(n^{d/2})$. Our concentration radius is optimal up to logarithmic factors for constant $d$, improving known results by polynomial factors in the number of spins. We demonstrate the efficacy of polynomial functions as statistics for testing the strength of interactions in social networks in both synthetic and real world data.