1 Introduction↩︎

Community refers to a set of closely related nodes within a network, also known as a cluster or module in literature [1], [2]. 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 [3]. In social event detection, analyzing message groups within social streams helps to understand the development trends of events and analyze public sentiment [4]. Community detection also plays a role in recent retrieval-augmented generation (RAG) applications, like GraphRAG [5]. Furthermore, community detection has extensive applications across various domains, including recommender systems [6], medicine [7], biomedical research [8], social networks [9], [10], and more. 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 [1], [11]–[15]. 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 [16]–[18]. Overlapping community detection typically entails higher computational costs and time overhead than disjoint community detection. Over the past two decades, numerous algorithms for overlapping community detection have been proposed, including those based on modularity [19], label propagation [20], [21], seed expansion [22], [23], non-negative matrix factorization [24], and spectral clustering [25]. However, existing overlapping community detection methods [24], [26], [27] 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 [24] and SLPA [21] detect overlapping communities in unweighted and undirected graphs. Methods like Louvain [12], Leiden [11], and LPA [13] focus on detecting non-overlapping communities in undirected graphs. Thus, detecting overlapping communities in weighted, directed, large-scale networks remains a significant challenge.

Many real-world networks, particularly online social networks such as Facebook and Twitter, are inherently dynamic, with their network structures continually evolving over time. Correspondingly, the community structures within these networks also exhibit significant dynamism (as shown in Figure 1 (d)). Applying static community detection algorithms directly to network snapshots at different time points fails to fully utilize historical community information, and often results in substantially reduced computational efficiency as the network scale increases [28]. Contemporary incremental community detection methods attempt to address these challenges by updating community structures based on predefined heuristic rules [28]–[31] (e.g., node or edge insertions and deletions) or by extracting subgraphs affected by localized structural changes for partial re-optimization [32]–[34]. Nevertheless, these approaches often face challenges with computational efficiency in large-scale dense networks and struggle to fully identify all affected regions of the graph. As the network evolves, they also struggle to maintain a proper trade-off between detection accuracy and computational efficiency[33].

To tackle these challenges, we propose a novel algorithm named CoDeSEG (Community Detection via Structural Entropy Game) in large-scale complex networks. The proposed algorithm follows the game-theoretic inspired community formation game framework [26]. 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. Specifically, we first define the potential function as the 2-dimensional structural entropy (2D SE) [35] 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. Second, we 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. Third, we propose a cascading influence propagation-based adaptive community update strategy to extend our algorithm to dynamic network scenarios. This strategy comprises two core mechanisms: (1) hierarchical affected node identification, which detects directly affected nodes triggered by network changes (e.g., node/edge additions/deletions) and subsequently identifies indirectly affected nodes through cascading influence during node gaming; (2) adaptive node removal, which differentially evaluates the stability of nodes’ community affiliations based on node hierarchy (direct/indirect influence), and removes stable nodes. This strategy guides perturbed network regions to converge toward stable community structures during the multi-round game. Notably, the proposed algorithm is applicable to diverse network types, including unweighted, weighted, undirected, and directed graphs, generating stable and reliable community structures within a unified paradigm. The algorithm’s simplicity also facilitates straightforward parallelization, further enhancing its efficiency by allowing node strategies to be computed concurrently. Experiments on nine real-world networks and five synthetic networks demonstrate CoDeSEG’s consistent superiority across three community detection tasks (overlapping, non-overlapping, dynamic), outperforming all baselines in performance while incurring significantly lower time overhead than the second-fastest baseline. The codes of CoDeSEG and baselines, along with datasets, are publicly available on GitHub².

In summary, the contributions of this paper are as follows:

• We propose a novel heuristic algorithm for community detection in large-scale networks, termed  CoDeSEG. This algorithm introduces 2D SE to define the potential function of the community formation game and derives a node utility function with nearly constant time complexity. To the best of our knowledge, CoDeSEG is the fastest known algorithm for large-scale network community detection.

• We design a two-stage algorithm for detecting overlapping communities in diverse graphs. CoDeSEG identifies non-overlapping communities through the proposed community formation game and subsequently detects overlapping communities rapidly using a node overlap heuristic function based on structural entropy.

• We propose a cascading influence propagation-based adaptive community update strategy that integrates hierarchical influential node identification with an adaptive node removal mechanism, thereby extending CoDeSEG to dynamic network environments. This strategy comprehensively identifies all potentially affected nodes and minimizes computational overhead, thereby achieving a better trade-off between detection efficiency and quality.

• Experimental results on fourteen large-scale networks and three detection tasks (i.e., overlapping, non-overlapping, and dynamic detection) demonstrate that the CoDeSEG  algorithm consistently outperforms state-of-the-art community detection methods in terms of ONMI, NMI, and F1-score, while also achieving substantial reductions in detection time. Notably, compared to the fastest overlapping detection baseline, CoDeSEG  achieves an average speedups of 33 times.

This paper is an extended version of our conference paper [36], published at The Web Conference 2025. The journal version introduces the following major enhancements: (1) We propose a novel cascading influence propagation-based adaptive community update strategy, which enables the original framework to adapt to dynamic networks while preserving theoretical consistency (Section 3.4). (2) We conduct experiments on two large-scale real-world dynamic network datasets and provide detailed empirical analyses that comprehensively validate the effectiveness and stability of the proposed method in dynamic community detection tasks (Sections 5.1.3, 5.2 and 5.3). In addition, we perform non-overlapping community detection experiments on five additional large-scale synthetic networks (Section 5.1.2); (3) We present a more comprehensive discussion of related work, particularly in dynamic community detection and structural entropy (Section 6).

2 Preliminaries↩︎

In this section, we summarize the concepts and definitions related to the background of our work, including community detection, community formation games, and structural entropy.

2.1 Community Detection↩︎

Community detection aims to identify groups of nodes within a network that exhibit high internal cohesion and low external coupling. Based on the temporal characteristics of the network, which can be categorized into static community detection and dynamic community detection.

2.2 Community Formation Game↩︎

Chen et al. [26] propose a game-theoretic-based community detection framework, named community formation game, that simulates the strategy selection and interactions of nodes within a network to identify community structures. In the game, each node \(x \in \mathcal{V}\) is treated as a rational participant (player), consistently choosing the best strategy (community) that maximizes utility function. When the game converges to a Nash equilibrium, it corresponds to the communities the algorithm detects. We present relevant definitions, as follows:

2.3 Structural Entropy↩︎

Structural entropy (SE) quantifies uncertainty and information content in complex networks, with lower values indicating more ordered structures and higher values reflecting greater disorder [35]. Communities within a network can be identified by minimizing its 2D SE.

3 Methodology↩︎

This section introduces the proposed algorithm, CoDeSEG. Section 3.1 presents the structural entropy-based heuristic for the community formation game, followed by Section 3.2, which details key strategy computations. The complete static community detection algorithm is outlined in Section 3.3, while Section 3.4 introduces the Cascading Influence Propagation-based Adaptive (CIPA) community update strategy for dynamic community detection. Furthermore, Section 3.5 analyzes the time and space complexity of CoDeSEG, and Section 3.6 describes its parallel implementation.

3.1 Structural Entropy based Heuristic Function↩︎

The proposed algorithm models community formation as a potential game, where the potential function is the network’s 2D SE \(\mathcal{H}^{2}(\mathcal{P})\). Each node selects the community that most reduces this entropy as its optimal strategy. When the game converges to a Nash equilibrium, yielding communities with a minimized 2D SE. Consider a node in \(G\) adopting a strategy, such as altering its community membership, resulting in a new partition denoted by \(\mathcal{P}^\prime\). We define the heuristic function \(\Delta\) as the change in the potential function: \[\Delta = \mathcal{H}^{2}(\mathcal{P}) - \mathcal{H}^{2}(\mathcal{P}^\prime).\]

In the disjoint community formation game, each node aims to maximize the value of \(\Delta\) by moving to the best adjacent community, resulting in a partition with reduced 2D structural entropy. A node can choose from three strategies: Stay, Leave and be alone, and Transfer to another community.

Stay. Node \(x\) decides to stay in the current community, then the partition \(\mathcal{P}\) remains unchanged, \(\mathcal{P}^\prime=\mathcal{P}\). The value of heuristic function \(\Delta_{\text{S}}\) is: \[\Delta_{\text{S}} = \mathcal{H}^{2}(\mathcal{P}) - \mathcal{H}^{2}(\mathcal{P}^\prime) = 0.\]

