# Robustness against Frustration in Community Detection

Lucas Lopes Felipe, Konstantin Avrachenkov, Daniel Sadoc Menasché

► To cite this version:

Lucas Lopes Felipe, Konstantin Avrachenkov, Daniel Sadoc Menasché. Robustness against Frustration in Community Detection. SIGMETRICS 2025 - ACM Sigmetrics 2025 (Student Competition), Jun 2025, Stony Brook, United States. pp.128-130, 10.1145/3764944.3764977. hal-05458107

HAL Id: hal-05458107

https://inria.hal.science/hal-05458107v1

Submitted on 14 Jan 2026

HAL is a multi-disciplinary open access
archive for the deposit and dissemination of sci-
entific research documents, whether they are pub-
lished or not. The documents may come from
teaching and research institutions in France or
abroad, or from public or private research centers.

L'archive ouverte pluridisciplinaire HAL, est
destinée au dépôt et à la diffusion de documents
scientifiques de niveau recherche, publiés ou non,
émanant des établissements d'enseignement et de
recherche français ou étrangers, des laboratoires
publics ou privés.

<figure><img src="image_1.png" /></figure>

Distributed under a Creative Commons CC BY 4.0 - Attribution - International License
# Robustness against Frustration in Community Detection

Lucas Lopes Felipe
UFRJ
Rio de Janeiro, Brazil

Konstantin Avrachenkov
INRIA
Sophia Antipolis, France

Daniel Sadoc Menasché
UFRJ
Rio de Janeiro, Brazil

## ABSTRACT

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.

## Keywords

Community Detection, Leiden algorithm, Constant Potts Model, Hedonic Games, Ising Frustration

## 1. INTRODUCTION

Community detection is a cornerstone of network science, with applications spanning from social network analysis to systems biology [6, 4]. The Leiden algorithm [8] is a state-of-the-art method for partitioning networks that can optimize various quality functions, with the Constant Potts Model (CPM) [7] being its default. While its empirical success is well-documented, its theoretical underpinnings can be enhanced by viewing it as a decentralized, multi-agent system.

In this work, we cast community detection as a hedonic game [2, 3], where nodes are rational agents choosing communities to maximize their utility. Each agent faces a fundamental trade-off between two competing objectives:

1. Maximize “friends”: Join a community to increase the number of neighbors within its community;

2. Minimize “strangers”: Join a community to decrease the number of non-neighbors within its community.

This dual objective often leads to frustration, a concept from statistical physics, e.g., in the Ising model, that we adapt to describe scenarios where no single community is optimal for a node on both criteria simultaneously.

<caption>Algorithm 1: Better-Response Algorithm.</caption>

Input : $G = (V, E)$; $\gamma$; Initial partition $\pi: V \to \{1, ..., K\}$
(mapping node $i$ to its community index $\sigma_i$).
Output: Equilibrium partition $\bar{\pi}$.
1 changed $\leftarrow$ true;
2 while changed do
3 changed $\leftarrow$ false;
4 foreach node $i \in V$ do
5 Let $\sigma_i^* \leftarrow \arg\max_{k \in \{1, ..., K\}} \varphi_i^\gamma(C_k)$;
6 if $\sigma_i^* \neq \pi(i)$ then
7 Move node $i$ to community $\sigma_i^*$ (i.e., update
$\pi(i) \leftarrow \sigma_i^*$);
8 changed $\leftarrow$ true;
9 end
10 end
11 end
12 return $\bar{\pi}$

To resolve this conflict, we introduce the Familiarity Index, $F = \Delta d/(\Delta d + \Delta \bar{d})$, which quantifies the trade-off for a potential move between communities, where $\Delta d$ is the change in friends and $\Delta \bar{d}$ is the change in strangers. The CPM's resolution parameter, $\gamma$, then acts as the decision threshold: for a frustrated agent, the decision to move is governed by comparing $F$ to $\gamma$. Indeed, if $F > \gamma$, the benefit of gaining friends outweighs the cost of acquiring more strangers. This framework provides a clear, agent-level interpretation for the CPM objective.

A node is **robust** if its current community is clearly preferred over all other communities reachable through a unilateral move by simultaneously maximizing friends and minimizing strangers. In this scenario, the decision is frustration-free, meaning the optimal community choice is independent of the resolution parameter $\gamma \in [0, 1]$. Table 1 summarizes the analogies between hedonic games, the Ising model, and community detection, highlighting how frustration and robustness provide a unifying language.

