# Social Network Community-Discovery Algorithm Based on a Balance Factor

Authors: Lizhao Liu; Xiaomei Shu; Biao Cai
Journal: Discrete Dynamics in Nature and Society
 (2022)

---

## Abstract

Community discovery plays a crucial role in understanding the structure of networks. In recent years, the application of clustering algorithms in the community-discovery tasks of complex networks has been studied frequently. In this study, we proposed a balance factor of node density and node-degree centrality for the core-node selection problem in community discovery. We also proposed a new community-discovery algorithm based on the balance factor, adaptability, and modularity increment, which is based on the balance factor (BComd). First, the proposed method was able to identify the core nodes in a community. Second, we used node-degree centrality, node density, and adaptability to detect overlaps between communities and then we removed these overlaps from the network to obtain a subnetwork with a clear community structure. Third, we obtained the preliminary community divisions by clustering the subnetworks, and these preliminary communities were usually the core parts of the communities they belonged to. Finally, each preliminary community was compressed into a new node, and then, the new network was clustered using the Louvain algorithm. The experimental results showed that the algorithm identified the core nodes in communities well, effectively discovered overlaps between communities, and had superior performance in large-scale networks.


---

## Body

## 1. Introduction

Complex-network analysis has been applied in many fields, such as text analysis [1, 2], user identification [3], and recommendation systems [4]. The key attribute of complex networks is their community structure, an object of great interest that has been studied extensively in various works [5, 6]. Research on complex-network community-discovery algorithms holds great significance in analyzing the hierarchical structure of complex networks, the formation of communities, the spreading nature of nodes, and the mining of their internal-network characteristics.Many community-detection algorithms have been proposed for complex networks [7–9]. The Girvan-Newman (GN) [10] algorithm is a classical community-discovery algorithm based on hierarchical clustering. The basic idea is to detect the edges connecting different communities in a graph and remove them to achieve segmentation. In a graph, the edges connecting different communities are usually those with large edge-betweenness. Edge-betweenness is the proportion of the number of shortest paths passing through the edge to the total number of shortest paths in the graph. The time complexity of GN algorithms is Omn2, where n is the number of nodes and m is the number of edges. Because of its high complexity, the algorithm often is not directly applicable to large-scale networks. The k-means clustering algorithm [11] divides data into multiple clusters based on the minimum error function. This algorithm has the characteristics of fast clustering, easy implementation, and effective classification in large datasets and is widely used for community detection in complex networks. However, the initial clustering-center selection of the traditional k-means clustering algorithm is a random process and cannot guarantee effective clustering [12]. And CNN [35, 36] based community-detection method [33] can make good performance.In response to the problems of the noted algorithms, we have proposed a balance factor for determining the core nodes in the community. This balance factor can select reasonable nodes as initial clustering centers, thus avoiding the problem of ineffective clustering caused by randomly selecting the initial centers. On the basis of this balance factor, we proposed the BComd algorithm. The time complexity of the algorithm isOnk¯, where n is the number of nodes in the network and k¯ is the average of the node degrees in the network. The BComd algorithm had a considerably lower time complexity than the GN algorithm. In summary, the proposed method achieved better experimental results than traditional tests using several commonly used publicly available large network datasets.This paper is organized as follows: Section2 introduces several theories. In Section 3, the proposed method is described in detail, and then the experimental results are introduced in Section 4. Finally, the conclusion is summarized in Section 5.


## 2. Methodology

### 2.1. Notions

In this section, the concepts and methods used by the algorithm are introduced separately. The node density and degree are used to construct the balance factor, and the modularity measure factor and fitness factor are used for community clustering.


#### 2.1.1. Node Density

We determined the node density [13] by the number of edges and nodes in the subgraph generated by that node's h-hop forward width-first search. The higher the node density, the stronger the community belongingness of the node, which is inconsistent with traditional degree centrality; the leaf nodes have the smallest degree but have the largest community belongingness-1. The node density in the network is defined as follows:(1)densityvih=E′V′V′−1/2,where i represents the ith node, ℎ is the number of forward hops from the node, G′ represents the subgraph generated by the h-hop width-priority search of the node V′, V′ is the node set of the subgraph, V′ represents the number of nodes V′ in the subgraph, E′ represents the edge set of the subgraph G′, and E′ refers to the number of middle edges in E′. Node density is directly related to the location of nodes in the network. Nodes with low node density are usually closely related to other communities. In contrast, nodes with high node density generally are not related to other communities generally.


#### 2.1.2. Modularity and Modularity Increment

Modularity is a measurement concept proposed by Newman and Girvan [10] and is a quality index for evaluating network partitions. The range of modularity is −1/21 [23], and it is the difference between the number of connected edges of nodes in the community and the number of connected edges under random conditions. The greater the modularity, the better the effect of community division. Modularity is defined as follows:(2)Q=12m∑i,jAij−kikj2mδCi,Cj,where m is the number of edges of the network, and Aij is the element of the ith row and j-th column of collocation matrix A corresponding to the network. If there is a connecting edge between nodes i and j, Aij is 1; otherwise, it is 0. Additionally, ki is the degree of node i, so kikj/2m indicates the possibility of connected edges between node i and node j in a random situation. Ci is the community to which node i belongs, and when the communities to which node i and node j belong are the same, δCi,Cj  = 1; otherwise, it is 0. Let eij be the ratio of the number of edges connecting the vertices in community i to the vertices in community j to the total number of edges. Then it can be expressed with the following equation:(3)eij=12m∑vwAvwδCv,i.Letai  =  ∑jeij, which represents the ratio of the number of edges associated with nodes to the total number of edges in the community i, where(4)ai=12m∑vkvδCv,i.The modularity can also be represented as follows:(5)Q=∑ieii−ai2.Newman also proposed the equation for ∆Q [14], the change of merging the community i and j, which is as follows:(6)ΔQ=eij+eji−2aiaj=2eij−aiaj.


#### 2.1.3. Adaptability

Lancichinetti et al. [15] defined an adaptability equation, as follows:(7)fG=kinGkinG+kexGα,where kinG and kexG are the sum of the total internal degree and the total external degree of module G, respectively, and α is the resolution parameter that controls the community's size. A natural choice for α is 1. Formula (7) gives the ratio of the internal degree of the community to the total degree, which corresponds to the so-called weak definition of the community introduced by Radicchi et al. [16]. Given the adaptability function, the adaptability of node A corresponds to module g. Then fgA is defined as the change in the adaptability of the module with and without node A, which is as follows:(8)fgA=fg+A−fg−A,where the symbol g+Aorg−A represents the subgraph obtained from module g, where node A is located inside (outside). In this study, α was set to 1.


### 2.2. Proposed Algorithm

We constructed the balance factor based on the partitioning of the degree and density of the graph. The degrees in a graph showed a long-tailed distribution, and it was found in [13] that the density also generally followed a long-tailed distribution. It has been verified that nodes with small density tend to be the cross nodes between communities [13], so we constructed the balance factor of community belongingness based on the characteristics of density and degree.This section introduces the algorithm proposed in this paper. The balance factor based on node density and node-degree centrality is given in detail in Section2.2.1, which identifies the core nodes in the community. In Section 2.2.2, the balanced distribution of nodes in the network is introduced. Experiments found that the fitting curves of the balanced distribution of nodes in the Amazon, DBLP, and YouTube networks all had a similar parabolic shape. According to this finding, we proposed a method to detect overlapping parts in the network. Section 2.2.3 explains this community-detection method (i.e., the BComd algorithm), which is based on the balance factor, adaptability, and modularity increment.


#### 2.2.1. Balance Factor Construction