Leave and be alone. Suppose the original partition is \(\mathcal{P}=\{\mathcal{C}_1, \mathcal{C}_2, \dots, \mathcal{C}_k\}\) and when node \(x\) leaves its community \(\mathcal{C}_k\), resulting a new partition \(\mathcal{P}^\prime=\{\mathcal{C}_1, \mathcal{C}_2, \dots, \mathcal{C}_k^\prime, \{ x\}\}\), where \(\mathcal{C}_k = \mathcal{C}_k^\prime \cup \{x\}\). The value of heuristic function \(\Delta_{\text{L}}(x, \mathcal{C}_k)\) is: \[\label{EqDeltaLeave} \begin{align} \Delta_{\text{L}}(x, \mathcal{C}_k) =& \mathcal{H}^{2}(\mathcal{P}) - \mathcal{H}^{2}(\mathcal{P}^\prime) \\ =& \mathcal{H}^{2}(\mathcal{C}_k) - \mathcal{H}^{2}(\mathcal{C}_k^\prime) - \mathcal{H}^{2}(\{x\}). \end{align}\tag{1}\] The calculation details for Equation (1 ) are provided in Section 3.2. If community \(\mathcal{C}_k\) is a singleton, then \(\Delta_\text{L}(x, \mathcal{C}_k) = 0\).

Transfer to another community. Suppose \(x\) transfers from \(\mathcal{C}_1\) to \(\mathcal{C}_k\), the original partition is \(\mathcal{P}=\{\mathcal{C}_1, \mathcal{C}_2, \dots, \mathcal{C}_k\}\) and the new partition is \(\mathcal{P}^\prime=\{\mathcal{C}_1^\prime, \mathcal{C}_2, \dots, \mathcal{C}_k^\prime\}\), where \(\mathcal{C}_1^\prime = \mathcal{C}_1 \backslash \{x\}\), \(\mathcal{C}_k^\prime = \mathcal{C}_k \cup \{x\}\). The transfer strategy can be seen as a composite transformation of two steps. Firstly, node \(x\) leaves \(\mathcal{C}_1\) and does not join any community, which yields an intermediate \(\mathcal{P}^m = \{ \mathcal{C}_1^\prime, \mathcal{C}_2, \dots, \mathcal{C}_k, \{x\} \}\). Secondly, node \(x\) join \(\mathcal{C}_k\), resulting in new partition \(\mathcal{P}^\prime\). We can easily figure out that the second step is an inverse transformation of the Leave and be alone strategy. Therefore, the value of the heuristic function \(\Delta_{\text{T}}(x, \mathcal{C}_1, \mathcal{C}_k)\) can be expressed as: \[\label{EqDeltaTransfer} \begin{align} \Delta_{\text{T}}&(x, \mathcal{C}_1, \mathcal{C}_k) = \mathcal{H}^{2}(\mathcal{P}) - \mathcal{H}^{2}(\mathcal{P}^\prime)\\ &= (\mathcal{H}^{2}(\mathcal{P}) -\mathcal{H}^{2}(\mathcal{P}^m)) + (\mathcal{H}^{2}(\mathcal{P}^m) - \mathcal{H}^{2}(\mathcal{P}^\prime)) \\ &= \Delta_{\text{L}}(x, \mathcal{C}_1) - \Delta_{\text{L}}(x, \mathcal{C}_k). \end{align}\tag{2}\] Since a node \(x\) may have several adjective target communities, we denote the best-transferring with max \(\Delta_{\text{T}}\) as \(\Delta_{\text{T}}(x, \mathcal{C}_{\text{best}})\).

In our community formation game, a node will only join a new community if it decreases the network’s 2D structural entropy. Consequently, a node will prefer to stay in its current community unless another community offers a further reduction in 2D structural entropy. Thus, the Leave and be alone strategy is optional. As shown in Figure 2, node \(x\) selects its movement strategy according to the following formula: \[\label{EqStrategy} S(x) = \max (\Delta_\text{S}, \Delta_{\text{T}}(x, \mathcal{C}_{\text{best}})).\tag{3}\] After identifying disjoint communities, we propose using a SE heuristic to determine whether a node \(x\) should overlap between communities.

Overlap nodes. Suppose partition \(\mathcal{P} = \{\mathcal{C}_1, \mathcal{C}_2, \dots, \mathcal{C}_k\}\), for a node \(x \notin \mathcal{C}_k\), exists \(y \in \text{Neighbors}(x), \;y \in \mathcal{C}_k\). If we copy (overlap) \(x\) to community \(\mathcal{C}_k\), we create a new overlapping partition \(\mathcal{P}^\prime = \{\mathcal{C}_1, \mathcal{C}_2, \dots, \mathcal{C}_k^\prime\}\), where \(\mathcal{C}_k^\prime = \mathcal{C}_k \cup \{x\}\). Since the copy action does not affect the origin community, we define the overlapping heuristic function as follows: \[\label{EqOverlap} \begin{align} \Delta_{\text{O}}(x, \mathcal{C}_k) = \mathcal{H}^{2}(\mathcal{P}) - \mathcal{H}^{2}(\mathcal{P}^\prime) = - \Delta_L(x, \mathcal{C}_k^\prime). \\ \end{align}\tag{4}\] If \(\Delta_\text{O}(x, \mathcal{C}_k) > 0\), it means the overlap action reduces the partition’s structural entropy. However, this criterion may allow excessive node overlapping. To address this, we propose using the average value of \(\Delta_\text{L}(x_i, \mathcal{C}_k)\) for nodes in the community \(\mathcal{C}_k\) as a threshold. Nodes can only overlap with \(\mathcal{C}_k\) if their \(\Delta_\text{L}(x, \mathcal{C}_k)\) exceeds this threshold.

3.2 Efficient computation of \(\Delta_{\text{L}}(x, \mathcal{C}_k)\)↩︎

The formulas for the strategies above highlight that efficiently completing the community formation game depends on quickly computing the node leave strategy. By deriving Equation (1 ), we obtain an efficient formula for computing \(\Delta_{\text{L}}(x, \mathcal{C}_k)\): \[\label{EqEfficentDeltaLeave} \begin{align} &\Delta_{\text{L}}(x, \mathcal{C}_k) = \mathcal{H}^{2}(\mathcal{P}) - \mathcal{H}^{2}(\mathcal{P}^\prime) \\ &= \frac{g_{\mathscr{c}_k^\prime}}{v_\lambda} \log \frac{v_{\mathscr{c}_k^\prime}}{v_\lambda} - \frac{g_{\mathscr{c}_k}}{v_\lambda} \log \frac{v_{\mathscr{c}_k}}{v_\lambda} + \frac{d_x}{v_\lambda} \log \frac{v_{\mathscr{c}_k}}{v_\lambda} + \frac{v_{\mathscr{c}_k^\prime}}{v_\lambda} \log \frac{v_{\mathscr{c}_k}}{v_{\mathscr{c}_k^\prime}}, \end{align}\tag{5}\] where \(v_{\mathscr{c}_k^\prime}\) represents the volume of \(\mathcal{C}_k^\prime\), and \(g_{\mathscr{c}_k^\prime}\) denotes the sum of the degrees (weights) of the cut edges of \(\mathcal{C}_k^\prime\). The detailed derivation is provided in Appendix C.

By caching all community volumes \(\{ v_{c_1}, v_{c_2}, \dots, v_{c_k} \}\) and cut edge summations \(\{ g_{c_1}, g_{c_2}, \dots, g_{c_k} \}\), computing \(v_{c_k^\prime}\) and \(g_{c_k^\prime}\) becomes straightforward, allowing us to calculate \(\Delta_{\text{L}}(x, \mathcal{C}_k)\) in constant time complexity, \(O(1)\). For an undirected graph, \(v_{c_k^\prime}\) and \(g_{c_k^\prime}\) can be computed using the following equations: \[\label{EqUpdateVolCut} v_{c_k^\prime} =v_{c_k} - d_x, \quad g_{c_k^\prime} = g_{c_k} + 2 d_x^{\text{in}} - d_x,\tag{6}\] where \(d_x^{\text{in}}\) denotes the sum of edge weights between node \(x\) and its neighbor nodes within community \(\mathcal{C}_k\). The proposed strategies can be easily adapted for directed networks by separately considering the in-degree and out-degree of node \(x\) relative to community \(\mathcal{C}_k\). Consequently, Equation (6 ) is updated accordingly: \[v_{c_k^\prime} = v_{c_k} - d_x, \quad g_{c_k^\prime} = g_{c_k} + d_x^{\text{in}} +d_x^{\text{out}} - d_x .\] Once a node \(x\) is transferred to a new community, we will update the statistics of the target and source communities using the following formulas, \[\label{EqUpdateTarget} \begin{array}{ll} v_{c_t} \gets v_{c_t} + d_x, & v_{c_k} \gets v_{c_k^\prime},\\ g_{c_t} \gets g_{c_t} - 2d_x^{\text{in}} + d_x, & g_{c_k} \gets g_{c_k^\prime}.\\ \end{array}\tag{7}\] For directed graphs, we can easily derive similar formulas for updating community statistics.

3.3 Static Community Detection Algorithm↩︎

After developing effective methodologies for community formation games, we introduce a new two-stage algorithm for overlapping community detection. Figure 3 provides an overview of this algorithm. In the non-overlapping phase, each node \(x\) sequentially implements the best strategy from Equation (3 ) until all nodes are assigned to their communities. In the overlapping phase, nodes \(x\) can overlap multiple communities if the overlap action meets the specified threshold.

