From Leiden to Pleasure Island: The Constant Potts Model for Community Detection as a Hedonic Game
This provides a game-theoretic framework for network partitioning, offering incremental improvements in efficiency and accuracy for data science applications.
The paper tackles community detection in networks by reinterpreting the Constant Potts Model as a hedonic game, proving convergence in pseudo-polynomial time and showing that robust partitions improve accuracy in community tracking scenarios, with experiments demonstrating higher recovery of ground-truth communities.
Community detection is one of the fundamental problems in data science which consists of partitioning nodes into disjoint communities. We present a game-theoretic perspective on the Constant Potts Model (CPM) for partitioning networks into disjoint communities, emphasizing its efficiency, robustness, and accuracy. Efficiency: We reinterpret CPM as a potential hedonic game by decomposing its global Hamiltonian into local utility functions, where the local utility gain of each agent matches the corresponding increase in global utility. Leveraging this equivalence, we prove that local optimization of the CPM objective via better-response dynamics converges in pseudo-polynomial time to an equilibrium partition. Robustness: We introduce and relate two stability criteria: a strict criterion based on a novel notion of robustness, requiring nodes to simultaneously maximize neighbors and minimize non-neighbors within communities, and a relaxed utility function based on a weighted sum of these objectives, controlled by a resolution parameter. Accuracy: In community tracking scenarios, where initial partitions are used to bootstrap the Leiden algorithm with partial ground-truth information, our experiments reveal that robust partitions yield higher accuracy in recovering ground-truth communities.