GLOD: The Local Greedy Expansion Method for Overlapping Community Detection in Dynamic Provenance Networks

Abstract

Local overlapping community detection is a hot problem in the field of studying complex networks. It is the process of finding dense clusters based on local network information. This paper proposes a method called local greedy extended dynamic overlapping community detection (GLOD) to address the challenges of detecting high-quality overlapping communities in complex networks. The goal is to improve the accuracy of community detection by considering the dynamic nature of community boundaries and leveraging local network information. The GLOD method consists of several steps. First, a coupling seed is constructed by selecting nodes from blank communities (i.e., nodes not assigned to any community) and their similar neighboring nodes. This seed serves as the starting point for community detection. Next, the seed boundaries are extended by applying multiple community fitness functions. These fitness functions determine the likelihood of nodes belonging to a specific community based on various local network properties. By iteratively expanding the seed boundaries, communities with higher density and better internal structure are formed. Finally, the overlapping communities are merged using an improved version of the Jaccard coefficient, which is a measure of similarity between sets. This step ensures that overlapping nodes between communities are properly identified and accounted for in the final community structure. The proposed method is evaluated using real networks and three sets of LFR (Lancichinetti–Fortunato–Radicchi) networks, which are synthetic benchmark networks widely used in community detection research. The experimental results demonstrate that GLOD outperforms existing algorithms and achieves a 2.1% improvement in the F-score, a community quality evaluation metric, compared to the LOCD framework. It outperforms the best existing LOCD algorithm on the real provenance network. In summary, the GLOD method aims to overcome the limitations of existing community detection algorithms by incorporating local network information, considering overlapping communities, and dynamically adjusting community boundaries. The experimental results suggest that GLOD is effective in improving the quality of community detection in complex networks.

1. Introduction

Many real-world networks, such as social networks and citation graphs [1,2,3,4], contain community structure, and analyzing network structure and knowledge extraction is an important research topic [5,6]. The purpose of community detection is to partition the entire network into different communities, ensuring that nodes within a community are tightly connected, while nodes between different communities are relatively sparsely connected. However, the concept of community itself lacks a universally accepted definition, as discussed in Fortunato [7]. The dynamic provenance network refers to changes in the number of nodes, the number of edges of nodes, and the structure of local communities. Real-world community structures often produce overlapping intersections. Therefore, discovering overlapping communities is more helpful in understanding the topological and functional structures of networks, and using community networks as a guide is of great significance for analyzing information dissemination and information tracing.

Community detection algorithms typically require global information of the entire network [8]. However, global information of real-world networks may be unavailable or costly to obtain [9]. Local community detection starts from the perspective of local structures and detects node community membership based on local information. Therefore, local expansion methods are more suitable for discovering communities in large-scale networks. The accuracy and running time of community detection are two important evaluation metrics for local expansion-based community discovery methods. However, these two metrics are mutually constrained, and improving both accuracy and running time is an NP-hard problem. Currently, existing local overlapping detection algorithms, such as LFM [10], are inefficient in detecting the local maximum of fitness functions for community detection, and there is a problem of creating empty communities by deleting nodes. The LOCD framework [11] selects representative nodes to join communities but does not consider the analysis and merging issues after community detection. Reid et al. [12] pointed out that overlap is indeed an important feature of many real-world networks. Baltsou et al. [13] proposed that local community detection can also evaluate the community structure of a network. Gupta et al. [14] proposed faction propagation in networks to detect overlapping nodes. Shi et al. [15] pointed out that local expansion methods are more suitable for large-scale networks. Newman et al. [16] proposed modularity to measure the quality of detected communities.

The existing LOCD local overlapping community detection algorithm [11] has three problems that need to be improved in order to enhance the quality of community detection: First, selecting a single node to expand the community leads to the problem of seed invalidity. Second, when nodes within a community are deleted, there may be nodes that do not belong to any community. Third, when there are too many overlapping nodes in overlapping communities, there is a problem of redundant communities that multiple communities contain similar overlapping nodes, that is, multiple overlapping nodes belong to the same multiple communities. This creates redundancy in some communities. Redundancy is defined as a one-third threshold, and communities exceeding this threshold are considered redundant communities.

This paper proposes a method called GLOD for local overlapping community detection, which addresses three common issues in existing methods. The main contributions are as follows:

(1) Utilizing the same computational process and neighbor similarity to expand nodes into coupled seeds can reduce seed invalidity and avoid the issue of creating blank communities due to node deletion.

(2) Extending community boundaries based on centrality seeds through a blended community fitness function yields locally well-adapted and structurally stable community discovery results. This approach mitigates the problem of excessive reliance on the influence of central nodes and avoids community jitter.

(3) Comparing and merging results of overlapping communities based on an improved Jaccard coefficient helps maintain high community coverage while reducing redundancy in communities.