Non-overlapping Community Detection. We propose a non-overlapping community detection algorithm designed to minimize 2D SE using a potential game, where the optimal strategy is computed by Equation (3 ). Once the game reaches a Nash equilibrium, the communities stabilize and no longer change. As shown in Algorithm [AlgNonOverlapDetect], we initialize each node as an individual cluster and compute their volumes, setting the cut edges’ summations as the node degrees (lines 1-3). In a directed network, the volumes of these communities are node in-degrees, and the summations of cut edges are node out-degrees. The heart of our algorithm lies in an iterative loop of community formation games. We evaluate every node \(x\) in each iteration and determine the optimal strategy for \(x\) to significantly minimize the 2D SE of the graph (lines 7-17). To get the best strategy for a node, we first compute the heuristic \(\Delta_{\text{L}}(x, \mathcal{C}_x)\) that provides a measure of the impact when node \(x\) leaves its current community. The maximum heuristic function value \(\Delta_{\max}\) is initially set to \(\Delta_{\text{L}}(x, \mathcal{C}_x)\), and the target community index \(t\) is set to \(t_c\) indicating stay in the current community (lines 7-11). Then, we evaluate each adjacent community \(\mathcal{C}_k\) to determine if moving node \(x\) to any of these communities would result in a greater heuristic function value (lines 12-17). For each \(\mathcal{C}_k\), we compute the transfer heuristic \(\Delta_{\text{T}}(x, \mathcal{C}_x, \mathcal{C}_k)\) and compare it to the maximum heuristic function value. If moving to an adjacent community \(\mathcal{C}_k\) offers a larger heuristic function value, we update \(\Delta_{\max}\) and set \(t\) to the index of community \(\mathcal{C}_k\) (lines 15-17). Finally, we find the optimal index \(t\) and the maximum heuristic function value \(\Delta_{\max}\). Suppose the strategy indicates that node \(x\) should move to another community. We transfer \(x\) from its current community \(\mathcal{C}_x\) to the target community \(\mathcal{C}_t\) (line 19) and update the statistics of the source and target communities, such as adjusting community volumes and cut edge summations via Equation (7 ) (line 20).

At the end of each iteration, if all nodes choose to stay in their current community (i.e., \(M=0\)), the algorithm is considered converged. In practice, we introduce a stopping criterion: if the average of \(\Delta_{\text{T}}\) decreases significantly compared to the initial average node entropy, it suggests that further adjustments will have little impact on improving the community structure. Formally, the stopping criterion is defined as: \[\label{eq:termination} \frac{\Delta_{sum}}{M} \leq \frac{\tau_n}{|V|} \sum_{x \in V} - \frac{d_x}{v_\lambda} \cdot \log \frac{d_x}{v_\lambda} ,\tag{8}\] where \(\Delta_{sum}\) represents the change in the graph’s 2D SEduring the current iteration, \(M\) denotes the number of nodes that changed communities, and \(\tau_n\) is a hyper-parameter, with a range of \((0, 1)\). Ultimately, our algorithm outputs the partition \(\mathcal{P}\), which represents the final assignment of nodes into non-overlapping communities.

Overlapping Community Detection. The overlapping community detection algorithm begins with a non-overlapping partition \(\mathcal{P}\) of the network \(G\). The goal of the overlapping community detection (Algorithm 5) is to generate a set of overlapping communities \(\mathcal{P}^o\) of \(G\). Initially, \(\mathcal{P}^o\) is identical to \(\mathcal{P}\). For each node \(x\) in the network, the algorithm iterates over all its adjacent communities \(\mathcal{C}_k\). It computes the overlapping heuristic function \(\Delta_{\text{O}}(x, \mathcal{C}_k)\). If the heuristic function exceeds the overlap threshold \(\tau_o\), we overlap node \(x\) to community \(\mathcal{C}_k\). We define the overlap threshold \(\tau_o\) as the average of node heuristic function values: \[\tau_o = \frac{\gamma}{|\mathcal{C}_k|} \sum_{x_i \in \mathcal{C}_k } { - \Delta_L(x_i, \mathcal{C}_k) },\] where \(\gamma\) represents the overlap factor, which is employed to actively regulate the degree of community overlapping. The iterative process ensures that nodes overlap in communities, significantly reducing the network’s 2D structural entropy.

3.4 Dynamic Community Detection Algorithm↩︎

As illustrated in Fig.6, we present a Cascading Influence Propagation-based Adaptive (CIPA) strategy to extend CoDeSEG for dynamic community detection. CIPA is derived from the node structural entropy game and adaptively maintains the set of active (gameable) nodes by tracking variations in node-selection strategies. In this way, it preserves detection accuracy while improving computational efficiency. The proposed method integrates two key components: Hierarchical affected node identification and Adaptive node removal.

The hierarchical affected node identification mechanism is designed to dynamically identify nodes whose strategies may change in the current network snapshot. To achieve this, the affected nodes are partitioned into two disjoint sets: (i) the directly affected set \(\mathcal{V}^{d}\), consisting of newly added nodes and those involved in edge additions or deletions, and (ii) the indirectly affected set \(\mathcal{V}^{ind}\), comprising nodes whose neighbors belong to the directly affected set and whose community memberships have changed. Initially, the directly affected set is constructed by quantifying the variations in nodes and edges between two consecutive snapshots: \[\label{dr95nodes} \begin{align} \mathcal{V}^{\text{add}} &= \mathcal{V}_t \setminus \mathcal{V}_{t-1}, \quad \mathcal{E}^{\text{add}} = \mathcal{E}_t \setminus \mathcal{E}_{t-1}, \\ \mathcal{V}^{\text{del}} &= \mathcal{V}_{t-1} \setminus \mathcal{V}_t, \quad \mathcal{E}^{\text{del}} = \mathcal{E}_{t-1} ,\setminus \mathcal{E}_t,\\ \mathcal{V}^{d} &= \mathcal{V}^{\text{add}} \setminus \mathcal{V}^{\text{del}} \cup \bigcup_{x \in \mathcal{V}^{\text{del}}} \mathcal{N}_x\\ &\cup \{ x \mid \exists e \in \mathcal{E}^{\text{del}} \cup \mathcal{E}^{\text{add}} , x \in e \}, \end{align}\tag{9}\] where \(\mathcal{V}_t\) and \(\mathcal{E}_t\) denote the node and edge sets of the current snapshot \(G_t\), and \(\mathcal{V}_{t-1}\) and \(\mathcal{E}_{t-1}\) denote those of the previous snapshot \(G_{t-1}\). The sets \(\mathcal{V}^{\text{add}}\) and \(\mathcal{E}^{\text{add}}\) represent the newly added nodes and edges, while \(\mathcal{V}^{\text{del}}\) and \(\mathcal{E}^{\text{del}}\) denote the removed nodes and edges, respectively. \(\mathcal{N}_x\) denotes a node’s neighboring set. Newly added nodes are initialized as independent communities, leading to the following initial partition: \[\label{init95patition} \mathcal{P}_t = \mathcal{P}_{t-1} \cup \left\{ \{x\} \mid x \in \mathcal{V}^{\text{add}} \right\},\tag{10}\] where \(\mathcal{P}_t\) and \(\mathcal{P}_{t-1}\) denote the community partitions of \(G_{t}\) and \(G_{t-1}\), respectively. Furthermore, during the game process, if an affected node \(x\) (\(x \notin \mathcal{V}^{\text{add}}\)) updates its strategy (i.e., \(S(x) \neq \Delta_s\)), all of its previously unaffected neighbors are incorporated into the indirectly affected node set: \[\label{eqVind} \mathcal{V}^{ind} \gets \mathcal{V}^{ind} \cup \{y \mid y \in \mathcal{N}_x \setminus \mathcal{V}^d\}.\tag{11}\]

The adaptive node removal mechanism aims to exclude stabilized nodes from the affected set, thereby reducing redundant computations and enhancing detection efficiency. Considering the varying degrees of influence, distinct removal strategies are applied to directly and indirectly affected nodes. Specifically, a directly affected node is deemed stabilized and removed from the affected set if its chosen strategy remains unchanged for \(r\) consecutive iterations (i.e., \(S(x) = \Delta_s\)). For indirectly affected nodes, those that remain in their current communities are considered unaffected and are consequently removed. Conversely, if an indirectly affected node changes its strategy, it is regarded as genuinely influenced and is transferred to the directly affected set for continued monitoring. This process is formalized as follows: \[\begin{cases} \mathcal{V}^{d} \leftarrow \mathcal{V}^{d} \setminus \{x\} & \text{if } x \in \mathcal{V}^{d} \land l_x \geq r \\ \mathcal{V}^{\text{ind}} \leftarrow \mathcal{V}^{\text{ind}} \setminus \{x\} & \text{if } x \in \mathcal{V}^{\text{ind}} \land S(x) = \Delta_S \\ \begin{cases} \mathcal{V}^{\text{ind}} \leftarrow \mathcal{V}^{\text{ind}} \setminus \{x\} \\ \mathcal{V}^{d} \leftarrow \mathcal{V}^{d} \cup \{x\} \end{cases} & \text{if } x \in \mathcal{V}^{\text{ind}} \land S(x) \neq \Delta_S \end{cases} ~,\] where \(l_x\) denotes the number of consecutive iterations during which \(x\) has remained stable. It is worth noting that, for overlapping dynamic networks, one may first obtain the non-overlapping community structure via CIPA, and subsequently derive the overlapping communities based on Algorithm 5. The pseudo-code of CIPA is provided in Appendix D.

