# A Node Similarity and Community Link Strength-Based Community Discovery Algorithm

Authors: Haijuan Yang; Jianjun Cheng; Zeyi Yang; Handong Zhang; Wenbo Zhang; Ke Yang; Xiaoyun Chen
Journal: Complexity
 (2021)

---

## Abstract

Community structure is one of the common characteristics of complex networks. In the practical work, we have noted that every node and its most similar node tend to be assigned to the same community and that two communities are often merged together if there exist relatively more edges between them. Inspired by these observations, we present a community-detection method namedNSCLS in this paper. Firstly, we calculate the similarities between any node and its first- and second-order neighbors in a novel way and then extract the initial communities from the network by allocating every node and its most similar node to the same community. In this procedure, some nodes located at the community boundaries might be classified in the incorrect communities. To make a redemption, we adjust their community affiliations by reclassifying each of them into the community in which most of its neighbors have been. After that, there might exist relatively larger number of edges between some communities. Therefore, we consider to merge such communities to improve the quality of the final community structure further. To this end, we calculate the link strength between communities and merge some densely connected communities based on this index. We evaluate NSCLS on both some synthetic networks and some real-world networks and show that it can detect high-quality community structures from various networks, and its results are much better than the counterparts of comparison algorithms.


---

## Body

## 1. Introduction

Complex networks are widely used to represent systems in the real world, and they often exhibit a structural characteristic of community structure, where nodes can be divided into groups naturally with much denser connections within groups than between groups. The community structure is a meaningful property of networks which can reflect the interactions of system components at the mesoscale level. For instance, communities can be groups of scientific papers in citation networks [1], sharing same topics, and this characteristic can help to discover some newborn or interdisciplinary studies. Communities in metabolic networks or protein-protein interaction networks [2] can be used to identify pathways or complexes. In social networks, communities often correspond to real social groupings having the same interests or professional occupations [2–4]. Therefore, detecting communities can shed light on exploring and utilizing the relationships between the structural characteristics and the functional modules.Community detection becomes a hot spot in complex network studies in recent years. The detected communities can be nonoverlapped or overlapped, i.e., one node can affiliate to one community or more than one communities. We concern the problem of detecting nonoverlapping communities here. A large number of approaches [5–9] have been proposed. We also devise a novel method to address the problem in this paper, which is inspired by the phenomena observed in our practical work that each node, and its most similar node tend to be assigned to the same community, and two communities with many edges between them tend to be merged together to form a larger community. We call the proposed method NSCLS (acronym for Node Similarity and Community Link Strength), in which we firstly calculate the similarity between any node and its first- and second-order neighbors in a novel way, then classify the node and its most similar node into the same community. In this way, we obtain a series of initial communities. For some nodes located at the community boundaries, their current community affiliations might be irrational. To make a redemption, we reclassify each of them to the community in which most of its neighbors have been. After that, for some pairs of communities, the intercommunity edges might be more than the intracommunity ones. Thus, we consider to merge such communities into larger ones. To this end, we define and calculate an index, link strength, for two adjacent communities, and merge some densely connected communities based on the value of that index. We also conduct extensive experiments both on some synthetic networks and on some real-world networks to testify the effectiveness of NSCLS and compare the results with those of six popular community-detection algorithms. The experiments show that the results detected by NSCLS are much better than the counterparts of comparison algorithms.The major advantages and contributions of this paper are summarized as follows:We propose a novel similarity calculation approach, which needs only to consider the node’s first- and second-order neighbors; therefore, it is quite efficientThe nodes assigned to the same community are highly similar to one another, ensuring the cohesiveness and the purity of the communityAn index,link strength between communities, is proposed as a measure to merge some tightly connected initial communities, and the quality of the resultant community structure is much higher than those of the comparison algorithmsIn the rest of the paper, Section2 reviews some literature about community detection. Section 3 elaborates the details of the proposed algorithm. The experimental results and analysis are presented in Section 4, and the paper is ended with a conclusion in Section 5.


## 2. Related Work

As mentioned above, many methods have been proposed for discovering communities in networks. Those methods explore community structures in the networks from different perspectives. The most widely used ones are modularity dependent methods. Girvan and Newman proposed GN [3, 4] method in 2002, which divides the network into some groups iteratively by deleting the edge with the largest betweenness from the network. For measuring the goodness of the community structure, they proposed a measure metric, modularity (denoted as Q), at the same time. The effective value of modularity falls in the range 0,1, with larger value indicating better result. Since then, the modularity has been a de facto index for measuring the quality of the community structure. Many subsequently methods [2, 10–13] detect communities from networks via attempting to acquire the optimal modularity.Some methods, such as LPA [14] and its variations [15–17], mine communities in networks through utilizing properties of community. LPA updates the label of each node to be the one occurred most frequently in its neighbors, and this is equivalent to classify the node into the community in which most of its neighbors belong. The advantages of LPA are its simplicity and its efficiency; hence, many variations have been proposed afterwards. LabelRank [15] uses four matrix operators (Propagation + Inflation + Cutoff + Conditional update) to modify the label propagation criterion and gets a stable version of LPA. SkipLPA [16] only assigns the initial unique labels to certain nodes; the remaining nodes obtain initial labels from their neighbors and do not participate in the label propagation in the subsequent steps. Thus, its performance improves significantly without compromising the quality of the extracted communities. MemLPA [17] implements a so-called ‘memory mechanism’ for each node that allows it to maintain a list of labels with its associated score and to make utilization of this information in propagating the labels.Another kind of method which made use of community properties is random-walk-based algorithms. Owing to the characteristic of community with dense intracommunity edges and sparse intercommunity connections, a walker tends to stay in a community in a random walk, rather than transitions to another one. Therefore, the nodes visited during a short walk are highly likely to belong to the same community. Infomap [18] detects communities by encoding the path visited during the random walk with the minimal length. Walktrap [19] exploits random walk to calculate the node similarity and community similarity and then obtains the community structure by repeatedly merging the pairs of most similar communities. PPC [20] exploits many limited-length random walks to obtain a list of nodes sorted by their cluster-similarity to the starting node and then finds a suitable cutting point in the list under the guidance of the modularity to partition the network into two subnetworks. This process is repeated until no further partitioning can obtain a better modularity, and a hierarchy of communities is made. RWA [21] exploits random walks to compute the probability that a node belongs to a community and then joins the node in the community with the largest probability correspondingly.In addition to the typical dynamic procedure of random walk, other network-dynamics-based methods are also used to extract communities in networks. Attractor [22], for example, employs the distance dynamics to reveal communities in networks. The network nodes interact with one another, and the interactions might change the distances among nodes, while the distance changes can impact the interaction in reverse. Such interplays render nodes with close relationships aggregate together, while nodes in different communities depart from each other, thus forming communities naturally. P-attractor [23] improves the distance dynamics model to simulate the distance evolution among the neighborhood subnetworks. Since the number of such subnetworks are much smaller than that of nodes in the network, this algorithm can be applied on large networks.Some methods detect communities based on the concept of “density”. SCAN [24], for example, defines the concepts “core” nodes, “structure reachability” and “structure connectivity” based on the density of nodes, and the distributions of node connections and then extracts communities by identifying groups of structurally connected nodes. IsoFdp [25] maps the network nodes as points in a low-dimensional manifold expecting that the point distribution in the low-dimensional space can keep the closeness of the original nodes and then obtains the final results by employing a density peak clustering algorithm [26]. LCCD [27] identifies the structural centers using the strategy brought forth in the density peak clustering algorithm [26] first and then expands each center to be a community with a local search.To some extent, the essence of detecting communities is equivalent to clustering nodes in networks. The similarities between data points play an important role in many algorithms’ clustering procedure. Similarly, the similarities between nodes are also vital for many community-detection algorithms. Various kinds of ways are used to calculate the similarities between nodes. We have mentioned previously that Walktrap [19] performs random walks to calculate the similarities between nodes, which represent actually the probabilities to go from one node to another, then defines the distances between nodes and between communities using the calculated similarities, and extracts the communities by repeatedly merging the most similar communities. Sim_closure [28] defines the similarity between two nodes as the sum of the reciprocal of their common neighbors’ degrees if they are connected by an edge or 0 otherwise and then gets the communities by identifying the similarity closure of nodes. Similarity_CNM [29] takes the Jaccard index as the similarity between nodes to infer a “virtual network” from the original network and then applies the optimized version of CNM [10] to extract communities from the inferred network. ASOCCA [30] calculates the similarity between two adjacent nodes as the sum of their common neighbors’ local clustering coefficient, then obtains the initial communities by combining the pairs of nodes with the highest similarities, and finally obtains the result by optimizing the initial communities using a merging strategy. APAS [31] uses two kinds of matrices, “Diffusion Kernel” matrix [32] and “Regular Equivalence” matrix [33], as the similarity matrices, respectively, and then applies the affinity propagation clustering algorithm [34] to extract communities iteratively, and in each iteration, the similarity matrix is updated adaptively.To some extent, the proposed method, NSCLS, is also a similarity-based community detection method, which calculates the similarities between any node and its first- and second-order neighbors in a novel way, then attains the initial communities by generally allocating each node and its most similar node to the same communities, next adjusts the community affiliations of some boundary nodes, and finally acquires the resultant community structure by merging some initial communities according to a devised index,link strength between communities. The details will be elaborated in Section 3.


## 3. The Proposed Method: NSCLS

Just as aforementioned, the proposed method, NSCLS, obtains the initial communities based on the node similarities and acquires the resultant community structure by merging some of the initial communities. Clearly, the node similarity and the link strength between communities are the key components for the method. Therefore, we first explain how to calculate them and then present the process of NSCLS.In this paper, each network involved is essentially an undirected and unweighted graph, which is represented asGV,E, where V and E are the sets of nodes and edges, respectively.


### 3.1. The Similarity between Nodes and the Link Strength between Communities

#### 3.1.1. The Similarity between Nodes