The center of a network is especially important because it affects the entire network's operation, so choosing the right core node improves the accuracy of community detection. Degree centrality is a direct metric to portray the centrality of nodes, which reflects the importance of nodes in the network. Node density reflects the community affiliation of nodes, and nodes with low node density tend to establish close connections with other communities. In contrast, nodes with high node density do not establish connections with other communities. In this paper, node density was combined with node-degree centrality as the criteria for selecting core nodes. Node-degree centrality is defined as the number of links incident to the node:Cdi  =  ki, where ki denotes the degree of the node vi. Balance factor B is then defined as follows:(9)Bvi=αCdiK++1−αDensityvi1,i=1,2…,n,where the value of K is equal to the maximum degree in the network, n is the number of nodes in the network, and α  = 0.4. Nodes located at the center of the cluster shared many edges with other partners in the group. Therefore, the core nodes should have a high degree of centrality and aggregation. According to equation (9), the nodes with high Bvi values in the network satisfied this requirement. Therefore, we choose the node with the highest Bvi value as the core node. According to equation (9), the node-degree centrality had a greater influence on selecting core nodes than node density. Selecting nodes with large values as the initial nodes of the community can reduce the negative impact caused by the community's uncertainty to which the seed nodes belong. For instance, if a structural hole in the network were randomly selected as the initial node of the community, then during the community expansion phase, the added nodes would have a greater chance of coming from different communities.Figure1 shows the balance factor of the nodes in the Karate network. The size of the node represents its Bvi value, so the larger the node, the larger the Bvi value. The Bvi values of nodes 1 and 34 were the largest, and these two nodes also happened to be the core nodes of these two real communities. Choosing these as the initial nodes of the two communities would lead to better clustering results. Conversely, if node 10 was randomly selected as the initial node of the community, it is highly likely to be added into node 3 and node 34 when the community is expanded, and these two nodes would belong to different communities. In summary, our proposed Bvi value helped choose a reasonable node as the initial node. Choosing such a node could reduce the negative impact caused by the uncertainty of the community to which the seed node belongs, thus improving the clustering accuracy of the algorithm.Figure 1
The balance factor of nodes in the Karate network.


#### 2.2.2. Balanced Distribution of Nodes

If the overlapping nodes between communities could be detected and these nodes and their edges could be removed from the network, the community structure would be more apparent (see the proof in Section4.3). We clustered the subnetworks obtained by removing the overlaps to obtain the initial community divisions, usually the core parts of the communities they belonged to. We compressed each primary community into one node and then clustered the new network using the Louvain algorithm to improve the clustering accuracy. However, we did not know the overlap between communities for unknown networks, so we used the following method to detect the overlap.We usedlogki−mink/logmaxk−mink as the x coordinate and Bvi/max B as the y coordinate, where maxkmink was the maximum (minimum) degree of the network and max B was the maximum Bvi value in the network. All nodes in the network were output on the coordinate system. Figure 2 shows the balanced distribution of nodes on the Amazon, DBLP, and YouTube datasets; these datasets were derived from the Stanford Large Network Dataset Collection (SNAP) [17].Figure 2
The balance distribution of nodes.Because one horizontal coordinate corresponded to multiple vertical coordinates in the image, we took the average of the vertical coordinates and performed a curve fit using a cubic function. As shown by the red parabola in Figure3, we found that the fitted curve had a similar parabolic shape.Figure 3
Nodes with high node density (with red color).We used half of the average density of nodes in the network as the boundary. Nodes with a density higher than half of the average were considered to have higher node density. These are the nodes denoted by red nodes in Figure3.Next, a line was drawn perpendicular to thex axis through the lowest point of the parabola. We assumed the node on the right side of the line had a high degree of centrality, so we changed the node's color to the right of the line to red, as shown in Figure 4. The blue nodes in Figure 4 were considered to have low density and degree centrality, so these nodes were more likely to be strongly connected to multiple communities. The chance was greater that they were in the overlapping parts between communities.Figure 4
Red and blue partition results.To further find the overlap between communities, we defined the set of nodesvi and its neighbors as a subgraph Gvi. We set α = 1, and the adaptability of the subgraph Gvi was the ratio of the internal degree of the subgraph Gvi to the total degree. If Gvi had high adaptability, this indicated dense internal connectivity and sparse external connectivity, which meant that the neighbors of the node vi were close to each other. In contrast, if Gvi had low adaptability, it meant that the neighbors of the node vi were sparsely connected and might belong to different communities. Therefore, if the adaptability of Gvi was low, we considered that node vi tended to be closely connected with other communities. For the adaptability of the subgraph Gvi, a threshold value δ was set.Our algorithm divided the nodes in the network into two groups. Nodes located in the red area and withfGvi > δ were in group 1, whereas nodes located in the blue area or with fGvi < δ were in group 2. Nodes in group 2 and the edges linked to them were removed from the network to obtain a subnet with a clearer community structure. We set the threshold δ to three-fourths of the average fGvi value. This approach effectively detected overlaps between communities and removed the overlaps before clustering, which gave better community-detection results, as demonstrated in Section 4.3.


#### 2.2.3. BComd Algorithm

The algorithm started with the core nodes and had two sets: community C and the node set W adjacent to community C (each node in W has at least one neighbor in community C). We selected the neighbor node with the largest ∆Q from W in each step and calculated its adaptability. If the adaptability of the neighbor node was positive, we added it to community C and updated W to include the newly discovered neighbor nodes. If the adaptability of the neighbor was negative, it was deleted from W. This process was continued until W was empty. To facilitate the description of the algorithm, we assigned the following definitions.Definition 1.
G = (V, E) was defined as an undirected unweighted network, where V was the vertex set, and E was the edge set. Note that |V| = n and |E| = m.Definition 2.
NG (s) was defined as the set of neighbor nodes of node s.Definition 3.
Ng (s) was defined as the set of neighbor nodes of node s in group 1.Algorithm 1: BComd Algorithm 1
Input: NetworkG(V, E)Output: All CommunitiesStep 1: Calculate theBvi of all nodes in the network. Sort the nodes in V in descending order to obtain sequence l.Step 2: Use the method in Section3.2 to divide the nodes in the network into two groups. Delete the nodes in group 2 and the edges linked to them from the network; then delete the nodes in group 2 from sequence l.Step 3: Select the first nodes in l as the core node and remove it from sequence l. At this point, there is only node s in community C. Add Ng (s) to W.Step 4: For each node inW, calculate its ∆Q for the scenario in which it joins community C.Step 5: Select neighborv with the maximum ∆Q from W and calculate its adaptability. a. If the adaptability is positive, add node v to community C and remove it from both W and sequence l. W=W∪Ngv−w∩C. For node z, which was previously in W, we do not need to recalculate its ∆Q but simply update it according to the following equations:ΔQ=ΔQ+1/m−2Cdv/2m×z/2m,vis adjacent to z,ΔQ=ΔQ−2Cdv/2m×Cdz/2m,otherwise.For those nodes newly added toW, calculate their ∆Q. b. If the adaptability is negative, remove node from W.Repeat Step 5 until there are no nodes inW. At this point, the detection of community C is finished.Step 6: Go back to Step 3 and repeat the following steps until there are no nodes in sequencel.Step 7: Add the nodes and edges deleted in Step 2 back to the network. At this point, the network consists of two parts: one with the previously deleted nodes and the other with the multiple communities that have been detected. We treated each previously deleted node as a community with only one node.Step 8: Compress each community into a single node. The link weights between the new nodes are derived from the sum of the link weights between the nodes in the corresponding two communities. The links between nodes in the same community lead to a self-loop of that community in the new network. The new network is clustered using the Louvain algorithm.Step 9: Execute the Community Integration Strategy.Step 10: Export all communities.


#### 2.2.4. Community Integration

Shang et al. [18] proposed a community-membership function. Considering that a given network G = (V, E) and a prepartition SCG=SC1,SC2,…,SCw, then SCkk=1,2,…,w are the subcommunities in the network, where w is the number of subcommunities and Γ(SCk) is the set of nodes adjacent to subcommunity SCk. This is an aggregation of the external nodes connected to SCk, as follows:(10)fCMSCi,SCj=ΓSCi∩SCjΓSCi,where ΓSCi∩SCj represents the connectivity between subcommunities SCi and SCj, and ΓSCi represents the number of neighbor nodes connected to SCi. Here fCMSCi,SCj evaluates the degree of closeness between SCi and SCj. Shang et al. [18] also defined a function represented by fCI to calculate the degree of mutual membership between two communities:(11)fCISCi,SCj=fCMSCi,SCj+fCMSCj,SCi,i,j=1,2,…,W.This function is called the mutual membership function. First, we set the merge thresholdδ. Then, for community C, fCI for all its neighboring communities was calculated, and the community with the largest fCI was selected. If fCI > δ, then both communities were merged.


### 2.3. Complexity Analysis