3.5 Algorithm Complexity↩︎

Time complexity. In static community detection, CoDeSEG’s time complexity is \(O(I \cdot d_{\max} \cdot |\mathcal{V}|)\), where \(|\mathcal{V}|\) denotes the number of nodes in the graph, \(d_{\max}\) represents the maximum degree of any node, and \(I\) is the number of iterations required for the algorithm to converge to a stable partition. In dynamic detection, the time complexity is reduced to \(O(I\cdot d_{\max} \cdot |\mathcal{V}^{d} \cup \mathcal{V}^{ind}|)\), where \(\mathcal{V}^{d}\) and \(\mathcal{V}^{ind}\) denote the sets of directly and indirectly affected nodes, respectively. Detailed time complexity analysis is provided in Appendix E.

Space complexity. The overall space complexity of the proposed algorithm is \(O(|\mathcal{E}|)\), where \(|\mathcal{E}|\) represents the number of edges in the network. Specifically, the storage of the node adjacency list requires \(O(2 \cdot |\mathcal{E}|) = O(|\mathcal{E}|)\) space, while the space complexities for storing the community volume, community cut, community partition, and node degree are all \(O(|\mathcal{V}|)\). Consequently, the overall space complexity of the algorithm is \(O(|\mathcal{E}| + 4 \cdot |\mathcal{V}|) = O(|\mathcal{E}|)\), where \(|\mathcal{V}| \leq |\mathcal{E}|\).

3.6 Parallelism Implementation↩︎

Parallelization can fully exploit the multi-core architecture of modern CPUs, significantly reducing the algorithm’s runtime. The proposed algorithm is readily parallelizable. In our parallelized CoDeSEG algorithm, each node in different threads independently calculates the optimal strategy based on the current partition. During the execution of the movement strategy, a mutex lock ensures the correct update of statistics such as \(C_k\) and \(g_c\). It is crucial to note that when the volume and cut of a community are concurrently updated by multiple threads, the increments must be recalculated. However, it is worth mentioning that as the algorithm progresses, the number of nodes requiring movement decreases sharply, thereby enhancing the acceleration effect of parallelism.

During the overlapping community detection, CoDeSEG is inherently parallelizable. A node’s inclusion in an overlapping community is determined by the change in entropy resulting from its addition, which depends only on the outcomes of non-overlapping community detection and the node’s connections to those communities. This allows the overlapping strategies for each node to be calculated concurrently.

4 Experimental Setup↩︎

This section provides a comprehensive description of the experimental setup, including the datasets, baseline methods for comparison, evaluation metrics, and implementation details.

Datasets. To thoroughly evaluate the effectiveness of CoDeSEG, we conduct systematic experiments on three types of network datasets: (1) overlapping community detection on seven large-scale real-world networks from SNAP [37], including Amazon, YouTube, DBLP, LiveJournal, Orkut, Friendster, and Wiki; (2) comparative overlapping community detection on two complex social networks and five large-scale synthetic networks, specifically X12_static (Tweet12_static) [38], X18_static (Tweet18_static) [39], LFRs; and (3) dynamic community detection performance evaluation on two real-world dynamic networks, namely X12 (Tweet12) and X18 (Tweet18). Statistics of datasets are summarized in Table 1, with detailed descriptions provided in Appendix F.

Baselines. To assess the performance of CoDeSEG  across various networks, we compare it with four overlapping detection methods–SLPA [21],Bigclam [24], NcGame [40], and Fox [41], four non-overlapping detection methods–Louvain [12], DER [42], Leiden [11], and FLPA [43], and four dynamic detection methods–QCA [30], DynaMo [28], DCDME [32], and DCDBFE [33]. Detailed descriptions and implementations of baselines are provided in Appendix G.

Evaluation Metrics. To validate the effectiveness of the proposed algorithm, we employ two widely used evaluation metrics: the Average F1-Score (F1) [24], [44] and Overlapping Normalized Mutual Information (ONMI) [45]. For non-overlapping community detection tasks, we instead adopt the standard Normalized Mutual Information (NMI). More details on these metrics are provided in Appendix H.

5.7pt

Implementation. In our CoDeSEG, the termination threshold \(\tau_n\), overlapping factor \(\gamma\), and round stability threshold \(r\) are set to 0.3, 1, and 2, respectively. All experiments are conducted on a server with a hardware configuration of dual 16-core Intel Xeon Silver 4314 processors @ 2.40GHz and 1024GB of memory.

5 Experiments↩︎

In this section, we conduct extensive experiments to validate the effectiveness of the proposed CoDeSEG. Our goal is to address the following five key questions: RQ1: How does the CoDeSEG perform in overlapping, non-overlapping, and dynamic community detection tasks compared to baselines? RQ2: How does the detection efficiency of CoDeSEG on different tasks compare to the baselines? RQ3: How does the performance of the CIPA-based dynamic CoDeSEG compare with that of the static CoDeSEG? RQ4: Can CoDeSEG achieve fast convergence, and how do key hyperparameters impact its performance? RQ5: How does parallelization of CoDeSEG influence its performance and efficiency?

5.5pt

5.1 Effectiveness of CoDeSEG↩︎

In this section, we perform experiments on overlapping, non-overlapping, and dynamic networks to comprehensively evaluate the effectiveness of CoDeSEG. As summarized in Tables ¿tbl:tab:Result1? to ¿tbl:tab:Result3?, the results indicate that CoDeSEG significantly outperforms all baseline methods across all evaluated network scenarios, confirming the effectiveness of the utility function that combines potential games with structural entropy in uncovering network community structures.

5.1.1 Overlapping community detection↩︎

As shown in Tables ¿tbl:tab:Result1?, CoDeSEG consistently ranks first or second in both ONMI and F1 scores across all seven overlapping networks, demonstrating particularly strong performance on YouTube, Orkut, Friendster, and Wiki, where it achieves the highest values. This highlights the effectiveness and robustness of using structural entropy to uncover community structures in networks. Moreover, the proposed overlapping heuristic function effectively distinguishes the overlapping community memberships of nodes. Specifically, compared to SLPA and Bigclam, CoDeSEG consistently achieved the highest ONMI and F1 scores across all datasets. On larger networks such as Orkut and Friendster, the performance of SLPA and Bigclam deteriorated significantly. For SLPA, the inherent randomness in the selection of initial nodes and the label propagation process may negatively affect the detection results. Similarly, Bigclam relies on an initial estimate of community size, and inaccuracies in estimating the number of communities can adversely affect the network’s structural analysis. Although the NcGame algorithm achieves the best F1 score on the Amazon dataset, its generalization ability on other datasets is relatively weak, with performance dropping significantly. This limitation arises because NcGame focuses exclusively on maximizing each node’s individual utility, neglecting the constraints that nodes must satisfy when joining communities. Additionally, the second-best FOX algorithm determines community memberships based on an approximate evaluation of the number of local triangles associated with each node to assess community cohesiveness. This approximation can result in incorrect community assignments, particularly for high-degree nodes. Notably, CoDeSEG uniquely supports community detection in the large-scale directed network Wiki, whereas baseline methods exhibit significant performance degradation when Wiki is treated as an undirected network. Specifically, CoDeSEG improves ONMI by 381.25% and F1 by 55.59% compared to the best-performing baseline, SLPA, underscoring its distinct advantages in directed network scenarios.

5.1.2 Non-overlapping community detection↩︎

As shown in Table ¿tbl:tab:Result2?, compared to all baselines, CoDeSEG achieves an average improvement of 31.33% in NMI and 4.02% in F1 score on X12_static and X18_static. On large-scale synthetic networks, the average improvements in NMI and F1 score reach 2.51% and 9.63%, respectively. Specifically, Leiden and Louvain consistently underperform compared to CoDeSEG across all networks. This is due to their tendency to excessively merge small communities during modularity maximization—a limitation exacerbated in dense networks. DER demonstrates poor performance in large-scale dense networks, primarily because its low-dimensional vectors fail to discriminate community structures under dense connectivity. Moreover, the algorithm incurs prohibitively high space complexity, exceeding available system memory when processing networks with 200K nodes (LFR_200K). Although FLPA works well on synthetic networks with clear community structures, its effectiveness declines on dense real-world networks as accumulated randomness during label propagation destabilizes community partitioning. In contrast, CoDeSEG exhibits significantly higher stability and robustness. Visual analysis of detection results can be found in Appendix I.

