# An Autonomous Divisive Algorithm for Community Detection Based on Weak Link and Link-Break Strategy

Authors: Xiaoyu Ding; Jianpei Zhang; Jing Yang; Yiran Shen
Journal: Mathematical Problems in Engineering
 (2018)

---

## Abstract

Divisive algorithms are widely used for community detection. A common strategy of divisive algorithms is to remove the external links which connect different communities so that communities get disconnected from each other. Divisive algorithms have been investigated for several decades but some challenges remain unsolved: (1) how to efficiently identify external links, (2) how to efficiently remove external links, and (3) how to end a divisive algorithm with no help of predefined parameters or community definitions. To overcome these challenges, we introduced a concept of the weak link and autonomous division. The implementation of the proposed divisive algorithm adopts a new link-break strategy similar to a tug-of-war contest, where communities act as contestants and weak links act as breakable ropes. Empirical evaluations on artificial and real-world networks show that the proposed algorithm achieves a better accuracy-efficiency trade-off than some of the latest divisive algorithms.


---

## Body

## 1. Introduction

The study of networks is now one of the most active interdisciplinary research fields [1, 2]. In the research of computer science and sociology, complex systems are abstracted as networks or graphs. The basic components of the network are nodes and links. Nodes represent entities of interest. Links represent associations among entities. Community structure is one of the most important properties of complex systems, and community detection is an effective approach to study this property. The goal of detecting community structure is to get an appropriate classification where the links to the nodes with the community are dense, while the links to the nodes out of the community are sparse [3–7].Nowadays, different community detection algorithms have been proposed [1, 2], such as divisive algorithms [8–11], clustering algorithms [5, 12–15], modularity optimization algorithms [16–20], and label propagation algorithms [21–24]. This paper focuses on the study of divisive algorithms which separate communities by detecting and removing links. Girvan and Newman [25] proposed a significant algorithm based on the betweenness which can identify external links [10]. However, as a global centrality index, the calculation of betweenness is time-consuming and each iteration of the algorithm removes only one link from the network. To improve the efficiency of divisive algorithms, Radicchi et al. [9] proposed the edge-clustering coefficient which is a local centrality index. Based on the edge-clustering coefficient, the proposed algorithm can remove multiple links from the network at each iteration. However, the result of the algorithm is a mass of trivial partitions. To get a trade-off between accuracy and efficiency, Yang et al. [11] proposed an algorithm based on closed walks. However, the termination of the algorithm depends on the quality function modularity [16, 26, 27].This paper focuses on three challenges: (1) how to detect external links efficiently, (2) how to remove external links efficiently, and (3) how to end a divisive algorithm with no help of predefined parameters or community definitions. Actually, if communities can distinguish between internal and external links, then communities can remove external links, keep internal links, and define themselves. Based on this idea, we present a concept of the weak link and autonomous division. The implementation of the autonomous divisive (AD) algorithm adopts a new link-break strategy similar to a tug-of-war contest.We summarize the main contributions of this paper as follows:(i)
We propose a concept of the weak link. We define the weak link as a link which locates on the boundary of a community and is likely to connect another community. By removing weak links, communities get disconnected from each other. The experimental results on both artificial and real-world networks show that the weak link improves the efficiency for detecting external links.(ii)
We propose a link-break strategy based on the weak link. The link-break strategy achieves a great efficiency by detecting and removing multiple weak links at each iteration of the proposed algorithm. Based on the link-break strategy, the number of iterations of a divisive algorithm can be reduced.(iii)
We propose an autonomous divisive algorithm based on the weak link and link-break strategy. “Autonomous” means the proposed divisive algorithm does not require parameters, nontopological information, and community definition. The proposed algorithm can end with no help of predefined parameters or community definitions.The rest of the paper is organized as follows. Section2 reviews related works of divisive algorithms. Section 3 introduces the proposed definitions and algorithm. We test our algorithm and compare it with other divisive algorithms in Section 4. Section 5 concludes our study.


## 2. Related Works

### 2.1. Betweenness (GN) Algorithm

Girvan and Newman [25] proposed the GN algorithm. In their work, they proposed betweenness focusing on the links that are most “between” communities. Each iteration of GN removes the link with the highest betweenness and then recalculates the betweenness of all the links affected by the removal. For further study, they considered alternative definitions of betweenness. Experimental results showed that the proposed algorithm based on the shortest path betweenness shows the best performance [10].


### 2.2. Distance Dissimilarity (DD) Algorithm

Zhou [8] proposed the DD algorithm to quantify the differences between communities. Zhou introduced the dissimilarity index to measure the possibility that two adjacent nodes belong to the same community. Besides, Zhou also introduced a resolution threshold value known as the dissimilarity threshold. At each iteration of DD, the value of dissimilarity threshold decreases differentially. Based on the dissimilarity threshold, DD can remove multiple links at each iteration and get hierarchically organized communities characterized by upper and lower dissimilarity thresholds [8].


### 2.3. Information Centrality (IC) Algorithm

Fortunato et al. [28] proposed the IC algorithm based on information centrality defined as the relative decrement of network efficiency caused by the removal of a link. IC expects the link locating between communities to have high information centrality and the link locating within a community to have low information centrality [28]. Each iteration of IC accomplishes two tasks: calculating the information centrality of each link and removing the link with the highest information centrality. Experimental results showed that IC is effective at discovering community structures when the communities are cohesively connected with each other [28].


### 2.4. Edge-Clustering Coefficient (CD) Algorithm

Radicchi et al. [9] proposed the CD algorithm to solve two problems. The first problem is the quantitative definition of community, and the other problem is the time-consuming nature of divisive algorithms. To solve the first problem, they introduced two alternative quantitative definitions of community. To solve the second problem, they suggested a local centrality index edge-clustering coefficient. Based on the edge-clustering coefficient, CD can remove multiple links at each iteration.


### 2.5. Closed Walks (CW) Algorithm

Yang et al. [11] proposed the CW algorithm and introduced closed walks as a local centrality index. CW considers the closed walks of orders three and four based on three convincing pieces of evidence. The first evidence comes from statistical data where, in complex networks, the proportion of the links that participated in closed walks of orders 3 and 4 reaches ninety percent [11]. The second evidence comes from thethree degrees of influence property of sociological significance [29]. The third evidence comes from the property that information usually propagates along paths without repeated nodes. Experimental results showed that CW is an effective way to solve the double peak structure problem [11].


## 2.1. Betweenness (GN) Algorithm

Girvan and Newman [25] proposed the GN algorithm. In their work, they proposed betweenness focusing on the links that are most “between” communities. Each iteration of GN removes the link with the highest betweenness and then recalculates the betweenness of all the links affected by the removal. For further study, they considered alternative definitions of betweenness. Experimental results showed that the proposed algorithm based on the shortest path betweenness shows the best performance [10].


## 2.2. Distance Dissimilarity (DD) Algorithm

Zhou [8] proposed the DD algorithm to quantify the differences between communities. Zhou introduced the dissimilarity index to measure the possibility that two adjacent nodes belong to the same community. Besides, Zhou also introduced a resolution threshold value known as the dissimilarity threshold. At each iteration of DD, the value of dissimilarity threshold decreases differentially. Based on the dissimilarity threshold, DD can remove multiple links at each iteration and get hierarchically organized communities characterized by upper and lower dissimilarity thresholds [8].