There are many approaches to calculate similarities between nodes. We are aware of at least four previously proposed ways of doing this which are widely employed in community detection.Jaccard similarity:(1)simJaccardu,v=Γu∩ΓvΓu∪Γv.Cosine similarity:(2)simcosineu,v=Γu∩ΓvΓu×Γv.Hub promoted index:(3)simhpiu,v=Γu∩ΓvminΓu,Γv.Hub depressed index:(4)simhdiu,v=Γu∩ΓvmaxΓu,Γv,where Γx=w|w∈V,x,w∈E is the set of neighbor nodes of x.However, how good a metric of the similarity between two nodes remains still open, there is no unique approach which can denote similarity between two nodes appropriately in all cases, and each metric can only measure partly common characteristics between two nodes. For instance, all the above indexes are based on the number of common neighbors between two nodes; the idea of them is intuitive that the more common neighbors exist between two nodes, the more similar they are. However, these metrics have at least one disadvantage: they cannot differentiate the tightness relation between two nodes whether they are connected directly or indirectly. This might lead to an inconsistency with the fact and then further result in inaccurate communities.Taking the Jaccard index as an example, Figure1 illustrates two scenarios in which Jaccard similarity obtains the problematic results. Both of them show that two substructures widely existed in networks, in which v1 and v2 connect to the rest of the network correspondingly with almost the same style as v3 and v4, respectively, except that v1 and v2 are directly connected, whereas v3 connects to v4 indirectly. However, simJaccardv1,v2<simJaccardv3,v4 in both cases. That is to say, the existence of an edge contrarily decreases the similarity between the two end nodes of the edge. In other words, the indirectly connected nodes are closer than the directly connected ones when measured using such similarity index, which conflicts with the general intuition.Figure 1
Two scenarios which generic common neighbor-based similarity might lead to problematic result.
(a)(b)To address this situation, we devise a novel approach for calculating the similarity between nodesu and v:(5)simu,v=au,v+Γu∩Γv|Γu|+Γv/2,where au,v is the element of the adjacency matrix A, i.e., au,v=1 if u,v∈E, or 0 otherwise. Clearly, simv1,v2≥simv3,v4 in both of the two cases presented in Figure 1, which coincides with the intuition.


#### 3.1.2. The Link Strength between Communities

In the proposed method, we need to merge some initial communities to improve the quality of the resultant communities. To this end, we devise an index,link strength between communities, to determine which pair of communities should be joined together. It is naturally to consider using the number of intercommunity edges as a criterion to merge communities, but this strategy inclines to select larger communities to merge and might result in some giant communities.After investigating the relationships between adjacent communities, we propose a relative index. We firstly define the density of edges connecting from the communityCi to Cj:(6)dCi,Cj=u,v|u∈Ci,v∈Cj,u,v∈ECi.It is an asymmetric index, which measures fairly for a community of the average number of edges connecting outside of it to the other one, regardless of the community size.Based on the concept of density of intercommunity edges, thelink strength between the communities Ci and Cj is defined as(7)LSCi,Cj=dCi,Cj×dCj,CiECiin×ECjin×NCi,where ECiin and ECjin represent the sets of edges inside of the communities Ci and Cj, respectively, and NCi stands for the set of communities adjacent to Ci.The link strength is a relative index indicating the closeness degree for two adjacent communities. Its value falls in0,1; the larger value reflects more edges existing between the two communities. Hence, they are more inclined to be merged.


### 3.2. Obtaining the Initial Communities

This is the first stage of the proposed method, and its logic is described as the pseudocode listed in Algorithm1.Algorithm 1: Get_similarity_based_communities (G).
Input:GV,E, the network; k, the community-size threshold.Output:CS, the initial community structure.(1)
Calculate the similarities between any node and its first- and second-order neighbors according to equation (5):forv∈VdoΓv←x|x∈V,v,x∈EΓ2v←y|y∈V,x∈Γv,x,y∈Eforu∈Γv∪Γ2vdosimv,u←au,v+Γu∩Γv/|Γu|+Γv/2(2)
Mark every node as unclassified and initialize variablesCS and U to record the community structure and the unvisited nodes, respectively:foreachv∈Vdov.label←0CS←ϕ;U←Vcom_id←0(3)
Select nodev with the largest degree from U, find its most similar node, and determine their community affiliations:v←argmaxu|Γu‖u∈UU←U−vu←argmaxxsimv,x|x∈Γv∪Γ2vifv.label=0then/∗v is not classified yet ∗/ifu.label≠0thenv.label←u.labeli←u.labelCi←Ci∪velse/∗create a new community for v and u∗/com_id←com_id+1v.label←com_id;u.label←com_idCcom_id←v,uCS←CS∪Ccom_idelse/∗v has already been in a community ∗/i←v.label;j←u.labelifCi<kthenifu.label≠0then/∗ merge two communities ∗/forw∈Cidow.label←u.labelCj←Cj∪CiCS←CS−Cielse/∗u has not been classified yet ∗/u.label←v.labelCi←Ci∪u(4)
Repeat step 3 untilU=ϕ.(5)
returnCSIn this algorithm, we calculate the similarity between every node and its first- and second-order neighbors first and then detect communities in the network by utilizing the calculated similarities. To facilitate the implementation, we attach a nonnegative-valued attribute ‘label’ to every node, which indicates the node’s community affiliation if its value is positive, or the node being still unclassified otherwise. Then, we select one node from the network in the descending order of the degree, denote it as v, find its most similar node u in the network, and then determine their community affiliations by considering the combination of their current status accordingly in the following ways:(1)
v is not classified into any community yet, whereas u has definite community affiliation already: we insert node v into the community in which node u belongs.(2)
Bothv and u are still unclassified: we create a new community for them.(3)
Bothv and u have been allocated into some communities: we merge v’s community and u’s community if the former is smaller than a given threshold, k, or leave the two communities untouched otherwise. In this case, the node v has been previously passively absorbed in the community as the one most similar to some other node. If that community contains only a very small number of nodes, it is unlikely to be expanded in the succeeded iterations since the most similar nodes (such as u) of its members have been already in other communities. Therefore, it is unnecessary to keep such a small community in the result, and we merge v’s community into u’s community.(4)
v has already been a classified node, whereas u is still unclassified: we intend to insert u into v’s community; however, we need to ensure the closeness between u and the other nodes in v’s community. Here, we also limit the size of v’s community to be smaller than the threshold, k, i.e., if v’s community contains less than k nodes, we insert the node u into it.The above operations are repeated iteratively, until all the nodes are processed. Then, we obtain a series of initial communities.


### 3.3. Boundary Node Moving and Initial Community Merging

Algorithm1 constructs the initial community structure by allocating nodes and their most similar nodes to the same communities. However, we have found in practice that the quality of the structure is not as better as expected sometimes, even for some nodes, and their community affiliations are problematic. Figure 2 shows the result of running Algorithm 1 on an example network, in which the nodes plotted in different colors form different initial communities.Figure 2
The problem existed in the initial community structure.Algorithm1 identifies 4 communities from the network; most of the nodes’ community affiliations are appropriate. However, the belongingness of the nodes v9 and v11 is obviously problematic. The node v9 plays a hub role in the network, and it should be allocated to the node v1’s community according to the network topology, but now it is classified in the node v14’s community since v14 is its most similar node. For node v11, the case is more serious, it is unexpectedly allocated in node v16’s community for the same reason that v16 is its most similar node, but it does not have any edge connecting with other nodes in that community at all. Therefore, we need to adjust the community affiliations of those nodes. For simplicity, we move such nodes located at the community boundaries to the communities in which most of their respective neighbors belong.In addition, some of the initial communities might be too small due to the strategy used in Algorithm1. The nodes v and u form a community only containing themselves if they are mutual most similar nodes, and the aforementioned community-size restriction might result in some small-scaled communities as well. We have also found in practice that there might exist more edges between some initial communities than those inside the corresponding communities sometimes. Therefore, we consider to merge those pairs of communities to improve the resultant communities. To this end, we calculate the link strength between every pair of communities and merge those pairs whose link strength are larger than a threshold θ, which is initially calculated adaptively by setting it to be 100 times of the minimal link strength and then repeatedly being divided to be the half of its previous value, until its value is no longer larger than the maximal link strength. In the subsequent iterations, it is attenuated to be 90% of its previous value each time. This merging operation is repeated until the corresponding modularity cannot be improved anymore; then, we obtain the final community structure.The logic implementing the ideas described above is presented in Algorithm2, the steps and operations are very clear, and the modularity [4] used in this algorithm is defined for community structure CS=C1,C2,…,Ck:(8)Q=∑i=1keii−ai2,where eii is the diagonal element of a k×k matrix e, whose elements eij represent the ratio of edges located between the communities Ci and Cj, and ai=∑j=1keij is the ratio of edges associated with nodes in community Ci.Algorithm 2: Adjustment for boundary nodes’ community affiliations and merging of some initial communities.
Input:GV,E, the network; CSinit, the initial community structure.Output:CS, the final community structure.(1)
Adjust the community affiliations of boundary nodes in the initial communities:forv∈VdoΓv←u|u∈V,v,u∈Et←argmaxjΓv∩CjCj∈CSinitift≠v.labelthens←v.labelv.label←tCt←Ct∪vCs←Cs−vifCs=ϕthenCSinit←CSinit−Cs(2)
Merge some communities according to thelink strength between communities:(2.1)
Calculate the modularityQ for CSinit according to equation (8):Q←∑i=1CSiniteii−ai2.(2.2)
CalculateLSCi,Cj for all community pairs Ci,Cj using equation (6) and (7).(2.3)
Determine the initial value of the threshold,θ, adaptively:LSmin←minLSCi,Cj|Ci∈CSinit,Cj∈CSinitLSmax←maxLSCi,Cj|Ci∈CSinit,Cj∈CSinitθ←LSmin×100whileθ>LSmaxdoθ←θ/2(2.4)
Merge all community pairsCi,Cj with LSCi,Cj>θ:foreachCi∈CSinit,Cj∈CSinitCi≠CjdoifLSCi,Cj>θthenCi←Ci∪CjCSinit←CSinit−Cj(2.5)
RecalculateLSCi,Cj and LSCj,Ci for ∀Cj∈CSinitCj≠Ci using equation (6) and (7).(2.6)
Reduce thresholdθ to 90% of its value: θ←θ×90%(2.7)
Calculate modularityQnew for community structure CSinit after merging:Qnew←∑i=1CSiniteii−ai2ifQnew>QthenCS←CSinit(2.8)
Repeat steps:ref stp:merge:merge.4 through:ref stp:merge:merge.7 until the conditionQnew>Q in step:ref stp:merge:merge.7 is not satisfied.(3)
returnCS


### 3.4. Time Complexity