5.1.3 Dynamic community detection↩︎

As shown in Table ¿tbl:tab:Result3?, CoDeSEG achieves significant improvements: NMI and F1-scores increase by 6.95% and 10.70% on X12, and by 22.43% and 9.92% on X18, respectively. This demonstrates the strong adaptability of the CIPA-based CoDeSEG to complex dynamic networks. For the DCDME and DCDBFE methods, their reliance solely on local topological similarity while ignoring edge weights leads to significant accuracy degradation in dense networks with ambiguous community boundaries. For modularity-based methods (QCA and DynaMo), they suffer from the resolution limit of modularity, which biases results toward merging small communities. Specifically, QCA relies on predefined rules for the local modularity optimization of atomic events (single-node/edge changes). Over the long-term evolution of the network, the bias from these local decisions accumulates and eventually induces drift in community structure. Although DynaMo further refines the classification of network evolution events, its incremental update strategy only covers directly affected nodes and their first-order neighbors, failing to detect all potentially affected nodes transitively. Notably, the CIPA strategy employs a hierarchical affected node identification mechanism that more effectively covers globally affected nodes. Moreover, the utility function derived from community potential game and the network’s 2D SE enables nodes to make globally optimal decisions, resulting in more robust outcomes in dynamic community detection.

3pt

5.2 Efficiency of CoDeSEG↩︎

Table 2 reports the time consumption on overlapping and non-overlapping networks. For overlapping detection, CoDeSEG is consistently the most efficient, with the advantage becoming more pronounced on larger networks (e.g., LiveJournal, Orkut, and Friendster). On average, CoDeSEG achieves a \(33\times\) speedup over the fastest baseline per network. This is mainly because CoDeSEG converges in only a few iterations, whereas Bigclam typically requires many more. Moreover, Bigclam exhibits unstable convergence, leading to an unusually long runtime on YouTube (even longer than on larger networks such as LiveJournal and Orkut). SLPA’s detection time is limited by the specified number of iterations and the need to iteratively compare and remove detected communities, where some communities are subsets of others. NcGame cannot dynamically update key variables during detection, introducing additional computation on large-scale graphs. For FOX, runtime grows with the number of overlapping nodes. For non-overlapping detection, CoDeSEG yields a \(546\times\) speedup over DER and is on average \(1.8\times\) faster than the fastest baseline, FLPA. While FLPA is comparable to CoDeSEG on small graphs (LFR_50K and LFR_100K), its efficiency degrades progressively as the network scales. Overall, CoDeSEG’s superior performance and efficiency make it highly scalable for large, complex, real-world networks.

As shown in Figure 7, we measure snapshot-to-snapshot node/edge changes on two dynamic networks (X12 and X18) and report the runtime of all dynamic methods per snapshot. CoDeSEG remains competitive efficiency in dynamic detection. Although DynaMo (the fastest baseline) attains a similar runtime to CoDeSEG on X12 and X18, its detection performance is notably worse. Compared with QCA, which achieves the best accuracy, CoDeSEG delivers an \(80\times\) speedup, largely due to the CIPA-based adaptive node removal that avoids redundant computations. DCDME and DCDBFE suffer severe bottlenecks on large-scale dynamics: their utility function computations are expensive, and they must re-process all potentially affected communities at each snapshot, causing their efficiency to degrade to the level of static detection when applied to rapidly evolving, complex networks. Overall, CoDeSEG achieves the best trade-off between efficiency and accuracy among all dynamic baselines.

5.3 Stability of CoDeSEG in Dynamic Network↩︎

To assess stability in dynamic scenarios, we compare the static and dynamic versions of CoDeSEG on X12 and X18. Figure 8 reports the results, where ‘Dynamic’ denotes the CIPA-extended CoDeSEG and ‘Static’ reruns the original CoDeSEG from scratch on each snapshot. Across both networks, the dynamic CoDeSEG achieves performance comparable to the static one: on X12, the average NMI/F1 drops are only 0.0024/0.0032, and on X18 they are merely 0.0039/0.0064. This consistency stems from CIPA accurately identifying potentially affected nodes, ensuring stable detection results between the dynamic and static CoDeSEG. Meanwhile, the dynamic CoDeSEG is substantially more efficient, yielding \(4.39\times\) and \(2.13\times\) speedups on X12 and X18, respectively, by updating only communities of potentially affected nodes per snapshot. Overall, the CIPA-extended CoDeSEG adapts well to rapidly evolving networks while maintaining detection quality on par with the static algorithm.

5.4 Convergence of CoDeSEG↩︎

Figure 9 illustrates the convergence of CoDeSEG during the non-overlapping detection phase on the Amazon and DBLP networks. As shown, both the 2D SE of the networks and the number of node movements decrease significantly within the first three iterations. By the fifth iteration, the algorithm has essentially converged, with the number of moved nodes accounting for only 1/200 of the total nodes. The algorithm’s linear complexity and rapid convergence make it highly efficient for large-scale complex networks. Furthermore,  CoDeSEG  demonstrates exceptional robustness and stability, with a smooth convergence process and no repeated node adjustments in the later iterations. All nodes successfully join their optimal communities, achieving an accurate Nash equilibrium. Moreover, as observed from Figure 9, the F1 score on Amazon stabilizes at the 5th iteration, while the F1 score on DBLP stabilizes at the 4th iteration. This indicates that the impact of a small number of unstable nodes on the final partition quality during the non-overlapping detection phase is minimal. Although a few nodes may not be assigned to their optimal communities in the non-overlapping phase, these nodes can be replicated to other appropriate communities—including their optimal ones—during the subsequent overlapping detection phase. Furthermore, we investigate the effect of the termination threshold \(\tau_n\) on the algorithm’s performance. If \(\tau_n\) is set too high (e.g., 0.4), the algorithm may terminate prematurely, leaving many nodes in an unstable state, thereby compromising performance. Conversely, if \(\tau_n\) is too low (e.g., 0.2), the algorithm requires more iterations, increasing computational time. By selecting an appropriate \(\tau_n\) (e.g., 0.3), the algorithm can maintain performance while effectively improving detection efficiency.

5.5 Parallelization Study↩︎

The primary objective of parallelizing the algorithm is to significantly reduce runtime while preserving as much of the performance as possible. To assess the impact of varying thread counts on performance and efficiency, we conduct experiments on the LiveJournal and Orkut networks using different thread configurations, as presented in Figure 10. The results reveal that although CoDeSEG’s partitioning outcomes show minor variations across different thread counts, these differences are negligible compared to the ground truth communities. Additionally, runtime reduction does not follow a strictly linear pattern as thread count increases. For instance, runtime with 32 threads is shorter in both networks than 64 threads. This can be attributed to the fact that as thread count rises, computational discrepancies between threads may lead to an increase in the number of iterations, thus prolonging the total runtime. Moreover, with more threads, overhead related to thread initialization, lock contention, and synchronization delays also rise. Therefore, balancing task partitioning granularity and the efficiency gains of parallelization is crucial when determining the optimal number of threads.

6 Related Work↩︎

This section provides an overview of the existing literature relevant to the proposed CoDeSEG. The discussion is structured into three categories: Static Community Detection, Dynamic Community Detection, and Structural Entropy.

Static Community Detection. Community detection has been studied for over two decades. Representative approaches include modularity optimization [11], [12], [19], [46], label propagation [20], [21], [43], seed expansion [22], [23], [47], non-negative matrix factorization [24], [48], [49], spectral clustering [25], [50], [51], and deep learning methods [52]–[55]. Deep learning typically performs community clustering/classification via node embeddings, yet the high encoding cost limits its use on large-scale networks [56], [57]. From a structural viewpoint, methods can be divided into non-overlapping [11], [12], [43], [46], [55] and overlapping community detection [21], [24], [40], [41], [58]. However, many algorithms assume specific graph types or community structures: Louvain [12] and FLPA [43] mainly target disjoint communities in undirected graphs, whereas BigClam [24] and SLPA [21] focus on overlapping communities in undirected graphs. Recently, game-theoretic algorithms have gained attention for effective and efficient community discovery by modeling interdependent agent decisions. Chen et al. propose a community game that motivates subsequent designs of utility functions for disjoint detection [26]; Alvari et al. [58] leverage structural equivalence to uncover overlapping structures; Crampes et al. [59] formulate a potential game for node reassignment but require a pre-specified number of communities. For large-scale graphs, FOX [41] estimates node–community closeness by approximately counting intra-community triangles. Ferdowsi et al. [40] develop a two-stage non-cooperative game that detects disjoint communities via local utilities and then identifies overlapping nodes based on membership benefits. Nevertheless, both efficiency and detection quality in large-scale settings still need further improvement. In contrast, we propose a utility function based on 2D SE and community potential game that facilitates efficient community detection while accounting for the global partition of the network.