In this section, we analyze the time complexity of each stage. During the calculation ofBvi, Bvi for each node should be calculated. We defined the average degree of nodes in the network as k¯ and the total number of nodes in the network as n. Then the time complexity of this process was Onk¯. The time complexity of the sorting operation was Onlogn. In the grouping strategy, the time complexity was caused by removing nodes and their edges from the network. We defined the number of nodes to be deleted as b2. For each node to be deleted, the number of edges related to it was equal to its degree, so the time complexity was Ob2k¯. In the process of community expansion, the BComd algorithm processed only one node at each step, and the time complexity of processing each node was almost linear, so the time complexity was On. Because, in most cases, k¯>logn, the complexity of the BComd algorithm was Onk¯+nlogn+b2k¯+n=Onk¯.


## 2.1. Notions

In this section, the concepts and methods used by the algorithm are introduced separately. The node density and degree are used to construct the balance factor, and the modularity measure factor and fitness factor are used for community clustering.


### 2.1.1. Node Density

We determined the node density [13] by the number of edges and nodes in the subgraph generated by that node's h-hop forward width-first search. The higher the node density, the stronger the community belongingness of the node, which is inconsistent with traditional degree centrality; the leaf nodes have the smallest degree but have the largest community belongingness-1. The node density in the network is defined as follows:(1)densityvih=E′V′V′−1/2,where i represents the ith node, ℎ is the number of forward hops from the node, G′ represents the subgraph generated by the h-hop width-priority search of the node V′, V′ is the node set of the subgraph, V′ represents the number of nodes V′ in the subgraph, E′ represents the edge set of the subgraph G′, and E′ refers to the number of middle edges in E′. Node density is directly related to the location of nodes in the network. Nodes with low node density are usually closely related to other communities. In contrast, nodes with high node density generally are not related to other communities generally.


### 2.1.2. Modularity and Modularity Increment

Modularity is a measurement concept proposed by Newman and Girvan [10] and is a quality index for evaluating network partitions. The range of modularity is −1/21 [23], and it is the difference between the number of connected edges of nodes in the community and the number of connected edges under random conditions. The greater the modularity, the better the effect of community division. Modularity is defined as follows:(2)Q=12m∑i,jAij−kikj2mδCi,Cj,where m is the number of edges of the network, and Aij is the element of the ith row and j-th column of collocation matrix A corresponding to the network. If there is a connecting edge between nodes i and j, Aij is 1; otherwise, it is 0. Additionally, ki is the degree of node i, so kikj/2m indicates the possibility of connected edges between node i and node j in a random situation. Ci is the community to which node i belongs, and when the communities to which node i and node j belong are the same, δCi,Cj  = 1; otherwise, it is 0. Let eij be the ratio of the number of edges connecting the vertices in community i to the vertices in community j to the total number of edges. Then it can be expressed with the following equation:(3)eij=12m∑vwAvwδCv,i.Letai  =  ∑jeij, which represents the ratio of the number of edges associated with nodes to the total number of edges in the community i, where(4)ai=12m∑vkvδCv,i.The modularity can also be represented as follows:(5)Q=∑ieii−ai2.Newman also proposed the equation for ∆Q [14], the change of merging the community i and j, which is as follows:(6)ΔQ=eij+eji−2aiaj=2eij−aiaj.


### 2.1.3. Adaptability

Lancichinetti et al. [15] defined an adaptability equation, as follows:(7)fG=kinGkinG+kexGα,where kinG and kexG are the sum of the total internal degree and the total external degree of module G, respectively, and α is the resolution parameter that controls the community's size. A natural choice for α is 1. Formula (7) gives the ratio of the internal degree of the community to the total degree, which corresponds to the so-called weak definition of the community introduced by Radicchi et al. [16]. Given the adaptability function, the adaptability of node A corresponds to module g. Then fgA is defined as the change in the adaptability of the module with and without node A, which is as follows:(8)fgA=fg+A−fg−A,where the symbol g+Aorg−A represents the subgraph obtained from module g, where node A is located inside (outside). In this study, α was set to 1.


## 2.1.1. Node Density

We determined the node density [13] by the number of edges and nodes in the subgraph generated by that node's h-hop forward width-first search. The higher the node density, the stronger the community belongingness of the node, which is inconsistent with traditional degree centrality; the leaf nodes have the smallest degree but have the largest community belongingness-1. The node density in the network is defined as follows:(1)densityvih=E′V′V′−1/2,where i represents the ith node, ℎ is the number of forward hops from the node, G′ represents the subgraph generated by the h-hop width-priority search of the node V′, V′ is the node set of the subgraph, V′ represents the number of nodes V′ in the subgraph, E′ represents the edge set of the subgraph G′, and E′ refers to the number of middle edges in E′. Node density is directly related to the location of nodes in the network. Nodes with low node density are usually closely related to other communities. In contrast, nodes with high node density generally are not related to other communities generally.


## 2.1.2. Modularity and Modularity Increment

Modularity is a measurement concept proposed by Newman and Girvan [10] and is a quality index for evaluating network partitions. The range of modularity is −1/21 [23], and it is the difference between the number of connected edges of nodes in the community and the number of connected edges under random conditions. The greater the modularity, the better the effect of community division. Modularity is defined as follows:(2)Q=12m∑i,jAij−kikj2mδCi,Cj,where m is the number of edges of the network, and Aij is the element of the ith row and j-th column of collocation matrix A corresponding to the network. If there is a connecting edge between nodes i and j, Aij is 1; otherwise, it is 0. Additionally, ki is the degree of node i, so kikj/2m indicates the possibility of connected edges between node i and node j in a random situation. Ci is the community to which node i belongs, and when the communities to which node i and node j belong are the same, δCi,Cj  = 1; otherwise, it is 0. Let eij be the ratio of the number of edges connecting the vertices in community i to the vertices in community j to the total number of edges. Then it can be expressed with the following equation:(3)eij=12m∑vwAvwδCv,i.Letai  =  ∑jeij, which represents the ratio of the number of edges associated with nodes to the total number of edges in the community i, where(4)ai=12m∑vkvδCv,i.The modularity can also be represented as follows:(5)Q=∑ieii−ai2.Newman also proposed the equation for ∆Q [14], the change of merging the community i and j, which is as follows:(6)ΔQ=eij+eji−2aiaj=2eij−aiaj.


## 2.1.3. Adaptability

Lancichinetti et al. [15] defined an adaptability equation, as follows:(7)fG=kinGkinG+kexGα,where kinG and kexG are the sum of the total internal degree and the total external degree of module G, respectively, and α is the resolution parameter that controls the community's size. A natural choice for α is 1. Formula (7) gives the ratio of the internal degree of the community to the total degree, which corresponds to the so-called weak definition of the community introduced by Radicchi et al. [16]. Given the adaptability function, the adaptability of node A corresponds to module g. Then fgA is defined as the change in the adaptability of the module with and without node A, which is as follows:(8)fgA=fg+A−fg−A,where the symbol g+Aorg−A represents the subgraph obtained from module g, where node A is located inside (outside). In this study, α was set to 1.


## 2.2. Proposed Algorithm

We constructed the balance factor based on the partitioning of the degree and density of the graph. The degrees in a graph showed a long-tailed distribution, and it was found in [13] that the density also generally followed a long-tailed distribution. It has been verified that nodes with small density tend to be the cross nodes between communities [13], so we constructed the balance factor of community belongingness based on the characteristics of density and degree.This section introduces the algorithm proposed in this paper. The balance factor based on node density and node-degree centrality is given in detail in Section2.2.1, which identifies the core nodes in the community. In Section 2.2.2, the balanced distribution of nodes in the network is introduced. Experiments found that the fitting curves of the balanced distribution of nodes in the Amazon, DBLP, and YouTube networks all had a similar parabolic shape. According to this finding, we proposed a method to detect overlapping parts in the network. Section 2.2.3 explains this community-detection method (i.e., the BComd algorithm), which is based on the balance factor, adaptability, and modularity increment.


### 2.2.1. Balance Factor Construction