## 2.3. Information Centrality (IC) Algorithm

Fortunato et al. [28] proposed the IC algorithm based on information centrality defined as the relative decrement of network efficiency caused by the removal of a link. IC expects the link locating between communities to have high information centrality and the link locating within a community to have low information centrality [28]. Each iteration of IC accomplishes two tasks: calculating the information centrality of each link and removing the link with the highest information centrality. Experimental results showed that IC is effective at discovering community structures when the communities are cohesively connected with each other [28].


## 2.4. Edge-Clustering Coefficient (CD) Algorithm

Radicchi et al. [9] proposed the CD algorithm to solve two problems. The first problem is the quantitative definition of community, and the other problem is the time-consuming nature of divisive algorithms. To solve the first problem, they introduced two alternative quantitative definitions of community. To solve the second problem, they suggested a local centrality index edge-clustering coefficient. Based on the edge-clustering coefficient, CD can remove multiple links at each iteration.


## 2.5. Closed Walks (CW) Algorithm

Yang et al. [11] proposed the CW algorithm and introduced closed walks as a local centrality index. CW considers the closed walks of orders three and four based on three convincing pieces of evidence. The first evidence comes from statistical data where, in complex networks, the proportion of the links that participated in closed walks of orders 3 and 4 reaches ninety percent [11]. The second evidence comes from thethree degrees of influence property of sociological significance [29]. The third evidence comes from the property that information usually propagates along paths without repeated nodes. Experimental results showed that CW is an effective way to solve the double peak structure problem [11].


## 3. An Autonomous Divisive Algorithm for Community Detection

### 3.1. Motivation

In real-world networks, it is often easier to discriminate between internal links and external links than to recognize overlapping nodes [1]. Defining communities as sets of links rather than nodes may be a promising strategy to analyze networks with overlapping communities [30, 31]. Based on this idea, many community detection algorithms [32–36] aim to find the differences in the property of links to extract high-quality community structures from networks. Based on network topology information, this paper discusses the difference between the properties of internal links and external links. We introduce a concept of the weak link to locate external links. In addition, we introduced a new link-break strategy and an autonomous division, so that the proposed divisive algorithm is free from parameters, nontopological information, and definition of community.


### 3.2. Definition of Weak Link

Many real-world complex systems can be represented as a graphG=V,E. V is the set of nodes, E is the set of links, V=n, and E=m. Most community detection algorithms are based on the notion that a community should have more internal connections than external connections [1, 2]. This notion skillfully generalizes the difference of the density distribution between internal links and external links. However, more properties of links are urgently needed to make divisive algorithms free from parameters, nontopological information, and community definitions.First, to tell the difference between the properties of internal links and external links, as a baseline, we investigate the expected contribution of a node to its neighbors for spreading information. If a node can only get its neighbors’ information, then the node will expect that its neighbors’ contribution for spreading information is uniform. We define the expected contribution that nodej made to its neighbor i for spreading information as(1)Eij=1di,where di is the degree of node i.Second, we investigate the property of internal links. In a community, core members, hub members, and outlier members play different roles in spreading information [37].Core members contribute greatly to spreading information inside communities;hub members serve as hubs for spreading information both inside and outside communities;outlier members prefer to receive information rather than send information. In a community, from core members to outlier members, the node’s contribution for spreading information declines. Therefore, if node i and node j are two endpoints of an internal link and Rij is the real contribution of node j to its neighbor i for spreading information, we expect that Rij≥Eij  and  Rji≤Eji or Rij≤Eij  and  Rji≥Eji.Lastly, we investigate the property of external links. The biggest difference between the properties of internal links and external links is that external links connect different communities. As the two endpoints of an external link play an important role in spreading information between communities, we expect that both of the endpoints have a real contribution which is greater than the expected contribution. Hence, if nodei and node j are the two endpoints of an external link, we expect that Rij>Eij  and  Rji>Eji. We define the weak link as follows.Definition 1 (weak link).
A linkl with two endpoints i and j is a weak link if Rij>Eij  and  Rji>Eji.


### 3.3. Determination of Weak Link

To determine whether a link is a weak link, it is essential to quantify the real contribution of the two endpoints of a link for spreading information. Thus, we investigate the structure of the shortest path tree of each endpoint and introduce the shortest path coverage as a measure.We use the shortest path coverage to estimate whether a node is at the edge of a potential community based on the following observations. There are three subgraphs in Figure1. The graphs in Figures 1(b) and 1(c) are the isomorphic graphs of Figure 1(a). In Figures 1(b) and 1(c), the solid lines present the shortest path tree of nodes A and B. If we consider Figure 1(a) as a community, then node A is a core member. In Figure 1(a), there are eight links, and there are four links and six links in the shortest path tree in Figures 1(b) and 1(c). We can see that there are four links in Figure 1(b) and two links in Figure 1(c) which are presented as dashed lines making no contribution to the shortest path tree; besides, the length of the shortest path from the source node A is 4 and the length of the shortest path from the source node B is 6. From Figure 1, we can summarize that, in a community, a core member gets in touch more quickly with the other members than a less important member, and the depth of the shortest path tree of a core member is shorter than that of a less important member.Figure 1
Observations of the shortest path tree.
(a)
(b)
(c)To calculate the shortest path coverage, we have to calculate the end-frequency and arrival-frequency. Definitions of end-frequency, arrival-frequency, and the shortest path coverage are shown in Definitions2, 3, and 4. Examples of the calculation of the three concepts are shown in Figure 2.Figure 2
Calculation of end-frequency, arrival-frequency, and the shortest path coverage; the number inside the node is the node’s ID. (a) The calculation of end-frequency; the number beside the node is the node’s end-frequency; (b) the calculation of arrival-frequency; the number beside the node is the node’s arrival-frequency; (c) the calculation of the shortest path coverage; the number beside the node is the node’s shortest path coverage.
(a)
(b)
(c)Definition 2 (end-frequency).
In the shortest path tree, the end-frequency of nodeV is the number of distinct shortest paths that start from source node S and end at node V. End-frequency is written as E.Definition 3 (arrival-frequency).
In the shortest path tree, the arrival-frequency of nodeV is the number of distinct shortest paths that start from source node S and arrive at node V. Arrival-frequency is written as A.Definition 4 (shortest path coverage).
In the shortest path tree, suppose that nodeV is a neighbor of source node S; the shortest path coverage of node V is the proportion of the arrival-frequency of node V to the sum of the end-frequency of all the reachable nodes of source node S. The shortest path coverage is written as C.The calculation of end-frequency is a top-down process using breadth-first search in timeO(m). We show an example for calculating the end-frequency in Figure 2(a). The end-frequency of the source node is 1. In the shortest path tree, the end-frequency of a node is the sum of the end-frequency of all its parent nodes. For example, in Figure 2(a), there is one shortest path from node S to node 1 and one shortest path from node S to node 2, and then the end-frequency of node 3 is 1+1=2. The end-frequency is formulated as(2)Echild=1Parents=⌀∑parent∈ParentsEparentParents≠⌀,where “Parents” is the parent node set of node child, “parent” is a node in “Parents,” Echild is the end-frequency of node child, and Eparent is the end-frequency of node parent.The calculation of arrival-frequency is a bottom-up process in timeO(m). We show an example for calculating the arrival-frequency in Figure 2(b). The arrival-frequency of a leaf node is its end-frequency. In the shortest path tree, the arrival-frequency of a node is its end-frequency plus the sum of its contribution to the arrival-frequency of its child nodes. In Figure 2(a), the end-frequency of nodes 2, 3, and 4 is 1, 2, and 1, respectively. In Figure 2(b), the arrival-frequency of nodes 3 and 4 is 4 and 3. The contribution of node 2 to the arrival-frequency of nodes 3 and 4 is 4×1/2=2 and 3×1/1=3. In Figure 2(b), the arrival-frequency of node 2 is 1+2+3=6. The arrival-frequency is formulated as(3)Aparent=EparentChildren=⌀Eparent+∑child∈ChildrenAchildEparentEchildChildren≠⌀,where “Children” is the child node set of node parent, “child” is a node in “Children,” Eparent is the end-frequency of node parent, Echild is the end-frequency of node child, Aparent is the arrival-frequency of node parent, and Achild is the arrival-frequency of node child.The shortest path coverage can be calculated in timeO(1). We show an example for calculating the shortest path coverage in Figure 2(c). For example, in Figure 2(b), the arrival-frequency of nodes 1 and 2 is 3 and 6; then, in Figure 2(c), the shortest path coverage of nodes 1 and 2 is 3/(3+6)=1/3 and 6/(3+6)=2/3. The real contribution of node j to its neighbor i for spreading information is given as(4)Rij=Cij=Aj∑k∈NeighborsAk=AjAi-1,where “Neighbors” is the neighbor set of node i, k is a node in “Neighbors,” Aj is the arrival-frequency of node j, and Cij is the shortest path coverage of j.