Dynamic Community Detection. Many real-world networks evolve continuously, and directly applying static community detection to dynamic networks is often computationally prohibitive, motivating dedicated dynamic community detection methods. Existing approaches are commonly grouped into three classes: instant-optimal, temporal trade-off, and incremental (our method belongs to the incremental class). Instant-optimal methods [60]–[62] rerun static algorithms on affected regions and then match/merge the results with previous communities, but repeated static optimization becomes a major bottleneck in large-scale settings. Temporal trade-off methods [63], ma2017evolutionary? jointly detect and track communities by leveraging both current and historical snapshots, yet they often require pre-specifying the number of communities. Incremental methods [28]–[30], [32], [33] update community structures by adapting to snapshot-to-snapshot changes. FacetNet [64] iteratively discovers dynamic communities by combining non-negative matrix factorization with cost optimization. QCA [30] uses hand-crafted update rules for node/edge additions and deletions, while DynaMo [28] enhances detection speed by further segmenting network change events and processing them in batches.DCDME [32] and DCDBFE [33] extract affected subgraphs and revise communities based on the Matthew effect and bird flock effect, respectively. However, as the network evolves, such locality-based updates may miss potentially affected nodes, causing detection quality to degrade over time. Based on the CIPA strategy, our algorithm achieves a better balance between efficiency and detection quality.

Structural Entropy. Structural Entropy (SE) [35], based on Shannon’s information theory and the Minimum Description Length principle, quantifies the uncertainty of graph structures across hierarchical levels. Initially applied to community detection, employing a global greedy strategy to merge communities within a network by minimizing the 2D SE. However, as noted in the literature, the original SE minimization process suffers from prohibitively high computational complexity, posing a fundamental challenge to its efficient implementation. This paper effectively addresses this challenge. By integrating community game theory, we successfully reduce the computational complexity of minimizing two-dimensional SE (2D SE) to a linear level. Furthermore, this study extends the theory of SE to scenarios involving both overlapping community detection and dynamic community detection. Beyond community detection, structural entropy finds broad application across diverse domains, including social event detection [4], [65], social bot detection [66], [67], graph structure learning [53], [68], and image segmentation [69], [70].

7 Conclusion↩︎

In this paper, we propose a fast heuristic community detection algorithm by minimizing the 2D SE of networks within the framework of a potential game. By designing a utility function with nearly linear time complexity, our algorithm can efficiently detect high-quality communities in large-scale networks, completing the process within minutes, even for networks comprising millions of nodes. Furthermore, we introduce the CIPA strategy, which extends the original algorithm to dynamic community detection. This strategy enables the algorithm to efficiently and adaptively update communities in dynamic networks, eliminating the need for full network re-detection. Extensive experiments on multiple large-scale networks demonstrate the practical effectiveness and computational efficiency of our approach. We envision broad applications for CoDeSEG across diverse fields, including social networks, biomedicine, and e-commerce. In future work, we aim to extend the algorithm to handle more complex heterogeneous networks and further enhance its efficiency through distributed computing paradigms and advanced subgraph partitioning techniques.

7.1 Glossary of Notations↩︎

Notations used in this paper, along with their corresponding description, are presented in Table [tbl:TabNotations].

7.2 Structural Entropy↩︎

SE [35] is defined on an encoding tree, where the encoding tree \(\mathcal{T}\) of a graph \(G = (\mathcal{V}, \mathcal{E})\) represents a hierarchical partition of \(G\) and satisfies the following conditions:

1. Each node \(\alpha\) in \(\mathcal{T}\) corresponds to a subset of nodes \(T_{\alpha} \subseteq \mathcal{V}\). The root node \(\lambda\) of \(\mathcal{T}\) contains the entire set of nodes, i.e., \(T_{\lambda} = \mathcal{V}\). Each leaf node \(\gamma\) in \(\mathcal{T}\) is associated with exactly one node from the graph \(G\), meaning \(T_{\gamma} = \{x\}\), where \(x \in \mathcal{V}\).

2. For each node \(\alpha\) in \(\mathcal{T}\), denote all its children as \(\beta_1, \dots, \beta_k\), then \(T_{\beta_1}, \dots, T_{\beta_k}\) is a partition of \(T_{\alpha}\).

3. For each node \(\alpha\) in \(\mathcal{T}\), denote its height as \(h(\alpha)\). Let \(h(\gamma) = 0\) and \(h(\bar{\alpha}) = h(\alpha)+1\), where \(\bar{\alpha}\) is the parent of \(\alpha\). The height of \(\mathcal{T}\) , \(h(\mathcal{T}) = \max\limits_{\alpha \in \mathcal{T}}{h(\alpha)}\).

The SE of graph \(G\) on encoding tree \(\mathcal{T}\) is defined as: \[\mathcal{H}^{\mathcal{T}}(G) = - \sum_{\alpha \in\mathcal{T},\alpha \neq \lambda } \frac{g_\alpha}{vol(\lambda)}\log \frac{vol(\alpha)}{vol(\bar{\alpha})},\] where \(g_\alpha\) is the summation of the degrees of the cut edges of \(\mathcal{T}_\alpha\) (i.e., the weight sum of edges with exactly one endpoint in \(\mathcal{T}_\alpha\)). \(vol(\alpha)\), \(vol(\bar{\alpha})\), and \(vol(\lambda)\) represent the volumes, i.e., the sums of node degrees within \(\mathcal{T}_\alpha\), \(\mathcal{T}_{\bar{\alpha}}\) and \(\mathcal{T}_\lambda\), respectively. The \(d\)-dimensional SE of \(G\) is realized by acquiring an optimal encoding tree of height \(d\), in which the disturbance derived from noise or stochastic variation is minimized: \[\mathcal{H}^{(d)}(G) = \min_{\forall \mathcal{T}: h(\mathcal{T}) = d} \{ \mathcal{H}^{\mathcal{T}} (G) \}.\]

Communities within a network can be identified by minimizing its 2D SE. Suppose \(\mathcal{P}=\{\mathcal{C}_1, \mathcal{C}_2, \dots, \mathcal{C}_k\}\) is a partition of the network \(G\), the 2D SE is defined as: \[\begin{align} \mathcal{H}^{2}(\mathcal{P}) = - \sum_{c \in \mathcal{P} } \left( \frac{g_{c}}{v_\lambda} \log \frac{v_c}{v_\lambda} + \sum_{x \in c } \frac{d_x}{v_\lambda} \log \frac{d_x}{v_c} \right), \end{align}\] where \(d_x\) is the degree of node \(x\), \(v_\lambda\) is the network’s volume. \(g_c\) and \(v_c\) denote the volume and cut of \(c\), respectively.

7.3 Proof of the \(\Delta_{\text{L}}(x, \mathcal{C})\) Computation Formula↩︎

Suppose the original partition is \(\mathcal{P}=\{\mathcal{C}_1, \mathcal{C}_2, \dots, \mathcal{C}_k\}\) and when node \(x\) leaves \(\mathcal{C}_k\), forming a new partition \(\mathcal{P}^\prime=\{\mathcal{C}_1, \mathcal{C}_2, \dots, \mathcal{C}_k^\prime, \{ x\}\}\), where \(\mathcal{C}_k = \mathcal{C}_k^\prime \cup \{x\}\). \(\mathcal{T}^\prime\) and \(\mathcal{T}\) are encoding tree according to \(\mathcal{P}^\prime\) and \(\mathcal{P}\), \(\lambda\) is the root node of the encoding tree of graph \(G\).