The center of a network is especially important because it affects the entire network's operation, so choosing the right core node improves the accuracy of community detection. Degree centrality is a direct metric to portray the centrality of nodes, which reflects the importance of nodes in the network. Node density reflects the community affiliation of nodes, and nodes with low node density tend to establish close connections with other communities. In contrast, nodes with high node density do not establish connections with other communities. In this paper, node density was combined with node-degree centrality as the criteria for selecting core nodes. Node-degree centrality is defined as the number of links incident to the node:Cdi  =  ki, where ki denotes the degree of the node vi. Balance factor B is then defined as follows:(9)Bvi=αCdiK++1−αDensityvi1,i=1,2…,n,where the value of K is equal to the maximum degree in the network, n is the number of nodes in the network, and α  = 0.4. Nodes located at the center of the cluster shared many edges with other partners in the group. Therefore, the core nodes should have a high degree of centrality and aggregation. According to equation (9), the nodes with high Bvi values in the network satisfied this requirement. Therefore, we choose the node with the highest Bvi value as the core node. According to equation (9), the node-degree centrality had a greater influence on selecting core nodes than node density. Selecting nodes with large values as the initial nodes of the community can reduce the negative impact caused by the community's uncertainty to which the seed nodes belong. For instance, if a structural hole in the network were randomly selected as the initial node of the community, then during the community expansion phase, the added nodes would have a greater chance of coming from different communities.Figure1 shows the balance factor of the nodes in the Karate network. The size of the node represents its Bvi value, so the larger the node, the larger the Bvi value. The Bvi values of nodes 1 and 34 were the largest, and these two nodes also happened to be the core nodes of these two real communities. Choosing these as the initial nodes of the two communities would lead to better clustering results. Conversely, if node 10 was randomly selected as the initial node of the community, it is highly likely to be added into node 3 and node 34 when the community is expanded, and these two nodes would belong to different communities. In summary, our proposed Bvi value helped choose a reasonable node as the initial node. Choosing such a node could reduce the negative impact caused by the uncertainty of the community to which the seed node belongs, thus improving the clustering accuracy of the algorithm.Figure 1
The balance factor of nodes in the Karate network.


### 2.2.2. Balanced Distribution of Nodes

If the overlapping nodes between communities could be detected and these nodes and their edges could be removed from the network, the community structure would be more apparent (see the proof in Section4.3). We clustered the subnetworks obtained by removing the overlaps to obtain the initial community divisions, usually the core parts of the communities they belonged to. We compressed each primary community into one node and then clustered the new network using the Louvain algorithm to improve the clustering accuracy. However, we did not know the overlap between communities for unknown networks, so we used the following method to detect the overlap.We usedlogki−mink/logmaxk−mink as the x coordinate and Bvi/max B as the y coordinate, where maxkmink was the maximum (minimum) degree of the network and max B was the maximum Bvi value in the network. All nodes in the network were output on the coordinate system. Figure 2 shows the balanced distribution of nodes on the Amazon, DBLP, and YouTube datasets; these datasets were derived from the Stanford Large Network Dataset Collection (SNAP) [17].Figure 2
The balance distribution of nodes.Because one horizontal coordinate corresponded to multiple vertical coordinates in the image, we took the average of the vertical coordinates and performed a curve fit using a cubic function. As shown by the red parabola in Figure3, we found that the fitted curve had a similar parabolic shape.Figure 3
Nodes with high node density (with red color).We used half of the average density of nodes in the network as the boundary. Nodes with a density higher than half of the average were considered to have higher node density. These are the nodes denoted by red nodes in Figure3.Next, a line was drawn perpendicular to thex axis through the lowest point of the parabola. We assumed the node on the right side of the line had a high degree of centrality, so we changed the node's color to the right of the line to red, as shown in Figure 4. The blue nodes in Figure 4 were considered to have low density and degree centrality, so these nodes were more likely to be strongly connected to multiple communities. The chance was greater that they were in the overlapping parts between communities.Figure 4
Red and blue partition results.To further find the overlap between communities, we defined the set of nodesvi and its neighbors as a subgraph Gvi. We set α = 1, and the adaptability of the subgraph Gvi was the ratio of the internal degree of the subgraph Gvi to the total degree. If Gvi had high adaptability, this indicated dense internal connectivity and sparse external connectivity, which meant that the neighbors of the node vi were close to each other. In contrast, if Gvi had low adaptability, it meant that the neighbors of the node vi were sparsely connected and might belong to different communities. Therefore, if the adaptability of Gvi was low, we considered that node vi tended to be closely connected with other communities. For the adaptability of the subgraph Gvi, a threshold value δ was set.Our algorithm divided the nodes in the network into two groups. Nodes located in the red area and withfGvi > δ were in group 1, whereas nodes located in the blue area or with fGvi < δ were in group 2. Nodes in group 2 and the edges linked to them were removed from the network to obtain a subnet with a clearer community structure. We set the threshold δ to three-fourths of the average fGvi value. This approach effectively detected overlaps between communities and removed the overlaps before clustering, which gave better community-detection results, as demonstrated in Section 4.3.


### 2.2.3. BComd Algorithm

The algorithm started with the core nodes and had two sets: community C and the node set W adjacent to community C (each node in W has at least one neighbor in community C). We selected the neighbor node with the largest ∆Q from W in each step and calculated its adaptability. If the adaptability of the neighbor node was positive, we added it to community C and updated W to include the newly discovered neighbor nodes. If the adaptability of the neighbor was negative, it was deleted from W. This process was continued until W was empty. To facilitate the description of the algorithm, we assigned the following definitions.Definition 1.
G = (V, E) was defined as an undirected unweighted network, where V was the vertex set, and E was the edge set. Note that |V| = n and |E| = m.Definition 2.
NG (s) was defined as the set of neighbor nodes of node s.Definition 3.
Ng (s) was defined as the set of neighbor nodes of node s in group 1.Algorithm 1: BComd Algorithm 1
Input: NetworkG(V, E)Output: All CommunitiesStep 1: Calculate theBvi of all nodes in the network. Sort the nodes in V in descending order to obtain sequence l.Step 2: Use the method in Section3.2 to divide the nodes in the network into two groups. Delete the nodes in group 2 and the edges linked to them from the network; then delete the nodes in group 2 from sequence l.Step 3: Select the first nodes in l as the core node and remove it from sequence l. At this point, there is only node s in community C. Add Ng (s) to W.Step 4: For each node inW, calculate its ∆Q for the scenario in which it joins community C.Step 5: Select neighborv with the maximum ∆Q from W and calculate its adaptability. a. If the adaptability is positive, add node v to community C and remove it from both W and sequence l. W=W∪Ngv−w∩C. For node z, which was previously in W, we do not need to recalculate its ∆Q but simply update it according to the following equations:ΔQ=ΔQ+1/m−2Cdv/2m×z/2m,vis adjacent to z,ΔQ=ΔQ−2Cdv/2m×Cdz/2m,otherwise.For those nodes newly added toW, calculate their ∆Q. b. If the adaptability is negative, remove node from W.Repeat Step 5 until there are no nodes inW. At this point, the detection of community C is finished.Step 6: Go back to Step 3 and repeat the following steps until there are no nodes in sequencel.Step 7: Add the nodes and edges deleted in Step 2 back to the network. At this point, the network consists of two parts: one with the previously deleted nodes and the other with the multiple communities that have been detected. We treated each previously deleted node as a community with only one node.Step 8: Compress each community into a single node. The link weights between the new nodes are derived from the sum of the link weights between the nodes in the corresponding two communities. The links between nodes in the same community lead to a self-loop of that community in the new network. The new network is clustered using the Louvain algorithm.Step 9: Execute the Community Integration Strategy.Step 10: Export all communities.


### 2.2.4. Community Integration

Shang et al. [18] proposed a community-membership function. Considering that a given network G = (V, E) and a prepartition SCG=SC1,SC2,…,SCw, then SCkk=1,2,…,w are the subcommunities in the network, where w is the number of subcommunities and Γ(SCk) is the set of nodes adjacent to subcommunity SCk. This is an aggregation of the external nodes connected to SCk, as follows:(10)fCMSCi,SCj=ΓSCi∩SCjΓSCi,where ΓSCi∩SCj represents the connectivity between subcommunities SCi and SCj, and ΓSCi represents the number of neighbor nodes connected to SCi. Here fCMSCi,SCj evaluates the degree of closeness between SCi and SCj. Shang et al. [18] also defined a function represented by fCI to calculate the degree of mutual membership between two communities:(11)fCISCi,SCj=fCMSCi,SCj+fCMSCj,SCi,i,j=1,2,…,W.This function is called the mutual membership function. First, we set the merge thresholdδ. Then, for community C, fCI for all its neighboring communities was calculated, and the community with the largest fCI was selected. If fCI > δ, then both communities were merged.