### 3.4. Autonomous Division and Link-Break Strategy

As shown in Section2, several advanced algorithms have been proposed to detect communities in networks, but they all have certain limitations. For example, GN [25] and IC [28] are time-consuming on large-scale networks; DD [8] depends on some parameters; CD [9] and CW [11] depend on the order of cyclic structures. Besides, all these algorithms have a common limitation that the output of these algorithms depends on quality function or community definition. We proposed link-break strategy and autonomous division to overcome these limitations.To overcome the limitation on efficiency, a link-break strategy should have the ability to detect and remove multiple links at each iteration. To overcome the limitation on parameters and nontopological information, an autonomous division should take full advantage of the topology of the network. To overcome the limitation on quality function and community definition, an autonomous division should be able to terminate the algorithm when a satisfactory solution is reached.The proposed link-break strategy is designed similarly to a tug-of-war contest. In the contest, communities act as contestants and links act as ropes. Weak links play the role of breakable ropes. When the force exerted on a breakable rope exceeds the rope’s limit, the rope breaks. Then, the force exerted on the other ropes changes and other breakable ropes will continue to break. This process will repeat until there are no breakable ropes available in the system. Lastly, different communities get disconnected from each other.Based on the weak link, autonomous division is easy to carry out. First, the concept of the weak link is proposed based on the topological properties of networks with a community structure. Second, based on the weak link, an algorithm has the ability to detect and remove multiple links at each iteration.


### 3.5. The Proposed Algorithm

Based on the concepts of the weak link and autonomous division, the proposed algorithm repeats detecting and removing weak links, until no weak links are left in the network. We show the determination of the weak link in Algorithm1. We show the AD algorithm in Algorithm 2.Algorithm 1:Determination of the weak link.
(1) Input: Graph G, node set V, link set E.
(2) Output: Weak link set W.
(3) Process:
(4) for each link lij∈E
(5) calculate Eij, Rij, Eji, Rji.
(6) if  Rij>Eij  &  Rji>Eji
(7) W=W∪lij.
(8) end if
(9) end for
(10) return Weak link set W.Algorithm 2:The AD algorithm.
(1) Input: Graph G, node set V, link set E.
(2) Output: Community set C.
(3) Process:
(4) Get weak link set  W from G.
(5) while  W≠⌀  do
(6) E=E-W, G=V,E, W=⌀.
(7) Get weak link set  W from G.
(8) end while
(9) Each component is considered as a community.
(10) return community set C.


### 3.6. Time Complexity Analysis

Suppose AD algorithm works on a network withn nodes and m links. Based on the analysis in Section 3.3, at each iteration of the AD algorithm, the time complexity of the calculation of the shortest path coverage is O(nm). Suppose that the number of potential weak links is nweak and the number of iterations is I. Because at each iteration of Algorithm 2 multiple weak links can be removed from the network, according to step (5) to step (8), it can be inferred that 0≤I≤nweak. In most free-scale networks, I≪nweak≪n, so the time complexity of AD algorithm is O(nm). In sparse graph which has an obvious community structure, the time complexity of the AD algorithm is O(n2). We list the time complexity of the AD algorithm and the other five divisive algorithms mentioned in Section 2 in Table 1.Table 1
Time complexity of divisive algorithms for community detection.
Algorithms
Time complexity
References
AD
O
n
m
[—]
GN
O
n
m
2
[10, 25]
DD
O
n
3
[8]
IC
O
n
m
3
[28]
CD
O
k
m
[9]
CW
O
a
m
+
b
m
2
[11]


## 3.1. Motivation

In real-world networks, it is often easier to discriminate between internal links and external links than to recognize overlapping nodes [1]. Defining communities as sets of links rather than nodes may be a promising strategy to analyze networks with overlapping communities [30, 31]. Based on this idea, many community detection algorithms [32–36] aim to find the differences in the property of links to extract high-quality community structures from networks. Based on network topology information, this paper discusses the difference between the properties of internal links and external links. We introduce a concept of the weak link to locate external links. In addition, we introduced a new link-break strategy and an autonomous division, so that the proposed divisive algorithm is free from parameters, nontopological information, and definition of community.


## 3.2. Definition of Weak Link

Many real-world complex systems can be represented as a graphG=V,E. V is the set of nodes, E is the set of links, V=n, and E=m. Most community detection algorithms are based on the notion that a community should have more internal connections than external connections [1, 2]. This notion skillfully generalizes the difference of the density distribution between internal links and external links. However, more properties of links are urgently needed to make divisive algorithms free from parameters, nontopological information, and community definitions.First, to tell the difference between the properties of internal links and external links, as a baseline, we investigate the expected contribution of a node to its neighbors for spreading information. If a node can only get its neighbors’ information, then the node will expect that its neighbors’ contribution for spreading information is uniform. We define the expected contribution that nodej made to its neighbor i for spreading information as(1)Eij=1di,where di is the degree of node i.Second, we investigate the property of internal links. In a community, core members, hub members, and outlier members play different roles in spreading information [37].Core members contribute greatly to spreading information inside communities;hub members serve as hubs for spreading information both inside and outside communities;outlier members prefer to receive information rather than send information. In a community, from core members to outlier members, the node’s contribution for spreading information declines. Therefore, if node i and node j are two endpoints of an internal link and Rij is the real contribution of node j to its neighbor i for spreading information, we expect that Rij≥Eij  and  Rji≤Eji or Rij≤Eij  and  Rji≥Eji.Lastly, we investigate the property of external links. The biggest difference between the properties of internal links and external links is that external links connect different communities. As the two endpoints of an external link play an important role in spreading information between communities, we expect that both of the endpoints have a real contribution which is greater than the expected contribution. Hence, if nodei and node j are the two endpoints of an external link, we expect that Rij>Eij  and  Rji>Eji. We define the weak link as follows.Definition 1 (weak link).
A linkl with two endpoints i and j is a weak link if Rij>Eij  and  Rji>Eji.