The proposed method consists of Algorithms1 and 2; thus, its time consumption is the summation of the time cost of the two algorithms accordingly. For Algorithm 1, its time complexity is Od¯2V+V+VlogV for calculating the similarities between the nodes and their first- and second-order neighbors, marking the nodes as unclassified and determining the remaining nodes’ community affiliations (we use a max heap to select the node in the descending order of degree), where d¯ is the average degree of nodes in the network. This can be simplified to be OVlogV for sparse networks because d¯2≪logV or Od¯2∼OlogV at most in such networks.For Algorithm2, the step of adjusting the boundary nodes’ community affiliations consumes OV time, and the step of merging some initial communities needs OE+E+V for calculating the modularity and the link strength between all pairs of communities both in OE by traveling the edges in the network and merging communities whose link strength are larger than the threshold, θ, with at most OV alternations of the nodes’ community affiliations. Since the selection of the minimal and the maximal link strength can be implemented as a by-product along with the calculation of the link strength between communities, the time consumption of other operations can be ignored compared with those of the above steps. This time cost can be simplified to be OE or OV in sparse networks.In summary, the total time complexity of NSCLS in the worst case isOVlogV, which is much more efficient than many community detection algorithms.


## 3.1. The Similarity between Nodes and the Link Strength between Communities

### 3.1.1. The Similarity between Nodes

There are many approaches to calculate similarities between nodes. We are aware of at least four previously proposed ways of doing this which are widely employed in community detection.Jaccard similarity:(1)simJaccardu,v=Γu∩ΓvΓu∪Γv.Cosine similarity:(2)simcosineu,v=Γu∩ΓvΓu×Γv.Hub promoted index:(3)simhpiu,v=Γu∩ΓvminΓu,Γv.Hub depressed index:(4)simhdiu,v=Γu∩ΓvmaxΓu,Γv,where Γx=w|w∈V,x,w∈E is the set of neighbor nodes of x.However, how good a metric of the similarity between two nodes remains still open, there is no unique approach which can denote similarity between two nodes appropriately in all cases, and each metric can only measure partly common characteristics between two nodes. For instance, all the above indexes are based on the number of common neighbors between two nodes; the idea of them is intuitive that the more common neighbors exist between two nodes, the more similar they are. However, these metrics have at least one disadvantage: they cannot differentiate the tightness relation between two nodes whether they are connected directly or indirectly. This might lead to an inconsistency with the fact and then further result in inaccurate communities.Taking the Jaccard index as an example, Figure1 illustrates two scenarios in which Jaccard similarity obtains the problematic results. Both of them show that two substructures widely existed in networks, in which v1 and v2 connect to the rest of the network correspondingly with almost the same style as v3 and v4, respectively, except that v1 and v2 are directly connected, whereas v3 connects to v4 indirectly. However, simJaccardv1,v2<simJaccardv3,v4 in both cases. That is to say, the existence of an edge contrarily decreases the similarity between the two end nodes of the edge. In other words, the indirectly connected nodes are closer than the directly connected ones when measured using such similarity index, which conflicts with the general intuition.Figure 1
Two scenarios which generic common neighbor-based similarity might lead to problematic result.
(a)(b)To address this situation, we devise a novel approach for calculating the similarity between nodesu and v:(5)simu,v=au,v+Γu∩Γv|Γu|+Γv/2,where au,v is the element of the adjacency matrix A, i.e., au,v=1 if u,v∈E, or 0 otherwise. Clearly, simv1,v2≥simv3,v4 in both of the two cases presented in Figure 1, which coincides with the intuition.


### 3.1.2. The Link Strength between Communities

In the proposed method, we need to merge some initial communities to improve the quality of the resultant communities. To this end, we devise an index,link strength between communities, to determine which pair of communities should be joined together. It is naturally to consider using the number of intercommunity edges as a criterion to merge communities, but this strategy inclines to select larger communities to merge and might result in some giant communities.After investigating the relationships between adjacent communities, we propose a relative index. We firstly define the density of edges connecting from the communityCi to Cj:(6)dCi,Cj=u,v|u∈Ci,v∈Cj,u,v∈ECi.It is an asymmetric index, which measures fairly for a community of the average number of edges connecting outside of it to the other one, regardless of the community size.Based on the concept of density of intercommunity edges, thelink strength between the communities Ci and Cj is defined as(7)LSCi,Cj=dCi,Cj×dCj,CiECiin×ECjin×NCi,where ECiin and ECjin represent the sets of edges inside of the communities Ci and Cj, respectively, and NCi stands for the set of communities adjacent to Ci.The link strength is a relative index indicating the closeness degree for two adjacent communities. Its value falls in0,1; the larger value reflects more edges existing between the two communities. Hence, they are more inclined to be merged.


## 3.1.1. The Similarity between Nodes

There are many approaches to calculate similarities between nodes. We are aware of at least four previously proposed ways of doing this which are widely employed in community detection.Jaccard similarity:(1)simJaccardu,v=Γu∩ΓvΓu∪Γv.Cosine similarity:(2)simcosineu,v=Γu∩ΓvΓu×Γv.Hub promoted index:(3)simhpiu,v=Γu∩ΓvminΓu,Γv.Hub depressed index:(4)simhdiu,v=Γu∩ΓvmaxΓu,Γv,where Γx=w|w∈V,x,w∈E is the set of neighbor nodes of x.However, how good a metric of the similarity between two nodes remains still open, there is no unique approach which can denote similarity between two nodes appropriately in all cases, and each metric can only measure partly common characteristics between two nodes. For instance, all the above indexes are based on the number of common neighbors between two nodes; the idea of them is intuitive that the more common neighbors exist between two nodes, the more similar they are. However, these metrics have at least one disadvantage: they cannot differentiate the tightness relation between two nodes whether they are connected directly or indirectly. This might lead to an inconsistency with the fact and then further result in inaccurate communities.Taking the Jaccard index as an example, Figure1 illustrates two scenarios in which Jaccard similarity obtains the problematic results. Both of them show that two substructures widely existed in networks, in which v1 and v2 connect to the rest of the network correspondingly with almost the same style as v3 and v4, respectively, except that v1 and v2 are directly connected, whereas v3 connects to v4 indirectly. However, simJaccardv1,v2<simJaccardv3,v4 in both cases. That is to say, the existence of an edge contrarily decreases the similarity between the two end nodes of the edge. In other words, the indirectly connected nodes are closer than the directly connected ones when measured using such similarity index, which conflicts with the general intuition.Figure 1
Two scenarios which generic common neighbor-based similarity might lead to problematic result.
(a)(b)To address this situation, we devise a novel approach for calculating the similarity between nodesu and v:(5)simu,v=au,v+Γu∩Γv|Γu|+Γv/2,where au,v is the element of the adjacency matrix A, i.e., au,v=1 if u,v∈E, or 0 otherwise. Clearly, simv1,v2≥simv3,v4 in both of the two cases presented in Figure 1, which coincides with the intuition.


## 3.1.2. The Link Strength between Communities

In the proposed method, we need to merge some initial communities to improve the quality of the resultant communities. To this end, we devise an index,link strength between communities, to determine which pair of communities should be joined together. It is naturally to consider using the number of intercommunity edges as a criterion to merge communities, but this strategy inclines to select larger communities to merge and might result in some giant communities.After investigating the relationships between adjacent communities, we propose a relative index. We firstly define the density of edges connecting from the communityCi to Cj:(6)dCi,Cj=u,v|u∈Ci,v∈Cj,u,v∈ECi.It is an asymmetric index, which measures fairly for a community of the average number of edges connecting outside of it to the other one, regardless of the community size.Based on the concept of density of intercommunity edges, thelink strength between the communities Ci and Cj is defined as(7)LSCi,Cj=dCi,Cj×dCj,CiECiin×ECjin×NCi,where ECiin and ECjin represent the sets of edges inside of the communities Ci and Cj, respectively, and NCi stands for the set of communities adjacent to Ci.The link strength is a relative index indicating the closeness degree for two adjacent communities. Its value falls in0,1; the larger value reflects more edges existing between the two communities. Hence, they are more inclined to be merged.


## 3.2. Obtaining the Initial Communities

This is the first stage of the proposed method, and its logic is described as the pseudocode listed in Algorithm1.Algorithm 1: Get_similarity_based_communities (G).
Input:GV,E, the network; k, the community-size threshold.Output:CS, the initial community structure.(1)
Calculate the similarities between any node and its first- and second-order neighbors according to equation (5):forv∈VdoΓv←x|x∈V,v,x∈EΓ2v←y|y∈V,x∈Γv,x,y∈Eforu∈Γv∪Γ2vdosimv,u←au,v+Γu∩Γv/|Γu|+Γv/2(2)
Mark every node as unclassified and initialize variablesCS and U to record the community structure and the unvisited nodes, respectively:foreachv∈Vdov.label←0CS←ϕ;U←Vcom_id←0(3)
Select nodev with the largest degree from U, find its most similar node, and determine their community affiliations:v←argmaxu|Γu‖u∈UU←U−vu←argmaxxsimv,x|x∈Γv∪Γ2vifv.label=0then/∗v is not classified yet ∗/ifu.label≠0thenv.label←u.labeli←u.labelCi←Ci∪velse/∗create a new community for v and u∗/com_id←com_id+1v.label←com_id;u.label←com_idCcom_id←v,uCS←CS∪Ccom_idelse/∗v has already been in a community ∗/i←v.label;j←u.labelifCi<kthenifu.label≠0then/∗ merge two communities ∗/forw∈Cidow.label←u.labelCj←Cj∪CiCS←CS−Cielse/∗u has not been classified yet ∗/u.label←v.labelCi←Ci∪u(4)
Repeat step 3 untilU=ϕ.(5)
returnCSIn this algorithm, we calculate the similarity between every node and its first- and second-order neighbors first and then detect communities in the network by utilizing the calculated similarities. To facilitate the implementation, we attach a nonnegative-valued attribute ‘label’ to every node, which indicates the node’s community affiliation if its value is positive, or the node being still unclassified otherwise. Then, we select one node from the network in the descending order of the degree, denote it as v, find its most similar node u in the network, and then determine their community affiliations by considering the combination of their current status accordingly in the following ways:(1)
v is not classified into any community yet, whereas u has definite community affiliation already: we insert node v into the community in which node u belongs.(2)
Bothv and u are still unclassified: we create a new community for them.(3)
Bothv and u have been allocated into some communities: we merge v’s community and u’s community if the former is smaller than a given threshold, k, or leave the two communities untouched otherwise. In this case, the node v has been previously passively absorbed in the community as the one most similar to some other node. If that community contains only a very small number of nodes, it is unlikely to be expanded in the succeeded iterations since the most similar nodes (such as u) of its members have been already in other communities. Therefore, it is unnecessary to keep such a small community in the result, and we merge v’s community into u’s community.(4)
v has already been a classified node, whereas u is still unclassified: we intend to insert u into v’s community; however, we need to ensure the closeness between u and the other nodes in v’s community. Here, we also limit the size of v’s community to be smaller than the threshold, k, i.e., if v’s community contains less than k nodes, we insert the node u into it.The above operations are repeated iteratively, until all the nodes are processed. Then, we obtain a series of initial communities.