The rest of this paper is organized as follows. Section 2 introduces some related methods. In Section 3, we describe the problems of local overlapping community detection and some methods used in our framework. Section 4 presents our method and the complexity analysis of the method. Section 5 presents the experimental results and analysis. Finally, we provide conclusions.

2. Related Work

Local overlapping community detection is helpful in understanding the topological and functional structure of the propagation graph; therefore, utilizing community networks as a guide is of great significance for analyzing information propagation and information tracing. In this section, we will elaborate on the progress and existing issues of community detection from three aspects: local community detection, overlapping community detection, and local overlapping community detection.

2.1. Local Community Detection

The purpose of local community detection is to find the community membership of nodes based on local information [17,18]. Luo et al. [8] proposed two local community detection algorithms, DMF_M and DMF_R. DiTursi et al. [17] extended traditional local community detection in static networks to dynamic networks that change over time. Fanrong et al. [19] discussed the problem of ineffective seeds, where seed nodes sometimes do not participate in community detection. Therefore, community expansion starts not from a single node but from the maximum clique that includes the seed nodes. They proposed a local community detection algorithm based on maximum clique expansion (LCD-MC). Christopoulos [20] proposed a framework to track the evolution of a community in dynamic networks by focusing on a key node called the anchor, overcoming the identity problem and validating its effectiveness through experiments. Huang [21] introduced Community Contrastive Learning (Community-CL), an online framework that combines contrastive learning with graph views to simultaneously learn node representations and detect communities in networks, outperforming state-of-the-art baselines in community detection tasks. Qing’s [22] approach combines weighted modularity with spectral clustering to accurately estimate the number of communities in weighted networks, including those with negative edge weights and signed networks. Yao [23] introduced a new modularity function 𝐹2 and proposed a constrained Louvain algorithm that outperforms other methods, including the classical Louvain algorithm and Newman’s fast method, in community detection on various networks. Wan [24] introduced a novel spatial autoregressive and gravity model united method (SARGM) to simulate benchmark spatial networks and proposed a spectral-clustering-based spatial community detection method (SCSCD) that outperforms other methods in accuracy and effectiveness, with a case study on a high-speed train network in China.

2.2. Overlapping Community Detection

Overlapping is one of the important features of propagation graphs. Tanmoy et al. [25] proposed a vertex-based metric, GenPerm, but the problem of ineffective seeds (vertices) still exists. Bai et al. [26] developed the OCDDP overlapping community detection algorithm based on density peaks. The algorithm first sets a distance matrix based on similarity and then selects community cores. Rezvani et al. [27] proposed a fitness-based method based on triangles to address the free-rider and separation effects of overlapping nodes. The local fitness method (LFM) [10] found that the local maximum of the fitness function is inefficient for detecting communities, as the algorithm repeats detecting nodes when they are included in multiple communities. The clique percolation method (CPM) [28] finds k small clusters in the network and shares (k − 1) nodes to obtain a single community. However, this algorithm cannot assign nodes that do not belong to any community. LOC [29] solves this problem by selecting nodes with the highest density and using an algorithm based on the clique expansion strategy for community partitioning, which improves the efficiency and quality of community detection. In addition, compared with overlapping community detection algorithms that focus on the global structure of the network, the computational cost of local overlapping community detection methods is greatly reduced. Xu H et al. [30] proposed the influence-based community overlap propagation algorithm (INF-COPRA) that improves the accuracy of overlapping community detection by ranking the influence of nodes and labels, outperforming existing methods in benchmark and real networks. Li X et al. [31] proposed algorithm combines local expansion and label propagation to detect overlapping components in community structures, achieving higher effectiveness, accuracy, and stability across diverse network structures. Lin H et al. [32] proposed an algorithm for detecting overlapping communities in social networks using an augmented attribute graph and an improved weight adjustment strategy, demonstrating its effectiveness through extensive experiments on synthetic and real-world datasets. Huang M et al. [33] proposed approach, ESNMF, utilizes symmetric non-negative matrix factorization and outperforms existing methods for community detection in large-scale networks by dividing the network into sub-graphs and extracting precise communities through non-negative matrix factorization. Peng Y et al. [34] proposed the DSNE algorithm and community density metric (D), which offers an effective approach for detecting overlapping communities in bipartite networks, outperforming existing algorithms and providing a more comprehensive evaluation of community structures compared to modularity. Gao R et al. [35] introduced an algorithm for overlapping community detection in complex networks based on membership degree propagation, which achieves improved accuracy and speed compared to other methods while reducing computational complexity. Li Y et al. [36] proposed the Two Expansions of Seeds (TES) algorithm, which effectively discovers overlapping communities in complex networks, outperforming existing algorithms in terms of robustness, accuracy, and redundancy reduction. Tsung et al. [37] proposed a novel algorithm for detecting overlapping communities by introducing a node weight allocation problem and extending the modularity measure, showing improved results in detecting valuable overlapping nodes.

2.3. Local Overlapping Community Detection

