Edge Probability Graph Models Beyond Edge Independency: Concepts, Analyses, and Algorithms

Desirable random graph models (RGMs) should (i) reproduce common patterns in real-world graphs (e.g., power-law degrees, small diameters, and high clustering), (ii) generate variable (i.e., not overly similar) graphs, and (iii) remain tractable to compute and control graph statistics. A common class of RGMs (e.g., Erdos-Renyi and stochastic Kronecker) outputs edge probabilities, so we need to realize (i.e., sample from) the output edge probabilities to generate graphs. Typically, the existence of each edge is assumed to be determined independently, for simplicity and tractability. However, with edge independency, RGMs provably cannot produce high subgraph densities and high output variability simultaneously. In this work, we explore RGMs beyond edge independence that can better reproduce common patterns while maintaining high tractability and variability. Theoretically, we propose an edge-dependent realization (i.e., sampling) framework called binding that provably preserves output variability, and derive closed-form tractability results on subgraph (e.g., triangle) densities. Practically, we propose algorithms for graph generation with binding and parameter fitting of binding. Our empirical results demonstrate that RGMs with binding exhibit high tractability and well reproduce common patterns, significantly improving upon edge-independent RGMs.