# Heuristic Artificial Bee Colony Algorithm for Uncovering Community in Complex Networks

Authors: Yuquan Guo; Xiongfei Li; Yufei Tang; Jun Li
Journal: Mathematical Problems in Engineering
 (2017)

---

## Abstract

Community structure is important for us to understand the functions and structure of the complex networks. In this paper, Heuristic Artificial Bee Colony (HABC) algorithm based on swarm intelligence is proposed for uncovering community. The proposed HABC includes initialization, employed bee searching, onlooker searching, and scout bee searching. In initialization stage, the nectar sources with simple community structure are generated through network dynamic algorithm associated with complete subgraph. In employed bee searching and onlooker searching stages, the searching function is redefined to address the community problem. The efficiency of searching progress can be improved by a heuristic function which is an average agglomerate probability of two neighbor communities. Experiments are carried out on artificial and real world networks, and the results demonstrate that HABC will have better performance in terms of comparing with the state-of-the-art algorithms.


---

## Body

## 1. Introduction

A community is thought of as a set of nodes where nodes are densely interconnected and sparsely linked to other parts of the networks, producing a community structure of complex networks like that sketched in Figure1. In the case, there are three communities which are denoted by the dashed circles. A community is a set of nodes with a high density of internal links, whereas links between communities have a comparatively lower density.Figure 1
A community structure of small networks.In real world, many complex systems can be represented in terms of networks. For example, social networks are widely observed in our lives, because people naturally are clustered to form communities, within their work environment, family, and friends [1]. Another example is the proteins network [2], where they are interacted very frequently with each other, as they belong to metastatic cells, which have a high motility and invasiveness with respect to normal cells. Communities of proteins networks correspond to functional groups. The web is a network of HTML pages interconnected by hyperlinks. Communities of the web networks [3] are groups of pages having topical similarities. Internet is described by service and client as nodes and the connection between them by TCP or UDP. Communities of the Internet are groups of applications with similar function. The research of community structure in complex networks has positive theoretical and practical effects on analyzing topology structure of complex networks, understanding the functions of complex networks, detecting potential patterns of complex networks, and forecasting behaviors of complex networks.The rest of this paper is organized as follows: the related works are discussed in detail in Section2. Section 3 describes HABC, including overall framework of HABC, colony and nectar sources initialization, and heuristic searching progress. In Section 4, the experiments are carried out to verify the proposed method, and then in Section 5, conclusions are drawn.


## 2. Related Work

Many methods have been proposed recently to uncover the community structure of complex networks. For reviews and comparison, one can refer to references [4–8]. The community detection problem is challenging in part because it is not very well posed [9]. The essence of the community detection problem is a node-clustering problem of complex networks. To resolve it, various approaches have been developed in recent years, including hierarchical clustering, dynamic algorithm, and optimization. Most variants of the graph partitioning problem are NP-hard; that is, it is unlikely that the solution can be computed in a time growing as a power of the graph size [4]. For example, network community structure detection can be modeled as modularity maximization problems, but unfortunately, it has been proved that modularity optimization is a NP-hard problem, so it is probably impossible to find the solution in a time growing polynomially with the size of the graph.Hierarchical clustering is the first kind approach to detect community structure. Hierarchical clustering algorithms create a dendrogram according to the similarity between two groups of nodes and then uncover the community structure through cutting the dendrogram into subdendrogram. Hierarchical clustering algorithms can be classified into two categories: agglomerative algorithms and divisive algorithms. Agglomerative algorithms mainly include EAGLE [10], CPM [11], MCC [12], and CDHC [13]. Divisive algorithms mainly include GN [14] by Girvan and Newman, BCA [15] by Tyler et al., and local algorithm [16] by Radicchi et al. Hierarchical clustering has the advantage that it does not require a preliminary knowledge of community structure. However, the efficiency of these algorithms is poor in the procedure of cutting the dendrogram.Dynamic algorithms employ processes running on the networks. Random walk [17–19] and label propagation are often applied to detect communities in dynamic algorithms. A drawback of random walks algorithm is the fact that the final partition is strongly dependent on the choice of the parameter. Therefore the most meaningful partitions cannot be obtained. Label propagation includes LPA [20], CNP [21], k-rank [22], COPRA [23], and BMLPA [24]. Label propagation is near linear time algorithm. However, the result of label propagation algorithm is not stable.The methods in the third category produce communities by optimization [25]. In the community problem, the number of communities and the size of each community are unknown. For example, in a biological network, community structure is not observed. In order to evaluate the quality of a partition, many graph clustering indexes have been proposed [26–28]. Clustering indexes optimization becomes a very effective method to detect communities. Modularity proposed by Newman and Girvan is the most popular in these indexes [29]. Optimization of modularity includes hierarchical optimization of modularity by Blondel et al. [30], extremal-optimization-based algorithm that optimizes the modularity [31], and optimization modularity via mean field annealing [32]. However, Brandes found that the unknown complexity status of modularity maximization [33–35] is NP-complete in the strong sense [36]. Therefore, the study of modularity optimization has attracted attention recently. GA is applied to discover community [37–40]. The advantage of GA is the rapidity of convergence and universalness. However, premature convergence is the shortcoming of GA, and the speed of convergence is slow in later iteration process. Swarm intelligence based computation is an important approach of address optimization problem, and it mainly focuses on the collective behavior of decentralized, self-organized systems [41]. Ant colony optimization algorithms [42–44] are applied to detect community in complex networks. Our method which is named Heuristic Artificial Bee Colony (HABC) algorithm is this kind. The global optimization process of HABC is accelerated by positive feedback of bee colony optimizing.In this paper, we apply Artificial Bee Colony optimization algorithm to detect community structure. The algorithm is named HABC. The original Artificial Bee Colony (ABC) uses random searching [45], so it will lead to a time consuming search process for community detection problems. Therefore, based on ABC, the proposed HABC introduces a new heuristic function to the search process, in order to find the local optimal component according to neighbor communities. The HABC includes initialization and three searching processes. In initialization phase, every nectar source gets simply community structure through using network dynamic algorithm. Employed bees and onlookers use a heuristic function to guide the searching process.The key contributions of this paper can be summarized as follows:(1) proposing a Heuristic Artificial Bee Colony based community detection algorithm; (2) redefining a searching progress of Artificial Bee Colony algorithm to address community problem; (3) using an agglomerate probability of two neighbor communities as heuristic function of searching progress.