## 2.2.1. Balance Factor Construction

The center of a network is especially important because it affects the entire network's operation, so choosing the right core node improves the accuracy of community detection. Degree centrality is a direct metric to portray the centrality of nodes, which reflects the importance of nodes in the network. Node density reflects the community affiliation of nodes, and nodes with low node density tend to establish close connections with other communities. In contrast, nodes with high node density do not establish connections with other communities. In this paper, node density was combined with node-degree centrality as the criteria for selecting core nodes. Node-degree centrality is defined as the number of links incident to the node:Cdi  =  ki, where ki denotes the degree of the node vi. Balance factor B is then defined as follows:(9)Bvi=αCdiK++1−αDensityvi1,i=1,2…,n,where the value of K is equal to the maximum degree in the network, n is the number of nodes in the network, and α  = 0.4. Nodes located at the center of the cluster shared many edges with other partners in the group. Therefore, the core nodes should have a high degree of centrality and aggregation. According to equation (9), the nodes with high Bvi values in the network satisfied this requirement. Therefore, we choose the node with the highest Bvi value as the core node. According to equation (9), the node-degree centrality had a greater influence on selecting core nodes than node density. Selecting nodes with large values as the initial nodes of the community can reduce the negative impact caused by the community's uncertainty to which the seed nodes belong. For instance, if a structural hole in the network were randomly selected as the initial node of the community, then during the community expansion phase, the added nodes would have a greater chance of coming from different communities.Figure1 shows the balance factor of the nodes in the Karate network. The size of the node represents its Bvi value, so the larger the node, the larger the Bvi value. The Bvi values of nodes 1 and 34 were the largest, and these two nodes also happened to be the core nodes of these two real communities. Choosing these as the initial nodes of the two communities would lead to better clustering results. Conversely, if node 10 was randomly selected as the initial node of the community, it is highly likely to be added into node 3 and node 34 when the community is expanded, and these two nodes would belong to different communities. In summary, our proposed Bvi value helped choose a reasonable node as the initial node. Choosing such a node could reduce the negative impact caused by the uncertainty of the community to which the seed node belongs, thus improving the clustering accuracy of the algorithm.Figure 1
The balance factor of nodes in the Karate network.


## 2.2.2. Balanced Distribution of Nodes

If the overlapping nodes between communities could be detected and these nodes and their edges could be removed from the network, the community structure would be more apparent (see the proof in Section4.3). We clustered the subnetworks obtained by removing the overlaps to obtain the initial community divisions, usually the core parts of the communities they belonged to. We compressed each primary community into one node and then clustered the new network using the Louvain algorithm to improve the clustering accuracy. However, we did not know the overlap between communities for unknown networks, so we used the following method to detect the overlap.We usedlogki−mink/logmaxk−mink as the x coordinate and Bvi/max B as the y coordinate, where maxkmink was the maximum (minimum) degree of the network and max B was the maximum Bvi value in the network. All nodes in the network were output on the coordinate system. Figure 2 shows the balanced distribution of nodes on the Amazon, DBLP, and YouTube datasets; these datasets were derived from the Stanford Large Network Dataset Collection (SNAP) [17].Figure 2
The balance distribution of nodes.Because one horizontal coordinate corresponded to multiple vertical coordinates in the image, we took the average of the vertical coordinates and performed a curve fit using a cubic function. As shown by the red parabola in Figure3, we found that the fitted curve had a similar parabolic shape.Figure 3
Nodes with high node density (with red color).We used half of the average density of nodes in the network as the boundary. Nodes with a density higher than half of the average were considered to have higher node density. These are the nodes denoted by red nodes in Figure3.Next, a line was drawn perpendicular to thex axis through the lowest point of the parabola. We assumed the node on the right side of the line had a high degree of centrality, so we changed the node's color to the right of the line to red, as shown in Figure 4. The blue nodes in Figure 4 were considered to have low density and degree centrality, so these nodes were more likely to be strongly connected to multiple communities. The chance was greater that they were in the overlapping parts between communities.Figure 4
Red and blue partition results.To further find the overlap between communities, we defined the set of nodesvi and its neighbors as a subgraph Gvi. We set α = 1, and the adaptability of the subgraph Gvi was the ratio of the internal degree of the subgraph Gvi to the total degree. If Gvi had high adaptability, this indicated dense internal connectivity and sparse external connectivity, which meant that the neighbors of the node vi were close to each other. In contrast, if Gvi had low adaptability, it meant that the neighbors of the node vi were sparsely connected and might belong to different communities. Therefore, if the adaptability of Gvi was low, we considered that node vi tended to be closely connected with other communities. For the adaptability of the subgraph Gvi, a threshold value δ was set.Our algorithm divided the nodes in the network into two groups. Nodes located in the red area and withfGvi > δ were in group 1, whereas nodes located in the blue area or with fGvi < δ were in group 2. Nodes in group 2 and the edges linked to them were removed from the network to obtain a subnet with a clearer community structure. We set the threshold δ to three-fourths of the average fGvi value. This approach effectively detected overlaps between communities and removed the overlaps before clustering, which gave better community-detection results, as demonstrated in Section 4.3.


## 2.2.3. BComd Algorithm

The algorithm started with the core nodes and had two sets: community C and the node set W adjacent to community C (each node in W has at least one neighbor in community C). We selected the neighbor node with the largest ∆Q from W in each step and calculated its adaptability. If the adaptability of the neighbor node was positive, we added it to community C and updated W to include the newly discovered neighbor nodes. If the adaptability of the neighbor was negative, it was deleted from W. This process was continued until W was empty. To facilitate the description of the algorithm, we assigned the following definitions.Definition 1.
G = (V, E) was defined as an undirected unweighted network, where V was the vertex set, and E was the edge set. Note that |V| = n and |E| = m.Definition 2.
NG (s) was defined as the set of neighbor nodes of node s.Definition 3.
Ng (s) was defined as the set of neighbor nodes of node s in group 1.Algorithm 1: BComd Algorithm 1
Input: NetworkG(V, E)Output: All CommunitiesStep 1: Calculate theBvi of all nodes in the network. Sort the nodes in V in descending order to obtain sequence l.Step 2: Use the method in Section3.2 to divide the nodes in the network into two groups. Delete the nodes in group 2 and the edges linked to them from the network; then delete the nodes in group 2 from sequence l.Step 3: Select the first nodes in l as the core node and remove it from sequence l. At this point, there is only node s in community C. Add Ng (s) to W.Step 4: For each node inW, calculate its ∆Q for the scenario in which it joins community C.Step 5: Select neighborv with the maximum ∆Q from W and calculate its adaptability. a. If the adaptability is positive, add node v to community C and remove it from both W and sequence l. W=W∪Ngv−w∩C. For node z, which was previously in W, we do not need to recalculate its ∆Q but simply update it according to the following equations:ΔQ=ΔQ+1/m−2Cdv/2m×z/2m,vis adjacent to z,ΔQ=ΔQ−2Cdv/2m×Cdz/2m,otherwise.For those nodes newly added toW, calculate their ∆Q. b. If the adaptability is negative, remove node from W.Repeat Step 5 until there are no nodes inW. At this point, the detection of community C is finished.Step 6: Go back to Step 3 and repeat the following steps until there are no nodes in sequencel.Step 7: Add the nodes and edges deleted in Step 2 back to the network. At this point, the network consists of two parts: one with the previously deleted nodes and the other with the multiple communities that have been detected. We treated each previously deleted node as a community with only one node.Step 8: Compress each community into a single node. The link weights between the new nodes are derived from the sum of the link weights between the nodes in the corresponding two communities. The links between nodes in the same community lead to a self-loop of that community in the new network. The new network is clustered using the Louvain algorithm.Step 9: Execute the Community Integration Strategy.Step 10: Export all communities.


## 2.2.4. Community Integration