## 3.3. Boundary Node Moving and Initial Community Merging

Algorithm1 constructs the initial community structure by allocating nodes and their most similar nodes to the same communities. However, we have found in practice that the quality of the structure is not as better as expected sometimes, even for some nodes, and their community affiliations are problematic. Figure 2 shows the result of running Algorithm 1 on an example network, in which the nodes plotted in different colors form different initial communities.Figure 2
The problem existed in the initial community structure.Algorithm1 identifies 4 communities from the network; most of the nodes’ community affiliations are appropriate. However, the belongingness of the nodes v9 and v11 is obviously problematic. The node v9 plays a hub role in the network, and it should be allocated to the node v1’s community according to the network topology, but now it is classified in the node v14’s community since v14 is its most similar node. For node v11, the case is more serious, it is unexpectedly allocated in node v16’s community for the same reason that v16 is its most similar node, but it does not have any edge connecting with other nodes in that community at all. Therefore, we need to adjust the community affiliations of those nodes. For simplicity, we move such nodes located at the community boundaries to the communities in which most of their respective neighbors belong.In addition, some of the initial communities might be too small due to the strategy used in Algorithm1. The nodes v and u form a community only containing themselves if they are mutual most similar nodes, and the aforementioned community-size restriction might result in some small-scaled communities as well. We have also found in practice that there might exist more edges between some initial communities than those inside the corresponding communities sometimes. Therefore, we consider to merge those pairs of communities to improve the resultant communities. To this end, we calculate the link strength between every pair of communities and merge those pairs whose link strength are larger than a threshold θ, which is initially calculated adaptively by setting it to be 100 times of the minimal link strength and then repeatedly being divided to be the half of its previous value, until its value is no longer larger than the maximal link strength. In the subsequent iterations, it is attenuated to be 90% of its previous value each time. This merging operation is repeated until the corresponding modularity cannot be improved anymore; then, we obtain the final community structure.The logic implementing the ideas described above is presented in Algorithm2, the steps and operations are very clear, and the modularity [4] used in this algorithm is defined for community structure CS=C1,C2,…,Ck:(8)Q=∑i=1keii−ai2,where eii is the diagonal element of a k×k matrix e, whose elements eij represent the ratio of edges located between the communities Ci and Cj, and ai=∑j=1keij is the ratio of edges associated with nodes in community Ci.Algorithm 2: Adjustment for boundary nodes’ community affiliations and merging of some initial communities.
Input:GV,E, the network; CSinit, the initial community structure.Output:CS, the final community structure.(1)
Adjust the community affiliations of boundary nodes in the initial communities:forv∈VdoΓv←u|u∈V,v,u∈Et←argmaxjΓv∩CjCj∈CSinitift≠v.labelthens←v.labelv.label←tCt←Ct∪vCs←Cs−vifCs=ϕthenCSinit←CSinit−Cs(2)
Merge some communities according to thelink strength between communities:(2.1)
Calculate the modularityQ for CSinit according to equation (8):Q←∑i=1CSiniteii−ai2.(2.2)
CalculateLSCi,Cj for all community pairs Ci,Cj using equation (6) and (7).(2.3)
Determine the initial value of the threshold,θ, adaptively:LSmin←minLSCi,Cj|Ci∈CSinit,Cj∈CSinitLSmax←maxLSCi,Cj|Ci∈CSinit,Cj∈CSinitθ←LSmin×100whileθ>LSmaxdoθ←θ/2(2.4)
Merge all community pairsCi,Cj with LSCi,Cj>θ:foreachCi∈CSinit,Cj∈CSinitCi≠CjdoifLSCi,Cj>θthenCi←Ci∪CjCSinit←CSinit−Cj(2.5)
RecalculateLSCi,Cj and LSCj,Ci for ∀Cj∈CSinitCj≠Ci using equation (6) and (7).(2.6)
Reduce thresholdθ to 90% of its value: θ←θ×90%(2.7)
Calculate modularityQnew for community structure CSinit after merging:Qnew←∑i=1CSiniteii−ai2ifQnew>QthenCS←CSinit(2.8)
Repeat steps:ref stp:merge:merge.4 through:ref stp:merge:merge.7 until the conditionQnew>Q in step:ref stp:merge:merge.7 is not satisfied.(3)
returnCS


## 3.4. Time Complexity

The proposed method consists of Algorithms1 and 2; thus, its time consumption is the summation of the time cost of the two algorithms accordingly. For Algorithm 1, its time complexity is Od¯2V+V+VlogV for calculating the similarities between the nodes and their first- and second-order neighbors, marking the nodes as unclassified and determining the remaining nodes’ community affiliations (we use a max heap to select the node in the descending order of degree), where d¯ is the average degree of nodes in the network. This can be simplified to be OVlogV for sparse networks because d¯2≪logV or Od¯2∼OlogV at most in such networks.For Algorithm2, the step of adjusting the boundary nodes’ community affiliations consumes OV time, and the step of merging some initial communities needs OE+E+V for calculating the modularity and the link strength between all pairs of communities both in OE by traveling the edges in the network and merging communities whose link strength are larger than the threshold, θ, with at most OV alternations of the nodes’ community affiliations. Since the selection of the minimal and the maximal link strength can be implemented as a by-product along with the calculation of the link strength between communities, the time consumption of other operations can be ignored compared with those of the above steps. This time cost can be simplified to be OE or OV in sparse networks.In summary, the total time complexity of NSCLS in the worst case isOVlogV, which is much more efficient than many community detection algorithms.


## 4. Experiments

### 4.1. Networks and Comparison Algorithms

To assess the effectiveness of NSCLS, we have carried out extensive experiments on both some artificial networks and some real-world networks. The former is synthesized using the LFR benchmark generator, and the latter is abstracted from some real-world applications. For the former, we generate 5 series of networks with different scales using the parameters listed in Table1 to adjust the network characteristics. In the parameters, μ is a critical one, which regulates for each node the ratio of edges connecting outside of its community to the total edges incident to the node. We vary its value from 0.1 to 0.8 with increasing 0.1 each time, and for each value of μ, we generate 10 networks to run the experiment with expectation to eliminate the occasionality.Table 1
The parameter settings of the LFR benchmark generator used to synthesize the artificial networks.
NetworkVd¯dmaxexpdexpcomCminCmaxμLFR5005002050–2–110500.1–0.8LFR100010002050–2–110500.1–0.8LFR500050002050–2–110500.1–0.8LFR10000100002050–2–1205000.1–0.8LFR20000200002050–2–1205000.1–0.8For the real-world networks, the statistical information is presented in Table2. These networks are originated from different real-world applications, and their sizes span from tens to ten thousands of nodes. The first 5 have ground-truth community structures, whereas the others have no publicly acknowledged ground-truth community structures.Table 2
The information of real-world networks.
NetworkVEReferencesKarate club3478[35]Dolphin social network62159[36]Risk map4283[37]Football game schedule115613[3]Scientists collaboration118197[3]Les Mis.77254[38]Polbooks105441[39]Jazz1985484[40]E.Coli423519[41]E-mail11335451[42]PolBlogs149016715[43]NetSci.15892742[11]YeastL23617182[44]Power49416594[45]PGP1068024316[46]DBLP3170801049866[47]Amazon334863925872[47]We take all the above networks as the input of the proposed method to carry out the experiments and compare the detected results to the counterparts of some popular community-detection algorithms, namely, LPA [14], Walktrap [19], Attractor [22], IsoFdp [25], Sim_closure [28], and Leiden [13]; all of them have been introduced in Section 2.


### 4.2. Evaluation Metrics

There are many measures [48–51] which can be used to assess the detecting ability of the algorithms, and almost all of them accomplish this purpose via measuring the quality of the detected community structures from different perspectives. In this paper, we use three widely used metrics, say the modularity (Q) [4], the NMI [52], and the ratio of the detected number of communities to the real number of communities (R) [6], to evaluate the quality of the detected communities.The modularity can be calculated using equation (8), and it is defined as the difference between the fraction of the intracommunity edge number to the total number of edges in the network (∑i=1keii) and the expectation of that fraction (∑i=1kai2), which is calculated in a null-model graph built by maintaining the same nodes and degree distributions, but connecting edges between nodes randomly. In another words, the modularity measures how much the detected community structure differs from the random graph. Its effective value is in the range 0,1, and larger values indicate better results.The NMI is an information-theory-based metric, and it is calculated for the detected community structureCS=C1,C2,…,Ck and the ground-truth community structure P=P1,P2,…,Pt:(9)NMICS,P=−2∑i=1k∑j=1tnijlognij⋅n/ni⋅nj∑i=1knilogni/n+∑j=1tnjlogni/n,where n=V, ni=Ci, |nj=Pj, and nij=Ci∩Pj. Clearly, the NMI can only be used in the networks with the ground-truth communities being known a priori, and it measures the degree of the detected result approaching the ground truth. Its values fall in 0,1, and similarly, higher value is better.The ratio of the detected number of communities to the real number of communities is denoted asR and can be calculated:(10)R=CSP=kt.This index is used to indicate how well the algorithms reproduce the number of communities in the networks with known real communities and to reflect whether the resolution limit problem occurs or not to some extent. A value ofR<1 suggests that the resolution limit problem might exist in the detected community structure, and a value close to 1 is ideal.


### 4.3. Experimental Results for the Artificial Networks