## 3. Heuristic Artificial Bee Colony Algorithm

Before we introduce the proposed HABC, we would like to briefly introduce some basic concepts in network. A network can be modeled as a graphG=(V,E), where V is the set of nodes and E is the set of edges. A is the adjacency matrix of G. Aij is 1 if there is an edge form node i to node j and 0 for otherwise. A community in a network is a group of nodes where nodes are densely interconnected and sparsely linked to other parts of the networks. Community structure can be represented by a set P={C1,…,Ck}, where k is the number of communities and Ci is a community which is a set of nodes with the same community ID and P is regarded as a partition of the network.


### 3.1. Framework of HABC

Artificial Bee Colony (ABC) algorithm [45] simulates the behavior of a honey bee swarm for solving optimization problems. The model consists of two essential components: nectar source and bee colony. A nectar source represents a possible solution to the optimization problem. The nectar amount of a nectar source corresponds to the quality of the solution. The colony of bees consists of three groups of bees: employed bees, onlookers, and scouts. Employed bees are associated with a particular nectar source which is exploited by employed bees. Onlookers search nectar source which is shared by employed bees. Scouts search new nectar source when a nectar source is abandoned. The search process of ABC is directed by cooperation and conversion of bee colony. ABC is shown as a flowchart on Figure 2.Figure 2
Flowchart of the ABC algorithm.Based on ABC, the proposed HABC introduces a new heuristic function to the search process. The framework of HABC algorithm is shown in Algorithm1. HABC algorithm consists of three processes including setting parameters, initialization, and searching processes. Firstly, the following parameters need to be initialized: the number of nectar source (NNS), the maximum cycle number (MCN), and thelimit for abandoning nectar source. Secondly, initialization of HABC generates nectar source set NS, employed bee set EB, and onlooker bee set OB. A nectar source represents a solution of community problem. The number of employed bees is equal to the number of nectar sources. Thirdly, the search processes of the employed bees, the onlooker bees, and the scout bees are repeated until MCN is reached.Algorithm 1:Framework of HABC.
Input: a complex networkG=(V,E); Output: the set of communitiesC; ( 1 ) Initial parameters: NNS, MCN, limit; ( 2 ) NS, EB, OB←Initialization(); ( 3 ) For i=1 to MCN { For each employed bee of EB EmployedBeeSearch();  Calculate the probability value of the nectar sources; For each onlooker bee of OE OnlookerBeeSearch();  If there is an abandoned solution for the scout then NS←NS  ∪  ScoutBeeSearch(); C←the best solution so far;  ( 4 ) return C;


### 3.2. Colony and Nectar Source Initialization

In initialization period, HABC generates a nectar source set NS of NSN solutions, where a solution represents a partition of complex networks. Each solutionSi={CIDi1,CIDi2,…,CIDij,…,CIDin}, where i=1,2,…,NNS is an N-dimensional vector. n is the number of nodes of complex network G. The component CIDij is community ID of node j.The initialization has two stages. In the first stage, all complete subgraphs of complex networks are extracted byBron–Kerbosch algorithm [46]. The nodes in the same complete subgraph are assigned unique community ID. Other nodes of complex networks are randomly assigned unique community ID. We can get a nectar source with simple community structure. In the second stage, the nectar sources are generated though repeatedly running LPA [20] on the nectar source which is got in the first stage. Each nectar source gets simple community structure through initialization, and the nectar source set is diversity.


### 3.3. Heuristic Searching Progress

The nectar amount of nectar source corresponds to the quality (fitness) of the associated community solution. In HABC, the fitness function is defined by the following equation:(1)fitnessP=11+CP,where P is a partition of the network and C(P) is the conductance [17] of the network. The conductance of a network, which reflects how easily the diffusion occurs among different communities, is obtained by the following:(2)CP=1k∑i=1k1-in_volCivolCi,where vol(Ci) is volume of community Ci and in_vol(Ci) is referred to as the inward volume of Ci. vol(Ci) is defined as (3) and in_vol(Ci) is defined as (4):(3)volCi=∑x∈Ci,yAxy(4)in_volCi=∑x∈Ci,y∈CiAxy.The conductance of network is the average departure probability of the whole community. It reflects the diffusion capacity among different communities. The value of conductance is in the range from 0 to 1. High value of conductance indicates a strong community structure.The standard ABC algorithm uses (5) to generate a new nectar source position from the old one in the searching progress of bee colony, where k is a random nectar source index. k is different from i, and Ui, Xi, Xk are vectors which represent nectar sources. Xi represents current nectar source. Ui is new nectar source. Xk is a nectar source nearby Xi. The searching progress is accomplished by the component optimization of nectar source vector.(5)Ui=Xi+rand-1,1Xi-Xk.In HABC, the component CIDij of nectar source Si is community ID. The searching progress of employed bee and onlooker is the components optimization of a nectar source according to neighbor community ID of components. So the searching function of HABC is adapted as (6), where NCI1,…,NCIm are neighbor community ID of node j. In the searching progress of HABC, each component is updated according neighbor community ID.(6)CIDij=randNCI1,…,NCIm.The conductance of networks, which is the objective function of HABC, is average departure probability of all communities. So we can use the average agglomerate probability of two adjacent communities as the heuristic function of searching progress which is defined as follows:(7)hCi,Cj=12in_volCivolCi+in_volCjvolCj.Equation (7) can convert agglomerate probability of a node and a community as (8), where n is a node of networks. C(n) is the community in which n is a node. Equation (8) is applied as heuristic function to searching progress of employed bee, (6). A new search function is proposed as (9). The neighbor community ID set of node i is computed by Ln(i). CL is a community with community IDL.(8)hn,Cj=12in_volCnvolCn+in_volCjvolCj(9)CDIi=argmaxL⁡hi,CL,L∈Lni.For every nectar source, there is only one employed bee. The employed bee is sent into the nectar source with which it is associated. Each component of nectar source is optimized in the employed bee searching progress. Employed bee searching algorithm is proposed as in Algorithm3. A component of the nectar source is randomly selected and is updated according to (9). The employed bee searching progress is repeated until each component is updated.Onlooker searching progress is similar to the employed bee searching progress. But onlookers select nectar source according the probability which is calculated as (10). The probability is information about nectar source which is shared by employed bee. Searching progress of onlooker is important to distinguish HABC from other evolutionary algorithms. That is a greed searching algorithm which makes HABC fast convergence. Onlooker bee searching is proposed as Algorithm 4.(10)probi=CPi∑i=1NNSCPi.The employed bee whose nectar source has been exhausted by the bees becomes a scout. The scout searches the area surrounding hive for new nectar source. In line 4 of Algorithm2, the vector S is created. The scout bee searching runs LPA on S PN times. The scout bee searching progress is proposed as Algorithm 5.Algorithm 2:Initialization of HABC.
Input: a complex networksG=(V,E), the number of nectar source NNS, the number of label propagation NLP; Output: the set of nectar source NS, the set of employed bee EB, the set of onlooker bee OB; ( 1 ) create all complete subgraphs of complex networks G; ( 2 ) the nodes in same subgraph are assigned unique community ID; ( 3 ) the other nodes are assigned different community ID; ( 4 ) the vector S={CID1,CID2,…,CIDn} is generated where CIDi is community ID of node I; ( 5 )  NS=∅, EB=∅, OB=∅; ( 6 )  For i=1 to NNS Si←LPA(S, NLP); EmployBee←CreateEmployedBee(Si); EB←EB∪EmployBee; OnlookerBee←CreateOnlooker(Si); OB←OB∪{OnlookerBee}; NS←NS∪{Si};  ( 7 ) return NS, EB, OB;Algorithm 3:Employed bee search.
Input: employed bee ID EBID; Output: the nectar Source NS ( 1 ) For j=1 to N A noden which is not labeled is randomly selected. The neighbor community setLn of n is calculated. NSEBID⋅xn=arg⁡maxL⁡{hi,CL,L∈Ln(i)}; The noden is labeled;  ( 2 ) return NS;Algorithm 4:Onlooker bee search.
Input: the nectar source set NS; Output: the updated set of nectar source NS; ( 1 ) calculate prob() of every nectar source; ( 2 ) select a nectar source which prob() is maximum, and get EBID of the nectar source; ( 3 ) For i=1 to N Noden which is not labeled is randomly selected. The neighbor community set NCI ofn is calculated. NSEBID⋅xn=arg⁡maxL⁡{hi,CL,L∈Ln(i)}; The noden is labeled;  ( 4 ) return NS;Algorithm 5:Scout bee search.
Input:S, PN; Output: the set of communitiesC ( 1 )  Pi←LPA(S,PN); ( 2 )  EmployBee←CreateEmployedBee(Pi); ( 3 )  EB←EB∪{EmployBee}; ( 4 )  return {Pi};


## 3.1. Framework of HABC

Artificial Bee Colony (ABC) algorithm [45] simulates the behavior of a honey bee swarm for solving optimization problems. The model consists of two essential components: nectar source and bee colony. A nectar source represents a possible solution to the optimization problem. The nectar amount of a nectar source corresponds to the quality of the solution. The colony of bees consists of three groups of bees: employed bees, onlookers, and scouts. Employed bees are associated with a particular nectar source which is exploited by employed bees. Onlookers search nectar source which is shared by employed bees. Scouts search new nectar source when a nectar source is abandoned. The search process of ABC is directed by cooperation and conversion of bee colony. ABC is shown as a flowchart on Figure 2.Figure 2
Flowchart of the ABC algorithm.Based on ABC, the proposed HABC introduces a new heuristic function to the search process. The framework of HABC algorithm is shown in Algorithm1. HABC algorithm consists of three processes including setting parameters, initialization, and searching processes. Firstly, the following parameters need to be initialized: the number of nectar source (NNS), the maximum cycle number (MCN), and thelimit for abandoning nectar source. Secondly, initialization of HABC generates nectar source set NS, employed bee set EB, and onlooker bee set OB. A nectar source represents a solution of community problem. The number of employed bees is equal to the number of nectar sources. Thirdly, the search processes of the employed bees, the onlooker bees, and the scout bees are repeated until MCN is reached.Algorithm 1:Framework of HABC.
Input: a complex networkG=(V,E); Output: the set of communitiesC; ( 1 ) Initial parameters: NNS, MCN, limit; ( 2 ) NS, EB, OB←Initialization(); ( 3 ) For i=1 to MCN { For each employed bee of EB EmployedBeeSearch();  Calculate the probability value of the nectar sources; For each onlooker bee of OE OnlookerBeeSearch();  If there is an abandoned solution for the scout then NS←NS  ∪  ScoutBeeSearch(); C←the best solution so far;  ( 4 ) return C;


## 3.2. Colony and Nectar Source Initialization

In initialization period, HABC generates a nectar source set NS of NSN solutions, where a solution represents a partition of complex networks. Each solutionSi={CIDi1,CIDi2,…,CIDij,…,CIDin}, where i=1,2,…,NNS is an N-dimensional vector. n is the number of nodes of complex network G. The component CIDij is community ID of node j.The initialization has two stages. In the first stage, all complete subgraphs of complex networks are extracted byBron–Kerbosch algorithm [46]. The nodes in the same complete subgraph are assigned unique community ID. Other nodes of complex networks are randomly assigned unique community ID. We can get a nectar source with simple community structure. In the second stage, the nectar sources are generated though repeatedly running LPA [20] on the nectar source which is got in the first stage. Each nectar source gets simple community structure through initialization, and the nectar source set is diversity.


## 3.3. Heuristic Searching Progress

The nectar amount of nectar source corresponds to the quality (fitness) of the associated community solution. In HABC, the fitness function is defined by the following equation:(1)fitnessP=11+CP,where P is a partition of the network and C(P) is the conductance [17] of the network. The conductance of a network, which reflects how easily the diffusion occurs among different communities, is obtained by the following:(2)CP=1k∑i=1k1-in_volCivolCi,where vol(Ci) is volume of community Ci and in_vol(Ci) is referred to as the inward volume of Ci. vol(Ci) is defined as (3) and in_vol(Ci) is defined as (4):(3)volCi=∑x∈Ci,yAxy(4)in_volCi=∑x∈Ci,y∈CiAxy.The conductance of network is the average departure probability of the whole community. It reflects the diffusion capacity among different communities. The value of conductance is in the range from 0 to 1. High value of conductance indicates a strong community structure.The standard ABC algorithm uses (5) to generate a new nectar source position from the old one in the searching progress of bee colony, where k is a random nectar source index. k is different from i, and Ui, Xi, Xk are vectors which represent nectar sources. Xi represents current nectar source. Ui is new nectar source. Xk is a nectar source nearby Xi. The searching progress is accomplished by the component optimization of nectar source vector.(5)Ui=Xi+rand-1,1Xi-Xk.In HABC, the component CIDij of nectar source Si is community ID. The searching progress of employed bee and onlooker is the components optimization of a nectar source according to neighbor community ID of components. So the searching function of HABC is adapted as (6), where NCI1,…,NCIm are neighbor community ID of node j. In the searching progress of HABC, each component is updated according neighbor community ID.(6)CIDij=randNCI1,…,NCIm.The conductance of networks, which is the objective function of HABC, is average departure probability of all communities. So we can use the average agglomerate probability of two adjacent communities as the heuristic function of searching progress which is defined as follows:(7)hCi,Cj=12in_volCivolCi+in_volCjvolCj.Equation (7) can convert agglomerate probability of a node and a community as (8), where n is a node of networks. C(n) is the community in which n is a node. Equation (8) is applied as heuristic function to searching progress of employed bee, (6). A new search function is proposed as (9). The neighbor community ID set of node i is computed by Ln(i). CL is a community with community IDL.(8)hn,Cj=12in_volCnvolCn+in_volCjvolCj(9)CDIi=argmaxL⁡hi,CL,L∈Lni.For every nectar source, there is only one employed bee. The employed bee is sent into the nectar source with which it is associated. Each component of nectar source is optimized in the employed bee searching progress. Employed bee searching algorithm is proposed as in Algorithm3. A component of the nectar source is randomly selected and is updated according to (9). The employed bee searching progress is repeated until each component is updated.Onlooker searching progress is similar to the employed bee searching progress. But onlookers select nectar source according the probability which is calculated as (10). The probability is information about nectar source which is shared by employed bee. Searching progress of onlooker is important to distinguish HABC from other evolutionary algorithms. That is a greed searching algorithm which makes HABC fast convergence. Onlooker bee searching is proposed as Algorithm 4.(10)probi=CPi∑i=1NNSCPi.The employed bee whose nectar source has been exhausted by the bees becomes a scout. The scout searches the area surrounding hive for new nectar source. In line 4 of Algorithm2, the vector S is created. The scout bee searching runs LPA on S PN times. The scout bee searching progress is proposed as Algorithm 5.Algorithm 2:Initialization of HABC.
Input: a complex networksG=(V,E), the number of nectar source NNS, the number of label propagation NLP; Output: the set of nectar source NS, the set of employed bee EB, the set of onlooker bee OB; ( 1 ) create all complete subgraphs of complex networks G; ( 2 ) the nodes in same subgraph are assigned unique community ID; ( 3 ) the other nodes are assigned different community ID; ( 4 ) the vector S={CID1,CID2,…,CIDn} is generated where CIDi is community ID of node I; ( 5 )  NS=∅, EB=∅, OB=∅; ( 6 )  For i=1 to NNS Si←LPA(S, NLP); EmployBee←CreateEmployedBee(Si); EB←EB∪EmployBee; OnlookerBee←CreateOnlooker(Si); OB←OB∪{OnlookerBee}; NS←NS∪{Si};  ( 7 ) return NS, EB, OB;Algorithm 3:Employed bee search.
Input: employed bee ID EBID; Output: the nectar Source NS ( 1 ) For j=1 to N A noden which is not labeled is randomly selected. The neighbor community setLn of n is calculated. NSEBID⋅xn=arg⁡maxL⁡{hi,CL,L∈Ln(i)}; The noden is labeled;  ( 2 ) return NS;Algorithm 4:Onlooker bee search.
Input: the nectar source set NS; Output: the updated set of nectar source NS; ( 1 ) calculate prob() of every nectar source; ( 2 ) select a nectar source which prob() is maximum, and get EBID of the nectar source; ( 3 ) For i=1 to N Noden which is not labeled is randomly selected. The neighbor community set NCI ofn is calculated. NSEBID⋅xn=arg⁡maxL⁡{hi,CL,L∈Ln(i)}; The noden is labeled;  ( 4 ) return NS;Algorithm 5:Scout bee search.
Input:S, PN; Output: the set of communitiesC ( 1 )  Pi←LPA(S,PN); ( 2 )  EmployBee←CreateEmployedBee(Pi); ( 3 )  EB←EB∪{EmployBee}; ( 4 )  return {Pi};


## 4. Experiment and Analysis

In order to test performance of the proposed HABC, we do different experiments on both real and artificial synthetic networks. EAGLE is a classic hierarchical clustering community detection algorithm [10]. COPRA is an available method in the class of dynamic algorithms [23]. GCE is a local optimization algorithm [25] and HABC belongs to local optimization associated with globe target. Therefore, EAGLE, COPRA, and GCE are selected as compared methods. We use NMI [26] to evaluate the difference between the community structure uncovered by HABC method and the true community structure. NMI is defined as (11). It is based on defining a confusion matrix N, where the rows correspond to the “real” communities and the columns correspond to the “detected” communities. Nij is simply the number of nodes in the real community i that appear in the found community j. The number of real communities is denoted by CA and the number of found communities is denoted by CB. The sum over row i of matrix Nij is denoted by Ni·, and the sum over column j is denoted by N·j. The value of NMI is between 0 and 1. A higher NMI indicates that the detected communities more perfectly match the true communities.(11)NMI=-2∑i=1CA∑j=1CBCijlog⁡NijN/Ni·N·j∑i=1CANi·logNi·/N+∑j=1CBN·jlogN·j/N.


### 4.1. Artificial Networks

We apply HABC to the LFR benchmark [47] which is networks with various distributions of vertex degree and community size. There are many parameters to control the created networks: the number of nodes N, the average vertex degree k, the maximum vertex degree max_k, the mixing ratio μ, the exponent of the power law distribution of vertexes, the exponent of the power law distribution of community size, the minimum community size min_c, and the maximum community size max_c. In our experiment, we generate six network sets. The parameters of six network sets are shown in Table 1. The default configuration of LFR benchmark is k=15 and max_k=50.Table 1
Parameters for artificial networks.
Network set NodesN Mixing ratioμ Community size range m i n _ c m a x _ c N1 1000 0.1, 0.2, 0.3, 0.4, 0.5 10 50 N2 1000 0.1, 0.2, 0.3, 0.4, 0.5 30 100 N3 3000 0.1, 0.2, 0.3, 0.4, 0.5 10 50 N4 3000 0.1, 0.2, 0.3, 0.4, 0.5 30 100 N5 5000 0.1, 0.2, 0.3, 0.4, 0.5 10 50 N6 5000 0.1, 0.2, 0.3, 0.4, 0.5 30 100As shown in Figure3, each graph shows a comparative result of four methods on one network set which is generated by adjusting values of mixing ratio μ (0≤μ≤1). When the community structure is evident (0.1≤μ≤0.3), both HABC and other three methods can accurately detect the community structure. But the higher NMI value for HABC clearly illustrates that it is superior to other three algorithms when 0.1≤μ≤0.3. As can be seen in Figure 3(d), the NMI value of HABC is higher than other algorithms when 0.4≤μ≤0.5. But the effect of CPM, EAGLE, and GCE declines obviously when μ>0.4.Figure 3
Comparative NMI value for different algorithms on six network sets.
(a)
Network set N1 (b)
Network set N2 (c)
Network set N3 (d)
Network set N4 (e)
Network set N5 (f)
Network set N6In order to explore the accuracy of different algorithms, the number of standard communities in the benchmark is compared with the number of detected communities by four algorithms. As shown in Figure4, the cyan represents the number of standard communities each network sets. The black, red, green, and blue represent the number of uncovered correct communities by EAGLE, CPM, GCE, and HABC, respectively. We found that when μ (Mix) increases, the accuracy of these four algorithms declines. As can be seen from Figures 1 and 2, we can find inherent relationship between the accuracy of four algorithms and the number of uncovered communities. The closer the number of uncovered communities is to standard communities, the higher the NMI value is.Figure 4
The number of uncovered communities by four algorithms on six networks.
(a)
Network set N1 (b)
Network set N2 (c)
Network set N3 (d)
Network set N4 (e)
Network set N5 (f)
Network set N6In order to inspect the influences of community size range on different algorithms, the following experiment is conducted. The performance of each algorithm on network set N1 (μ=0.3, min_c=10, max_c=30) and N2 (μ=0.3, min_c=30, max_c=100) is compared. The performance of each algorithm on networks N3 (μ=0.3, min_c=10, max_c=30) and N4 (μ=0.3, min_c=30, max_c=100) is compared. The performance of each algorithm on networks N5 (μ=0.3, min_c=10, max_c=30) and N6 (μ=0.3, min_c=30, max_c=100) is compared. To investigate the effects of network size on different algorithms, we compare the performance of each method on network sets N1 (μ=0.3, min_c=10, max_c=30), N3 (μ=0.3, min_c=10, max_c=30), and N5 (μ=0.3, min_c=10, max_c=30). As can be seen from Figures 5 and 6, HABC has a better performance for different network size and different community range size compared with CPM, GCE, and EAGLE.Figure 5
The effects of network size on four algorithms.
(a)
HABC (b)
EAGLE (c)
CPM (d)
GCEFigure 6
The influences of community size range on four algorithms.
(a)
HABC (b)
EAGLE (c)
CPM (d)
GCE


### 4.2. Real World Networks

HABC is further tested on many real world networks which are shown in Table2. We select Zachary’s karate club network [48], dolphin network [49], American college football network [14], and books on US political network (Polbooks) [50]. For these networks, we cannot use NMI to evaluate performance of four algorithms, because the true community structures of these networks are unknown. Table 3 shows the comparison results of Q values of HABC, EAGLE, GCE, and CPM. The performance of HABC outperforms EAGLE, GCE, and CPM.Table 2
Summary of real world network.
Network Nodes Edges Community Karate 34 78 2 Dolphins 62 159 2 Football 115 613 12 Polbooks 105 441 3Table 3
Comparisons ofQ value of different algorithms on real world networks.
Network EAGLE CPM GCE HABC Karate 0.4019 0.3723 0.3824 0.4104 Dolphins 0.5197 0.4708 0.4896 0.5298 Football 0.5994 0.5764 0.5769 0.6081 Polbooks 0.5098 0.4478 0.4687 0.5103


## 4.1. Artificial Networks

We apply HABC to the LFR benchmark [47] which is networks with various distributions of vertex degree and community size. There are many parameters to control the created networks: the number of nodes N, the average vertex degree k, the maximum vertex degree max_k, the mixing ratio μ, the exponent of the power law distribution of vertexes, the exponent of the power law distribution of community size, the minimum community size min_c, and the maximum community size max_c. In our experiment, we generate six network sets. The parameters of six network sets are shown in Table 1. The default configuration of LFR benchmark is k=15 and max_k=50.Table 1
Parameters for artificial networks.
Network set NodesN Mixing ratioμ Community size range m i n _ c m a x _ c N1 1000 0.1, 0.2, 0.3, 0.4, 0.5 10 50 N2 1000 0.1, 0.2, 0.3, 0.4, 0.5 30 100 N3 3000 0.1, 0.2, 0.3, 0.4, 0.5 10 50 N4 3000 0.1, 0.2, 0.3, 0.4, 0.5 30 100 N5 5000 0.1, 0.2, 0.3, 0.4, 0.5 10 50 N6 5000 0.1, 0.2, 0.3, 0.4, 0.5 30 100As shown in Figure3, each graph shows a comparative result of four methods on one network set which is generated by adjusting values of mixing ratio μ (0≤μ≤1). When the community structure is evident (0.1≤μ≤0.3), both HABC and other three methods can accurately detect the community structure. But the higher NMI value for HABC clearly illustrates that it is superior to other three algorithms when 0.1≤μ≤0.3. As can be seen in Figure 3(d), the NMI value of HABC is higher than other algorithms when 0.4≤μ≤0.5. But the effect of CPM, EAGLE, and GCE declines obviously when μ>0.4.Figure 3
Comparative NMI value for different algorithms on six network sets.
(a)
Network set N1 (b)
Network set N2 (c)
Network set N3 (d)
Network set N4 (e)
Network set N5 (f)
Network set N6In order to explore the accuracy of different algorithms, the number of standard communities in the benchmark is compared with the number of detected communities by four algorithms. As shown in Figure4, the cyan represents the number of standard communities each network sets. The black, red, green, and blue represent the number of uncovered correct communities by EAGLE, CPM, GCE, and HABC, respectively. We found that when μ (Mix) increases, the accuracy of these four algorithms declines. As can be seen from Figures 1 and 2, we can find inherent relationship between the accuracy of four algorithms and the number of uncovered communities. The closer the number of uncovered communities is to standard communities, the higher the NMI value is.Figure 4
The number of uncovered communities by four algorithms on six networks.
(a)
Network set N1 (b)
Network set N2 (c)
Network set N3 (d)
Network set N4 (e)
Network set N5 (f)
Network set N6In order to inspect the influences of community size range on different algorithms, the following experiment is conducted. The performance of each algorithm on network set N1 (μ=0.3, min_c=10, max_c=30) and N2 (μ=0.3, min_c=30, max_c=100) is compared. The performance of each algorithm on networks N3 (μ=0.3, min_c=10, max_c=30) and N4 (μ=0.3, min_c=30, max_c=100) is compared. The performance of each algorithm on networks N5 (μ=0.3, min_c=10, max_c=30) and N6 (μ=0.3, min_c=30, max_c=100) is compared. To investigate the effects of network size on different algorithms, we compare the performance of each method on network sets N1 (μ=0.3, min_c=10, max_c=30), N3 (μ=0.3, min_c=10, max_c=30), and N5 (μ=0.3, min_c=10, max_c=30). As can be seen from Figures 5 and 6, HABC has a better performance for different network size and different community range size compared with CPM, GCE, and EAGLE.Figure 5
The effects of network size on four algorithms.
(a)
HABC (b)
EAGLE (c)
CPM (d)
GCEFigure 6
The influences of community size range on four algorithms.
(a)
HABC (b)
EAGLE (c)
CPM (d)
GCE


## 4.2. Real World Networks

HABC is further tested on many real world networks which are shown in Table2. We select Zachary’s karate club network [48], dolphin network [49], American college football network [14], and books on US political network (Polbooks) [50]. For these networks, we cannot use NMI to evaluate performance of four algorithms, because the true community structures of these networks are unknown. Table 3 shows the comparison results of Q values of HABC, EAGLE, GCE, and CPM. The performance of HABC outperforms EAGLE, GCE, and CPM.Table 2
Summary of real world network.
Network Nodes Edges Community Karate 34 78 2 Dolphins 62 159 2 Football 115 613 12 Polbooks 105 441 3Table 3
Comparisons ofQ value of different algorithms on real world networks.
Network EAGLE CPM GCE HABC Karate 0.4019 0.3723 0.3824 0.4104 Dolphins 0.5197 0.4708 0.4896 0.5298 Football 0.5994 0.5764 0.5769 0.6081 Polbooks 0.5098 0.4478 0.4687 0.5103


## 5. Conclusion

In this paper, Heuristic Artificial Bee Colony (HABC) algorithm is proposed for community detection. The proposed HABC is inspired by the intelligent behaviors of the bee swarm and contains four important sections, which are initialization, employed bee searching, onlooker searching, and scout searching stages. Combining LPA and Bron–Kerbosch algorithm, the initialization stage generates nectar sources to which an employed bee is assigned. Each nectar source represents a solution of community. Then the nectar source is explored by the employed bee and the onlooker. In exploring progress, a newly defined heuristic function is applied to guide searching nectar source. A nectar source will be abandoned when it is exhausted, and the scout is sent for discovering new nectar sources. Experiments are carried out on artificial and real networks, and the performance of the HABC has been analyzed in detail. Simulation results on six artificial network sets demonstrate that HABC has better performance at community detection quality with much higher NMI value than that of EAGLE, CPM, and GCE. The experimental results demonstrate that HABC has better performance at community detection quality aspect.



---

*Source: 4143638-2017-01-18.xml*