From Leiden to Pleasure Island: The Constant Potts Model for Community Detection as a Hedonic Game

• URL: http://arxiv.org/abs/2509.03834v1
• Date: Thu, 04 Sep 2025 02:50:54 GMT
• Title: From Leiden to Pleasure Island: The Constant Potts Model for Community Detection as a Hedonic Game
• Abstract summary: We present a game-theoretic perspective on the Constant Potts Model (CPM) for partitioning networks into disjoint communities.<n>We emphasize its efficiency, robustness, and accuracy.<n>In community tracking scenarios, where initial partitions are used to bootstrap the algorithm with partial ground-truth information, our experiments reveal that robust partitions yield higher accuracy in recovering ground-truth communities.
• Score: 0.0254890465057467
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: 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.

Related papers

• Characterizing Heterogeneous Rates in Finite Mixture Estimation via Partial Optimal Transport [88.55403215843967]
  Voronoi-based partial optimal transport (VPOT) for obtaining refined local and global convergence guarantees for the maximum likelihood estimator of the mixing measure.<n>Results hold in arbitrary fixed dimension without requiring mixing proportions to be uniformly bounded away from zero or prior knowledge of the true number of mixture components.
  arXiv  Detail & Related papers  (2026-09-15T04:32:53Z)
• A Secure and Private Distributed Bayesian Federated Learning Design [56.92336577799572]
  Distributed Federated Learning (DFL) enables decentralized model training across large-scale systems without a central parameter server.<n>DFL faces three critical challenges: privacy leakage from honest-but-curious neighbors, slow convergence due to the lack of central coordination, and vulnerability to Byzantine adversaries aiming to degrade model accuracy.<n>We propose a novel DFL framework that integrates Byzantine robustness, privacy preservation, and convergence acceleration.
  arXiv  Detail & Related papers  (2026-02-23T16:12:02Z)
• Mean-Field Control on Sparse Graphs: From Local Limits to GNNs via Neighborhood Distributions [5.081469534056712]
  Mean-field control (MFC) offers a scalable solution to the curse of dimensionality in multi-agent systems.<n>We bridge the gap to real-world network structures by proposing a rigorous framework for MFC on large sparse graphs.
  arXiv  Detail & Related papers  (2026-01-29T09:57:48Z)
• AI-Augmented Density-Driven Optimal Control (D2OC) for Decentralized Environmental Mapping [0.0]
  This paper presents an AI-augmented decentralized framework for multi-agent (multi-robot) environmental mapping under limited sensing and communication.<n>The proposed method introduces an adaptive and self-correcting mechanism that enables agents to iteratively refine local density estimates.
  arXiv  Detail & Related papers  (2026-01-28T23:55:02Z)
• Efficient Global-Local Fusion Sampling for Physics-Informed Neural Networks [5.257115841810259]
  We propose a Global-Local Fusion (GLF) Sampling Strategy that combines the strengths of both approaches.<n>New collocation points are generated by perturbing training points with Gaussian noise scaled inversely to the residual.<n>To further reduce computational overhead, a lightweight linear surrogate is introduced to approximate the global residual-based distribution.
  arXiv  Detail & Related papers  (2025-10-28T03:10:54Z)
• Discovering Communities in Continuous-Time Temporal Networks by Optimizing L-Modularity [9.695633462605564]
  We introduce LAGO, a novel method for uncovering dynamic communities by greedy optimization of Longitudinal Modularity.<n>Unlike prior approaches that rely on time discretization or assume rigid community evolution, LAGO captures the precise moments when nodes enter and exit communities.<n>We evaluate LAGO on synthetic benchmarks and real-world datasets, demonstrating its ability to efficiently uncover temporally and topologically coherent communities.
  arXiv  Detail & Related papers  (2025-10-01T10:25:16Z)
• What Makes Local Updates Effective: The Role of Data Heterogeneity and Smoothness [5.357435119431715]
  The thesis contributes to a self-contained guide for analyzing Local SGD in heterogeneous environments.<n>The thesis also extends to online learning, providing fundamental bounds under both first-order and bandit feedback.
  arXiv  Detail & Related papers  (2025-06-30T19:06:02Z)