## 3.3. Determination of Weak Link

To determine whether a link is a weak link, it is essential to quantify the real contribution of the two endpoints of a link for spreading information. Thus, we investigate the structure of the shortest path tree of each endpoint and introduce the shortest path coverage as a measure.We use the shortest path coverage to estimate whether a node is at the edge of a potential community based on the following observations. There are three subgraphs in Figure1. The graphs in Figures 1(b) and 1(c) are the isomorphic graphs of Figure 1(a). In Figures 1(b) and 1(c), the solid lines present the shortest path tree of nodes A and B. If we consider Figure 1(a) as a community, then node A is a core member. In Figure 1(a), there are eight links, and there are four links and six links in the shortest path tree in Figures 1(b) and 1(c). We can see that there are four links in Figure 1(b) and two links in Figure 1(c) which are presented as dashed lines making no contribution to the shortest path tree; besides, the length of the shortest path from the source node A is 4 and the length of the shortest path from the source node B is 6. From Figure 1, we can summarize that, in a community, a core member gets in touch more quickly with the other members than a less important member, and the depth of the shortest path tree of a core member is shorter than that of a less important member.Figure 1
Observations of the shortest path tree.
(a)
(b)
(c)To calculate the shortest path coverage, we have to calculate the end-frequency and arrival-frequency. Definitions of end-frequency, arrival-frequency, and the shortest path coverage are shown in Definitions2, 3, and 4. Examples of the calculation of the three concepts are shown in Figure 2.Figure 2
Calculation of end-frequency, arrival-frequency, and the shortest path coverage; the number inside the node is the node’s ID. (a) The calculation of end-frequency; the number beside the node is the node’s end-frequency; (b) the calculation of arrival-frequency; the number beside the node is the node’s arrival-frequency; (c) the calculation of the shortest path coverage; the number beside the node is the node’s shortest path coverage.
(a)
(b)
(c)Definition 2 (end-frequency).
In the shortest path tree, the end-frequency of nodeV is the number of distinct shortest paths that start from source node S and end at node V. End-frequency is written as E.Definition 3 (arrival-frequency).
In the shortest path tree, the arrival-frequency of nodeV is the number of distinct shortest paths that start from source node S and arrive at node V. Arrival-frequency is written as A.Definition 4 (shortest path coverage).
In the shortest path tree, suppose that nodeV is a neighbor of source node S; the shortest path coverage of node V is the proportion of the arrival-frequency of node V to the sum of the end-frequency of all the reachable nodes of source node S. The shortest path coverage is written as C.The calculation of end-frequency is a top-down process using breadth-first search in timeO(m). We show an example for calculating the end-frequency in Figure 2(a). The end-frequency of the source node is 1. In the shortest path tree, the end-frequency of a node is the sum of the end-frequency of all its parent nodes. For example, in Figure 2(a), there is one shortest path from node S to node 1 and one shortest path from node S to node 2, and then the end-frequency of node 3 is 1+1=2. The end-frequency is formulated as(2)Echild=1Parents=⌀∑parent∈ParentsEparentParents≠⌀,where “Parents” is the parent node set of node child, “parent” is a node in “Parents,” Echild is the end-frequency of node child, and Eparent is the end-frequency of node parent.The calculation of arrival-frequency is a bottom-up process in timeO(m). We show an example for calculating the arrival-frequency in Figure 2(b). The arrival-frequency of a leaf node is its end-frequency. In the shortest path tree, the arrival-frequency of a node is its end-frequency plus the sum of its contribution to the arrival-frequency of its child nodes. In Figure 2(a), the end-frequency of nodes 2, 3, and 4 is 1, 2, and 1, respectively. In Figure 2(b), the arrival-frequency of nodes 3 and 4 is 4 and 3. The contribution of node 2 to the arrival-frequency of nodes 3 and 4 is 4×1/2=2 and 3×1/1=3. In Figure 2(b), the arrival-frequency of node 2 is 1+2+3=6. The arrival-frequency is formulated as(3)Aparent=EparentChildren=⌀Eparent+∑child∈ChildrenAchildEparentEchildChildren≠⌀,where “Children” is the child node set of node parent, “child” is a node in “Children,” Eparent is the end-frequency of node parent, Echild is the end-frequency of node child, Aparent is the arrival-frequency of node parent, and Achild is the arrival-frequency of node child.The shortest path coverage can be calculated in timeO(1). We show an example for calculating the shortest path coverage in Figure 2(c). For example, in Figure 2(b), the arrival-frequency of nodes 1 and 2 is 3 and 6; then, in Figure 2(c), the shortest path coverage of nodes 1 and 2 is 3/(3+6)=1/3 and 6/(3+6)=2/3. The real contribution of node j to its neighbor i for spreading information is given as(4)Rij=Cij=Aj∑k∈NeighborsAk=AjAi-1,where “Neighbors” is the neighbor set of node i, k is a node in “Neighbors,” Aj is the arrival-frequency of node j, and Cij is the shortest path coverage of j.


## 3.4. Autonomous Division and Link-Break Strategy

As shown in Section2, several advanced algorithms have been proposed to detect communities in networks, but they all have certain limitations. For example, GN [25] and IC [28] are time-consuming on large-scale networks; DD [8] depends on some parameters; CD [9] and CW [11] depend on the order of cyclic structures. Besides, all these algorithms have a common limitation that the output of these algorithms depends on quality function or community definition. We proposed link-break strategy and autonomous division to overcome these limitations.To overcome the limitation on efficiency, a link-break strategy should have the ability to detect and remove multiple links at each iteration. To overcome the limitation on parameters and nontopological information, an autonomous division should take full advantage of the topology of the network. To overcome the limitation on quality function and community definition, an autonomous division should be able to terminate the algorithm when a satisfactory solution is reached.The proposed link-break strategy is designed similarly to a tug-of-war contest. In the contest, communities act as contestants and links act as ropes. Weak links play the role of breakable ropes. When the force exerted on a breakable rope exceeds the rope’s limit, the rope breaks. Then, the force exerted on the other ropes changes and other breakable ropes will continue to break. This process will repeat until there are no breakable ropes available in the system. Lastly, different communities get disconnected from each other.Based on the weak link, autonomous division is easy to carry out. First, the concept of the weak link is proposed based on the topological properties of networks with a community structure. Second, based on the weak link, an algorithm has the ability to detect and remove multiple links at each iteration.