Shang et al. [18] proposed a community-membership function. Considering that a given network G = (V, E) and a prepartition SCG=SC1,SC2,…,SCw, then SCkk=1,2,…,w are the subcommunities in the network, where w is the number of subcommunities and Γ(SCk) is the set of nodes adjacent to subcommunity SCk. This is an aggregation of the external nodes connected to SCk, as follows:(10)fCMSCi,SCj=ΓSCi∩SCjΓSCi,where ΓSCi∩SCj represents the connectivity between subcommunities SCi and SCj, and ΓSCi represents the number of neighbor nodes connected to SCi. Here fCMSCi,SCj evaluates the degree of closeness between SCi and SCj. Shang et al. [18] also defined a function represented by fCI to calculate the degree of mutual membership between two communities:(11)fCISCi,SCj=fCMSCi,SCj+fCMSCj,SCi,i,j=1,2,…,W.This function is called the mutual membership function. First, we set the merge thresholdδ. Then, for community C, fCI for all its neighboring communities was calculated, and the community with the largest fCI was selected. If fCI > δ, then both communities were merged.


## 2.3. Complexity Analysis

In this section, we analyze the time complexity of each stage. During the calculation ofBvi, Bvi for each node should be calculated. We defined the average degree of nodes in the network as k¯ and the total number of nodes in the network as n. Then the time complexity of this process was Onk¯. The time complexity of the sorting operation was Onlogn. In the grouping strategy, the time complexity was caused by removing nodes and their edges from the network. We defined the number of nodes to be deleted as b2. For each node to be deleted, the number of edges related to it was equal to its degree, so the time complexity was Ob2k¯. In the process of community expansion, the BComd algorithm processed only one node at each step, and the time complexity of processing each node was almost linear, so the time complexity was On. Because, in most cases, k¯>logn, the complexity of the BComd algorithm was Onk¯+nlogn+b2k¯+n=Onk¯.


## 3. Experiment Setting

This section briefly introduces the network used in the experiment and the two evaluation metrics used in this study. It was experimentally demonstrated that eliminating overlapping parts obtained a clearer community structure and better community-detection results. Last, we compared the proposed algorithm with known algorithms. All experiments were performed on a PC equipped with a 2.70 GHz Intel Core processor and 4 GB RAM.


### 3.1. Dataset