## 2. FORMAL RESULTS

We establish that optimizing the CPM objective is equivalent to finding a Nash Equilibrium in a potential hedonic game [1]. This equivalence allows us to demonstrate that the local-move phase of the Leiden algorithm converges to an equilibrium in pseudo-polynomial time, specifically $O(cV^2)$ steps, where $V$ is the number of nodes and $\gamma = b/c$ (where $b, c \in \mathbb{N}$).

**Notation.** We represent a network as a graph $G = (V, E)$, where $V$ is the set of nodes and $E$ the set of edges. A partition $\pi = \{C_1, ..., C_K\}$ groups nodes into disjoint communities.
<table><caption>Table 1: Ising or Potts Model (Physics), Constant Potts Model (Community Detection), and Hedonic Games</caption><thead><tr><th>Ising or Potts Model (Physics)</th><th>Community Detection</th><th>Hedonic Game Theory</th></tr></thead><tbody><tr><td>Spins (magnetic particles)</td><td>Nodes in a network</td><td>Players (agents)</td></tr><tr><td>Aligned spins (same state)</td><td>Community (cluster of nodes)</td><td>Coalition (group of agents)</td></tr><tr><td>Local energy</td><td>Tradeoff: internal links vs. internal non-links</td><td>Individual utility, ϕ<sup>γ</sup><sub>i</sub> = (1 - γ)d<sup>k</sup><sub>i</sub> - γd̂<sup>k</sup><sub>i</sub></td></tr><tr><td>Ground state (no local change reduces energy)</td><td>Locally optimal partition</td><td>Nash Equilibrium (no agent can improve utility by moving)</td></tr><tr><td>Frustration: energy cannot be minimized for all edges</td><td>Conflicting objectives: best community differs by criterion</td><td>Frustration: No coalition satisfies all preferences</td></tr><tr><td>Hamiltonian: global energy decreases with better alignment</td><td>Constant Potts Mode minimizes internal non-links and maximizes links</td><td>Potential Game: global potential increases with utility</td></tr><tr><td>Unfrustrated spin: aligned with all neighbors</td><td>Robust node: community is optimal across γ ∈ [0, 1]</td><td>Totally robust agent: best group for all γ</td></tr><tr><td>Spin flips (e.g., Glauber dynamics)</td><td>Node relocation (e.g., Leiden algorithm)</td><td>Best-response dynamics</td></tr><tr><td>Low-energy configuration</td><td>Robust and stable community structure</td><td>Stable partition means strategic equilibrium</td></tr></tbody></table>

Each node $i \in \mathcal{V}$ belongs to a community $C_k = \pi(i)$. The number of neighbors (edges) that node $i$ has within community $C_k$ is denoted by $d_i^k$, while $\hat{d}_i^k$ denotes the number of non-neighbors (nodes in $C_k$ that are not adjacent to $i$). The resolution parameter $\gamma \in [0, 1]$ balances the preference for internal links ($d_i^k$) and internal non-links ($\hat{d}_i^k$). The individual utility of node $i$ with respect to community $C_k$ is given by $\phi_i^\gamma(C_k) = (1-\gamma)d_i^k - \gamma\hat{d}_i^k$. The global potential of a partition is denoted by $\Phi^\gamma(\pi)$ and satisfies $\Phi^\gamma(\pi) = -\mathcal{H}_{CPM}(\pi)$, where $\mathcal{H}_{CPM}$ is the Constant Potts Model Hamiltonian. We denote the change in utility when node $i$ moves from community $B$ to $A$ as $\Delta\phi_i^{BA}$, and define a partition to be a $\gamma$-equilibrium if no node has incentive to deviate under resolution $\gamma$. A partition is said to be robust over an interval $[\gamma_0, \gamma_1]$ if it is a Nash equilibrium for all $\gamma$ in that interval. A node is robust if it simultaneously maximizes $d_i^k$ and minimizes $\hat{d}_i^k$ in its current community.

**THEOREM 1 (Pseudo-P polynomial Time).** When $\gamma = b/c$ is rational with $b, c \in \mathbb{N}$, the better-response dynamics of Algorithm 1 converges to an equilibrium partition in at most $O(cV^2)$ steps, achieving pseudo-polynomial time complexity.

**Proof sketch.** The key insight is that the CPM-based potential function $\Phi^\gamma(\pi)$ is bounded between $-V^2$ and $V^2$ and takes values of the form $U/c$ for integer $U$, due to the rationality of $\gamma = b/c$. Since each better-response move by a node strictly increases the potential by at least $1/c$, and the total range of potential values is at most $2V^2$, the number of improving steps is bounded by $2cV^2$.