## 3.5. The Proposed Algorithm

Based on the concepts of the weak link and autonomous division, the proposed algorithm repeats detecting and removing weak links, until no weak links are left in the network. We show the determination of the weak link in Algorithm1. We show the AD algorithm in Algorithm 2.Algorithm 1:Determination of the weak link.
(1) Input: Graph G, node set V, link set E.
(2) Output: Weak link set W.
(3) Process:
(4) for each link lij∈E
(5) calculate Eij, Rij, Eji, Rji.
(6) if  Rij>Eij  &  Rji>Eji
(7) W=W∪lij.
(8) end if
(9) end for
(10) return Weak link set W.Algorithm 2:The AD algorithm.
(1) Input: Graph G, node set V, link set E.
(2) Output: Community set C.
(3) Process:
(4) Get weak link set  W from G.
(5) while  W≠⌀  do
(6) E=E-W, G=V,E, W=⌀.
(7) Get weak link set  W from G.
(8) end while
(9) Each component is considered as a community.
(10) return community set C.


## 3.6. Time Complexity Analysis

Suppose AD algorithm works on a network withn nodes and m links. Based on the analysis in Section 3.3, at each iteration of the AD algorithm, the time complexity of the calculation of the shortest path coverage is O(nm). Suppose that the number of potential weak links is nweak and the number of iterations is I. Because at each iteration of Algorithm 2 multiple weak links can be removed from the network, according to step (5) to step (8), it can be inferred that 0≤I≤nweak. In most free-scale networks, I≪nweak≪n, so the time complexity of AD algorithm is O(nm). In sparse graph which has an obvious community structure, the time complexity of the AD algorithm is O(n2). We list the time complexity of the AD algorithm and the other five divisive algorithms mentioned in Section 2 in Table 1.Table 1
Time complexity of divisive algorithms for community detection.
Algorithms
Time complexity
References
AD
O
n
m
[—]
GN
O
n
m
2
[10, 25]
DD
O
n
3
[8]
IC
O
n
m
3
[28]
CD
O
k
m
[9]
CW
O
a
m
+
b
m
2
[11]


## 4. Experiments and Results

In this section, the effectiveness of the AD algorithm is compared with the other five divisive algorithms mentioned in Section2 on both artificial and real-world networks. All the experiments are conducted on a computer with Intel(R) Core(TM) i3 CPU, 2.66 GHz, and 2 GB RAM.


### 4.1. Evaluation Criteria

#### 4.1.1. NMI

The normalized mutual information (NMI) is a similarity measure proven by Danon et al. [38]. NMI is based on defining a confusion matrix N, where the rows represent real communities and the columns represent detected communities. Nij is the element of N, which represents the number of nodes that belong to real community i and detected community j. Ni. is the sum of elements in row i, and N.i is the sum of elements in column i. Based on information theory, a measure of similarity between the partitions is then(5)IR,F=-2∑i=1cR∑j=1cFNijlog⁡NijN/Ni.N.j∑i=1cRNi.log⁡Ni./N+∑j=1cFN.jlog⁡N.j/N,where IR,F is the normalized mutual information, R represents the real partition, F represents the found partition, cR is the real communities in R, and  cF is the detected communities in F. If the detected communities are identical to the real communities, then IR,F=1. If the detected communities are totally independent of the real communities, then IR,F=0.


#### 4.1.2. Modularity

Girvan and Newman [10, 25] proposed modularity (Q) which is defined as(6)Q=∑C=1klCm-dC2m2,where k is the number of detected communities, C is the ID of community, lC is the number of internal links of C, and dC is the sum of the degrees of the nodes within C. This quality function measures the fraction of the links in the network that connect nodes of the same type minus the expected value of the same quantity in a network with the same community divisions but random connections between the nodes [10]. Q=0 indicates that the number of links within the communities is only random. Q=1 indicates the network with strong community structure.


#### 4.1.3. I-Measure

In this paper, we useI to evaluate the division efficiency of the algorithms.(7)I=The  number  of  iterations  of  the  algorithm.


### 4.2. Data Sets

#### 4.2.1. Artificial Networks

Lancichinetti-Fortunato-Radicchi (LFR) benchmark [39] produces networks with properties close to real-world networks. We use the LFR benchmark networks to test the algorithms. Some important parameters of the benchmark networks are given in Table 2. In Table 2, n denotes the number of nodes, k denotes the mean degree of the network, max⁡k denotes the maximum degree of node, min⁡c denotes the minimum size of community, max⁡c denotes the maximum size of community, and μ denotes the mixing parameter. For LFRμ, μ ranges from 0.1 to 0.8 with a span of 0.1. For LFRk, k ranges from 4 to 10 with a span of 1.Table 2
The parameters of artificial networks.
Networks
n
k
max
⁡
k
min
⁡
c
max
⁡
c
μ
LFRμ
128
8
16
10
50
0.1~0.8
LFRk
128
4~10
16
10
50
0.2


#### 4.2.2. Real-World Networks

The network of karate club(Karate) is a network of friendships between the 34 members of a karate club at a US university described by Zachary [40] in 1977. Zachary identified two communities of friendship in the network as shown in Figure 3.Figure 3
The network of the karate club.The network of bottlenose dolphins(Dolphins) is an undirected social network of frequent associations between 62 dolphins in a community living off Doubtful Sound compiled by Lusseau et al. [41]. A link between two dolphins was established by observation of the statistically significant frequent association. The network comprises two communities as shown in Figure 4.Figure 4
The network of the bottlenose dolphins.The network of political books(Books) was compiled by Krebs [42]. The nodes represent 105 books on American politics brought from https://Amazon.com. 441 links join pairs of books frequently purchased by the same buyer. The network is composed of three communities as shown in Figure 5.Figure 5
The network of the political books.The network of American football games(Football) between Division IA colleges during regular season Fall 2000 was compiled by Girvan and Newman [25]. The network is composed of 11 conferences plus a few other teams without a clear affiliation as shown in Figure 6.Figure 6
The network of the American football games.


### 4.3. Experiment Results

In our experiments, we ignore any quantitative definition of community and achieve the partition whenQ gets the maximum value. This will make the CD get better results, while reducing the efficiency. Besides, to avoid the local adjustment process of distance dissimilarity algorithm, DD removes the links that have the highest dissimilarity value at each iteration. We note that CD3 and CD4 represent the edge-clustering coefficient (CD) algorithm in orders 3 and 4.


#### 4.3.1. Results on Artificial Networks