The Karate Club [19] is a social network composed of 34 nodes and 78 edges. Each node represents a member of the club, and an edge indicates that two members are friends. The bottlenose dolphin community (Dolphin) [20] is a social network of frequent interactions between 62 dolphins living in New Zealand. The nodes in the network represent dolphins, and an edge represents the corresponding frequent contacts of dolphins. There are two communities in the network. American college football [21] is a network with 115 nodes and 616 edges. The nodes in the network represent the football teams, and an edge between two nodes represents a game between the two teams. American political books [22, 23] is a social network about American political books. Each node in the network represents a book. An edge between two books indicates that they are often purchased together, and the network has three communities, as shown in Table 1.Table 1
Real networks.
NetworkNo. of nodesNo. of edgesNo. of communitiesKarate34782Dolphin621592Football11561312Political books1054413Amazon33486392587275149DBLP317080104986613477YouTube1134890298762416386Amazon is the network of the products sold on Amazon.com, the nodes in the network refer to products, and an edge between two nodes indicates that they are often purchased together. The network has 334,863 nodes and 925,872 edges. DBLP is a coauthorship network in which the nodes in the network refer to authors, and an edge between two authors indicates that they have published at least one paper together. Last, YouTube is an online social network. The Amazon dataset, DBLP dataset, and YouTube dataset were all provided by Stanford University SNAP (https://snap.stanford.edu/data/index.html#onlinecoms).


### 3.2. Evaluation Metric

We compared BComd with other algorithms using the following two evaluation metrics:Given a networkG = (V, E), let T be the set of real communities and D be the set of communities detected by the community-detection algorithm. Each real community Ti∈T (or each detected community Di∈D) is a set of member nodes. The average F1 parametric is a popular metric for evaluating the similarity between two sets, and when applied to community detection, it can be formed as follows [24]:(12)F1T,D=121T∑Ti∈TFTi,D+1D∑Dj∈DFDj,T,where(13)FTi,D=maxDj∈DF1Ti,Dj.F1 Ti,Dj is the harmonic mean of precision and recall, and formula FDi,T can be expressed in the same way.Normalized mutual information (NMI) [15] is an important evaluation metric for community detection that can measure how similar the community-segmentation results of the algorithm are to the real results. Assume that vectors X and Y denote two specific segmentation results of the network, where the ith bit of each vector indicates the class to which the ith point belongs. The larger the mutual information of X and Y, the more the information that can be provided to the other, and the more similar they are:(14)IX,Y=HX−HX|Y=∑y∈Y∑x∈Xpx,ylogpx,ypxpy,where px,y denotes the joint-distribution probability of X and Y. Adjusting the mutual information to a scale between zero and one is called standardized mutual information, and the expression is as follows:(15)UX,Y=2IX,YHX+HY.NMI ranges from zero to one, and the larger the value, the better the algorithm performance.


## 3.1. Dataset

The Karate Club [19] is a social network composed of 34 nodes and 78 edges. Each node represents a member of the club, and an edge indicates that two members are friends. The bottlenose dolphin community (Dolphin) [20] is a social network of frequent interactions between 62 dolphins living in New Zealand. The nodes in the network represent dolphins, and an edge represents the corresponding frequent contacts of dolphins. There are two communities in the network. American college football [21] is a network with 115 nodes and 616 edges. The nodes in the network represent the football teams, and an edge between two nodes represents a game between the two teams. American political books [22, 23] is a social network about American political books. Each node in the network represents a book. An edge between two books indicates that they are often purchased together, and the network has three communities, as shown in Table 1.Table 1
Real networks.
NetworkNo. of nodesNo. of edgesNo. of communitiesKarate34782Dolphin621592Football11561312Political books1054413Amazon33486392587275149DBLP317080104986613477YouTube1134890298762416386Amazon is the network of the products sold on Amazon.com, the nodes in the network refer to products, and an edge between two nodes indicates that they are often purchased together. The network has 334,863 nodes and 925,872 edges. DBLP is a coauthorship network in which the nodes in the network refer to authors, and an edge between two authors indicates that they have published at least one paper together. Last, YouTube is an online social network. The Amazon dataset, DBLP dataset, and YouTube dataset were all provided by Stanford University SNAP (https://snap.stanford.edu/data/index.html#onlinecoms).


## 3.2. Evaluation Metric

We compared BComd with other algorithms using the following two evaluation metrics:Given a networkG = (V, E), let T be the set of real communities and D be the set of communities detected by the community-detection algorithm. Each real community Ti∈T (or each detected community Di∈D) is a set of member nodes. The average F1 parametric is a popular metric for evaluating the similarity between two sets, and when applied to community detection, it can be formed as follows [24]:(12)F1T,D=121T∑Ti∈TFTi,D+1D∑Dj∈DFDj,T,where(13)FTi,D=maxDj∈DF1Ti,Dj.F1 Ti,Dj is the harmonic mean of precision and recall, and formula FDi,T can be expressed in the same way.Normalized mutual information (NMI) [15] is an important evaluation metric for community detection that can measure how similar the community-segmentation results of the algorithm are to the real results. Assume that vectors X and Y denote two specific segmentation results of the network, where the ith bit of each vector indicates the class to which the ith point belongs. The larger the mutual information of X and Y, the more the information that can be provided to the other, and the more similar they are:(14)IX,Y=HX−HX|Y=∑y∈Y∑x∈Xpx,ylogpx,ypxpy,where px,y denotes the joint-distribution probability of X and Y. Adjusting the mutual information to a scale between zero and one is called standardized mutual information, and the expression is as follows:(15)UX,Y=2IX,YHX+HY.NMI ranges from zero to one, and the larger the value, the better the algorithm performance.


## 4. Experimental Results and Analysis

### 4.1. Experimental Results

In this study, we compared the proposed algorithm with the FG algorithm [25], GN algorithm [26], k-means algorithm [11], sparse linear-coding method (SLC) [27], equation (13), algorithm [28], and MIGA algorithm [29]. The results are given in Table 2. The BComd algorithm was compared with each reference algorithm using the F1 and NMI metrics. The results showed that the proposed method performed well, especially on the first two datasets for which the community structure was clear. For both the Karate Club and Dolphin networks, the values of F1 and NMI obtained by our method were 1.0, which means that the community structure of both networks detected by our method was consistent with the actual structure. The MIGA algorithm achieved the best NMI and F1 values for the Football dataset. For the American political books, the proposed method obtained the maximum value of NMI, whereas the best value of F1 was obtained by equation (20) algorithm. In summary, the BComd algorithm performed well on networks with clear community structures, but it did not work sufficiently well on small networks with complex community structures.Table 2
Experimental results of the community-discovery algorithms on small graphs (F1 and NMI).
DatasetCriterionFGGNk-meansEquation (20)SLCMIGABComdKarateF10.9710.9700.8791.00.9711.01.0NMI0.8370.8360.6661.00.8371.01.0DolphinF10.9370.9800.7700.9610.9800.9651.0NMI0.6520.8900.4170.8140.8900.8141.0FootballF10.5280.8020.7300.8590.8460.8640.842NMI0.6970.8780.8220.8650.7930.9160.847Political booksF10.7250.8080.6550.8290.7980.7970.782NMI0.5680.5680.4540.5970.5840.5850.637The bold values show best performance.In terms of the effect of the large graph, we compared the results of the proposed algorithm with the LPA algorithm [30], WLPA algorithm [24], Louvain algorithm [31], and WLouvain algorithm [24]. The measurement method was to run each community-detection algorithm on the Amazon dataset, DBLP dataset, and YouTube dataset. Then we compared the running results (all communities) with the top 5000 real communities on each network. We observed that BComd had the best performance. The proposed algorithm obtained the highest F1 and NMI values in all three datasets, especially on the YouTube network. It was significantly better than the other algorithms. Therefore, the BComd algorithm was superior to the other algorithms on large networks, as shown in Table 3.Table 3
Experimental results of the community-discovery algorithms on large graphs (F1 and NMI).
DatasetCriterionLPAWLPALouvainWLouvainBComdAmazonF10.450.450.4630.4590.566NMI0.4250.4130.430.4240.535DBLPF10.390.390.390.3910.493NMI0.2490.2550.2490.2680.370YouTubeF10.0430.1440.0430.1610.440NMI0.0160.0320.0160.0510.234The bold values show best performance.


### 4.2. Proof of Effectiveness of Eliminating Overlaps

The idea of the BComd algorithm was to detect overlapping nodes between communities and delete these nodes and their edges from the network to obtain a clearer community-structure subnet. The subnetworks were then clustered to obtain primary-community divisions, and these primary communities were usually the core of the community they belonged to. Each primary community was compressed into one node, and then the new network was clustered using the Louvain algorithm to improve the clustering accuracy.This section demonstrates experimentally that a more explicit community structure and better community-detection results could be obtained by eliminating overlaps. The idea of the proof is as follows:(1)
Use the BComd algorithm introduced in Section2.2.2 including Step 2 of the algorithm, which eliminates the overlaps and then performs community detection to get result ①(2)
Use the BComd algorithm introduced in Section 3.3 while omitting Step 2 to perform the community-detection directly without eliminating the overlaps to obtain result ②(3)
Compare results ① and ②. If the results of ① are better than ② on multiple networks, eliminating the overlaps can lead to a clearer community structure and better community detectionThis section was run on three large networks: the Amazon, DBLP, and YouTube datasets. The community-detection results were compared with ground-truth communities to get their F1 and NMI values. The experimental results obtained are shown in Table4. Table 4 shows that the effect of ① was better on the three networks. Therefore, the proposed method effectively found the overlaps between communities. It also demonstrated that eliminating overlaps can yield a clearer community structure and better community-detection results.Table 4
Experimental results demonstrating the effectiveness of eliminating overlaps (F1 and NMI).
DatasetCriterion①②AmazonF10.5880.481NMI0.3630.234DBLPF10.4900.329NMI0.2720.142YouTubeF10.4910.117NMI0.1570.018The bold values show best performance.


### 4.3. Experimental Result Analysis

From the experimental results, we found that the algorithm proposed in this paper performed well in large-scale networks. We believe there were two reasons for this. First, the descending balance factor we designed selected more reasonable nodes as the seed nodes for community expansion. These seed nodes that satisfied both high node density and high centrality were more likely to be the central or edge nodes of the community. Such initial nodes reduced the negative impact caused by the uncertainty of the community to which the seed node belonged, thereby improving the accuracy of the algorithm. As can be seen from Figure5, nodes with strong ties to more than one community had smaller Bvi values, whereas those at the center of the community had larger Bvi values. This further demonstrated that the balance factor described in this paper can find core nodes in a network.Figure 5
The balance factor of each node in the Karate Club and Dolphin databases.Additionally, we used degree centrality, node density, and adaptability to find overlaps between communities, and we removed these overlaps from the network to obtain a subnet with a clear community structure. Our experiments found that the subnet had many groups. In the initial community delineation obtained by clustering the subnet, many communities had an adaptability of one, indicating that the subnet had a clear community structure with strong connections within communities and sparse connections between communities. It also showed that the overlaps we were looking for were correct. After clustering the subnets to obtain the preliminary community structure, we compressed each preliminary community into a node. We then used the Louvain algorithm to cluster the new network, thereby improving the accuracy of community detection. As demonstrated in Section4.3, eliminating overlapping parts could yield subnets with clearer community structure and better community-detection results. However, our algorithm was less effective in small-scale networks because the balanced distribution of nodes in a small graph did not satisfy a parabolic distribution, so removing any overlapping nodes from the small graph made it impossible to obtain subnets with a clear community structure. This led to a decrease in clustering accuracy. For networks with clear community structure, such as the Karate Club and Dolphin networks, our algorithm achieved 100% accuracy (see Figure 5). When the community structure was complex, however, it was impossible to obtain subgraphs with clear community structure by removing nodes, such as Football and American political books. Figure 6 shows that the clustering accuracy of the method was low.Figure 6
The balance distribution of nodes in a small graph.


### 4.4. Running-Time Analysis

Table5 shows the average running time spent by each method on the three large networks with the units in seconds. The LPA, Louvain, and BComd algorithms were all written in Python. All experiments were conducted on a PC with a 2.70 GHz Intel Core processor and 4 GB RAM. The running times are shown in Table 5. We identified a difference in running time between the BComd algorithm and Louvain algorithm at the stages of Bvi calculation and clustering subnets. The proposed algorithm was slower than Louvain's algorithm on the Amazon and DBLP datasets but was faster on the YouTube dataset.Table 5
Running time (unit: s).
DatasetLPA (s)Louvain (s)BComd (s)Amazon425.072153.292867.161DBLP428.598557.458792.686YouTube523.30419057.2855432.796The bold values show best performance.If the size of the subnet was the same as the original network, the algorithm in this paper ran longer than the Louvain algorithm because the BComd algorithm needed to calculate theBvi value for each node, which took more time. However, when the algorithm deleted many nodes and edges, the generated subnet was much smaller than the original network. Clustering such subnets reduced the running time. After the initial community division was obtained by subnet clustering, each community was compressed into one node. A community that contained multiple edges and multiple nodes was compressed into one node. The previously deleted nodes and edges were added back. The new network was much smaller than the original network, and the running time was further reduced for the new network clustering. If the deleted nodes were a fixed percentage of the total network nodes, then the number of deleted nodes and edges was greater for a larger network, and the advantage of running the subnet was greater. However, the ratio of deleted nodes to the total nodes of the network was not a fixed value; rather, it was related to the network's structure and the size of the overlap we detected. Nevertheless, we still found that the larger the network, the greater the advantage of running the subnet, and when such an advantage was large enough to offset the extra time spent on the Bvi computation, the BComd algorithm was faster than the Louvain algorithm. Although it ran slower than the Louvain algorithm on the Amazon network and BDLP network, our algorithm also ran faster than the Louvain algorithm on the YouTube dataset.


## 4.1. Experimental Results

In this study, we compared the proposed algorithm with the FG algorithm [25], GN algorithm [26], k-means algorithm [11], sparse linear-coding method (SLC) [27], equation (13), algorithm [28], and MIGA algorithm [29]. The results are given in Table 2. The BComd algorithm was compared with each reference algorithm using the F1 and NMI metrics. The results showed that the proposed method performed well, especially on the first two datasets for which the community structure was clear. For both the Karate Club and Dolphin networks, the values of F1 and NMI obtained by our method were 1.0, which means that the community structure of both networks detected by our method was consistent with the actual structure. The MIGA algorithm achieved the best NMI and F1 values for the Football dataset. For the American political books, the proposed method obtained the maximum value of NMI, whereas the best value of F1 was obtained by equation (20) algorithm. In summary, the BComd algorithm performed well on networks with clear community structures, but it did not work sufficiently well on small networks with complex community structures.Table 2
Experimental results of the community-discovery algorithms on small graphs (F1 and NMI).
DatasetCriterionFGGNk-meansEquation (20)SLCMIGABComdKarateF10.9710.9700.8791.00.9711.01.0NMI0.8370.8360.6661.00.8371.01.0DolphinF10.9370.9800.7700.9610.9800.9651.0NMI0.6520.8900.4170.8140.8900.8141.0FootballF10.5280.8020.7300.8590.8460.8640.842NMI0.6970.8780.8220.8650.7930.9160.847Political booksF10.7250.8080.6550.8290.7980.7970.782NMI0.5680.5680.4540.5970.5840.5850.637The bold values show best performance.In terms of the effect of the large graph, we compared the results of the proposed algorithm with the LPA algorithm [30], WLPA algorithm [24], Louvain algorithm [31], and WLouvain algorithm [24]. The measurement method was to run each community-detection algorithm on the Amazon dataset, DBLP dataset, and YouTube dataset. Then we compared the running results (all communities) with the top 5000 real communities on each network. We observed that BComd had the best performance. The proposed algorithm obtained the highest F1 and NMI values in all three datasets, especially on the YouTube network. It was significantly better than the other algorithms. Therefore, the BComd algorithm was superior to the other algorithms on large networks, as shown in Table 3.Table 3
Experimental results of the community-discovery algorithms on large graphs (F1 and NMI).
DatasetCriterionLPAWLPALouvainWLouvainBComdAmazonF10.450.450.4630.4590.566NMI0.4250.4130.430.4240.535DBLPF10.390.390.390.3910.493NMI0.2490.2550.2490.2680.370YouTubeF10.0430.1440.0430.1610.440NMI0.0160.0320.0160.0510.234The bold values show best performance.


## 4.2. Proof of Effectiveness of Eliminating Overlaps

The idea of the BComd algorithm was to detect overlapping nodes between communities and delete these nodes and their edges from the network to obtain a clearer community-structure subnet. The subnetworks were then clustered to obtain primary-community divisions, and these primary communities were usually the core of the community they belonged to. Each primary community was compressed into one node, and then the new network was clustered using the Louvain algorithm to improve the clustering accuracy.This section demonstrates experimentally that a more explicit community structure and better community-detection results could be obtained by eliminating overlaps. The idea of the proof is as follows:(1)
Use the BComd algorithm introduced in Section2.2.2 including Step 2 of the algorithm, which eliminates the overlaps and then performs community detection to get result ①(2)
Use the BComd algorithm introduced in Section 3.3 while omitting Step 2 to perform the community-detection directly without eliminating the overlaps to obtain result ②(3)
Compare results ① and ②. If the results of ① are better than ② on multiple networks, eliminating the overlaps can lead to a clearer community structure and better community detectionThis section was run on three large networks: the Amazon, DBLP, and YouTube datasets. The community-detection results were compared with ground-truth communities to get their F1 and NMI values. The experimental results obtained are shown in Table4. Table 4 shows that the effect of ① was better on the three networks. Therefore, the proposed method effectively found the overlaps between communities. It also demonstrated that eliminating overlaps can yield a clearer community structure and better community-detection results.Table 4
Experimental results demonstrating the effectiveness of eliminating overlaps (F1 and NMI).
DatasetCriterion①②AmazonF10.5880.481NMI0.3630.234DBLPF10.4900.329NMI0.2720.142YouTubeF10.4910.117NMI0.1570.018The bold values show best performance.


## 4.3. Experimental Result Analysis

From the experimental results, we found that the algorithm proposed in this paper performed well in large-scale networks. We believe there were two reasons for this. First, the descending balance factor we designed selected more reasonable nodes as the seed nodes for community expansion. These seed nodes that satisfied both high node density and high centrality were more likely to be the central or edge nodes of the community. Such initial nodes reduced the negative impact caused by the uncertainty of the community to which the seed node belonged, thereby improving the accuracy of the algorithm. As can be seen from Figure5, nodes with strong ties to more than one community had smaller Bvi values, whereas those at the center of the community had larger Bvi values. This further demonstrated that the balance factor described in this paper can find core nodes in a network.Figure 5
The balance factor of each node in the Karate Club and Dolphin databases.Additionally, we used degree centrality, node density, and adaptability to find overlaps between communities, and we removed these overlaps from the network to obtain a subnet with a clear community structure. Our experiments found that the subnet had many groups. In the initial community delineation obtained by clustering the subnet, many communities had an adaptability of one, indicating that the subnet had a clear community structure with strong connections within communities and sparse connections between communities. It also showed that the overlaps we were looking for were correct. After clustering the subnets to obtain the preliminary community structure, we compressed each preliminary community into a node. We then used the Louvain algorithm to cluster the new network, thereby improving the accuracy of community detection. As demonstrated in Section4.3, eliminating overlapping parts could yield subnets with clearer community structure and better community-detection results. However, our algorithm was less effective in small-scale networks because the balanced distribution of nodes in a small graph did not satisfy a parabolic distribution, so removing any overlapping nodes from the small graph made it impossible to obtain subnets with a clear community structure. This led to a decrease in clustering accuracy. For networks with clear community structure, such as the Karate Club and Dolphin networks, our algorithm achieved 100% accuracy (see Figure 5). When the community structure was complex, however, it was impossible to obtain subgraphs with clear community structure by removing nodes, such as Football and American political books. Figure 6 shows that the clustering accuracy of the method was low.Figure 6
The balance distribution of nodes in a small graph.


## 4.4. Running-Time Analysis

Table5 shows the average running time spent by each method on the three large networks with the units in seconds. The LPA, Louvain, and BComd algorithms were all written in Python. All experiments were conducted on a PC with a 2.70 GHz Intel Core processor and 4 GB RAM. The running times are shown in Table 5. We identified a difference in running time between the BComd algorithm and Louvain algorithm at the stages of Bvi calculation and clustering subnets. The proposed algorithm was slower than Louvain's algorithm on the Amazon and DBLP datasets but was faster on the YouTube dataset.Table 5
Running time (unit: s).
DatasetLPA (s)Louvain (s)BComd (s)Amazon425.072153.292867.161DBLP428.598557.458792.686YouTube523.30419057.2855432.796The bold values show best performance.If the size of the subnet was the same as the original network, the algorithm in this paper ran longer than the Louvain algorithm because the BComd algorithm needed to calculate theBvi value for each node, which took more time. However, when the algorithm deleted many nodes and edges, the generated subnet was much smaller than the original network. Clustering such subnets reduced the running time. After the initial community division was obtained by subnet clustering, each community was compressed into one node. A community that contained multiple edges and multiple nodes was compressed into one node. The previously deleted nodes and edges were added back. The new network was much smaller than the original network, and the running time was further reduced for the new network clustering. If the deleted nodes were a fixed percentage of the total network nodes, then the number of deleted nodes and edges was greater for a larger network, and the advantage of running the subnet was greater. However, the ratio of deleted nodes to the total nodes of the network was not a fixed value; rather, it was related to the network's structure and the size of the overlap we detected. Nevertheless, we still found that the larger the network, the greater the advantage of running the subnet, and when such an advantage was large enough to offset the extra time spent on the Bvi computation, the BComd algorithm was faster than the Louvain algorithm. Although it ran slower than the Louvain algorithm on the Amazon network and BDLP network, our algorithm also ran faster than the Louvain algorithm on the YouTube dataset.


## 5. Conclusion

We proposed a balanced factor measure based on node-degree centrality and node density, representing the community belongingness of nodes. Accordingly, we proposed a balanced factor-based algorithm for social network community detection. The algorithm could select more reasonable nodes as seed nodes for community expansion, effectively determining the overlapping nodes, and also deleted overlapping nodes in the initial community division to obtain better community division results. The final experiments also verified the effectiveness of the proposed method. The next step in our research should focus on the practical optimization of the balance factor-based community-detection algorithm applied to industrial super-large datasets. The computational complexity of the balance factor of the algorithm was low, and the main complexity was reflected in the clustering process. Therefore, the parallel optimization of the clustering process should be the focus of future research.



---

*Source: 7518422-2022-02-08.xml*