Robustness against Frustration in Community Detection

We reinterpret the Leiden algorithm for community detection through a game-theoretic lens, modeling it as a hedonic game where nodes act as rational agents. This perspective uncovers an equivalence between Constant Potts Model (CPM) optimization and Nash equilibria. We introduce an agent-level notion of frustration, which arises when agents face a trade-off between maximizing intra-community links and minimizing non-links. The resolution parameter resolves this conflict by acting as a decision threshold against a proposed social metric. We prove convergence guarantees and demonstrate empirically that robustness (the absence of frustration) correlates with higher accuracy in synthetic networks with known, symmetric ground-truth communities.