\[\label{EqDeltaLeaveProof} \begin{align} \Delta_L&(x, \mathcal{C}) = \mathcal{H}^{2}(\mathcal{P})-\mathcal{H}^{2}(\mathcal{P}^\prime) \\ =& - \sum_{\alpha \in \mathcal{T}, \alpha \neq \lambda} \frac{g_\alpha}{v_{\lambda}} \log \frac{v_\alpha}{v_{\bar{\alpha}}} + \sum_{\alpha^\prime \in \mathcal{T}^\prime, \alpha^\prime \neq \lambda} \frac{g_{\alpha^\prime}}{v_\lambda} \log \frac{v_{\alpha^{\prime}}}{v_{\bar{\alpha}^\prime}} \\ =& \underbrace{ - \frac{g_{\mathscr{c}_k}}{v_\lambda} \log \frac{v_{\mathscr{c}_k}}{v_\lambda} - \sum_{x_i \in \mathcal{C}_k \setminus \{x\}} \frac{d_{x_i}}{v_\lambda} \log \frac{d_{x_i}}{v_{\mathscr{c}_k}} }_{\mathcal{H}^{2}(\mathcal{C}_k \setminus \{x\})} \underbrace{ -\frac{d_x}{v_\lambda} \log \frac{d_x}{v_{\mathscr{c}_k}} }_{\mathcal{H}^{2}(x)} \\ & \underbrace{ + \frac{g_{\mathscr{c}_k^\prime}}{v_\lambda} \log \frac{v_{\mathscr{c}_k^\prime}}{v_\lambda} + \sum_{x_i \in \mathcal{C}_k^\prime} \frac{d_{x_i}}{v_\lambda} \log \frac{d_{x_i}}{v_{\mathscr{c}_k^\prime}} }_{-\mathcal{H}^2(\mathcal{C}_k^\prime)} \underbrace{ + \frac{d_x}{v_\lambda} \log \frac{d_x}{v_\lambda} }_{-\mathcal{H}^2(\{x\})} \\ =& \frac{g_{\mathscr{c}_k^\prime}}{v_\lambda} \log \frac{v_{\mathscr{c}_k^\prime}}{v_\lambda} - \frac{g_{\mathscr{c}_k}}{v_\lambda} \log \frac{v_{\mathscr{c}_k}}{v_\lambda} + \frac{d_x}{v_\lambda}(\log \frac{d_x}{v_\lambda} - \log \frac{d_x}{v_{\mathscr{c}_k}} ) \\ &+ \sum_{x_i \in \mathcal{C}_k^\prime} \frac{d_{x_i}}{v_\lambda} ( \log \frac{d_{x_i}}{v_{\mathscr{c}_k^\prime}} - \log \frac{d_{x_i}}{v_{\mathscr{c}_k}}) \\ =& \frac{g_{\mathscr{c}_k^\prime}}{v_\lambda} \log \frac{v_{\mathscr{c}_k^\prime}}{v_\lambda} - \frac{g_{\mathscr{c}_k}}{v_\lambda} \log \frac{v_{\mathscr{c}_k}}{v_\lambda} + \frac{d_x}{v_\lambda} \log \frac{v_{\mathscr{c}_k}}{v_\lambda} \\ &+ \log \frac{v_{\mathscr{c}_k}}{v_{\mathscr{c}_k^\prime}} \sum_{x_i \in \mathcal{C}_k^\prime} \frac{d_{x_i}}{v_\lambda} \\ =& \frac{g_{\mathscr{c}_k^\prime}}{v_\lambda} \log \frac{v_{\mathscr{c}_k^\prime}}{v_\lambda} - \frac{g_{\mathscr{c}_k}}{v_\lambda} \log \frac{v_{\mathscr{c}_k}}{v_\lambda} + \frac{d_x}{v_\lambda} \log \frac{v_{\mathscr{c}_k}}{v_\lambda} + \frac{v_{\mathscr{c}_k^\prime}}{v_\lambda} \log \frac{v_{\mathscr{c}_k}}{v_{\mathscr{c}_k^\prime}},\\ \end{align}\tag{12}\] where, \(d_x^\text{in}\) denotes the sum of edges from node \(x\) to nodes \(x_j \in \mathcal{C}_k\). Since the \(v_{\mathscr{c}_k}\), \(g_{\mathscr{c}_k}\) and \(d_x^\text{in}\) can be cached during the algorithm iterations: \[v_{\mathscr{c}_k^\prime} = v_{\mathscr{c}_k} - d_x, \quad g_{\mathscr{c}_k^\prime} = g_{\mathscr{c}_k} - 2* d_x^\text{in} + d_x. \\\]

1.6mm

7.4 Pseudo-code of CIPA↩︎

Algorithm [Alg:CIPA] presents the pseudo-code of the Cascading Influence Propagation-based Adaptive (CIPA) strategy. Given the community partition \(\mathcal{P}{t-1}\) of the previous snapshot \(G{t-1}\), CIPA first initializes the partition \(\mathcal{P}_t\) for the current snapshot \(G_t\) (Line 1), and then updates the per-community’s volume and cut, according to edge/node additions and deletions (Lines 2–11). In contrast to the static CoDeSEG, the CIPA-enabled dynamic CoDeSEGrestricts the updates to the affected node set and iteratively refines it in an adaptive manner (Lines 12–32): it cascades the influence to identify additional potentially impacted nodes during the iterations, and removes nodes that have reached a stable state based on the stable-round threshold \(r\). This preserves detection quality while substantially reducing redundant computations, thereby allowing the original algorithm to efficiently accommodate continuously evolving dynamic networks.

7.5 Detailed Time Complexity Analysis↩︎

Static Community Detection. In the non-overlapping detection phase, the algorithm initially sets each node as an individual cluster and initializes community volumes and cut edge summations, which takes \(O(|\mathcal{V}|)\) time. For each node, the best strategy computation for each node depends on its degree, taking \(O(d_{\text{avg}})\) time, since we can compute \(\Delta_{\text{L}}(x, C)\) in \(O(1)\) time. Therefore, evaluating and updating all nodes in one iteration requires \(O(d_{\text{avg}} \cdot |\mathcal{V}| )\). Overall, given that the algorithm runs for \(I\) iterations, the total time complexity is \(O(I \cdot d_{\text{avg}} \cdot |\mathcal{V}|)\). This complexity indicates that the algorithm’s performance scales linearly with the number of nodes and their average degree, with the number of iterations needed for convergence influencing the overall computational effort. In the overlapping community detection phase, the algorithm’s time complexity is \(O(d_{\text{avg}} \cdot |\mathcal{V}| )\). This complexity arises because each node is processed by iterating over its adjacent communities.

Dynamic Community Detection. In the dynamic community detection setting, the per-snapshot time complexity of our algorithm is reduced to \(O\!\left(I \cdot d_{\max} \cdot \left|\mathcal{V}^{d} \cup \mathcal{V}^{ind}\right|\right)\), where \(\mathcal{V}^{d}\) and \(\mathcal{V}^{ind}\) denote the sets of directly and indirectly affected nodes in the current snapshot, respectively. \(I\) is the maximum number of iterations, and \(d_{\max}\) is the maximum node degree. Specifically, initializing the community partition for the current snapshot takes \(O\!\left(\left|\mathcal{V}^{add}\right|\right)\) time. Next, updating the community statistics (i.e., volumes and cuts) requires scanning the changed edges, which costs \(O\!\left(\left|\mathcal{E}^{add} \cup \mathcal{E}^{del}\right|\right)\), where \(\mathcal{E}^{add}\) and \(\mathcal{E}^{del}\) denote the sets of added and deleted edges, respectively. Moreover, since each indirectly affected node must be incident to at least one changed edge, we have \(\left|\mathcal{E}^{add} \cup \mathcal{E}^{del}\right| \leq \left|\mathcal{V}^{ind}\right|\), and thus \(O\!\left(\left|\mathcal{E}^{add} \cup \mathcal{E}^{del}\right|\right)=O\!\left(\left|\mathcal{V}^{ind}\right|\right)\). During the detection stage, the algorithm only processes nodes identified as affected, with the cost of \(O\!\left(I \cdot d_{\max} \cdot \left|\mathcal{V}^{d} \cup \mathcal{V}^{ind}\right|\right)\). Therefore, the total per-snapshot complexity is \[\begin{align} &O\!\left(\left|\mathcal{V}^{add}\right| + \left|\mathcal{V}^{ind}\right| + I \cdot d_{\max} \cdot \left|\mathcal{V}^{d} \cup \mathcal{V}^{ind}\right|\right)\\ &= O\!\left(I \cdot d_{\max} \cdot \left|\mathcal{V}^{d} \cup \mathcal{V}^{ind}\right|\right), \end{align}\] which indicates that the runtime is directly determined by the number of potentially affected nodes identified by the dynamic update mechanism.

7.6 Datasets↩︎

We conduct comprehensive experiments on fourteen large-scale networks, which are described in detail as follows:

• Amazon [37] is constructed by crawling the Amazon website, and each product category provided by Amazon defines a ground-truth community.

• YouTube [37] is a video-sharing platform that also functions as a social network, allowing users to establish friendships and create groups that other users can join. These user-defined groups are considered ground-truth communities.

• DBLP [37] is a co-authorship network where two authors are connected if they have published at least one paper together. Authors who have published in a specific journal or conference form a community.

• LiveJournal [37] is a free online blogging community where users can declare friendships with each other. User-defined friendship groups are considered ground-truth communities.

• Orkut [37] is a free online social network where users can form friendships and create groups that other members can join. These user-defined groups are considered ground-truth communities.

• Friendster [37] is originally launched as a social networking platform, enabling users to establish friendships and create groups. The user-defined groups are regarded as ground-truth communities.

• Wiki [37] is a directed overlapping network constructed from Wikipedia hyperlink data collected in September 2011. This network comprises page titles and their associated category information, where each article may belong to multiple categories.