Figure7 shows the results of the algorithms on LFRμ data sets. The NMI values got by AD are about 0.15 lower than the average of the other algorithms. The Q values got by AD are close to the average of the other algorithms. Figure 8 shows the results of the algorithms on LFRk data sets. When k is low, the NMI and Q values got by AD are lower than those got by the other algorithms. However, when k increases, the NMI and Q values got by AD explode, which means AD is more effective in discovering community structures when the communities are cohesively connected with each other.Figure 7
Results onLFRμ.
(a)
(b)
(c)
(d)Figure 8
Results onLFRk.
(a)
(b)
(c)
(d)From Figures7 and 8, it seems that AD does not perform better than most of the other algorithms. Actually, all the other algorithms except for AD are guided by modularity Q as mentioned in Section 4.3, paragraph 1, which means Figures 7 and 8 show the best performance of the other algorithms. However, AD is not guided by modularity Q or any of the parameters, which means Figures 7 and 8 show the average performance of AD. Thus, we cannot say that AD performs worse than the other algorithms.From Figures7 and 8, we can observe that the I values got by AD are lower than those got by the other algorithms, which means that the link-break strategy of AD can reduce the number of iterations of divisive algorithm, thus improving the efficiency of the algorithm. Besides, we can observe that IC has the highest time complexity, which verifies the analysis of Table 1. Based on thetime cost values got by the algorithms, we arrange the algorithms in an ascending order of time complexity: CD3<CD4<DD<CW<AD<GN<IC.


#### 4.3.2. Results on Real-World Networks

From Table3, we can observe that, forKarate, AD gets the highest NMI value. Besides, AD also gets a higher Q value than that of DD, CD4, and CW. ForI-measure, AD algorithm gets the lowest I value.Table 3
The results onKarate.
Measures
AD
GN
DD
IC
CD3
CD4
CW
NMI
1.00
0.58
0.39
0.66
0.67
0.57
0.64
Q
0.37
0.40
0.32
0.37
0.38
0.30
0.33
I
2
24
42
22
7
21
17From Table4, we can observe that, forDolphins, AD gets a higher NMI value than that of GN, IC, CD3, CD4, and CW. Besides, AD gets a higher Q value than that of DD. For I-measure, AD gets the lowest I value. From NMI and Q values in Table 4, we can also observe that NMI and Q are independent of each other. NMI is used to evaluate the quality of a partition when the real community structure is known, while Q is used to evaluate the quality of a partition when the real community structure is unknown.Table 4
The results onDolphins.
Measures
AD
GN
DD
IC
CD3
CD4
CW
NMI
0.75
0.55
0.80
0.39
0.23
0.54
0.54
Q
0.39
0.52
0.38
0.45
0.41
0.50
0.52
I
3
32
19
54
17
22
19From Table5, we can observe that, forBooks, AD gets a higher NMI value than that of GN, CD3, and CW. Besides, AD gets a higher Q value than that of DD, IC, CD4, and CW. For I-measure, AD gets the lowest I value.Table 5
The results onBooks.
Measures
AD
GN
DD
IC
CD3
CD4
CW
NMI
0.55
0.54
0.57
0.56
0.49
0.55
0.51
Q
0.52
0.52
0.49
0.51
0.52
0.48
0.49
I
4
51
66
45
84
19
40From Table6, we can observe that, forFootball, AD gets the lowest NMI and Q value. There are two reasons for the poor results of NMI and Q. First, there are few teams without a clear affiliation. As shown in Figure 6, for the teams of conference “Independents,” only teams 81 and 83 connected to each other. Second, some teams are more tightly connected with the teams from other conferences than the teams from the same conference. For example, all the teams of “Sun Belt” have more connections to the teams outside the conference than to the teams inside the conference. For I-measure, AD gets the lowest I value.Table 6
The results onFootball.
Measures
AD
GN
DD
IC
CD3
CD4
CW
NMI
0.79
0.90
0.86
0.86
0.92
0.92
0.92
Q
0.58
0.60
0.60
0.60
0.60
0.60
0.60
I
5
186
189
177
29
94
91From Tables3, 4, 5, and 6, we can observe that AD performs better in identifying communities from real-world networks than identifying communities from artificial networks. There are two reasons for this phenomenon. First, AD is proposed based on the differences between the properties of internal links and external links in the real-world networks where the internal and external links exhibit different characteristics. Second, LFR benchmark simulates some features of real-world networks (the node degree and community size are in power distribution); however, it does not consider the differences between the properties of internal links and external links. Therefore, we have a reason to believe that AD performs better in identifying communities from real-world networks than identifying communities from artificial networks.


## 4.1. Evaluation Criteria

### 4.1.1. NMI

The normalized mutual information (NMI) is a similarity measure proven by Danon et al. [38]. NMI is based on defining a confusion matrix N, where the rows represent real communities and the columns represent detected communities. Nij is the element of N, which represents the number of nodes that belong to real community i and detected community j. Ni. is the sum of elements in row i, and N.i is the sum of elements in column i. Based on information theory, a measure of similarity between the partitions is then(5)IR,F=-2∑i=1cR∑j=1cFNijlog⁡NijN/Ni.N.j∑i=1cRNi.log⁡Ni./N+∑j=1cFN.jlog⁡N.j/N,where IR,F is the normalized mutual information, R represents the real partition, F represents the found partition, cR is the real communities in R, and  cF is the detected communities in F. If the detected communities are identical to the real communities, then IR,F=1. If the detected communities are totally independent of the real communities, then IR,F=0.


### 4.1.2. Modularity

Girvan and Newman [10, 25] proposed modularity (Q) which is defined as(6)Q=∑C=1klCm-dC2m2,where k is the number of detected communities, C is the ID of community, lC is the number of internal links of C, and dC is the sum of the degrees of the nodes within C. This quality function measures the fraction of the links in the network that connect nodes of the same type minus the expected value of the same quantity in a network with the same community divisions but random connections between the nodes [10]. Q=0 indicates that the number of links within the communities is only random. Q=1 indicates the network with strong community structure.


### 4.1.3. I-Measure

In this paper, we useI to evaluate the division efficiency of the algorithms.(7)I=The  number  of  iterations  of  the  algorithm.


## 4.1.1. NMI

The normalized mutual information (NMI) is a similarity measure proven by Danon et al. [38]. NMI is based on defining a confusion matrix N, where the rows represent real communities and the columns represent detected communities. Nij is the element of N, which represents the number of nodes that belong to real community i and detected community j. Ni. is the sum of elements in row i, and N.i is the sum of elements in column i. Based on information theory, a measure of similarity between the partitions is then(5)IR,F=-2∑i=1cR∑j=1cFNijlog⁡NijN/Ni.N.j∑i=1cRNi.log⁡Ni./N+∑j=1cFN.jlog⁡N.j/N,where IR,F is the normalized mutual information, R represents the real partition, F represents the found partition, cR is the real communities in R, and  cF is the detected communities in F. If the detected communities are identical to the real communities, then IR,F=1. If the detected communities are totally independent of the real communities, then IR,F=0.


## 4.1.2. Modularity

Girvan and Newman [10, 25] proposed modularity (Q) which is defined as(6)Q=∑C=1klCm-dC2m2,where k is the number of detected communities, C is the ID of community, lC is the number of internal links of C, and dC is the sum of the degrees of the nodes within C. This quality function measures the fraction of the links in the network that connect nodes of the same type minus the expected value of the same quantity in a network with the same community divisions but random connections between the nodes [10]. Q=0 indicates that the number of links within the communities is only random. Q=1 indicates the network with strong community structure.


## 4.1.3. I-Measure

In this paper, we useI to evaluate the division efficiency of the algorithms.(7)I=The  number  of  iterations  of  the  algorithm.


## 4.2. Data Sets