Kamuhanda et al. [38] used the non-negative matrix factorization (NMF) algorithm to address multiple local community detection, but the quality of community detection on sparse networks is not ideal. Hollocou et al. [39] proposed a method called MULTICOM to discover multiple local communities, but community detection based on seed influence will have a large error compared to the true communities. The (α,γ)-OCS model [40] is based on the α-adjacency-γ-quasi-k-clique method, and uses the idea of local maximum cliques for local overlapping community detection. However, the difficulty lies in determining the number of nodes in the local maximum clique, as the size of the maximum cliques in different networks is unknown, making it difficult to estimate the parameters. Ni et al. [11] proposed a framework called LOCD, but the LOCD framework uses nodes as seeds, which leads to the problem of seed inefficiency and does not consider the issue of community similarity. Riolo M A et al. [41] proposed an information theoretic method for identifying building blocks in specific networks, highlighting the valuable insights provided by traditional community detection approaches.

3. Preliminaries

In order to clarify the proposed overlapping community detection method in this paper, we first introduce some background knowledge, including the problem description of local overlapping community detection, the neighbor similarity function used for seed community formation, the community fitness function used for local community expansion, the Jaccard coefficient used for community merging, and the F-score used for overall analysis in experiments.

3.1. Problem Statement

For graph G and given node v, node v is an overlapping node belonging to both communities c₁ and c₂. Our goal is to find communities c₁ and c₂ using only local information for node v.

3.2. The Common Neighbor Similarity

The rough seed nodes (i.e., rough communities) can weaken the influence of a single seed on community expansion. The calculation of similarity is Equation (1), where $N(v_i)$ is the set of neighbors of node v_i. The rough node V, the process of roughening, and the neighbors of the node are classified into a set according to the similarity. Rough nodes are used as seeds, which contain multiple nodes with high similarity as a whole, and are initially composed of v_i and its most similar neighbors, following the common neighbor similarity NC. By sorting the centrality of the rough node V, the largest node V with the highest centrality is selected as the seed s.

$$NC\left(v_i,v_j\right)=\mid \mathrm{N}\left(v_i\right){\displaystyle \cap }\mathrm{N}\left(v_j\right)\mid$$

(1)

3.3. Community Fitness Function

The community fitness function serves as a criterion for determining whether a node can join the current community and determines who can be added from the set of neighboring nodes to the initial community.

3.3.1. f(C) Method

The fitness function f(C) of a community C in the graph G = (V,E) is defined as follows. Here, $d_{\mathrm{in}}^C$ and $d_{\mathrm{out}}^C$ denote the weighted node degrees of all nodes in C within and outside C, respectively, and $\mathsf{\alpha }>0$ is a tunable parameter that controls the size of the community, called the resolution parameter. Based on this, $\forall v\in C{\displaystyle \cup }N\left(C\right)$, the fitness of node v is defined by Equation (3). The LFM algorithm [10] adds the node with the maximum fitness to the current community C in each iteration to obtain a new community $C^{\prime }$, then computes the fitness of all nodes in $C^{\prime }$ and removes nodes with negative fitness to obtain a new community $C^{″}$. This process is repeated until the fitness function no longer increases. Chen et al. [42] found that the NMI value of overlapping communities is highest when $\mathsf{\alpha }=0.8$ in practical applications. Therefore, in this experiment, we adopt the overlapping community partitioning strategy with the highest NMI value.

$$f\left(C\right)=\frac{d_{\mathrm{in}}^C}{{\left(d_{\mathrm{in}}^C+d_{\mathrm{out}}^C\right)}^{\alpha }},$$

(2)