Since the communities have been embedded in the 5 series of artificial networks, we use the NMI andR to assess the quality of the detected results. We take the networks in each series as the input one by one to run NSCLS and comparison algorithms, and the detected NMI’s are shown in Figure 3.Figure 3
The NMI extracted from the artificial networks. (a) LFR500. (b) LFR1000. (c) LFR5000. (d) LFR10000. (e) LFR20000.
(a)(b)(c)(d)(e)The proposed method NSCLS performs the best on all the artificial networks duringμ≤0.4, and its superiority elongates to μ<0.6 in the LFR500 series of networks, μ<0.7 in LFR1000 and LFR5000, and μ<0.5 in LFR20000. On the other networks in the 5 series, almost all of its NMI rank either the second or the third. Its performance is not satisfactory only on a very small number of networks with μ=0.8 because such networks are already close to the random graph, and the community structure in those networks are ambiguous. Even though, the NMIs detected by NSCLS are still larger than those of Sim_closure, Leiden, or LPA.For the comparison algorithms, Sim_closure obtains almost the largest NMI the same as those of NSCLS in LFR500 and LFR1000 withμ≤0.5 and in LFR5000 with μ<0.7. However, it performs poorly on almost all of the LFR10000 and LFR20000 series of networks; in particular, its NMIs are much lower than those of NSCLS and other comparison algorithm except for those of the attractor when μ<0.6. LPA also achieves quite larger or even the largest NMI’s on the networks with clear community boundaries, but its performance drops dramatically when μ>0.5 due to its label-updating strategy. On such networks, the nodes tend to accept the wrong labels from their neighborhoods to update their owns. IsoFdp gets the similar results with NSCLS on LFR500 and LFR1000, but it performs the worst in LFR5000 in most cases, and it cannot even manage to obtain the effective results from LFR10000 and LFR20000 due to the large scales of these networks. The attractor performs fairly on all the 5 series of networks, and it can extract quite larger NMIs in LFR1000 and LFR5000, but its NMIs in LFR500, LFR10000, and LFR20000 are much lower than the others. In particular, its NMIs are the lowest during μ<0.6 on the latter two series of networks. Walktrap’s performance is closest to that of NSCLS, and this algorithm even extracts the NMIs larger than those of NSCLS on LFR10000 and LFR20000 when μ>0.5, but its NMIs are lower on LFR500 with μ<0.6 and LFR1000 and LFR5000 with 0.5<μ<0.8 than those of NSCLS. Leiden obtains the best results on LFR500, LFR10000, and LFR20000 series of networks with μ<0.7, but its NMIs on LFR1000 and LFR5000 are smaller than those of NSCLS.This comparison results suggest that although no algorithm can dominate the others on all networks, the proposed method can obtain the high-quality community structures, and it presents the superiority over the competitors on some networks.We also compare the detected results of NSCLS and the other algorithms in terms ofR and the ratio between the detected number of communities and the real number of communities; the results are presented in Figure 4.Figure 4
The ratio of the number of the detected communities to the real number of communities in the artificial networks. (a) LFR500. (b) LFR1000. (c) LFR5000. (d) LFR10000. (e) LFR20000.
(a)(b)(c)(d)(e)Clearly, NSCLS detects the most accurate number of communities from all the 5 series of networks; the absolute majority of itsR values are the ideal ones, 1. On the remaining cases, its R values are still the ones closest to 1. For the comparison algorithms, Walktrap obtains the results closest to those of NSCLS, but its R values deviate from 1 with larger offsets than NSCLS in most cases. LPA detects the community number almost the same as the real number of communities during μ<0.5, but the values of R close to 0 when μ>0.5, which corresponds to the NMIs that also are close to 0, this is because LPA tends to obtain a trivial solution where all the nodes are classified in a single giant community on such networks due to its label update strategy. The attractor detects much more communities from all the 5 series of networks than the real communities; thus, its R values deviate far from 1 positively, and its detected community number even reaches almost 70 times of the number of real communities on LFR20000. Sim_closure extracts the number of communities the same as the real number of communities from the networks with μ<0.5 in the LFR500, LFR1000, and LFR5000 series, and on the other networks in the first two series, its R values are smaller than 1. However, on the networks in LFR5000 with μ>0.5 and all the networks in LFR10000 and LFR20000 series, its results are slightly similar with those of the attractor; it obtains much more communities than the ground truth. IsoFdp cannot detect the effective results from LFR10000 and LFR20000 series of networks as aforementioned; its R values detected from the other 3 series of networks are smaller than 1. Similarly, Leiden detects the smaller number of communities than the ground truth; thus, its R values in almost all the series of networks are smaller than 1. These results indicate that the resolution limit problem might exist in the results detected by IsoFdp and Leiden. In particular, Leiden detects the communities via maximizing the modularity, and the resolution limit problem is the common issue existing in the modularity-optimization based algorithms; the experimental results testify that Leiden is not fortunate enough to overcome this issue.


### 4.4. Experimental Results for the Real-World Networks

In this section, we present the experimental results detected in the real-world networks. As aforementioned, the ground-truth communities of the first 5 networks listed in Table2 have been known in advance; the remaining 12 networks have no publicly admitted ground-truth communities.


#### 4.4.1. Networks with the Ground-Truth Communities

Since the ground-truth communities have been already known, we take both the modularity (Q) and the NMI as the measures to assess the quality of the community structures detected by NSCLS and the comparison algorithms. The values of these two indexes are recorded in Table 3.Table 3
The experimental results on the networks with ground-truth community structures. The largest values of the two indexes on each network are typed in bold, and the second largest values are marked with an underline.
NetworkMetricGTSim_closureWalktrapLPAAttractorIsoFdpLeidenNSCLSKarateQ0.3710.3710.3530.3850.3710.3710.420.399NMI1.0001.0000.5040.620.8591.0000.6870.826DolphinQ0.5190.5010.4890.4640.450.5050.5300.519NMI1.0000.8280.6320.7190.6990.7440.8911.000Risk mapQ0.6210.5730.6240.600.5730.5190.6340.624NMI1.0000.8940.8480.8210.7780.7140.9450.848FootballQ0.6010.5990.6030.5890.6010.5990.6050.601NMI1.0000.9790.9540.9450.9230.9820.9661.000CollaborationQ0.7390.7490.7330.640.6940.6680.7510.738NMI1.0000.8610.8180.7430.8650.8230.8760.981Considering in terms of the modularity, Leiden obtains the largest modularity on all the 5 networks. This is natural because it is a modularity optimization-based algorithm as mentioned previously and its goal and methodology are to maximize the modularity. Thus, its modularities are naturally the largest. The proposed method NSCLS ranks the second on the modularity three times, and on the other two networks, NSCLS still ranks the third, and its modularities are only smaller than those of Leiden and Walktrap on the Risk map network and Leiden and Sim_closure on the scientists collaboration network. For other comparison algorithms, only Sim_closure obtains the second largest modularity once (on the scientists’ collaboration network) and Walktrap detects the second largest modularities twice (on the Risk map network and the Football game schedule network, respectively), LPA, IsoFdp, and attractor cannot manage to acquire the best or the second best results once.When measuring from the perspective of the NMI, NSCLS extracts the best results three times. In particular, it obtains the largest NMI, 1, in the Dolphin social network and the Football game schedule network, which indicates that NSCLS detects the community structures identical to the ground truth in these networks, whereas Leiden obtains the largest NMI once, which contrasts to the best results measured in terms of the modularity and testifies to some extent once more that the resolution limit problem does exist in its detected results. For other comparison algorithms, only each of Sim_closure and IsoFdp acquires the largest NMIs once (on the Karate club network). Walktrap, LPA, and attractor can only get the second best results on some network sometimes.To sum up, the above comparison results exemplify the superiority of the proposed method over the competitors to some extent, and it can steadily detect the high-quality community structures from networks.In addition, the sizes of these networks are relatively small; thus, the detected results can be visualized conveniently. Below, we show the detected results and analyze them individually.(1) The Karate Club Network. This is a network describing the relationships among 34 members of a karate club, where nodes represent club members, and edges reflect the constantly contacting relationships between members. A dispute risen between the administrator and the instructor leads to the club being split into two fractions; the corresponding divisions are always taken as the ground-truth communities of this network, which is as illustrated in Figure 5(a).Figure 5
The Karate club network: (a) the ground-truth community structure; (b) the community structure detected by NSCLS.
(a)(b)Taking this network as the input of the proposed method, we acquire the community structure presented in Figure5(b). Compared with the ground truth, NSCLS splits the nodes ‘5’, ‘6’, ‘7’, ‘11’, and ‘17’ from the larger component to form a separate community. In other words, the detected community structure is different from the ground truth. However, from Table 3, we can see that this structure corresponds to a larger modularity than the ground truth. This matches with the logic of Algorithm 2, in which we keep the community structure with the largest modularity in the community-merging procedure. Those five nodes are separated from the main component as an independent community just for the reason that such split can lead to a larger modularity.(2) The Dolphin Social Network. This network is about the social relationships between a group of dolphins living in Doubtful Sound, New Zealand. There are 62 nodes and 159 edges in total, and each edge represents that the two dolphins are observed co-occurring frequently. This network contains four communities, which are shown in Figure 6(a).Figure 6
The Dolphin social network: (a) the ground-truth community structure; (b) the community structure obtained by NSCLS.
(a)(b)NSCLS extracts the result shown in Figure6(b), which is just the same as the ground truth. In fact, the boundaries between the communities in which the nodes ‘topless’ and ‘grin’ belong, respectively, are not very clear. However, fortunately, NSCLS identifies the four communities and all the nodes are correctly classified. This result also testifies the effectiveness of the proposed similarity calculation approach and community-detection method. The proposed method outperforms the comparison algorithms significantly.(3) The Risk Map Network. This network is a world map loaded in the board game, Risk, and it contains 42 nodes and 83 edges. The nodes in the network represent countries; each edge represents the relation that the two countries are geographically adjacent. All the countries involved distribute over 6 continents; hence, this network can be naturally divided into 6 communities, and the ground-truth community structure is exhibited in Figure 7(a).Figure 7
The Risk map network: (a) the ground-truth community structure; (b) the community structure uncovered by the proposed method.
(a)(b)The proposed method finds 7 communities in this network, which is displayed in Figure7(b). NSCLS divides the community containing the nodes numbered consecutively from ‘17’ to ‘28’ into two communities, since this split can lead to a larger modularity than that of the ground truth. It classifies the nodes ‘26’, ‘33’, and ‘34’ into the community embracing the nodes numbered ‘10’–‘16’. This might be attributed to the adjustment for the community affiliation of the node ‘26’, which connects three communities with 2 edges per community. Thus, it is reasonable to allocate it to any one of the three communities, and NSCLS distributes it into the community consisting of the nodes ‘10’–‘16’. Since then, the status of the node ‘34’ is similar to that of ‘26’, and next, the node ‘33’ is also adjusted into that community accordingly.(4) Football Game Schedule Network. The network is compiled from the NCAA Division-I football game programs for the 2000 season; it corresponds to the game schedule. During the season, there are 115 teams participating in the games, and 613 games were played among them. The teams are organized as 12 conferences, which are regarded as the ground-truth community structure and illustrated in Figure 8(a).Figure 8
The football game schedule network: (a) the ground-truth community structure; (b) the community structure obtained by the proposed method.
(a)(b)The proposed method attains the result shown in Figure6(b), which is also exactly consistent with the ground truth. There is a community of 4 nodes in this network, which is the one including the nodes ‘59’, ‘60’, ‘64’, and ‘98’. All the comparison algorithms cannot recognize these communities correctly, and almost all of them dissolve it and distribute the four nodes into other communities, but NSCLS can identify this community successfully. This result reflects the great ability of the proposed method once again.(5) Scientists Collaboration Network. The network depicts the collaboration relationships between scientists working at the Santa Fe Institute, and it consists of 118 nodes and 197 edges. The nodes in this network represent scientists and each edge indicates that the two scientists have co-authored at least one article. According to the specialisms, the scientists are divided into 6 categories, which correspond to the real communities and are demonstrated in Figure 9.Figure 9
The scientists’ collaboration network: (a) the ground-truth community structure; (b) the community structure revealed by the proposed method.
(a)(b)From this network, NSCLS detects the result which is presented in Figure9(b). Clearly, it also detects the community structure in this network with a high degree of success; only one node (‘106’) is misclassified into the opposite community. This node has only two neighbors, which are located in the different communities, and its connection style is more similar with other neighbors of the node ‘78’. Hence, it is attracted by them to join the community in which the node ‘78’ belongs. This community structure is the one which most approaches the ground truth among the results of comparison algorithms.


