Colored Configuration Model preserves user interaction patterns for polarization analysis

A new KDD 2026 paper by Leonardo Pellegrina tackles a core problem in network analysis: how to statistically assess whether observed patterns in social networks are meaningful. The Colored Configuration Model (CCM) is a null model specifically designed for vertex-colored multigraphs—graphs where nodes have a color (e.g., political stance) and multiple edges can exist. Existing null models only preserve simple features like degree sequences, but CCM goes further by preserving the Colored Degree Matrix (CDM), which tracks, for each vertex, the number of neighbors of each color. This allows the model to fix the color assortativity of all nodes—the propensity of users to interact with like-minded peers—making it possible to test whether phenomena like network polarization are statistically significant given the observed interaction preferences.

To sample from CCM, Pellegrina develops two algorithms: Sirius-B, a straightforward baseline using Metropolis-Hastings sampling, and Sirius, a refined approach tailored to preserve the CDM with provably faster mixing. Experiments on real-world online social networks show that evaluating polarization significance with Sirius can lead to different insights compared to older null models. For researchers studying debates, echo chambers, or political homophily, Sirius provides a statistically rigorous way to isolate the effect of color assortativity from other network characteristics. This work is a practical step toward more reliable hypothesis testing in computational social science.