Community Detection in Large-Scale Complex Networks via Structural Entropy Game

Yantuan Xian, Pu Li, Hao Peng, Zhengtao Yu, Yan Xiang, Philip S. Yu · 2025

Read Community Detection in Large-Scale Complex Networks via Structural Entropy Game by Yantuan Xian, Pu Li, Hao Peng, Zhengtao Yu, Yan Xiang, Philip S. Yu (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2501-15130.txt.

Introduction

Yantuan Xian and five co-authors present a 2025 paper on finding communities in huge networks through a game based on structural entropy. Communities, dense clusters of nodes, reveal organization in social, biological, and information networks. At millions of nodes and billions of edges, many classic methods crawl or fail, and several handle only simple graph types.

Their algorithm treats each node as a player choosing which community to join. Moves that lower the network's two dimensional structural entropy pay off, so self interested play drives the map toward tidy communities. The design targets scale directly. Tests in the paper compare speed and quality against established detectors on large graphs.

Catalog record

CREATORYantuan Xian, Pu Li, Hao Peng, Zhengtao Yu, Yan Xiang, Philip S. Yu
YEAR2025
COLLECTIONPAPERS
FORMATTXT
FILE SIZE63 KB
VERSION1.0
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2501-15130

Browse the full library · About the Tower of Babel

Full text

The opening of the work, from the library's hosted text:

Community Detection in Large-Scale Complex Networks via Structural Entropy Game Yantuan Xian, Pu Li, Hao Peng, Zhengtao Yu, Yan Xiang, Philip S. Yu Abstract . Community detection is a critical task in graph theory, social network analysis, and bioinformatics, where communities are defined as clusters of densely interconnected nodes. However, detecting communities in large-scale networks with millions of nodes and billions of edges remains challenging due to the inefficiency and unreliability of existing methods. Moreover, many current approaches are limited to specific graph types, such as unweighted or undirected graphs, reducing their broader applicability. To address these issues, we propose a novel heuristic community detection algorithm, termed CoDeSEG, which identifies communities by minimizing the two-dimensional (2D) structural entropy of the network within a potential game framework. In the game, nodes decide to stay in current community or move to another based on a strategy that maximizes the 2D structural entropy utility function. Additionally, we introduce a structural entropy-based node overlapping heuristic for detecting overlapping communities, with a near-linear time complexity. Experimental results on real-world networks demonstrate that CoDeSEG is the fastest method available and achieves state-of-the-art performance in overlapping normalized mutual information (ONMI) and F1 score. Conference: Proceedings of the ACM Web Conference 2025; April 28–May 2, 2025; Sydney, Australia. Proceedings of the ACM Web Conference 2025 (WWW ’25), April 28–May 2, 2025, Sydney, Australia CCS: Computing methodologies Cluster analysis CCS: Mathematics of computing Graph algorithms 1. Introduction Community refers to a set of closely related nodes within a network, also known as a cluster or module in literature ( Fortunato, 2010 ; Fortunato and Newman, 2022 ) . Community detection is a task that reveals fundamental structural information within real-world networks, providing valuable insights by identifying tightly knit subgroups. In drug discovery, for instance, detecting protein functional groups facilitates the identification of novel, valuable proteins ( Ma et al., 2019 ) . In social event detection, analyzing message groups within social streams helps to understand the development trends of events and analyze public sentiment ( Cao et al., 2024b ) . Community detection also plays a role in recent retrieval-augmented generation (RAG) applications, like GraphRAG ( Edge et al., 2024 ) . Furthermore, community detection has extensive applications across various domains, including recommender systems ( Basuchowdhuri et al., 2014 ) , medicine ( Barabási et al., 2011 ) , biomedical research ( Rahiminejad et al., 2019 ; Manipur et al., 2021 ) , social networks ( Fortunato and Hric, 2016 ; Peng et al., 2024 ) , and more. Figure 1 . Illustration of non-overlapping and overlapping community structures in a network. As illustrated in Figure 1 (b), most early research on community detection has focused on disjoint clusters, where each node belongs to a single community, and there is no overlap between communities ( Fortunato, 2010 ; Traag et al., 2019 ; Blondel et al., 2008 ; Raghavan et al., 2007 ; Traag et al., 2011 ; Cao et al., 2024a ; Yang et al., 2024 ) . However, nodes often participate in multiple communities in many real-world applications (as depicted in Figure 1 (c)), sparking a growing interest in detecting overlapping communities ( Palla et al., 2005 ; Xie et al., 2013 ; Kelley, 2009 ) . Overlapping community detection typically entails higher computational costs and time overhead than disjoint community detection. In the past two decades, numerous algorithms for overlapping community detection have been proposed, including those based on modularity ( Cherifi et al., 2019 ) , label propagation ( Lu et al., 2018 ; Xie et al., 2011 ) , seed expansion ( Whang et al., 2013 ; Hollocou et al., 2018 ) , non-negative matrix factorization ( Yang and Leskovec, 2013 ) , spectral clustering ( Van Lierde et al., 2019 ) . However, existing overlapping community detection methods ( Chen et al., 2010 ; Gopalan and Blei, 2013 ; Lancichinetti et al., 2009 ; Yang and Leskovec, 2013 ) struggle to scale to networks with millions of nodes and billions of edges, often requiring days or longer to produce results. Many well-established and widely-used methods for large-scale networks are typically limited to specific types of graphs, such as unweighted or undirected graphs, thereby restricting their applicability. For instance, algorithms like Bigclam ( Yang and Leskovec, 2013 ) and SLPA ( Xie et al., 2011 ) detect overlapping communities in unweighted and undirected graphs. Methods like Louvain ( Blondel et al., 2008 ) , Leiden ( Traag et al., 2019 ) , and LPA ( Raghavan et al., 2007 ) focus on detecting non-overlapping communities in undirected graphs. Detecting overlapping communities in weighted, directed, large-scale networks remains a significant challenge. In recent years, deep learning-based community detection models have achieved promising results by learning node embeddings and detecting communities through node clustering or classification ( Zou et al., 2023 ; Sun et al., 2024 ; Zeng et al., 2024 ) . However, due to the learning and encoding processes of deep models, these methods demonstrate inefficiencies when applied to large-scale networks ( Su et al., 2024 ; Jin et al., 2023 ) . To tackle these challenges, we propose a novel algorithm named CoDeSEG ( Co mmunity De tection via S tructural E ntropy G ame) for detecting overlapping communities in large-scale complex networks. The proposed algorithm follows the game-theoretic inspired community detection framework ( Chen et al., 2010 ) , named as community formation game . In the game, we quantify the rewards and required costs associated with nodes joining or leaving a community through the changes in structural entropy. The Nash equilibrium of the game directly corresponds to the network’s community structure, with each node’s community memberships at equilibrium serving as the output of the community detection algorithm. The community-formation-game-based algorithm shows its effectiveness and efficiency in large-scale networks. Lyu et al. propose the FOX ( Lyu et al., 2020 ) algorithm, which measures the closeness between nodes and communities by approximating the number of triangles in communities. Ferdowsi et al. introduce a two-phase non-cooperative game model for community detection, where non-overlapping communities are first identified using a local interaction utility function, followed by identifying overlapping nodes based on the payoffs derived from community memberships ( Ferdowsi and Aghababaei Samani, 2022 ) . In contrast to these methods, we define the potential function as the 2-dimensional structural entropy (2D SE) ( Li and Pan, 2016 ) of the network and derive an efficient node utility function computable in approximately constant time. By applying the node utility to the community formation game, we detect communities in large-scale networks efficiently. We also present a structural entropy-based node overlap heuristic function to detect overlapping communities, which can leverage the intermediate results of the community formation game to speed up the algorithm. Moreover, the proposed algorithms can apply to various graphs, whether unweighted, weighted, undirected, or directed graphs, to produce stable, reliable community structures in a unified framework. To our knowledge, CoDeSEG is the fastest known algorithm for large-scale network community detection. The algorithm’s simplicity also supports straightforward parallelization, further enhancing its efficiency by computing the node strategies concurrently. Experiments on real-world networks demonstrate that CoDeSEG consistently outperforms baselines in performance while incurring significantly lower time

Read the complete text