#### 4.4.2. Networks without the Ground-Truth Community Structure

Because the ground-truth community structures of these networks are still unknown, we assess the quality of the detected results in terms of the modularity only. The detected modularity values are plotted in the bar chart visually and are illustrated in Figure10.Figure 10
The bar chart of the modularity obtained by comparison algorithms and the proposed method.On these networks, Leiden and the proposed method show their significant advantages over the comparison algorithms. Leiden acquires the largest modularity in most networks for the same reason that it is based on the modularity-optimization strategy. The proposed method is not aimed at maximizing the modularity; it still detects the best result from the NetSci. network, and its modularity is equal to that of Leiden. On the other networks, its detected modularities are only slightly smaller than those of Leiden. For the other comparison algorithms, including Walktrap, IsoFdp, LPA, and attractor, all of their modularities are much lower than the counterparts of NSCLS. In particular, Walktrap cannot manage to get an effective result from the DBLP network because there are more than one million edges in this network, and its random walks take too long time to accomplish. IsoFdp cannot extract the effective communities from the E. Coli, Polblogs, NetSci., YeastL, DBLP, and Amazon networks either, due to either the disconnection or the large scales of those networks, since it can only be applied to the connected medium-scaled networks. This result manifests that the proposed method can steadily detect high-quality communities in various networks.


## 4.1. Networks and Comparison Algorithms

To assess the effectiveness of NSCLS, we have carried out extensive experiments on both some artificial networks and some real-world networks. The former is synthesized using the LFR benchmark generator, and the latter is abstracted from some real-world applications. For the former, we generate 5 series of networks with different scales using the parameters listed in Table1 to adjust the network characteristics. In the parameters, μ is a critical one, which regulates for each node the ratio of edges connecting outside of its community to the total edges incident to the node. We vary its value from 0.1 to 0.8 with increasing 0.1 each time, and for each value of μ, we generate 10 networks to run the experiment with expectation to eliminate the occasionality.Table 1
The parameter settings of the LFR benchmark generator used to synthesize the artificial networks.
NetworkVd¯dmaxexpdexpcomCminCmaxμLFR5005002050–2–110500.1–0.8LFR100010002050–2–110500.1–0.8LFR500050002050–2–110500.1–0.8LFR10000100002050–2–1205000.1–0.8LFR20000200002050–2–1205000.1–0.8For the real-world networks, the statistical information is presented in Table2. These networks are originated from different real-world applications, and their sizes span from tens to ten thousands of nodes. The first 5 have ground-truth community structures, whereas the others have no publicly acknowledged ground-truth community structures.Table 2
The information of real-world networks.
NetworkVEReferencesKarate club3478[35]Dolphin social network62159[36]Risk map4283[37]Football game schedule115613[3]Scientists collaboration118197[3]Les Mis.77254[38]Polbooks105441[39]Jazz1985484[40]E.Coli423519[41]E-mail11335451[42]PolBlogs149016715[43]NetSci.15892742[11]YeastL23617182[44]Power49416594[45]PGP1068024316[46]DBLP3170801049866[47]Amazon334863925872[47]We take all the above networks as the input of the proposed method to carry out the experiments and compare the detected results to the counterparts of some popular community-detection algorithms, namely, LPA [14], Walktrap [19], Attractor [22], IsoFdp [25], Sim_closure [28], and Leiden [13]; all of them have been introduced in Section 2.


## 4.2. Evaluation Metrics

There are many measures [48–51] which can be used to assess the detecting ability of the algorithms, and almost all of them accomplish this purpose via measuring the quality of the detected community structures from different perspectives. In this paper, we use three widely used metrics, say the modularity (Q) [4], the NMI [52], and the ratio of the detected number of communities to the real number of communities (R) [6], to evaluate the quality of the detected communities.The modularity can be calculated using equation (8), and it is defined as the difference between the fraction of the intracommunity edge number to the total number of edges in the network (∑i=1keii) and the expectation of that fraction (∑i=1kai2), which is calculated in a null-model graph built by maintaining the same nodes and degree distributions, but connecting edges between nodes randomly. In another words, the modularity measures how much the detected community structure differs from the random graph. Its effective value is in the range 0,1, and larger values indicate better results.The NMI is an information-theory-based metric, and it is calculated for the detected community structureCS=C1,C2,…,Ck and the ground-truth community structure P=P1,P2,…,Pt:(9)NMICS,P=−2∑i=1k∑j=1tnijlognij⋅n/ni⋅nj∑i=1knilogni/n+∑j=1tnjlogni/n,where n=V, ni=Ci, |nj=Pj, and nij=Ci∩Pj. Clearly, the NMI can only be used in the networks with the ground-truth communities being known a priori, and it measures the degree of the detected result approaching the ground truth. Its values fall in 0,1, and similarly, higher value is better.The ratio of the detected number of communities to the real number of communities is denoted asR and can be calculated:(10)R=CSP=kt.This index is used to indicate how well the algorithms reproduce the number of communities in the networks with known real communities and to reflect whether the resolution limit problem occurs or not to some extent. A value ofR<1 suggests that the resolution limit problem might exist in the detected community structure, and a value close to 1 is ideal.


## 4.3. Experimental Results for the Artificial Networks

Since the communities have been embedded in the 5 series of artificial networks, we use the NMI andR to assess the quality of the detected results. We take the networks in each series as the input one by one to run NSCLS and comparison algorithms, and the detected NMI’s are shown in Figure 3.Figure 3
The NMI extracted from the artificial networks. (a) LFR500. (b) LFR1000. (c) LFR5000. (d) LFR10000. (e) LFR20000.
(a)(b)(c)(d)(e)The proposed method NSCLS performs the best on all the artificial networks duringμ≤0.4, and its superiority elongates to μ<0.6 in the LFR500 series of networks, μ<0.7 in LFR1000 and LFR5000, and μ<0.5 in LFR20000. On the other networks in the 5 series, almost all of its NMI rank either the second or the third. Its performance is not satisfactory only on a very small number of networks with μ=0.8 because such networks are already close to the random graph, and the community structure in those networks are ambiguous. Even though, the NMIs detected by NSCLS are still larger than those of Sim_closure, Leiden, or LPA.For the comparison algorithms, Sim_closure obtains almost the largest NMI the same as those of NSCLS in LFR500 and LFR1000 withμ≤0.5 and in LFR5000 with μ<0.7. However, it performs poorly on almost all of the LFR10000 and LFR20000 series of networks; in particular, its NMIs are much lower than those of NSCLS and other comparison algorithm except for those of the attractor when μ<0.6. LPA also achieves quite larger or even the largest NMI’s on the networks with clear community boundaries, but its performance drops dramatically when μ>0.5 due to its label-updating strategy. On such networks, the nodes tend to accept the wrong labels from their neighborhoods to update their owns. IsoFdp gets the similar results with NSCLS on LFR500 and LFR1000, but it performs the worst in LFR5000 in most cases, and it cannot even manage to obtain the effective results from LFR10000 and LFR20000 due to the large scales of these networks. The attractor performs fairly on all the 5 series of networks, and it can extract quite larger NMIs in LFR1000 and LFR5000, but its NMIs in LFR500, LFR10000, and LFR20000 are much lower than the others. In particular, its NMIs are the lowest during μ<0.6 on the latter two series of networks. Walktrap’s performance is closest to that of NSCLS, and this algorithm even extracts the NMIs larger than those of NSCLS on LFR10000 and LFR20000 when μ>0.5, but its NMIs are lower on LFR500 with μ<0.6 and LFR1000 and LFR5000 with 0.5<μ<0.8 than those of NSCLS. Leiden obtains the best results on LFR500, LFR10000, and LFR20000 series of networks with μ<0.7, but its NMIs on LFR1000 and LFR5000 are smaller than those of NSCLS.This comparison results suggest that although no algorithm can dominate the others on all networks, the proposed method can obtain the high-quality community structures, and it presents the superiority over the competitors on some networks.We also compare the detected results of NSCLS and the other algorithms in terms ofR and the ratio between the detected number of communities and the real number of communities; the results are presented in Figure 4.Figure 4
The ratio of the number of the detected communities to the real number of communities in the artificial networks. (a) LFR500. (b) LFR1000. (c) LFR5000. (d) LFR10000. (e) LFR20000.
(a)(b)(c)(d)(e)Clearly, NSCLS detects the most accurate number of communities from all the 5 series of networks; the absolute majority of itsR values are the ideal ones, 1. On the remaining cases, its R values are still the ones closest to 1. For the comparison algorithms, Walktrap obtains the results closest to those of NSCLS, but its R values deviate from 1 with larger offsets than NSCLS in most cases. LPA detects the community number almost the same as the real number of communities during μ<0.5, but the values of R close to 0 when μ>0.5, which corresponds to the NMIs that also are close to 0, this is because LPA tends to obtain a trivial solution where all the nodes are classified in a single giant community on such networks due to its label update strategy. The attractor detects much more communities from all the 5 series of networks than the real communities; thus, its R values deviate far from 1 positively, and its detected community number even reaches almost 70 times of the number of real communities on LFR20000. Sim_closure extracts the number of communities the same as the real number of communities from the networks with μ<0.5 in the LFR500, LFR1000, and LFR5000 series, and on the other networks in the first two series, its R values are smaller than 1. However, on the networks in LFR5000 with μ>0.5 and all the networks in LFR10000 and LFR20000 series, its results are slightly similar with those of the attractor; it obtains much more communities than the ground truth. IsoFdp cannot detect the effective results from LFR10000 and LFR20000 series of networks as aforementioned; its R values detected from the other 3 series of networks are smaller than 1. Similarly, Leiden detects the smaller number of communities than the ground truth; thus, its R values in almost all the series of networks are smaller than 1. These results indicate that the resolution limit problem might exist in the results detected by IsoFdp and Leiden. In particular, Leiden detects the communities via maximizing the modularity, and the resolution limit problem is the common issue existing in the modularity-optimization based algorithms; the experimental results testify that Leiden is not fortunate enough to overcome this issue.