To assess partition stability, we propose two criteria: a strict multi-objective criterion requiring nodes to maximize

neighbors and minimize non-neighbors simultaneously, and a relaxed single-objective criterion using a $\gamma$-weighted utility function, which the Leiden algorithm optimizes. A node is “robust” if it satisfies the strict criterion, and partition robustness is the fraction of such nodes.

**THEOREM 2 (Robustness).** Given a $\gamma$-equilibrium partition $\pi^\gamma$ that holds as equilibrium for $\gamma = \gamma_0$ and for $\gamma = \gamma_1$, with $\gamma_1 > \gamma_0$, then $\pi^\gamma$ is an $[\gamma_0, \gamma_1]$-robust equilibrium, denoted as $\pi^{[\gamma_0, \gamma_1]}$.

**Proof sketch.** The proof relies on the linearity of the utility difference $\Delta\phi_i^{BA}(\gamma)$ with respect to the resolution parameter $\gamma$. Suppose node $i$ belongs to community $B$ and considers moving to community $A \neq B$. If $\pi^\gamma$ is an equilibrium for both $\gamma_0$ and $\gamma_1$, then $\Delta\phi_i^{BA}(\gamma_0) \le 0$ and $\Delta\phi_i^{BA}(\gamma_1) \le 0$. Since the function is linear in $\gamma$, it follows that $\Delta\phi_i^{BA}(\gamma) \le 0$ for all $\gamma \in [\gamma_0, \gamma_1]$. Thus, node $i$ has no incentive to deviate within this interval. Repeating this argument for all nodes and all community pairs proves that $\pi^\gamma$ is $[\gamma_0, \gamma_1]$-robust.

**THEOREM 3 (Full Robustness).** An equilibrium partition $\pi^\gamma$, which 1) holds for $\gamma = 0$, and 2) in which all communities have the same number of nodes, is an equilibrium for any $\gamma \in [0, 1]$.

**Proof sketch.** If a node has no incentive to move under $\gamma = 0$, and all communities are equally sized, then it also has no incentive to move under $\gamma = 1$. Specifically, under $\gamma = 0$, equilibrium requires that $d_i^B \ge d_i^A$. Under $\gamma = 1$, the condition becomes $n_B - (d_i^B + 1) \le n_A - d_i^A$, where $n_A = n_B$ due to the balanced partition. This inequality is satisfied whenever $d_i^B \ge d_i^A$, showing that equilibrium at $\gamma = 0$ implies equilibrium at $\gamma = 1$. Applying Theorem 2, this establishes robustness for all $\gamma \in [0, 1]$.

Our theoretical results confirm that the Leiden algorithm's local-move phase efficiently converges to a hedonic game equilibrium. By leveraging pseudo-polynomial time complexity, multi-agent systems can efficiently scale, harnessing the power of distributed local moves.

### 3. EXPERIMENTAL RESULTS

Experimentally, we evaluate this framework using synthetic networks from the Symmetric Assortative Planted Partition Model (SAPPM) [5], testing efficiency, robustness, and accuracy in a community tracking scenario where initial partitions are perturbed by noise.

We find that partitions with higher robustness correlate with higher-quality solutions. In the SAPPM, we consider networks with varying connection probabilities ($p$) and difficulty factors ($\lambda = q/p$), and indicate that robustness effectively filters stable partitions among multiple equilibria.

**Samples for confidence intervals.** Each of the five heatmaps in Figure 1 comprises $10 \times 10$ cells, each cell corresponding to a pair of parameters ($p, \lambda$). To ensure confidence in the values expressed in each cell of the heatmap, we collect samples for the same parameters while varying the seed argument of the NetworkX SBM function. In particular, the value reported in each cell of Figure 1 is an average across 100 network samples. This suffices for the purpose of producing 95% confidence intervals of length less than 0.01.

Each heatmap corresponds to a different number of communities ($K \in \{2, 3, 4, 5, 6\}$), with $V = 1020$ fixed, and number of nodes per community $N = 1020/K$. The darker the
<figure><img src="image_2.png" /><figcaption>Figure 1: Robustness of the ground-truth partition varies as a function of the difficulty factor. Top row: Histograms showing the distribution of the fraction of robust nodes for various parameter settings. Bottom row: Heatmaps where each cell represents the average fraction of robust nodes for a given pair of connection probability *p* and difficulty factor *λ*.</figcaption></figure>