### 4.2.1. Artificial Networks

Lancichinetti-Fortunato-Radicchi (LFR) benchmark [39] produces networks with properties close to real-world networks. We use the LFR benchmark networks to test the algorithms. Some important parameters of the benchmark networks are given in Table 2. In Table 2, n denotes the number of nodes, k denotes the mean degree of the network, max⁡k denotes the maximum degree of node, min⁡c denotes the minimum size of community, max⁡c denotes the maximum size of community, and μ denotes the mixing parameter. For LFRμ, μ ranges from 0.1 to 0.8 with a span of 0.1. For LFRk, k ranges from 4 to 10 with a span of 1.Table 2
The parameters of artificial networks.
Networks
n
k
max
⁡
k
min
⁡
c
max
⁡
c
μ
LFRμ
128
8
16
10
50
0.1~0.8
LFRk
128
4~10
16
10
50
0.2


### 4.2.2. Real-World Networks

The network of karate club(Karate) is a network of friendships between the 34 members of a karate club at a US university described by Zachary [40] in 1977. Zachary identified two communities of friendship in the network as shown in Figure 3.Figure 3
The network of the karate club.The network of bottlenose dolphins(Dolphins) is an undirected social network of frequent associations between 62 dolphins in a community living off Doubtful Sound compiled by Lusseau et al. [41]. A link between two dolphins was established by observation of the statistically significant frequent association. The network comprises two communities as shown in Figure 4.Figure 4
The network of the bottlenose dolphins.The network of political books(Books) was compiled by Krebs [42]. The nodes represent 105 books on American politics brought from https://Amazon.com. 441 links join pairs of books frequently purchased by the same buyer. The network is composed of three communities as shown in Figure 5.Figure 5
The network of the political books.The network of American football games(Football) between Division IA colleges during regular season Fall 2000 was compiled by Girvan and Newman [25]. The network is composed of 11 conferences plus a few other teams without a clear affiliation as shown in Figure 6.Figure 6
The network of the American football games.


## 4.2.1. Artificial Networks

Lancichinetti-Fortunato-Radicchi (LFR) benchmark [39] produces networks with properties close to real-world networks. We use the LFR benchmark networks to test the algorithms. Some important parameters of the benchmark networks are given in Table 2. In Table 2, n denotes the number of nodes, k denotes the mean degree of the network, max⁡k denotes the maximum degree of node, min⁡c denotes the minimum size of community, max⁡c denotes the maximum size of community, and μ denotes the mixing parameter. For LFRμ, μ ranges from 0.1 to 0.8 with a span of 0.1. For LFRk, k ranges from 4 to 10 with a span of 1.Table 2
The parameters of artificial networks.
Networks
n
k
max
⁡
k
min
⁡
c
max
⁡
c
μ
LFRμ
128
8
16
10
50
0.1~0.8
LFRk
128
4~10
16
10
50
0.2


## 4.2.2. Real-World Networks

The network of karate club(Karate) is a network of friendships between the 34 members of a karate club at a US university described by Zachary [40] in 1977. Zachary identified two communities of friendship in the network as shown in Figure 3.Figure 3
The network of the karate club.The network of bottlenose dolphins(Dolphins) is an undirected social network of frequent associations between 62 dolphins in a community living off Doubtful Sound compiled by Lusseau et al. [41]. A link between two dolphins was established by observation of the statistically significant frequent association. The network comprises two communities as shown in Figure 4.Figure 4
The network of the bottlenose dolphins.The network of political books(Books) was compiled by Krebs [42]. The nodes represent 105 books on American politics brought from https://Amazon.com. 441 links join pairs of books frequently purchased by the same buyer. The network is composed of three communities as shown in Figure 5.Figure 5
The network of the political books.The network of American football games(Football) between Division IA colleges during regular season Fall 2000 was compiled by Girvan and Newman [25]. The network is composed of 11 conferences plus a few other teams without a clear affiliation as shown in Figure 6.Figure 6
The network of the American football games.


## 4.3. Experiment Results

In our experiments, we ignore any quantitative definition of community and achieve the partition whenQ gets the maximum value. This will make the CD get better results, while reducing the efficiency. Besides, to avoid the local adjustment process of distance dissimilarity algorithm, DD removes the links that have the highest dissimilarity value at each iteration. We note that CD3 and CD4 represent the edge-clustering coefficient (CD) algorithm in orders 3 and 4.


### 4.3.1. Results on Artificial Networks

Figure7 shows the results of the algorithms on LFRμ data sets. The NMI values got by AD are about 0.15 lower than the average of the other algorithms. The Q values got by AD are close to the average of the other algorithms. Figure 8 shows the results of the algorithms on LFRk data sets. When k is low, the NMI and Q values got by AD are lower than those got by the other algorithms. However, when k increases, the NMI and Q values got by AD explode, which means AD is more effective in discovering community structures when the communities are cohesively connected with each other.Figure 7
Results onLFRμ.
(a)
(b)
(c)
(d)Figure 8
Results onLFRk.
(a)
(b)
(c)
(d)From Figures7 and 8, it seems that AD does not perform better than most of the other algorithms. Actually, all the other algorithms except for AD are guided by modularity Q as mentioned in Section 4.3, paragraph 1, which means Figures 7 and 8 show the best performance of the other algorithms. However, AD is not guided by modularity Q or any of the parameters, which means Figures 7 and 8 show the average performance of AD. Thus, we cannot say that AD performs worse than the other algorithms.From Figures7 and 8, we can observe that the I values got by AD are lower than those got by the other algorithms, which means that the link-break strategy of AD can reduce the number of iterations of divisive algorithm, thus improving the efficiency of the algorithm. Besides, we can observe that IC has the highest time complexity, which verifies the analysis of Table 1. Based on thetime cost values got by the algorithms, we arrange the algorithms in an ascending order of time complexity: CD3<CD4<DD<CW<AD<GN<IC.


### 4.3.2. Results on Real-World Networks