• Benchmarking LLMs' Swarm intelligence [50.544186914115045]
  Large Language Models (LLMs) show potential for complex reasoning, yet their capacity for emergent coordination in Multi-Agent Systems (MAS) remains largely unexplored.<n>We introduce SwarmBench, a novel benchmark designed to systematically evaluate tasks of LLMs acting as decentralized agents.<n>We propose metrics for coordination effectiveness and analyze emergent group dynamics.
  arXiv  Detail & Related papers  (2025-05-07T12:32:01Z)
• A Local Perspective-based Model for Overlapping Community Detection [0.06206748337438322]
  We propose LQ-GCN, an overlapping community detection model from a local community perspective.<n>LQ-GCN employs a Bernoulli-Poisson model to construct a community affiliation matrix and form an end-to-end detection framework.<n>LQ-GCN achieves up to a 33% improvement in Normalized Mutual Information (NMI) and a 26.3% improvement in Recall compared to baseline models.
  arXiv  Detail & Related papers  (2025-03-27T14:43:42Z)
• Community Detection by ELPMeans: An Unsupervised Approach That Uses Laplacian Centrality and Clustering [0.0]
  Community in network analysis has become more intricate due to the recent hike in social networks.<n>This paper suggests a new approach named ELPMeans that strives to address this challenge.
  arXiv  Detail & Related papers  (2025-02-27T09:07:45Z)
• TANGO: Clustering with Typicality-Aware Nonlocal Mode-Seeking and Graph-Cut Optimization [2.4783546111391215]
  Density-based mode-seeking methods generate a emphdensity-ascending dependency from low-density points towards higher-density neighbors.<n>We introduce a novel concept called emphtypicality, by exploring the emphlocally defined dependency from a emphglobal perspective.<n>We devise an algorithm that effectively and efficiently identifies modes with the help of the global-view typicality.
  arXiv  Detail & Related papers  (2024-08-19T15:26:25Z)
• MNTD: An Efficient Dynamic Community Detector Based on Nonnegative Tensor Decomposition [3.714657619100999]
  This paper proposes a Modularity-ind Nonnegative RESCAL Decomposition (MNTD) model for dynamic community detection. The MNTD is superior to state-of-the-art dynamic community detection methods in the accuracy of community detection.
  arXiv  Detail & Related papers  (2024-07-26T16:17:53Z)
• CPR++: Object Localization via Single Coarse Point Supervision [55.8671776333499]
  coarse point refinement (CPR) is first attempt to alleviate semantic variance from an algorithmic perspective. CPR reduces semantic variance by selecting a semantic centre point in a neighbourhood region to replace the initial annotated point. CPR++ can obtain scale information and further reduce the semantic variance in a global region.
  arXiv  Detail & Related papers  (2024-01-30T17:38:48Z)
• Trust your Good Friends: Source-free Domain Adaptation by Reciprocal Neighborhood Clustering [50.46892302138662]
  We address the source-free domain adaptation problem, where the source pretrained model is adapted to the target domain in the absence of source data. Our method is based on the observation that target data, which might not align with the source domain classifier, still forms clear clusters. We demonstrate that this local structure can be efficiently captured by considering the local neighbors, the reciprocal neighbors, and the expanded neighborhood.
  arXiv  Detail & Related papers  (2023-09-01T15:31:18Z)
• Adaptive Local-Component-aware Graph Convolutional Network for One-shot Skeleton-based Action Recognition [54.23513799338309]
  We present an Adaptive Local-Component-aware Graph Convolutional Network for skeleton-based action recognition. Our method provides a stronger representation than the global embedding and helps our model reach state-of-the-art.
  arXiv  Detail & Related papers  (2022-09-21T02:33:07Z)
• GenDICE: Generalized Offline Estimation of Stationary Values [108.17309783125398]
  We show that effective estimation can still be achieved in important applications. Our approach is based on estimating a ratio that corrects for the discrepancy between the stationary and empirical distributions. The resulting algorithm, GenDICE, is straightforward and effective.
  arXiv  Detail & Related papers  (2020-02-21T00:27:52Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.