A novel heuristic community detection algorithm, termed CoDeSEG, which identifies communities by minimizing the network's two-dimensional structural entropy within a potential game framework, and introduces a structural entropy-based node overlapping heuristic for detecting overlapping communities, with a near-linear time complexity.
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 existing methods are limited to specific types of graph structures (such as unweighted or undirected graphs) or are designed solely for detecting static communities, reducing their broader applicability. To address these issues, we propose a novel heuristic community detection algorithm, termed CoDeSEG, which identifies communities by minimizing the network's two-dimensional (2D) structural entropy within a potential game framework. In the game, nodes decide to stay in the 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. Furthermore, we design a cascading influence propagation-based adaptive community update strategy, which dynamically identifies and processes nodes whose community affiliations may change during graph evolution, thereby effectively extending CoDeSEG to dynamic community detection scenarios. Experimental results on fourteen large-scale networks demonstrate that CoDeSEG achieves state-of-the-art performance across three community detection tasks (overlapping, non-overlapping, dynamic), while also delivering substantial improvements in detection efficiency.
Community detection is essential for uncovering the functional organization of complex networks. While traditional methods often rely on edge density, motif-based approaches use higher-order structural patterns to identify communities. However, existing research frequently employs conventional motifs, such as triangles or 4-node cliques, or lacks validation against networks with ground-truth communities. This study addresses these limitations by systematically evaluating eight small motifs across both synthetic and real-world networks with known community structures. We propose a framework that transforms unweighted graphs into weighted representations by assigning weights to node pairs based on their co-occurrence frequency within specific graphlets, while also preserving information about the original edges, rather than creating a potentially sparse (hyper)network. Thus, graphlet adjacency captures the topological complexity of a node by accounting for both its direct edges and the local connectivity patterns of its neighbors; this higher-order information is vital for accurate community detection. Our results demonstrate that graphlet-based weighting significantly enhances community detection in networks. We find that no single "universal" motif optimizes performance across all real-world networks. Rather than favoring only dense, clique-based structures, our findings highlight that simpler motifs can also provide strong performance in networks. These results suggest that relying exclusively on cliques may overlook critical connectivity patterns, offering a new perspective on how higher-order structures define communities in networks.
Anastasiia Dziuba, Jure Pražnikar· Journal of Intelligence and...· 0 citations
This study introduces a new ranking framework that integrates a quasi-Laplacian structural measure with a gravity-inspired aggregation process and demonstrates that the proposed framework consistently outperforms existing techniques in terms of accuracy, resolution, and computational simplicity.
This work proposes two scalable greedy algorithms based on gradient-guided edge selection that efficiently approximate marginal gains and prune the candidate edge set and achieves optimization performance comparable to exact greedy strategies while substantially reducing computational time.
Runze Zhang, Gengyu Wang, Zhongzhi Zhang· Proceedings of the 32nd ACM...· 0 citations
- Social networks generate vast amounts of relational data whose value lies not in individual data points but in the structure of connections among them. Graph analytics offers a mathematically grounded toolkit for uncovering this structure, ranging from simple degree counts to sophisticated community-detection and influence-propagation models. This paper presents a self-contained treatment of graph analytics as applied to social networks. We review the foundational graph-theoretic concepts underlying social network analysis, survey the principal families of graph analytics methods, and examine community detection and influence analysis in depth. To ground the discussion empirically, we conduct a case study on Zachary's Karate Club network and a synthetically generated scale-free network, computing centrality measures, detecting communities using the Louvain algorithm, and analysing degree-distribution behavior. The Louvain method partitions the Karate Club network into four communities with a modularity of 0.4266, closely matching the network's known factional split, while the synthetic network exhibits an approximate power-law degree distribution with exponent 1.76, consistent with preferential-attachment growth. We conclude with a discussion of open challenges and directions for future research, including dynamic graph analytics, scalability to billion-edge networks, and privacy-preserving analysis.
S. Sharma· Iconic research and engineer...· 0 citations
Community detection is a central problem in network science, traditionally performed on graphs, often via modularity maximization. Yet, many real-world systems inherently involve higher-order interactions between more than two entities, naturally modeled as hypergraphs. In such contexts, pairwise projections obscure higher-order structure and may lead to misleading communities. Recent works thus addressed higher-order community detection, with hypermodularity as one promising candidate. The state-of-the-art algorithm
h-louvain
[Kaminski et al., J. ComNetw 2024] mixes greedy optimization techniques for both modularity and hypermodularity in a multilevel scheme. While being effective with default parameters, the algorithm lacks guidance on how to combine the two objectives and thus needs parameter tuning. This parameter tuning step uses probabilistic strategies such as Bayesian Optimization Technique (BOT), resulting in a very significant overhead in running time. In this paper, we propose three algorithmic variants of
h-louvain
to recover communities of high accuracy without the need for time-consuming searches of mixing parameters. Our variants consist of new ideas for creating starting solutions for greedy multilevel algorithms and additional post-processing steps inspired by the community detection algorithm
leiden
[Traag et al., SciRep 2019] for graphs. In extensive experiments with over 50 real-world and randomly generated graphs, we show that across nearly all test cases, a member of our algorithm suite matches or surpasses
h-louvain
w. r. t. Asymmetric RMI; hence, they provide a more faithful community representation than the state of the art.
Fabian Brandt-Tumescheit, Henning Meyerhenke· Social Network Analysis and...· 0 citations
During the past decades, the world shifted towards online transactions. From data exchange, service provision to business, users and providers rely on the internet and social networks as a common platform for sharing and trading. In order to ensure an effective and reliable management of these networks and the flow of information within them, it is essential to detect user profiles and communities. In that context, triangle detection is a fundamental task in network analysis, as triangles are the smallest structure in a community. However, identifying triangles in large-scale and dense networks is a heavy and highly time-consuming treatment, due to costly neighborhood intersection computations. Our research aims to optimize intersection computation by minimizing the number of comparisons performed, avoid triangle duplication throughout the detection process and thus reducing the overall computation time. The method we propose, Test With Jumps for triangle detection without duplicates (TWJtr-D), is a refined version of Test With Jumps for triangle detection (TWJtr) algorithm. It optimizes intersection computing between neighbors sorted lists while avoiding redundant comparisons and duplicated triangles. Experimental results, on real-world datasets, demonstrate that TWJtr-D significantly reduces computation time and outperforms state-of-the-art methods which process in a similar pattern. This highlights the efficiency of TWJtr-D for triangle detection in large-scale networks. Future work will upgrade this method to parallel processing to rank its efficiency among algorithms in the same field.
Sarah Balbouzi, Lougmiri Zekri, Kheira Mechach· ITEGAM- Journal of Engineeri...· 0 citations