• X12_static and X12 [38]. X12_static is a Twitter social network in which nodes correspond to user-generated tweets. It comprises 68,841 English tweets collected over a 28-day period in 2012, encompassing 503 distinct event categories. In the X12_static network, nodes are linked through shared attributes, such as common hashtags or user mentions. In addition, we employ SBERT [71] to embed tweets, and compute pairwise cosine similarities. For each node, the 150 most semantically similar nodes are selected as neighbors. To construct the dynamic network X12, we transform X12_static into a temporal network consisting of ten consecutive snapshots. Each snapshot corresponds to a three-day interval, defined based on the posting timestamps of the tweets.

• X18_static and X18 [39]. X18_static is a Twitter social network consisting of 64,516 French tweets published over 23 days in 2018, covering 257 types of events. The construction method for the networks X18 and X18_static is identical to that of X12 and X12_static, with X18 comprising eight consecutive network snapshots.

• LFRs. To simulate the properties of real-world complex networks, five groups of large-scale weighted synthetic networks are generated using the LFR benchmark tool³.  [72] The networks contain 50K, 100K, 200K, 500K, and 1M nodes, respectively. The mixing parameter \(muw\) of the LFR benchmark tool is set to 0.6.

7.7 Baselines↩︎

The detailed descriptions of all baselines are as follows:

• SLPA [21] is an overlapping community detection method based on label propagation, designed to identify community structures in networks by propagating labels between nodes.

• Bigclam [24] is an overlapping community detection method for large networks based on Non-negative Matrix Factorization (NMF), which maximizes the likelihood estimate of the graph to find the optimal community structure.

• NcGame [40] is an overlapping community detection algorithm based on non-cooperative game theory, which treats nodes as self-interested participants to find communities that maximize individual node benefits.

• Fox [41] is a heuristic overlapping community detection method that measures the closeness between nodes and communities by approximating the number of triangles formed by nodes and communities.

• Louvain [12] is based on modularity optimization, which identifies non-overlapping community structures in networks through a multi-level optimization strategy.

• DER [42] is a diffusion entropy reduction graph clustering algorithm. It employs random walks to embed the graph in a space of measures, after which a modified version of k-means is applied in that space.

• Leiden [11] is an improved version of the Louvain algorithm, which enhances community detection accuracy and stability through local optimization and refinement steps.

• FLPA [43] is a fast variant of LPA [13] that is based on processing a queue of nodes whose neighborhood recently changed.

• QCA [30] is a rule-based modularity optimization algorithm that updates community structures according to predefined rules for node and edge additions and deletions.

• DynaMo [28] is a modularity-based method, which gradually maximizes modularity gain when updating the community structure of dynamic networks.

• DCDME [32] is based on the Matthew effect, which updates the community structure by iteratively processing all potentially affected communities in each snapshot.

• DCDBFE [33] is inspired by the bird flock effect, leveraging natural ecological principles to identify and update communities in dynamic networks.

The open-source implementations provided by the CDlib library⁴ are used for SLPA and DER, while the Igraph library⁵ implementations are employed for Louvain, Leiden, and FLPA. For BigClam, NcGame, Fox, QCA, DynaMo, DCDME, and DCDBFE, we used their respective open-source implementations^{6,7,8,9,10,11}.

7.8 Details of Evaluation Metrics.↩︎

Given a ground truth community \(\mathcal{C} \subseteq \mathcal{V}\) and a reconstructed community \(\mathcal{C}^\prime \subseteq \mathcal{V}\), the precision \(P(\mathcal{C}^\prime, \mathcal{C})\) and recall \(R(\mathcal{C}^\prime, \mathcal{C})\) are defined as follows: \[P(\mathcal{C}^\prime, \mathcal{C}) = \frac{|\mathcal{C} \cap \mathcal{C}^\prime|}{|\mathcal{C}^\prime|}, \quad R(\mathcal{C}^\prime, \mathcal{C}) = \frac{|\mathcal{C} \cap \mathcal{C}^\prime|}{|\mathcal{C}|}.\] Precision represents the fraction of the reconstruction in the ground truth, while recall represents the fraction of the ground truth in the reconstruction. These notions are often combined into a single number between 0 and 1, known as the \(F_1\)-score, defined as: \[F_1(\mathcal{C}^\prime, \mathcal{C}) = 2 \cdot \frac{P(\mathcal{C}^\prime, \mathcal{C}) \cdot R(\mathcal{C}^\prime, \mathcal{C})}{P(\mathcal{C}^\prime, \mathcal{C}) + R(\mathcal{C}^\prime, \mathcal{C})}.\] The \(F_1\)-score has the additional advantage of being symmetric, i.e., \(F_1(\mathcal{C}^\prime, \mathcal{C}) = F_1(\mathcal{C}, \mathcal{C}^\prime)\), and it equals \(1\) if and only if the sets \(\mathcal{C}\) and \(\mathcal{C}^\prime\) are identical. To evaluate the set of detected clusters, we define the \(F_1\) score for a collection of ground truth communities \(\mathcal{P}\) and a collection of detected communities \(\mathcal{P}^\prime\) [24], [44]. The F1-score for detection is calculated as the average of two values: the F1-score of the best-matching ground-truth community for each detected community, and the F1-score of the best-matching detected community for each ground-truth community: \[\begin{align} F_1(\mathcal{P}^\prime, \mathcal{P}) = \frac{1}{2} &\left( \frac{1}{|\mathcal{P}^\prime|} \sum_{\mathcal{C}^\prime \in \mathcal{P}^\prime} \max_{\mathcal{C} \in \mathcal{P}} F_1(\mathcal{C}^\prime, \mathcal{C}) \right. \\ & \left. + \frac{1}{|\mathcal{P}|} \sum_{\mathcal{C} \in \mathcal{P}} \max_{\mathcal{C}^\prime \in \mathcal{P}^\prime} F_1(\mathcal{C}, \mathcal{C}^\prime) \right). \end{align}\] We also use the ONMI based on information theory developed by Lancichinetti and Fortunato [45] and later refined by McDaid et al. [73]. \[\text{ONMI}(\mathcal{P}^\prime, \mathcal{P}) = \frac{I(\mathcal{P}^\prime, \mathcal{P})}{\max(H\left( \mathcal{P}^\prime), H(\mathcal{P}) \right)},\] where \(H(\mathcal{P})\) is the Shannon entropy of \(\mathcal{P}\), and \(I(\mathcal{P}^\prime, \mathcal{P})\) is the mutual information. It is important to note that the difference between NMI and ONMI lies in that nodes in \(\mathcal{P}\) and \(\mathcal{P}^\prime\) only belong to a single community. For the specific calculation formula, refer to literature [73]. F1 measures the node-level detection performance, while NMI aims at the community-level detection performance.

7.9 Visualization Study↩︎

To intuitively assess the effectiveness of the proposed algorithm in overlapping community detection, we visualize the top 5000 real communities from the Amazon dataset, ranked by node count. The top 200 communities are highlighted in distinct colors, while the remaining nodes are displayed in light gray. Meanwhile, we visualize the detection results of CoDeSEG, the best-performing baseline (Fox), and the worst-performing baseline (Bigclam), showing their alignment with the real communities. As depicted in Fig. 12, the detection results of CoDeSEG exhibit the closest match to the real communities, followed by Bigclam. This demonstrates that the 2D SE effectively models communities in real-world networks, and that the heuristic structural entropy function, grounded in the latent game framework, enables efficient detection. Conversely, Fox performs the worst on this dataset, likely due to its reliance on local triangle counting for community membership determination, which fails in certain network structures. In contrast, CoDeSEG shows greater robustness.

Similarly, for the visualization of the LFR_50K network, we compare the best-performing baseline, FLPA, with the worst-performing baseline, DER, among non-overlapping detection algorithms. As shown in Fig. 13, although FLPA achieves the best baseline performance, it still exhibits noticeable deviations from the ground-truth community structure. In contrast, the visualization results of CoDeSEG align closely with the ground-truth community structure, showing only minimal node assignment discrepancies. Unlike synthetic networks, which typically have clearer structures, real-world networks tend to exhibit more intricate and irregular community configurations. Nevertheless, CoDeSEG effectively captures the underlying community structure in both cases. Notably, DER performs poorly, clustering nearly all nodes into only two communities. This limitation stems from its measure space embedding approach, which fails to capture subtle node distinctions in large-scale network structures. In conclusion, CoDeSEG demonstrates superior robustness and accuracy in both overlapping and non-overlapping community detection tasks.

References↩︎

---

1. Corresponding author: Yantuan Xian↩︎

2. https://github.com/Kust-lp/CoDeSEG↩︎

3. https://github.com/eXascaleInfolab/LFR-Benchmark_UndirWeightOvp↩︎

4. https://cdlib.readthedocs.io↩︎

5. https://igraph.org/↩︎

6. https://github.com/snap-stanford/snap↩︎

7. https://doi.org/10.1038/s41598-022-15095-9↩︎

8. https://github.com/timgarrels/LazyFox↩︎

9. https://github.com/nogrady/dynamo↩︎

10. https://github.com/sunwww168/DCDME↩︎

11. https://github.com/sitiharyanti/DCDBFE_2024↩︎