color, the higher the fraction of fully-robust nodes. The heatmaps reveal several important insights:

**Robustness decreases as K grows.** As the number of communities (*K*) increases, the robustness of the ground truth partition tends to decrease. This is expected since the chance that the community of a given node is the community where this node has the highest number of neighbors and fewest non-neighbors diminishes as *K* increases. To illustrate that point, consider two extreme cases. The grand coalition (*K* = 1) is always fully robust, as nodes have no alternative communities to transition to. A set of singletons (*K* = *V*), in contrast, is never fully robust, as under the criterion of maximizing neighbors, nodes can benefit by transitioning to a community with an additional node.

**Effect of parameters *p* and *λ*.`** The robustness is higher for lower values of *λ* and higher values of *p*. Indeed, we observe a gradual decline of robustness as *λ* grows. For *K* = 2, the robustness remains high for a large range of *p* and *λ*. As *K* increases, the robustness heatmap starts to show a gradual decline where higher values of *λ* and lower values of *p* result in lower robustness. This occurs because lower intra-community connection probabilities (*p*) and higher inter-community connection probabilities (*q* = *p*(*λ*)) make communities less distinct and harder to detect.

**Robust partitions and ground truth.** Although not all the ground truth partitions correspond to an equilibrium, we observe that a significant fraction of those partitions does correspond to fully robust equilibria. These are the cells marked with dark blue in Figure 1, with robustness equal one. In those cases, nodes have no incentive to transition across communities for any value of *γ*. For the cases where a fraction of nodes has incentive to deviate, such incentive holds for any *γ*.

In community tracking, we simulate network evolution by perturbing ground-truth partitions with noise levels ($\eta \in \{0.1, 0.25, 0.5, 0.75, 1.0\}$). Compared against baselines — spectral clustering, Leiden (full-fledged), one-pass improvement, and a mirror strategy (also referred to as zero-order hold (ZOH) in the realm of signal processing and control theory) — our hedonic-game-based method (Leiden Phase 1) achieves high accuracy, measured via the Adjusted Rand Index (ARI). While simpler baselines perform well at very low noise ($\eta = 0.1$), our method excels as noise increases, achieving the highest accuracy (ARI $\approx 0.65$) under moder-

ate noise ($\eta = 0.5$), significantly outperforming methods like spectral clustering.

## 4. CONCLUSION AND FUTURE WORK

The hedonic game framework provides a powerful, agent-level interpretation of the Leiden algorithm and the CPM objective. By introducing the concepts of frustration and the Familiarity Index, we clarify the role of the resolution parameter $\gamma$ as a mechanism for resolving trade-offs in community formation. Our theoretical guarantees and experimental results demonstrate that this perspective is not only explanatory but also practical. The distributed nature of the algorithm is well-suited for decentralized environments, and using robustness as a filter can improve solution quality.

Future work could extend this robustness analysis to networks with asymmetric communities, as our current experiments focused on the symmetric case.

**Acknowledgement.** This work was partially funded by CAPES, CNPq and FAPERJ – CNE E-26/204.268/2024.

## 5. REFERENCES

[1] BOGOMOLNAIA, A., AND JACKSON, M. O. The stability of hedonic coalition structures. *Games and Economic Behavior* **38**, 2 (2002), 201–230.

[2] BRANDT, F., CONITZER, V., ENDRISS, U., LANG, J., AND PROCACCIA, A. D. *Handbook of computational social choice*. Cambridge University Press, 2016.

[3] DREZE, J. H., AND GREENBERG, J. Hedonic coalitions: Optimality and stability. *Econometrica: Journal of the Econometric Society* (1980), 987–1003.

[4] GIRVAN, M., AND NEWMAN, M. E. Community structure in social and biological networks. *PNAS* **99**, 12 (2002), 7821–7826.

[5] HOLLAND, P. W., LASKEY, K. B., AND LEINHARDT, S. Stochastic blockmodels: First steps. *Social Networks* **5**, 2 (1983), 109–137.

[6] NEWMAN, M. E. The structure and function of complex networks. *SIAM review* **45**, 2 (2003), 167–256.

[7] TRAAG, V. A., ET AL. Narrow scope for resolution-limit-free community detection. *Physical Review E* **84**, 1 (2011), 016114.

[8] TRAAG, V. A., ET AL. From Louvain to Leiden: guaranteeing well-connected communities. *Scientific reports* **9**, 1 (2019), 1–12.