## 4.4. Experimental Results for the Real-World Networks

In this section, we present the experimental results detected in the real-world networks. As aforementioned, the ground-truth communities of the first 5 networks listed in Table2 have been known in advance; the remaining 12 networks have no publicly admitted ground-truth communities.


### 4.4.1. Networks with the Ground-Truth Communities

Since the ground-truth communities have been already known, we take both the modularity (Q) and the NMI as the measures to assess the quality of the community structures detected by NSCLS and the comparison algorithms. The values of these two indexes are recorded in Table 3.Table 3
The experimental results on the networks with ground-truth community structures. The largest values of the two indexes on each network are typed in bold, and the second largest values are marked with an underline.
NetworkMetricGTSim_closureWalktrapLPAAttractorIsoFdpLeidenNSCLSKarateQ0.3710.3710.3530.3850.3710.3710.420.399NMI1.0001.0000.5040.620.8591.0000.6870.826DolphinQ0.5190.5010.4890.4640.450.5050.5300.519NMI1.0000.8280.6320.7190.6990.7440.8911.000Risk mapQ0.6210.5730.6240.600.5730.5190.6340.624NMI1.0000.8940.8480.8210.7780.7140.9450.848FootballQ0.6010.5990.6030.5890.6010.5990.6050.601NMI1.0000.9790.9540.9450.9230.9820.9661.000CollaborationQ0.7390.7490.7330.640.6940.6680.7510.738NMI1.0000.8610.8180.7430.8650.8230.8760.981Considering in terms of the modularity, Leiden obtains the largest modularity on all the 5 networks. This is natural because it is a modularity optimization-based algorithm as mentioned previously and its goal and methodology are to maximize the modularity. Thus, its modularities are naturally the largest. The proposed method NSCLS ranks the second on the modularity three times, and on the other two networks, NSCLS still ranks the third, and its modularities are only smaller than those of Leiden and Walktrap on the Risk map network and Leiden and Sim_closure on the scientists collaboration network. For other comparison algorithms, only Sim_closure obtains the second largest modularity once (on the scientists’ collaboration network) and Walktrap detects the second largest modularities twice (on the Risk map network and the Football game schedule network, respectively), LPA, IsoFdp, and attractor cannot manage to acquire the best or the second best results once.When measuring from the perspective of the NMI, NSCLS extracts the best results three times. In particular, it obtains the largest NMI, 1, in the Dolphin social network and the Football game schedule network, which indicates that NSCLS detects the community structures identical to the ground truth in these networks, whereas Leiden obtains the largest NMI once, which contrasts to the best results measured in terms of the modularity and testifies to some extent once more that the resolution limit problem does exist in its detected results. For other comparison algorithms, only each of Sim_closure and IsoFdp acquires the largest NMIs once (on the Karate club network). Walktrap, LPA, and attractor can only get the second best results on some network sometimes.To sum up, the above comparison results exemplify the superiority of the proposed method over the competitors to some extent, and it can steadily detect the high-quality community structures from networks.In addition, the sizes of these networks are relatively small; thus, the detected results can be visualized conveniently. Below, we show the detected results and analyze them individually.(1) The Karate Club Network. This is a network describing the relationships among 34 members of a karate club, where nodes represent club members, and edges reflect the constantly contacting relationships between members. A dispute risen between the administrator and the instructor leads to the club being split into two fractions; the corresponding divisions are always taken as the ground-truth communities of this network, which is as illustrated in Figure 5(a).Figure 5
The Karate club network: (a) the ground-truth community structure; (b) the community structure detected by NSCLS.
(a)(b)Taking this network as the input of the proposed method, we acquire the community structure presented in Figure5(b). Compared with the ground truth, NSCLS splits the nodes ‘5’, ‘6’, ‘7’, ‘11’, and ‘17’ from the larger component to form a separate community. In other words, the detected community structure is different from the ground truth. However, from Table 3, we can see that this structure corresponds to a larger modularity than the ground truth. This matches with the logic of Algorithm 2, in which we keep the community structure with the largest modularity in the community-merging procedure. Those five nodes are separated from the main component as an independent community just for the reason that such split can lead to a larger modularity.(2) The Dolphin Social Network. This network is about the social relationships between a group of dolphins living in Doubtful Sound, New Zealand. There are 62 nodes and 159 edges in total, and each edge represents that the two dolphins are observed co-occurring frequently. This network contains four communities, which are shown in Figure 6(a).Figure 6
The Dolphin social network: (a) the ground-truth community structure; (b) the community structure obtained by NSCLS.
(a)(b)NSCLS extracts the result shown in Figure6(b), which is just the same as the ground truth. In fact, the boundaries between the communities in which the nodes ‘topless’ and ‘grin’ belong, respectively, are not very clear. However, fortunately, NSCLS identifies the four communities and all the nodes are correctly classified. This result also testifies the effectiveness of the proposed similarity calculation approach and community-detection method. The proposed method outperforms the comparison algorithms significantly.(3) The Risk Map Network. This network is a world map loaded in the board game, Risk, and it contains 42 nodes and 83 edges. The nodes in the network represent countries; each edge represents the relation that the two countries are geographically adjacent. All the countries involved distribute over 6 continents; hence, this network can be naturally divided into 6 communities, and the ground-truth community structure is exhibited in Figure 7(a).Figure 7
The Risk map network: (a) the ground-truth community structure; (b) the community structure uncovered by the proposed method.
(a)(b)The proposed method finds 7 communities in this network, which is displayed in Figure7(b). NSCLS divides the community containing the nodes numbered consecutively from ‘17’ to ‘28’ into two communities, since this split can lead to a larger modularity than that of the ground truth. It classifies the nodes ‘26’, ‘33’, and ‘34’ into the community embracing the nodes numbered ‘10’–‘16’. This might be attributed to the adjustment for the community affiliation of the node ‘26’, which connects three communities with 2 edges per community. Thus, it is reasonable to allocate it to any one of the three communities, and NSCLS distributes it into the community consisting of the nodes ‘10’–‘16’. Since then, the status of the node ‘34’ is similar to that of ‘26’, and next, the node ‘33’ is also adjusted into that community accordingly.(4) Football Game Schedule Network. The network is compiled from the NCAA Division-I football game programs for the 2000 season; it corresponds to the game schedule. During the season, there are 115 teams participating in the games, and 613 games were played among them. The teams are organized as 12 conferences, which are regarded as the ground-truth community structure and illustrated in Figure 8(a).Figure 8
The football game schedule network: (a) the ground-truth community structure; (b) the community structure obtained by the proposed method.
(a)(b)The proposed method attains the result shown in Figure6(b), which is also exactly consistent with the ground truth. There is a community of 4 nodes in this network, which is the one including the nodes ‘59’, ‘60’, ‘64’, and ‘98’. All the comparison algorithms cannot recognize these communities correctly, and almost all of them dissolve it and distribute the four nodes into other communities, but NSCLS can identify this community successfully. This result reflects the great ability of the proposed method once again.(5) Scientists Collaboration Network. The network depicts the collaboration relationships between scientists working at the Santa Fe Institute, and it consists of 118 nodes and 197 edges. The nodes in this network represent scientists and each edge indicates that the two scientists have co-authored at least one article. According to the specialisms, the scientists are divided into 6 categories, which correspond to the real communities and are demonstrated in Figure 9.Figure 9
The scientists’ collaboration network: (a) the ground-truth community structure; (b) the community structure revealed by the proposed method.
(a)(b)From this network, NSCLS detects the result which is presented in Figure9(b). Clearly, it also detects the community structure in this network with a high degree of success; only one node (‘106’) is misclassified into the opposite community. This node has only two neighbors, which are located in the different communities, and its connection style is more similar with other neighbors of the node ‘78’. Hence, it is attracted by them to join the community in which the node ‘78’ belongs. This community structure is the one which most approaches the ground truth among the results of comparison algorithms.


### 4.4.2. Networks without the Ground-Truth Community Structure

Because the ground-truth community structures of these networks are still unknown, we assess the quality of the detected results in terms of the modularity only. The detected modularity values are plotted in the bar chart visually and are illustrated in Figure10.Figure 10
The bar chart of the modularity obtained by comparison algorithms and the proposed method.On these networks, Leiden and the proposed method show their significant advantages over the comparison algorithms. Leiden acquires the largest modularity in most networks for the same reason that it is based on the modularity-optimization strategy. The proposed method is not aimed at maximizing the modularity; it still detects the best result from the NetSci. network, and its modularity is equal to that of Leiden. On the other networks, its detected modularities are only slightly smaller than those of Leiden. For the other comparison algorithms, including Walktrap, IsoFdp, LPA, and attractor, all of their modularities are much lower than the counterparts of NSCLS. In particular, Walktrap cannot manage to get an effective result from the DBLP network because there are more than one million edges in this network, and its random walks take too long time to accomplish. IsoFdp cannot extract the effective communities from the E. Coli, Polblogs, NetSci., YeastL, DBLP, and Amazon networks either, due to either the disconnection or the large scales of those networks, since it can only be applied to the connected medium-scaled networks. This result manifests that the proposed method can steadily detect high-quality communities in various networks.