$$f\left(v\right)=\{\begin{array}{c}f\left(C{\displaystyle \cup }\left\{v\right\}\right)-f\left(C\right),\forall v\in N\left(C\right);\\ f\left(C\right)-f\left(C-\left\{v\right\}\right),\forall v\in C.\end{array}$$

(3)

3.3.2. ω(v_i) Method

During the community expansion phase in the DMF_M algorithm [8], the node with the highest value of ω(v_i) is selected by computing the node’s fitness and updating C, N, and M accordingly. Here, $N\left(v_i\right)$ denotes the set of neighbors of node $v_i$, $N_2\left(v_i\right)=\left\{x\mid y\in N\left(v_i\right),x\in N\left(y\right)\right\}$, and $N_{Ci}$ is the intersection of $N\left(v_i\right)$ and C.

$${\omega }_{\left(v_i\right)}=\{\begin{array}{c}\frac{\underset{v_j\in N_{Ci}}{max}\left(\frac{\left|N\left(v_i\right){\displaystyle \cap }N\left(v_j\right)\right|+1}{\mid N\left(v_j\right)|}+0.1\ast \frac{\left|N_2\left(v_i\right){\displaystyle \cap }{N}_2\left(v_j\right)\right|+1}{\left|N_2\left(v_j\right)\right|}\right)}{1.1} \Delta M\ge 0\\ 0, \Delta M<0,\end{array}$$

(4)

3.3.3. F(v, s). Method

In a graph G = (V,E), vi is the selected node, $\mathrm{s}=\left\{{\mathrm{v}}_{\mathrm{i}},{\mathrm{v}}_{\mathrm{j}}\right\}$ is the constructed seed where $v_k\in \mathrm{N}\left(v_i\right)$, and $\mathrm{N}\left(v_i\right)$ is the set of all neighboring sub-nodes of v_i. The value of F ranges from 0 to 1, and when F = 1, all elements in c are neighbors of $v_k$. Equation (5) describes the degree of affiliation of $v_i$’s neighboring nodes with the number of elements in seed s. It reflects how closely $v_i$’s neighbors are connected to seed s. To increase the density of internal nodes in s, we use this equation to expand the seed. Therefore, when the F value of a node is too high, it indicates that the node is highly influenced by s, and the node is added to s. Then, the local gain of s will increase.

$$F\left(v_k,s\right)=\frac{\mid \left(\mathrm{N}\left(v_k\right){\displaystyle \cap }s\right)\mid }{\left|s\right|}$$

(5)

3.4. The Jaccard Coefficient for Community Merging

The Jaccard coefficient [43] is used to evaluate the effectiveness of overlapping community detection results by measuring the similarity between the detected communities and the true community structure. It is defined as Equation (6). The GREESE method [44] merges communities when the Jaccard coefficient exceeds one-third of the nodes in the smallest community.

The modified community merging coefficient J is defined as shown in Equation (8). A larger J value indicates that communities should be merged, and when J = 0, the two communities are completely independent and unrelated. Here, $C_r$ represents the true community structure, while $C_f$ represents the community structure discovered using a community detection method. $OV$ is the set of only overlapping nodes, $O{V}_i$ is one of the shared overlapping node sets, $o_i{v}_i$ is an overlapping node in the $O{V}_i$ overlap set, and C is the set of multiple communities to which $O{V}_i$ belongs.

$$J=\frac{{{\displaystyle \sum }}_{C_{r,j}\in C_r}\underset{C_{j,}\in C_f}{max}J\left(C_{f,j},C_{r,i}\right)}{N_r}$$

(6)

$$\begin{array}{c}J\left(C_{f,j},C_{r,i}\right)=\frac{\left|C_{f,j}{\displaystyle \cap }{C}_{r,i}\right|}{\left|C_{f,j}{\displaystyle \cup }{C}_{r,i}\right|}\end{array}$$

(7)

$$\begin{array}{c}J\left(o_i{v}_i\right)={\mathsf{\Sigma }}_{o_i{v}_i\in C,C_i\in C,C_j\in C,i\ne j}\frac{1}{\left|C_i{\displaystyle \cup }{C}_j\right|}\end{array}$$

(8)

3.5. F-Score

F-score [45,46] is the harmonic mean of $precision$ and $recall$, used to measure the similarity/correlation between the given community detection result and the true community structure, and can assess the accuracy of the community detection result. Its calculation Equation is as follows.

$$F_s=\frac{{{\displaystyle \sum }}_{C_{r,i}\in C_r}\underset{C_{f,j}\in C_f}{max}{F}_s\left(C_{f,j},C_{r,i}\right)}{N_r}$$

(9)

$$F_s\left(C_{f,j},C_{r,i}\right)=\frac{2precision\left(C_{f,j},C_{r,i}\right)recall\left(C_{f,j},C_{r,i}\right)}{precision\left(C_{f,j},C_{r,i}\right)recall\left(C_{f,j},C_{r,i}\right)}$$

(10)

$$precision\left(C_{f,j},C_{r,i}\right)=\frac{\left|C_{f,j}{\displaystyle \cap }{C}_{r,i}\right|}{\left|C_{f,j}\right|}$$

(11)

$$recall\left(C_{f,j},C_{r,i}\right)=\frac{\left|C_{f,j}{\displaystyle \cap }{C}_{r,i}\right|}{\left|C_{r,i}\right|}$$

(12)

$$\mathit{precision} =\frac{{{\displaystyle \sum }}_{C_{r,i}\in C_r}\underset{C_{f,j}\in C_f}{max}precision\left(C_{f,j},C_{r,i}\right)}{N_r}$$

(13)

$$\mathit{recall} =\frac{{{\displaystyle \sum }}_{C_{r,i}\in C_r}\underset{C_{f,j}\in C_f}{max}recall\left(C_{f,j},C_{r,i}\right)}{N_r}$$

(14)

where $precision\left(C_{f,j},C_{r,i}\right)$ is the precision of community detection and $recall\left(C_{f,j},C_{r,i}\right)$ is the recall of community detection, as shown in the formula. Since the calculation requires information about the true community structure, the calculation of the F-score must include a dataset with the true community structure. The larger the value of the F-score, the better the quality of overlapping community detection.

4. Materials and Methods

To address the problem that global information is unattainable in dynamic provenance graphs, this paper proposes a local greedy expansion-based overlapping community detection method. The method integrates the fitness between local nodes and local communities, as well as the similarity between local nodes and nodes within the community, and expands the community boundaries through a variety of mixed similarity functions. Finally, the overlapping communities with shared nodes are analogized and merged to obtain the final community detection results.

4.1. Seeding Phase

In real-world networks, core nodes contribute significantly to information propagation and are usually located in densely connected regions of the network. Our method selects core nodes and their neighbors as seeds (i.e., the coarsening process). First, we select a transitional node v_i that has no community label yet from the newly added nodes in the dynamic traceability graph and aggregate its most similar neighboring nodes using Equation (1) to construct a new seed node V_i (i.e., a coarse community). Node v_i is the core of the rough node V_i, and the most similar neighboring nodes are used to guide the expansion of the seed node. V_i is a node set of G, where V_f is the node set obtained after the node expansion stage. Then, we rank the rough nodes based on the number and weight of nodes in the seed node, as well as the centrality measure of the seed node, to select a subset of core nodes as seeds S. The Algorithm 1 for the seed selection process is as follows:

Algorithm 1 Seeding Phase

Input: Graph G = (V, E); Input: NL collection of nodes without community tags Output: Seed S 1     S←$\varnothing$ 2        while NL≠$\varnothing$ do 3           for $v_i$ ∈ NL do 4              //Filter the nodes with the greatest similarity 5               $V_f$ = Perform C the expansion phase for {$v_i,v_j$} 6               $NC\left(v_i\right)$= $NC\left(v_i\right)$+ $V_f$ 7              //Iterate step 4 until no node with the greatest similarity 8              $V_i$←({$v_i$} ∪ $N\left(v_i\right)$) 9           end for 10         end while 11     $\mathrm{MaxDegreeSet} \leftarrow \arg \underset{V_i\in V}{max}\left(V_i. \mathrm{degree} +V_i. \mathrm{nodeCount} +V_i. \mathrm{edgeCount}, \dots \right)$ 12     return S

The benefit of this seed selection strategy is the ability to discover dispersed rough nodes with high local degree in the network. The communities extended through these nodes have a good local community structure, and the community detection results achieve local full coverage of the local network. This avoids the problem of nodes not belonging to any community due to node deletion.

4.2. Expansion Phase

The local expansion process aims to iteratively add the neighbors of seed nodes S to construct stable and effective communities. The current seed S is augmented or pruned to maximize the fitness function f(C), the ω(v_i) function, and the F(v,s) function. The process is repeated until none of the remaining neighbors meet the threshold for belonging to the current community. The Algorithm 2 for the local expansion of a given seed node S to a community is as follows.

Algorithm 2 Expansion Phase

Input: Graph G = (V, E); Seed S Output: Community C 1     for s ∈ S do 2        Ne = neighbors of s 3        for $v_i$ ∈ Ne do 4           $f\left(v_i\right)$, $w\left(v_i\right)$, $F\left(v_i,s\right)$ 5        end for 6        if $v_i$ ← $\arg \underset{v_i,f\left(v_i\right)}{max}\left(\left\{f\left(v_i\right)\right\}\right)$ or $\arg \underset{v_i,w\left(v_i\right)}{max}\left(\left\{w\left(v_i\right)\right\}\right)$ or $\arg \underset{v_i,F\left(v_i\right)}{max}\left(\left\{F\left(v_i,\mathrm{s}\right)\right\}\right)$ then 7           add $v_i$ to C 8        end if 9     end for 10 return C

During the process of expanding communities, it is necessary to greedily assign isolated neighboring nodes to appropriate communities. During the propagation phase, expansion involving multiple seed nodes does not involve duplicate calculations of merged communities in the iterative process, and overlapping nodes will be assigned to multiple communities.

4.3. Merge Phase

The problem of overlapping community detection involves the existence of common overlapping nodes among different communities, leading to some degree of similarity between communities. When the similarity is high, “overlapping excessively” may occur, resulting in redundant communities. Therefore, we merge communities with a large number of shared overlapping nodes to reduce redundancy and simplify the community structure. We use the community merging coefficient J as a measure, and when the value of J exceeds 1/3, multiple overlapping communities are merged. The Algorithm 3 for the merge phase process is as follows:

Algorithm 3 Merging Phase

Input: Overlapping node set $OV=\left\{O{V}_1,O{V}_2\dots O{V}_k\right\}$ 1     for $O{V}_i$ ∈ $OV$ do 2        for $o{v}_i$ ∈ $O{V}_i$ do 3           //computing $J\left(o{v}_i\right)$ 4           $J\left(O{V}_i\right)=J\left(o{v}_i\right)$ $+J\left(O{V}_i\right)$ 5        end for 6        if $J\left(O{V}_i\right)$ >= 1/3 then 7           if $O{V}_i$ $\in$ $C=\left\{c_1,c_2\dots c_k\right\}$ then 8               merge C 9           end if 10      end if 11  end for

$OV$ is a set of only overlapping nodes, $O{V}_i$ is a set of overlapping nodes that are shared by multiple communities in C, and $o_i{v}_i$ is one overlapping node in the set. When the overlap similarity $J\left(O{V}_i\right)$ is greater than 1/3, all overlapping communities C that $O{V}_i$ belongs to will be merged.

4.4. Complexity Analysis

The first stage of seed selection in the GLOD method uses neighbor similarity to form candidate seeds, with a time complexity of $O\left(n\right)$, where n is the number of nodes without community labels. The second stage of local community expansion expands the community boundary based on the node with the maximum fitness function, with a time complexity of $O\left(sN\right)$, where s is the size of the seed community and N$\left(v_i\right)$ is the set of neighbors of node v_i. The third stage of community comparison and merging has a time complexity of $O\left(c^2\right)$, where c is the total number of nodes in the community. Typically, the number of nodes in community c is much larger than that in the seed community s, but not all communities c are larger than seed community s. Overall, the worst-case time complexity of the GLOD method is $O\left(c^2\right)$.

5. Results

This section introduces the datasets and evaluations used in the experiments. The quality of overlap community detection is evaluated by comparing the F-score values with the LOCD1, LOCD2, LOCD3, LOCD4, LOCD5, LOCD6 [11], MULTICOM [39], and OCS [40] algorithms. The experimental results demonstrate the effectiveness of the GLOD algorithm.

5.1. Datasets

The experimental evaluation in this section is divided into two parts. The first part evaluates the performance of local overlap community detection algorithms using synthetic networks generated by the LFR benchmark [47]. The LFR benchmark test network is controlled by several parameters that determine the topology of the network. The parameter N controls the number of nodes in the network; $\overline{k}$ represents the average node degree of the network; $k_{max}$ represents the maximum node degree of the network; the parameter $O_n$ sets the number of overlapping nodes in the network; the parameter$O_m$ controls the number of communities to which each overlapping node belongs; $C_{min}$ and $C_{max}$ are used to control the range of community sizes that can be taken in the network; and $\mu$ is the overlapping parameter, which controls the probability that the nodes within a community are connected to nodes outside the community. By adjusting the different parameters of the LFR benchmark network, we can obtain topological graphs with different properties, which simulate real network data. In addition, the LFR benchmark network can also generate a community partition of network nodes, which can be used to compare the results of overlap community discovery with the generated true community structure and validate the effectiveness of the algorithm.

The second part is a real-world dataset, and in this experiment, we used the Amazon dataset (https://snap.stanford.edu/data/ accessed on 1 December 2022), which is a product sales network and can be found on their website. The Amazon dataset contains 75,149 communities, 334,863 nodes, and 925,872 edges. The Provenance Graph dataset, which is a computing-data provenance log, contains 14,575 communities, 134,882 nodes, and 285,376 edges.

5.2. Synthetic Networks

The simulation experiments evaluated the effectiveness of the algorithm using LFR benchmarks. First, three groups of LFR benchmark test networks were generated based on parameter settings with N = 5000 and $\mu \in \left\{0.1,0.3,0.4\right\}$, where each group of LFR networks had the same node size but different levels of community mixing. Each group contained seven network datasets with varying degrees of overlap, where $O_m\in \left[2,8\right]$. Other parameters were set to the same values: average node degree k = 10; maximum node degree $k_{max}$ = 50; number of overlapping nodes $O_n=0.1 \mathrm{N}$; and community size upper and lower bounds $c_{min}=25$ and $c_{max}=200$. As the number of communities to which overlapping nodes belong $O_m$ increases, the difficulty of detecting overlapping communities also increases.

• LFR dataset with N = 5000 and $\mu =0.1$.

From

Table 1. F-score on LFR networks with N = 5000, $\mu$ = 0.1.

Om	2	3	4	5	6	7	8
GLOD	0.9623	0.8386	0.7935	0.7647	0.7276	0.6953	0.6863
LOCD1	0.8118	0.7916	0.7673	0.7451	0.7123	0.683	0.6555
LOCD2	0.8275	0.7944	0.7847	0.759	0.7335	0.7019	0.6764
LOCD3	0.8128	0.791	0.7757	0.7539	0.7327	0.6983	0.6647
LOCD4	0.9299	0.8072	0.789	0.7409	0.7105	0.694	0.6606
LOCD5	0.9301	0.8174	0.7998	0.756	0.7279	0.7031	0.6719
LOCD6	0.9368	0.822	0.8038	0.7607	0.7344	0.7085	0.6765
(2, 1) OCS	0.7007	0.4867	0.566	0.4625	0.4246	0.5275	0.5462
(3, 0.8) OCS	0.6707	0.4376	0.5493	0.4476	0.406	0.5155	0.5584
(3, 0.9) OCS	0.4116	0.3708	0.3764	0.3939	0.3986	0.4197	0.3945
MULTICOM	0.238	0.2373	0.2329	0.2478	0.2417	0.2284	0.2261

, we can draw the following conclusions: Overall, as Om increases, the boundaries of overlapping communities become increasingly blurred, and the problem of identifying overlapping nodes becomes more difficult. This leads to a gradual decrease in the quality of overlapping community detection algorithms, as evidenced by a decreasing trend in F-score values. When $O_m\in \left\{2,3,5,8\right\}$, GLOD achieves the best F-score values, while LOCD6 performs best when $O_m\in \left\{4,6,7\right\}$. However, overall, GLOD outperforms the other algorithms. LOCD6 uses the maximal clique algorithm and has an advantage in identifying communities with a larger number of nodes when the community boundary is not very blurred. On the other hand, GLOD adopts a method of maximizing local correlation and the fitness function, resulting in a higher degree of separation and a larger number of communities when $O_m\in \left\{4,6,7\right\}$, leading to a decrease in F-score values.

Figure 1 shows the trend charts of the GLOD, LOCD, OCS, and MULTICOM algorithms. For the high-quality community detection algorithms, GLOD and LOCD, the F-score decreases, and the community boundaries become blurred as Om increases. Overall, the GLOD algorithm has an advantage over the others.

• LFR dataset with N = 5000, μ = 0.3

From

Table 2. F-score on LFR networks with N = 5000, $\mu$ = 0.3.

Om	2	3	4	5	6	7	8
GLOD	0.7894	0.6632	0.6864	0.6522	0.6397	0.6231	0.6095
LOCD1	0.7276	0.639	0.6618	0.693	0.6195	0.6372	0.6014
LOCD2	0.7329	0.6427	0.6523	0.687	0.6084	0.6414	0.5936
LOCD3	0.7265	0.6339	0.6487	0.6879	0.6035	0.6371	0.5931
LOCD4	0.6476	0.6165	0.6437	0.6026	0.5596	0.604	0.5717
LOCD5	0.6798	0.6348	0.6807	0.6124	0.5281	0.6047	0.5703
LOCD6	0.6731	0.634	0.682	0.616	0.5363	0.6103	0.5747
(2, 1) OCS	0.2804	0.1712	0.3078	0.2517	0.3106	0.2563	0.2275
(3, 0.8) OCS	0.2652	0.1459	0.3317	0.2113	0.3019	0.2848	0.2065
(3, 0.9) OCS	0.1795	0.2213	0.2202	0.2413	0.293	0.24	0.2152
MULTICOM	0.1689	0.1679	0.1557	0.1673	0.1722	0.1802	0.1674

, the following conclusions can be drawn: When $O_m\in \left\{2,3,4,6,8\right\}$, the GLOD algorithm obtains the best F-score value, LOCD1 obtains the maximum F-score value when $O_m\in \left\{5\right\}$ and LOCD2 obtains the maximum F-score value when $O_m\in \left\{7\right\}$. GLOD, LOCD1, LOCD2, and LOCD3 all adopt the DMF_M algorithm. It can be clearly seen that the F-score values of algorithms using DMF_M are higher than other algorithms when $O_m\in \left\{5,6,7,8\right\}$, indicating that the DMF_M algorithm has higher quality of overlapping community detection when dealing with overlapping nodes that belong to multiple communities.

As shown in Figure 2, the trend charts of the GLOD, LOCD, OCS, and MULTICOM algorithms are presented. When $O_m\in \left\{3,5,6\right\}$, the GLOD, LOCD, and OCS algorithms oscillate, but the GLOD algorithm has smaller fluctuations and a more stable trend. Overall, the community detection quality of the GLOD algorithm is more stable.

• LFR dataset with N = 5000, $\mu$ = 0.4

The following conclusions can be drawn from

Table 3. F-score on LFR networks with N = 5000, $\mu$ = 0.4.

Om	2	3	4	5	6	7	8
GLOD	0.7174	0.6038	0.5543	0.5377	0.5371	0.5296	0.5291
LOCD1	0.3866	0.4544	0.4257	0.4527	0.4762	0.5136	0.5089
LOCD2	0.3836	0.4762	0.4003	0.4439	0.4662	0.4964	0.5024
LOCD3	0.3777	0.4529	0.3869	0.4293	0.4499	0.4826	0.4958
LOCD4	0.6434	0.5489	0.4902	0.5048	0.5157	0.515	0.524
LOCD5	0.7055	0.57	0.4817	0.4621	0.5492	0.4862	0.4635
LOCD6	0.7039	0.5715	0.4828	0.4633	0.5502	0.4889	0.4663
(2, 1) OCS	0.3064	0.3053	0.2336	0.2646	0.2922	0.3599	0.3455
(3, 0.8) OCS	0.2984	0.287	0.2145	0.2496	0.2862	0.3607	0.3341
(3, 0.9) OCS	0.0491	0.0976	0.048	0.0499	0.0586	0.086	0.1212
MULTICOM	0.1468	0.1642	0.146	0.1445	0.1466	0.1469	0.1482

: when $O_m\in \left\{2,3,4,5,7,8\right\}$, the GLOD algorithm obtains the best F-score value, and LOCD5 obtains the maximum F-score value when $O_m\in \left\{6\right\}$. The GLOD algorithm has a high degree of separation for overlapping communities in highly overlapping networks, and there are no nodes with unknown community labels in small parts of the network, indicating a high level of local expandability.

Figure 3 shows the trend graphs of the GLOD, LOCD, OCS, and MULTICOM algorithms. When $O_m>4$, the GLOD algorithm tends to stabilize and remains above 0.5. The trend graph also indicates that the GLOD algorithm has a higher effectiveness in community detection than other algorithms. Overall, the community detection quality of the GLOD algorithm is more stable.

In summary, as the number of communities that have overlapping nodes belonging to $O_m$ increases, the quality of overlapping community detection decreases, resulting in a decreasing trend in F-score values for all 11 algorithms. However, algorithms that use a hybrid function during the expansion phase show higher quality in detecting overlapping communities as $O_m$ and μ increase, compared to algorithms using a single principle. Additionally, the GLOD algorithm has an extra integration phase, which better implements the effectiveness of local expansion compared to other algorithms.

5.3. Real-World Networks

For real-world network data, since the actual community structure is unknown, it is not possible to compare the community detection results with the true community results. Therefore, in this experiment, the Amazon dataset with real community structure and its dataset of top5000 communities were selected to verify the effectiveness of overlapping community detection.

As shown in Figure 4, on the Amazon dataset, the GLOD, LOCD1, LOCD2, and LOCD3 algorithms are significantly better than the LOCD4, LOCD5, LOCD6, OCS, and MULTICOM algorithms. Moreover, it is evident that the GLOD, LOCD1, LOCD2, and LOCD3 algorithms all use the DMF_M algorithm in the expansion phase, which significantly improves the quality of overlap community detection compared to those without the DMF_M algorithm. In the high-quality community dataset of the top5000 communities in Amazon, as the overlap degree of communities increases and the separability becomes clearer, the quality of community detection improves. The F-score values of all algorithms on the top5000 dataset have significantly increased, with the GLOD algorithm’s community detection effectiveness being 2.1% higher than the best LOCD2 algorithm. In the experiment, the OCS algorithm may generate blank communities where single nodes do not belong to any community, leading to a decrease in the quality of overlap community detection, which the GLOD algorithm addresses. Although LOCD’s six algorithms solve the blank community problem, it is challenging to define the fuzzy relationship threshold for calculating community centers, resulting in multiple community centers. GLOD’s focus in the expansion phase is on boundary problems, and community center weight is not the most critical issue to solve. During community merging, GLOD addresses the problem of high similarity between overlapping nodes belonging to multiple communities, merging related communities when the similarity between overlapping nodes exceeds 1/3, indirectly improving the quality of communities. In conclusion, in a dynamic graph with high-quality communities and a large number of nodes and edges, finding the global optimum as the graph scales up is an NP-hard problem. The GLOD algorithm can effectively detect overlap communities in the local graph through a hybrid method of local expansion.

On the Provenance Networks dataset, we can see that the overall trend is declining. The GLOD algorithm has an obvious advantage in the Provenance Networks data. The first stage is mainly on the seed selection of the neighbor similarity function. Although the boundary is not obvious, the community is found. The general orientation of the second part uses the f(C), $\omega \left(v_i\right)$ and $F\left(v,s\right)$ hybrid algorithm to expand and clarify the boundaries of the community. Finally, the J algorithm is used to merge redundant communities to further improve the quality of the community.

6. Conclusions

In this paper, we propose a method of local greedy expansion, called GLOD. This method uses neighbor similarity to form seed communities, which avoids the problem of invalid seeds caused by a single node forming a seed and the problem of blank communities. Furthermore, the method extends the boundaries of communities based on a mixed community similarity function, strictly controlling the separation boundaries of communities and avoiding community jitter. The analysis and merging of community detection results can reduce redundant communities while maintaining high coverage. Experiments on LFR test networks and real network datasets show that the GLOD method can achieve good community detection results on datasets with high overlap and good community quality.

In addition, GLOD may exhibit unstable community detection quality when the community boundaries are not clear or the dataset has low community quality. This is mainly observed in dynamic graphs, where the instability of local nodes causes floating computation issues. The next step will be to conduct further research on the adaptability function of community extension, so as to maintain stable community detection quality even when the community boundaries are not clear or the dataset has low community quality.