From Table3, we can observe that, forKarate, AD gets the highest NMI value. Besides, AD also gets a higher Q value than that of DD, CD4, and CW. ForI-measure, AD algorithm gets the lowest I value.Table 3
The results onKarate.
Measures
AD
GN
DD
IC
CD3
CD4
CW
NMI
1.00
0.58
0.39
0.66
0.67
0.57
0.64
Q
0.37
0.40
0.32
0.37
0.38
0.30
0.33
I
2
24
42
22
7
21
17From Table4, we can observe that, forDolphins, AD gets a higher NMI value than that of GN, IC, CD3, CD4, and CW. Besides, AD gets a higher Q value than that of DD. For I-measure, AD gets the lowest I value. From NMI and Q values in Table 4, we can also observe that NMI and Q are independent of each other. NMI is used to evaluate the quality of a partition when the real community structure is known, while Q is used to evaluate the quality of a partition when the real community structure is unknown.Table 4
The results onDolphins.
Measures
AD
GN
DD
IC
CD3
CD4
CW
NMI
0.75
0.55
0.80
0.39
0.23
0.54
0.54
Q
0.39
0.52
0.38
0.45
0.41
0.50
0.52
I
3
32
19
54
17
22
19From Table5, we can observe that, forBooks, AD gets a higher NMI value than that of GN, CD3, and CW. Besides, AD gets a higher Q value than that of DD, IC, CD4, and CW. For I-measure, AD gets the lowest I value.Table 5
The results onBooks.
Measures
AD
GN
DD
IC
CD3
CD4
CW
NMI
0.55
0.54
0.57
0.56
0.49
0.55
0.51
Q
0.52
0.52
0.49
0.51
0.52
0.48
0.49
I
4
51
66
45
84
19
40From Table6, we can observe that, forFootball, AD gets the lowest NMI and Q value. There are two reasons for the poor results of NMI and Q. First, there are few teams without a clear affiliation. As shown in Figure 6, for the teams of conference “Independents,” only teams 81 and 83 connected to each other. Second, some teams are more tightly connected with the teams from other conferences than the teams from the same conference. For example, all the teams of “Sun Belt” have more connections to the teams outside the conference than to the teams inside the conference. For I-measure, AD gets the lowest I value.Table 6
The results onFootball.
Measures
AD
GN
DD
IC
CD3
CD4
CW
NMI
0.79
0.90
0.86
0.86
0.92
0.92
0.92
Q
0.58
0.60
0.60
0.60
0.60
0.60
0.60
I
5
186
189
177
29
94
91From Tables3, 4, 5, and 6, we can observe that AD performs better in identifying communities from real-world networks than identifying communities from artificial networks. There are two reasons for this phenomenon. First, AD is proposed based on the differences between the properties of internal links and external links in the real-world networks where the internal and external links exhibit different characteristics. Second, LFR benchmark simulates some features of real-world networks (the node degree and community size are in power distribution); however, it does not consider the differences between the properties of internal links and external links. Therefore, we have a reason to believe that AD performs better in identifying communities from real-world networks than identifying communities from artificial networks.


## 4.3.1. Results on Artificial Networks

Figure7 shows the results of the algorithms on LFRμ data sets. The NMI values got by AD are about 0.15 lower than the average of the other algorithms. The Q values got by AD are close to the average of the other algorithms. Figure 8 shows the results of the algorithms on LFRk data sets. When k is low, the NMI and Q values got by AD are lower than those got by the other algorithms. However, when k increases, the NMI and Q values got by AD explode, which means AD is more effective in discovering community structures when the communities are cohesively connected with each other.Figure 7
Results onLFRμ.
(a)
(b)
(c)
(d)Figure 8
Results onLFRk.
(a)
(b)
(c)
(d)From Figures7 and 8, it seems that AD does not perform better than most of the other algorithms. Actually, all the other algorithms except for AD are guided by modularity Q as mentioned in Section 4.3, paragraph 1, which means Figures 7 and 8 show the best performance of the other algorithms. However, AD is not guided by modularity Q or any of the parameters, which means Figures 7 and 8 show the average performance of AD. Thus, we cannot say that AD performs worse than the other algorithms.From Figures7 and 8, we can observe that the I values got by AD are lower than those got by the other algorithms, which means that the link-break strategy of AD can reduce the number of iterations of divisive algorithm, thus improving the efficiency of the algorithm. Besides, we can observe that IC has the highest time complexity, which verifies the analysis of Table 1. Based on thetime cost values got by the algorithms, we arrange the algorithms in an ascending order of time complexity: CD3<CD4<DD<CW<AD<GN<IC.


## 4.3.2. Results on Real-World Networks

From Table3, we can observe that, forKarate, AD gets the highest NMI value. Besides, AD also gets a higher Q value than that of DD, CD4, and CW. ForI-measure, AD algorithm gets the lowest I value.Table 3
The results onKarate.
Measures
AD
GN
DD
IC
CD3
CD4
CW
NMI
1.00
0.58
0.39
0.66
0.67
0.57
0.64
Q
0.37
0.40
0.32
0.37
0.38
0.30
0.33
I
2
24
42
22
7
21
17From Table4, we can observe that, forDolphins, AD gets a higher NMI value than that of GN, IC, CD3, CD4, and CW. Besides, AD gets a higher Q value than that of DD. For I-measure, AD gets the lowest I value. From NMI and Q values in Table 4, we can also observe that NMI and Q are independent of each other. NMI is used to evaluate the quality of a partition when the real community structure is known, while Q is used to evaluate the quality of a partition when the real community structure is unknown.Table 4
The results onDolphins.
Measures
AD
GN
DD
IC
CD3
CD4
CW
NMI
0.75
0.55
0.80
0.39
0.23
0.54
0.54
Q
0.39
0.52
0.38
0.45
0.41
0.50
0.52
I
3
32
19
54
17
22
19From Table5, we can observe that, forBooks, AD gets a higher NMI value than that of GN, CD3, and CW. Besides, AD gets a higher Q value than that of DD, IC, CD4, and CW. For I-measure, AD gets the lowest I value.Table 5
The results onBooks.
Measures
AD
GN
DD
IC
CD3
CD4
CW
NMI
0.55
0.54
0.57
0.56
0.49
0.55
0.51
Q
0.52
0.52
0.49
0.51
0.52
0.48
0.49
I
4
51
66
45
84
19
40From Table6, we can observe that, forFootball, AD gets the lowest NMI and Q value. There are two reasons for the poor results of NMI and Q. First, there are few teams without a clear affiliation. As shown in Figure 6, for the teams of conference “Independents,” only teams 81 and 83 connected to each other. Second, some teams are more tightly connected with the teams from other conferences than the teams from the same conference. For example, all the teams of “Sun Belt” have more connections to the teams outside the conference than to the teams inside the conference. For I-measure, AD gets the lowest I value.Table 6
The results onFootball.
Measures
AD
GN
DD
IC
CD3
CD4
CW
NMI
0.79
0.90
0.86
0.86
0.92
0.92
0.92
Q
0.58
0.60
0.60
0.60
0.60
0.60
0.60
I
5
186
189
177
29
94
91From Tables3, 4, 5, and 6, we can observe that AD performs better in identifying communities from real-world networks than identifying communities from artificial networks. There are two reasons for this phenomenon. First, AD is proposed based on the differences between the properties of internal links and external links in the real-world networks where the internal and external links exhibit different characteristics. Second, LFR benchmark simulates some features of real-world networks (the node degree and community size are in power distribution); however, it does not consider the differences between the properties of internal links and external links. Therefore, we have a reason to believe that AD performs better in identifying communities from real-world networks than identifying communities from artificial networks.


## 5. Conclusions

In this paper, we proposed a new divisive algorithm to overcome the limitations on parameters, nontopological information, division efficiency, and community definitions. To make our algorithm free from parameters and nontopological information, we proposed the weak link which helps detect the links connecting different communities. To improve division efficiency, we proposed a link-break strategy based on the weak link, so that our algorithm could remove multiple links at each iteration. To overcome the limitation on community definition, we introduced an autonomous division in our algorithm to end the algorithm without the help of community definitions. Empirical evaluations on artificial and real-world networks showed that the proposed algorithm achieves a better accuracy-efficiency trade-off than some of the latest divisive algorithms.



---

*Source: 2942054-2018-01-15.xml*