## 4.4.1. Networks with the Ground-Truth Communities

Since the ground-truth communities have been already known, we take both the modularity (Q) and the NMI as the measures to assess the quality of the community structures detected by NSCLS and the comparison algorithms. The values of these two indexes are recorded in Table 3.Table 3
The experimental results on the networks with ground-truth community structures. The largest values of the two indexes on each network are typed in bold, and the second largest values are marked with an underline.
NetworkMetricGTSim_closureWalktrapLPAAttractorIsoFdpLeidenNSCLSKarateQ0.3710.3710.3530.3850.3710.3710.420.399NMI1.0001.0000.5040.620.8591.0000.6870.826DolphinQ0.5190.5010.4890.4640.450.5050.5300.519NMI1.0000.8280.6320.7190.6990.7440.8911.000Risk mapQ0.6210.5730.6240.600.5730.5190.6340.624NMI1.0000.8940.8480.8210.7780.7140.9450.848FootballQ0.6010.5990.6030.5890.6010.5990.6050.601NMI1.0000.9790.9540.9450.9230.9820.9661.000CollaborationQ0.7390.7490.7330.640.6940.6680.7510.738NMI1.0000.8610.8180.7430.8650.8230.8760.981Considering in terms of the modularity, Leiden obtains the largest modularity on all the 5 networks. This is natural because it is a modularity optimization-based algorithm as mentioned previously and its goal and methodology are to maximize the modularity. Thus, its modularities are naturally the largest. The proposed method NSCLS ranks the second on the modularity three times, and on the other two networks, NSCLS still ranks the third, and its modularities are only smaller than those of Leiden and Walktrap on the Risk map network and Leiden and Sim_closure on the scientists collaboration network. For other comparison algorithms, only Sim_closure obtains the second largest modularity once (on the scientists’ collaboration network) and Walktrap detects the second largest modularities twice (on the Risk map network and the Football game schedule network, respectively), LPA, IsoFdp, and attractor cannot manage to acquire the best or the second best results once.When measuring from the perspective of the NMI, NSCLS extracts the best results three times. In particular, it obtains the largest NMI, 1, in the Dolphin social network and the Football game schedule network, which indicates that NSCLS detects the community structures identical to the ground truth in these networks, whereas Leiden obtains the largest NMI once, which contrasts to the best results measured in terms of the modularity and testifies to some extent once more that the resolution limit problem does exist in its detected results. For other comparison algorithms, only each of Sim_closure and IsoFdp acquires the largest NMIs once (on the Karate club network). Walktrap, LPA, and attractor can only get the second best results on some network sometimes.To sum up, the above comparison results exemplify the superiority of the proposed method over the competitors to some extent, and it can steadily detect the high-quality community structures from networks.In addition, the sizes of these networks are relatively small; thus, the detected results can be visualized conveniently. Below, we show the detected results and analyze them individually.(1) The Karate Club Network. This is a network describing the relationships among 34 members of a karate club, where nodes represent club members, and edges reflect the constantly contacting relationships between members. A dispute risen between the administrator and the instructor leads to the club being split into two fractions; the corresponding divisions are always taken as the ground-truth communities of this network, which is as illustrated in Figure 5(a).Figure 5
The Karate club network: (a) the ground-truth community structure; (b) the community structure detected by NSCLS.
(a)(b)Taking this network as the input of the proposed method, we acquire the community structure presented in Figure5(b). Compared with the ground truth, NSCLS splits the nodes ‘5’, ‘6’, ‘7’, ‘11’, and ‘17’ from the larger component to form a separate community. In other words, the detected community structure is different from the ground truth. However, from Table 3, we can see that this structure corresponds to a larger modularity than the ground truth. This matches with the logic of Algorithm 2, in which we keep the community structure with the largest modularity in the community-merging procedure. Those five nodes are separated from the main component as an independent community just for the reason that such split can lead to a larger modularity.(2) The Dolphin Social Network. This network is about the social relationships between a group of dolphins living in Doubtful Sound, New Zealand. There are 62 nodes and 159 edges in total, and each edge represents that the two dolphins are observed co-occurring frequently. This network contains four communities, which are shown in Figure 6(a).Figure 6
The Dolphin social network: (a) the ground-truth community structure; (b) the community structure obtained by NSCLS.
(a)(b)NSCLS extracts the result shown in Figure6(b), which is just the same as the ground truth. In fact, the boundaries between the communities in which the nodes ‘topless’ and ‘grin’ belong, respectively, are not very clear. However, fortunately, NSCLS identifies the four communities and all the nodes are correctly classified. This result also testifies the effectiveness of the proposed similarity calculation approach and community-detection method. The proposed method outperforms the comparison algorithms significantly.(3) The Risk Map Network. This network is a world map loaded in the board game, Risk, and it contains 42 nodes and 83 edges. The nodes in the network represent countries; each edge represents the relation that the two countries are geographically adjacent. All the countries involved distribute over 6 continents; hence, this network can be naturally divided into 6 communities, and the ground-truth community structure is exhibited in Figure 7(a).Figure 7
The Risk map network: (a) the ground-truth community structure; (b) the community structure uncovered by the proposed method.
(a)(b)The proposed method finds 7 communities in this network, which is displayed in Figure7(b). NSCLS divides the community containing the nodes numbered consecutively from ‘17’ to ‘28’ into two communities, since this split can lead to a larger modularity than that of the ground truth. It classifies the nodes ‘26’, ‘33’, and ‘34’ into the community embracing the nodes numbered ‘10’–‘16’. This might be attributed to the adjustment for the community affiliation of the node ‘26’, which connects three communities with 2 edges per community. Thus, it is reasonable to allocate it to any one of the three communities, and NSCLS distributes it into the community consisting of the nodes ‘10’–‘16’. Since then, the status of the node ‘34’ is similar to that of ‘26’, and next, the node ‘33’ is also adjusted into that community accordingly.(4) Football Game Schedule Network. The network is compiled from the NCAA Division-I football game programs for the 2000 season; it corresponds to the game schedule. During the season, there are 115 teams participating in the games, and 613 games were played among them. The teams are organized as 12 conferences, which are regarded as the ground-truth community structure and illustrated in Figure 8(a).Figure 8
The football game schedule network: (a) the ground-truth community structure; (b) the community structure obtained by the proposed method.
(a)(b)The proposed method attains the result shown in Figure6(b), which is also exactly consistent with the ground truth. There is a community of 4 nodes in this network, which is the one including the nodes ‘59’, ‘60’, ‘64’, and ‘98’. All the comparison algorithms cannot recognize these communities correctly, and almost all of them dissolve it and distribute the four nodes into other communities, but NSCLS can identify this community successfully. This result reflects the great ability of the proposed method once again.(5) Scientists Collaboration Network. The network depicts the collaboration relationships between scientists working at the Santa Fe Institute, and it consists of 118 nodes and 197 edges. The nodes in this network represent scientists and each edge indicates that the two scientists have co-authored at least one article. According to the specialisms, the scientists are divided into 6 categories, which correspond to the real communities and are demonstrated in Figure 9.Figure 9
The scientists’ collaboration network: (a) the ground-truth community structure; (b) the community structure revealed by the proposed method.
(a)(b)From this network, NSCLS detects the result which is presented in Figure9(b). Clearly, it also detects the community structure in this network with a high degree of success; only one node (‘106’) is misclassified into the opposite community. This node has only two neighbors, which are located in the different communities, and its connection style is more similar with other neighbors of the node ‘78’. Hence, it is attracted by them to join the community in which the node ‘78’ belongs. This community structure is the one which most approaches the ground truth among the results of comparison algorithms.


## 4.4.2. Networks without the Ground-Truth Community Structure

Because the ground-truth community structures of these networks are still unknown, we assess the quality of the detected results in terms of the modularity only. The detected modularity values are plotted in the bar chart visually and are illustrated in Figure10.Figure 10
The bar chart of the modularity obtained by comparison algorithms and the proposed method.On these networks, Leiden and the proposed method show their significant advantages over the comparison algorithms. Leiden acquires the largest modularity in most networks for the same reason that it is based on the modularity-optimization strategy. The proposed method is not aimed at maximizing the modularity; it still detects the best result from the NetSci. network, and its modularity is equal to that of Leiden. On the other networks, its detected modularities are only slightly smaller than those of Leiden. For the other comparison algorithms, including Walktrap, IsoFdp, LPA, and attractor, all of their modularities are much lower than the counterparts of NSCLS. In particular, Walktrap cannot manage to get an effective result from the DBLP network because there are more than one million edges in this network, and its random walks take too long time to accomplish. IsoFdp cannot extract the effective communities from the E. Coli, Polblogs, NetSci., YeastL, DBLP, and Amazon networks either, due to either the disconnection or the large scales of those networks, since it can only be applied to the connected medium-scaled networks. This result manifests that the proposed method can steadily detect high-quality communities in various networks.


## 5. Conclusion

In this paper, we proposed a novel approach to calculate the similarities between any node and its first- and second-order neighbors; then, on the basis of the node similarities, we designed an algorithm to extract the initial communities by generally allocating nodes and their most similar nodes to the same communities, but considering some special cases individually. For some nodes located at the community boundaries, they might be misclassified in the inappropriate communities. To make a redemption, we then adjusted their community affiliations by distributing each of them to the community in which most of its neighbors belong. For some pairs of communities, the edges between them might be more than those inside the communities; therefore, we added further a merging procedure to join some of them together to improve the quality of the results.To test the performance of the proposed method, we conducted extensive experiments on both 5 series of synthetic networks and 17 real-world networks and compared the detected results with those of some state-of-the-art algorithms. The experimental results show the effectiveness of the proposed node similarity calculation approach and the superiority of the proposed method over the comparison algorithms; the proposed method can steadily detect high-quality communities from various networks and outperform the competitors significantly.



---

*Source: 8848566-2021-03-13.xml*