Community detection on complex networks based on a new centrality indicator and a new modularity function
Junfang Zhu Xuezao Ren Peijie Ma Kun Gao
cs.SI physics.soc-ph



Community detection on complex networks ]Community detection on complex networks based on a new centrality indicator and a new modularity function
    

 

^1School of Science, Southwest University of Science and Technology, Mianyang 621010, People's Republic of China

^2Big Data Research Center, University of Electronic Science and Technology of China, Chengdu 611731, People's Republic of China

renxuezao@aliyun.com




Community detection is a significant and challenging task in network research. Nowadays, plenty of attention has been focused on local methods of community detection. Among them, community detection with a greedy algorithm typically starts from the identification of local essential nodes called central nodes of the network; communities expand later from these central nodes by optimizing a modularity function. In this paper, we propose a new central node indicator and a new modularity function. Our central node indicator, which we call local centrality indicator (LCI), is as efficient as the well-known global maximal degree indicator and local maximal degree indicator; on certain special network structure, LCI performs even better. On the other hand, our modularity function F2 overcomes certain disadvantages—such as the resolution limit problem—of the modularity functions raised in previous literature. Combined with a greedy algorithm, LCI and F2 enable us to identify the right community structures for both the real-world networks and the simulated benchmark network. Evaluation based on the normalized mutual information (NMI) suggests that our community detection method with a greedy algorithm based on LCI and F2 performs superior to many other methods. Therefore, the method we proposed in this paper is potentially noteworthy.





Keywords: Complex Networks, community detection, modularity 

[
    Junfang Zhu^1,2, Xuezao Ren^1, Peijie Ma^1 and Kun Gao^1 
    
=============================================================







§ INTRODUCTION

Community is a basic feature of complex network on mesoscopic scale.<cit.>. It has been found in different types of complex networks, including  social networks<cit.>, biological networks with function modularity<cit.>, technological networks<cit.> and so on. A community is a group of nodes in a network, which have denser connections (edges) among themselves than with other nodes outside the group<cit.>. Community detection is of significant importance for network science<cit.>. However, a strict definition for community structure is still to be recognized. <cit.>. And it has been always a huge challenge to detect communities within a large network.


In past decades, many methods of community detection have been proposed, such as graph partitioning<cit.>, spectral clustering<cit.>, statistic inference<cit.>, dynamic methods<cit.>, and integer programming model<cit.>.

Especially, one class of methods that employs greedy algorithms to optimize a quality function has attracted much attention<cit.>. Such methods usually adopt a the nearest search technique to expand communities<cit.>. Two factors are vital for the accuracy of community detection with a greedy optimization algorithm. One is the selection of "central nodes" from which community expansion starts. Starting from "marginal nodes" instead of "central nodes," the result could be very different. Therefore, it is essential to discover actual "central nodes" by which local communities can be identified correctly<cit.>.

It has been realized that nodes with global maximal degrees may not all be central nodes, especially when such nodes are adjacent to each other, or all involved in a same community<cit.>.Therefore, Chen et al. selected nodes with local maximal degrees which locate dispersedly in the network as candidates for central nodes<cit.>.

However, a reliable way of central node selection is still an open problem.



The other vital factor for community detection is the objective function for the greedy optimization process, in which modularity functions measuring the "strength" of community structure are often used. One famous modularity function is the modularity Q as defined by Newman<cit.> (see section 2 for its definition). It has been applied to many community detection algorithms, including the Newman fast algorithm<cit.>, EO algorithm<cit.>, and greedy optimal algorithm<cit.>.


However, the calculation of Q requires certain global information of the whole network, which seriously increases the computational burden, especially for large networks. Besides, Q has been realized to have a resolution problem<cit.>. In past years, a number of local modularity functions have been proposed, such as R<cit.>, M<cit.> and F<cit.> and the modularity density D<cit.>. These modularity functions on the one hand overcome certain drawbacks of modularity Q, but on the other hand also have their own problems. For example, when an isolated subgraph within the network emerges as a community, or the whole network constitutes a single community, R is lack of definition, and M approaches infinite. For certain communities under optimal partition, the local modularity density D becomes negative<cit.>. The performances of these existing modularity functions are far from satisfactory; new functions of modularity are to be discovered.

In this paper, we propose a new method of community detection. Based on local information of network, we suggest a new indicator for central nodes, as well as a new modularity function of communities. Our greedy algorithm of community expansion allots residual nodes to communities detected by the new indicator for central nodes. Such an algorithm is applicable to real-world networks, and has been evaluated by normalized mutual information (NMI)<cit.> on benchmark networks through computer simulation. 



§ RELATED WORK


In this section, we briefly introduce some community detection methods raised in previous literature. We mainly introduce the central nodes indicators and modularity functions used in these methods. In latter part of this paper, we will compare the performances of these methods to the performance of our method proposed in this paper. 



 §.§ Central nodes indicators


In a heterogeneous network, the "importance" of nodes is not even; some nodes are obviously more important than other nodes<cit.>. Important nodes are called "central nodes" for community detection. Starting from central nodes rather than other less important nodes, a community expansion algorithm usually ends up with better outputs. It has been observed that nodes with higher degrees are in most cases more important than nodes with lower degrees for community detection. In previous literature<cit.>, nodes with either global maximal degrees or local maximal degrees are selected as central nodes. 

The global maximal degree indicator takes nodes of top k highest degrees as central nodes. However the selection of the value of k is often arbitrary. On the other hand, the global maximal degree indicator considers only the degree of a single node, which is not always sufficient. From the perspective of statistics<cit.>, nodes with global maximal degrees are not always central nodes. 

In contrast to the global maximal degree indicator, the local maximal degree indicator designates a node as a central node only if it has the highest degree among all its neighbors. Central nodes designated by the local maximal degree indicator usually locate dispersedly in the network, except when two or more adjacent nodes have equal degrees and are all designated as central nodes. Studies have revealed that the local maximal degree indicator usually performs better than the global maximal degree indicator<cit.>.  



 §.§ Modularity functions


Modularity function measures the strength of the community structure, and is widely used as quality functions in community detection algorithms. The most popular modularity function is the Newman's modularity Q <cit.> which is formulated as,


    Q =∑_i = 1^m [l_in(C_i)/L- (d(C_i)/2L)^2]

Here l_in(C_i) is the number of edges among nodes within community C_i. d(C_i) is the sum of degrees of  all nodes in C_i. L is total number of edges within the whole network. Q has been proved to be effective in previous literature<cit.>. However, it has also been revealed that Q has some serious shortcomings<cit.>. For example, there exists a "resolution limit problem" in Q<cit.>: when the size of a community is below a certain threshold, it can't be detected by Q. This threshold does not depend on particular network structure, but results only from the comparison between the number of links of interconnected communities and the total number of links of the network<cit.>. In some cases, maximizing Q tends to split a large community into smaller ones <cit.>. And some random networks, which by definition have no apparent community structure, may have unreasonably large values of Q<cit.>. All these shortcomings reflect that Q is far from perfect, which urges researchers to find better functions for modularity.

The calculation of modularity Q requires global information of the network. For the large networks, a modularity function based on local information has higher efficiency. For this Clauset defined a local modularity function R<cit.> which directly measures the sharpness of the boundary of a local community. For a local community D, nodes within it are split into two subsets, C and B. Subset C is consist of "core" nodes that have connections only within D, and subset B is consist of "boundary" nodes that have at least one connection to nodes outside D. Clauset defined the local modularity R as


    R =∑_i = 1^m B_in(C_i)/B_in(C_i)+B_out(C_i)

Here B_in is the number of edges that connect boundary nodes with nodes in D, B_out is the number of edges that connect boundary nodes with nodes out of D. 

Besides Q and R, two other modularity functions are also noticeable. Luo et al. <cit.> defined a modularity measure M which is defined as the ratio of the number of internal edges to the number of external edges of a community.


    M =∑_i = 1^m E_in(C_i)/E_out(C_i)


In which E_in(C_i) and E_out(C_i) are the number of internal edges and the number of external edges respectively.

And Lancichinetti et al.<cit.> defined a modularity F by comparing the "in-degree" of a community to α power of the "total-degree".


    F = ∑_i = 1^m d_in(C_i)/(d_in(C_i) + d_out(C_i))^α

Here d_in(C_i) denotes the in-degree of community C_i, i.e., twice the number of edges within the community, and d_out(C_i) denotes the out-degree of C_i which is the number of edges connecting nodes in the community with nodes out of the community. The total-degree is the sum of the in-degree and the out-degree. As in literature<cit.>, α is usually set to 1.



§ METHODS




 §.§ A new local centrality indicator
	

To extract central nodes of communities, for each node i in the network, we define a local centrality indicator (LCI) as following:


    LCI_i = k_i - 1/k_i∑_j ∈Γ _ik_j/k_i + 1/k_i∑_j ∈Γ _ik_j.


where k_i and k_j correspondingly represent the degrees of node i and node j, in which node j is a neighbor of node i in the network. Γ_i represents the set of all neighbors of node i. LCI reflects the centrality of each node locally in the network relative to its neighbors. Obviously, the value of LCI is between -1 and 1, and larger LCI indicates higher local centrality. Without loss of generality, in this paper we take nodes with LCI_i ≥ 0 as central nodes for community detection; other nodes are all non-central nodes.





 §.§ A new local modularity function
	

We propose a new local modularity function F2 for community detection. For community C_i in a network, the F2 of C_i is defined as 


    F2(C_i) = [d_in(C_i)]^2/[d_in(C_i) + d_out(C_i)]^2

where  d_in(C_i) and d_out(C_i) are the in-degree and out-degree of community C_i which are identically defined as in modularity F. The modularity F2 for the whole network is defined as the sum of F2 of all communities within the network.


    F2 = ∑_i = 1^mF2(C_i)


This new modularity F2 will be used as an optimal function in our greedy algorithm for community detection.




 §.§ Community detection with a greedy algorithm based on LCI and F2
	

Based on our new centrality indicator LCI and new modularity function F2, we detect communities within a complex network with a greedy algorithm. Detailed procedures are described below.

First of all, we extract all central nodes by LCI_i ≥ 0 in the network. Communities will then expand from these central nodes. 

Then we start the community expansion procedure. Initially, we randomly choose one from the central nodes. We take this node as a seed of a community, say C_1, and start expanding it. At each step of the expansion of C_1, we search in its unassigned neighbors, i.e., nodes that are directly connected to C_1 and haven't been assigned to any community. Our goal is to find one node among all these unassigned neighbors that maximizes the value of F2(C_1), if we add this node to C_1. In case the same maximal F2(C_1) can be obtained by adding different neighbors to C_1, we randomly choose one from these neighbors and add it to C_1. We repeat this step, until community C_1 stops expanding when any possible expansion of C_1 decreases its F2. Then we move on to the next community by randomly choosing another central node, which hasn't been assigned to any community, and expanding it exactly the same way as the expansion of C_1. We repeat this process, until all communities stop expanding, and there is no central nodes left unassigned in the network. It should be noted that in the above procedure, the order of choosing central nodes is random so that the order of expansions of different communities is random too. In principle, different orders may have different outputs. However, to our investigation, although the number of possible arrangements of orders is huge, these different arrangements only result in finite numbers of possible outputs. In practice, we usually implement the community expansion procedure for a number of times, and take the output with the highest F2 as the final output. 

Once the community expansion procedure is done, most nodes in the network should have been assigned to different communities. However, there may still exist a very small number of non-central nodes that remain unassigned. For each of these unassigned nodes, we search in its neighbors and find out the one with the highest LCI. We arbitrarily merge this unassigned node to the same community as its neighbor with the highest LCI. It should be noted that this operation may decrease the final F2 of the network, however it is reasonable because community structure with exactly the highest value of modularity function might be an overfit, as discussed in<cit.>. 





An intuitive exhibition of the above procedures can be found in figure 1.


To make our algorithm clear, we execute the algorithm on the example network in figure 1. Starting from central nodes 5, 6, 8, 10 randomly, different community structures are constructed by greedy algorithm. The community structure with maximal network modularity contains two communities C_1={3,4,5,6}, C_2={7,8,9,10} and two left nodes 1,2. Next, nodes 1, 2 are arranged to the community C_2 and C_1 respectively which is indicated by dash arrows, because the central value of the node 10 belonging to C_2 is larger than the other neighbors of node 1 and the central value of the node 5 in C_1 is larger than the other neighbors of node 2. Finally, two communities C_1={2,3,4,5,6}, C_2={1,7,8,9,10} are constructed.


For figure 3(a), there are three central nodes 2,6,10. Their central values are 0.6, 0.125, 0.125. Starting from these central nodes randomly and executing the process of greedy optimal algorithm of local modularity F2, we can obtain the community structure with maximal modularity F2=2.322 which is composed of three communities C_1={2,3,4,5}, C_2={6,7,8}, C_3={9,10,11} and a left node 1. Among the neighbors of the node 1, the node 2 has maximal central value, so the left node 1 should be arranged to the community C_1.

In figure 3(b), starting from central nodes 1,2,6,10,14 randomly, different community structures are constructed by greedy algorithm. The community  structure with maximal network modularity F2=3.4087 contains five communities C_1={2,3,4,5}, C_2={6,7,8,9}, C_3={10,11,12,13}, C_4={14,15,16,17} and C_5={1}. Here, node 1 has the role of community bridge, however it is a central node rather than a left node. So the node 1 construct a single community.

In figure 3(c), the community structure with maximal modularity contains C_1={3,4,5,6}, C_2={7,8,9,10} and two left nodes 1,2 by greedy algorithm starting from central nodes 5, 6, 8, 10 randomly. The left nodes 1, 2 should be arranged to the community C_2 and C_1 respectively, because the central value of the node 10 belonging to C_2 is larger than the other neighbors for node 1 and the central value of the node 5 in C_1 is larger than the other neighbors for node 2. 

For figure 3(d), the central nodes are 1,2,3,6,11,12,16,19. We can also obtain different community structures by greedy algorithm. Finally we select the community structure with maximal network modularity F2=4.5193 as the result of community expansion which is composed of C_1={1,2}, C_2={3,4,5}, C_3={6,7,8}, C_4={9,10,11}, C_5={12,13,14}, C_6={15,16,17} and C_7={18,19,20}. In this community structure, the community C_1 containing two central nodes plays the role of community bridges. They construct a community.

For these four example networks with clear community structure, we execute the same algorithm by different modularity functions F, M, R and Q. Only modularity Q has the difference that it will merge several small communities to one community for figure 3(b) and 3(d). The other results are all correct and are the same to the results given by modularity F2. 

Through the example networks, it is found that the algorithm based on the new local central indicator and local modularity F2 can identify the community structure correctly. After the expansion, the number of communities is determined. If there are left nodes, they are allocated to the communities with central nodes because their influences are too weak and usually are influenced by the other nodes. It is seen that sometimes the left nodes are the community bridge nodes which are the nodes connecting to multiple communities<cit.> such as the node 1 in figure 3(a) and the nodes 1, 2 in figure 3(c). Besides it is possible that the community constructed by central nodes play the role of community bridges, such as the node 1 in figure 3(b) and the nodes 1, 2 in figure 3(d). 








§ RESULTS




 §.§ Performance of the local centrality indicator (LCI)


A noticeable advantage of the local centrality indicator (LCI) is, it does not miss local central nodes with low degrees. In contrast, the global maximal degree and local maximal degree indicators would more or less have the problem.  Figure 1 shows an example: the network is constructed by two complete graphs connected through one edge only. Obviously each complete graph constitutes a community, and nodes 1 and 2 are central nodes. However, a global maximal degree indicator which extracts the top k highest degree nodes as central nodes, tends to equate node 2, which is a central node, with non-central nodes 3, 4 and 5.  As shown in figure 1(a), when k=1, node 2 will be classified as a non-central node; when k=2-5, not only node 2 but also nodes 3-5, are identified as central nodes. In both cases, the global maximal degree indicator fails to recognize the difference between the centrality of node 2 and the centrality of nodes 3-5. On the other hand, when two central nodes of different degrees are connected to each other, a local maximal degree indicator would fail to identify the one with lower degree as a central node, as node 2 in figure 1(b). In contrast, our LCI correctly identifies node 1 and 2 as central nodes. The local centrality of a node can be well measured by LCI in figure 1(c).





 §.§ Performance of the new modularity function F2


Modularity functions are customarily used as optimal functions for community detection. Comparing to previous modularity functions, such as Q, M and F, our modularity function F2 has certain advantages. It can be theoretically proven that a random network or a complete graph can't be divided into any two parts (See appendix). Unlike Q and M, which both have a resolution limit problem<cit.>, our F2 identifies small cliques well. In figure 2(a), we constructed a network with a series of p-cliques connected to a ring with single edges; each p-clique is a complete graph containing p nodes and p(p-1)/2 edges. Obviously, such a network has a clear community structure that each clique corresponds to a community. For such a network, F2 identifies each p-clique as an individual community.However, Q and M tend to merge adjacent cliques into a bigger community, as shown by the dashed ovals in figure 2(a). In previous literature, this is called a "resolution limit problem" of Q and M<cit.>. In contrast, F2 does not have the resolution limit problem; it always identifies single cliques rather than merged ones as communities; a theoretical proof can be found in Appendix A.

When the network is constructed by cliques of different sizes, Q and M still have a resolution limit problem on smaller cliques. As in figure 2(b), the network is constructed by two 6-cliques and two 3-cliques. In this case, Q and M can identify the 6-cliques as individual communities, but still tend to merge the 3-cliques into a bigger community. In contrast, F2 still identifies all four cliques as individual communities, regardless of their sizes. More theoretical proofs can be found in Appendix A.

On the other hand, when between-clique edges increase so that different cliques tend to be well connected, F2 can avoid splitting a well-connected community into smaller ones. Figure 2(c) shows such an example: each 4-clique has 6 inner edges but up to 10 between-clique edges; such a network has been recognized as a well-connected network in previous literature<cit.>.In this case, Q and F still tend to split the whole network into two communities, each consisting of a 4-clique, while F2 merges these two 4-cliques and identifies the whole network as a community. 


If the modularity is used as optimal function, intuitively the larger the network modularity F2 is, the more significant the community structure is. As an optimal function, the modularity F2 can overcome the resolution problem and avoid dividing a big community, such as a clique, to smaller communities. Besides, by F2 modularity function, a random network can't be divided to any two parts. (See the detailed proof in appendix)

Furtherly, compared with the modularity functions Q<cit.>, M<cit.>, F<cit.>, R<cit.>, modularity F2 has more ability to identify community structure for the majority of networks due to three advantages below. 

(a) The modularity F2 can identify small cliques. In figure 3(a), a network<cit.> is constructed by a ring with p-cliques connected through single links where each p-clique is a complete graph containing p nodes and p(p-1)/2 edges. Obviously, the network has the clear community structure where each clique corresponds with a community. For such network, modularity F2 will not merge two cliques into one community. Assuming the network contains 10 3-cliques, we construct two kinds of community structures as shown in figure 3(a). One kind is that each clique is a single community. The other kind is that two adjacent cliques is merged. The values of Q, M, F2, for two kinds of structures, are listed in single column and merge column at the table of figure 3(a). It is seen that the value of modularity F2 is larger for the single column than the merge column so that the correct community structure can be detected by F2. However, Q and M obtain the reverse results. Therefore, F2 has better identification ability under this condition. The theoretical proof is taken on at the appendix A when any h adjacent cliques are merged or each clique is a community. 

(b) The modularity F2 can distinguish the communities with different scales. In figure 3(b), the p-clique and q-clique have the same definition<cit.> as figure 3(a). When the difference of p and q is enough large, F2 can still identify the smaller community which is constructed by a single q-clique. However, Q and M can't identify. For example, when p=6 and q=3, the values of modularity functions Q, M, F2 are listed at table of figure 3(b). Obviously the F2 supports every q-clique as a single community. However, Q and M approve two small q-cliques being merged. More theoretical proof is taken on at the appendix A for the network with any value of p and q when p>q.  

(c) the F2 modularity can avoid splitting a well connected communities into several smaller communities. In figure 3(c), a well connected network is composed of a single big community containing all eight nodes<cit.>. It is shown that Q and F tend to divide the network to two communities each containing four nodes and F2 approves the whole network as a big community from the values of Q, F and F2 at the table. Obviously, compared with Q and F, F2 can identify the community structure correctly.
















 §.§ Community detection on several example networks


To show the effectiveness of the algorithm based on modularity F2, we execute our algorithm on several example networks in figure 3.

For figure 3(a), there are three central nodes 2,6,10. Their central values are 0.6, 0.125, 0.125. Starting from these central nodes randomly and executing the process of greedy optimal algorithm of local modularity F2, we can obtain the community structure with maximal modularity F2=2.322 which is composed of three communities C_1={2,3,4,5}, C_2={6,7,8}, C_3={9,10,11} and a left node 1. Among the neighbors of the node 1, the node 2 has maximal central value, so the left node 1 should be arranged to the community C_1.

In figure 3(b), starting from central nodes 1,2,6,10,14 randomly, different community structures are constructed by greedy algorithm. The community  structure with maximal network modularity F2=3.4087 contains five communities C_1={2,3,4,5}, C_2={6,7,8,9}, C_3={10,11,12,13}, C_4={14,15,16,17} and C_5={1}. Here, node 1 has the role of community bridge, however it is a central node rather than a left node. So the node 1 construct a single community.

In figure 3(c), the community structure with maximal modularity contains C_1={3,4,5,6}, C_2={7,8,9,10} and two left nodes 1,2 by greedy algorithm starting from central nodes 5, 6, 8, 10 randomly. The left nodes 1, 2 should be arranged to the community C_2 and C_1 respectively, because the central value of the node 10 belonging to C_2 is larger than the other neighbors for node 1 and the central value of the node 5 in C_1 is larger than the other neighbors for node 2. 

For figure 3(d), the central nodes are 1,2,3,6,11,12,16,19. We can also obtain different community structures by greedy algorithm. Finally we select the community structure with maximal network modularity F2=4.5193 as the result of community expansion which is composed of C_1={1,2}, C_2={3,4,5}, C_3={6,7,8}, C_4={9,10,11}, C_5={12,13,14}, C_6={15,16,17} and C_7={18,19,20}. In this community structure, the community C_1 containing two central nodes plays the role of community bridges. They construct a community.

For these four example networks with clear community structure, we execute the same algorithm by different modularity functions F, M, R and Q. Only modularity Q has the difference that it will merge several small communities to one community for figure 3(b) and 3(d). The other results are all correct and are the same to the results given by modularity F2. 

Through the example networks, it is found that the algorithm based on the new local central indicator and local modularity F2 can identify the community structure correctly. After the expansion, the number of communities is determined. If there are left nodes, they are allocated to the communities with central nodes because their influences are too weak and usually are influenced by the other nodes. It is seen that sometimes the left nodes are the community bridge nodes which are the nodes connecting to multiple communities<cit.> such as the node 1 in figure 3(a) and the nodes 1, 2 in figure 3(c). Besides it is possible that the community constructed by central nodes play the role of community bridges, such as the node 1 in figure 3(b) and the nodes 1, 2 in figure 3(d). 






 §.§ Community detections in real-world networks with a greedy algorithm employing LCI and F2


Three real-world networks are customarily  used to estimate the performance of a community detection method: the Zachary's karate club network<cit.>, the dolphin network<cit.>, and the college football network<cit.>; parameters of these networks are all listed in table 1. In this section, we will examine on these real-world networks the performance of our greedy algorithm for community detection based on LCI and F2.


  

For the karate network, among all 34 nodes five nodes have positive LCI values, which are nodes 34, 1, 33, 2 and 3, with LCI values 0.6328, 0.5754, 0.4049, 0.2180 and 0.2048 respectively. These nodes are identified as central nodes of the network. Then we implement a greedy algorithm to maximize the F2 of the network, and obtain two communities:  C_1={1,2,3,4,8,14,18,20,22}, C_2={9,10,15,16,19,21,23,24,27,28,30,31,33,34} in figure 3. And there are nine nodes (grey nodes in figure 3) left unassigned to either C_1 or C_2. Among them, nodes 5, 6, 7 and 11 are neighbors of node 1; these nodes are later assigned to community C_1. Samely, nodes 29 and 32 are neighbors of node 34, and are assigned to community C_2. For the rest three nodes, nodes 17, 25 and 26, node 17 is allocated to community C_1 through node 6, while nodes 25 and 26 are allocated to community C_2 through node 32. The final result of our community detection on the karate network suggests that the karate network contains two communities: C_1={1,2,3,4,8,14,18,20,22,5,6,7,11,17} and C_2={9,10,15,16,19,21,23,24,27,28,30,31,33,34,25,26,29,32}, which consist of 16 and 18 nodes respectively. This result is consistent with the observation of Zachary.   

For the dolphins network, following exactly the same procedures, we obtained 19 central nodes, and five communities, as shown in figure 4. In contrast, previous literature such as<cit.> typically splits the dolphins network into four communities. Among them, one community is exactly identical  to our community C_1, and other two communities are very close to our communities C_2 and C_3, except that three nodes, 40, 54 and 62, are allocated to community C_2 in <cit.>. In our communities, nodes, 54 and 62 are contained in community C_3, while node 40 is contained in community C_5. We believe that allocating these two nodes to community C_3 is reasonable because node 62 represents a male dolphin, while the gender of node 54 is unknown; allocating these two nodes to community C_3 makes the number of female dolphins, which is dominant in community C_2, grow. The last community in  <cit.> is technically a combination of our C_4 and C_5 without node 40. In a higher level of community structure detected in  <cit.>, not only C_4 and C_5, but also C_1, C_2 and C_3 are combined into one bigger community. As a result, the whole network is alternatively split into two communities: C_1+C_2+C_3, and C_4+C_5, in which node 40 belongs to the former community. To our viewpoint, such a higher level of community structure has a lower value of F2 than our community structure, but it is also reasonable. Finally, as for node 40, it has only two neighbors in the whole network, node 37 and node 58. We choose to allocate it to community C_2 since its neighbor in C_2, node 58, has a higher value of LCI than node 37, which is in a different community.







On the football network, communities obtained by our algorithm also show minor differences only to the reference community structure reported in <cit.>. Among the total 115 nodes of the network, which distribute in 12 communities, only 8 nodes, 29, 37, 43, 60, 64, 91, 98, 111, are allocated to different communities in our result than in <cit.>. Specially, in <cit.> nodes 37, 43 and 91 are allocated to the same community as nodes 81 and 83. However, there is no connections at all between the former three and latter two nodes. In contrast, our algorithm classifies nodes 81 and 83 as an individual community, while allocates nodes 37, 43 and 91 to other communities that they are actually connected to. Such a result, as we believe, should be more reasonable. 









 §.§ the performance of our community detection algorithm
     

We also applied the normalized mutual information (NMI) on benchmark networks to evaluate the performance of our community detection algorithm.  

Normalized mutual information (NMI) <cit.> is an evaluation indicator that measures the performance of a community detection algorithm. On a given network, it compares the community structure detected by a certain algorithm to a standard community structure of the same network, which is used as a reference. We firstly produce a confusion matrix N, its element N_ij on the ith row and jth column represents the number of nodes contained in the intersection between the  ith community of the reference, and the jth community detected by the algorithm to be evaluated. If N stands for the total number of nodes within the network, then NMI is defined as


    NMI =  - 2∑_i = 1^C_r∑_j = 1^C_fN_ijN/N_i.N_.j/∑_i = 1^C_rN_i.log (N_i./N) + ∑_j = 1^C_fN_.jlog (N_.j/N)

in which C_r indicates the number of reference communities. C_f denotes the number of communities detected by the algorithm to be evaluated. N_i. and N_.j stand for the sums of all elements in the ith row of jth column of N respectively. When the detected communities are exactly identical to the reference, NMI=1; on the other hand, when the detected communities are totally independent to the reference, NMI equals to 0. Therefore, NMI reflects the amount of information on the community structure that is correctly extracted by the given algorithm; it is widely used to evaluate the performance of a community detection algorithm.

One kind of classical benchmark networks are LFR networks<cit.>. For LFR networks, degrees of nodes are distributed according to power law with exponent 
2<γ<3 and the sizes of communities also obey the power law distribution with exponent 1<β< 2. 

Besides, the community size s and node degree k satisfy the constraint s_min>k_min and s_max>k_max. An important mixing parameter μ represents the ratio between the external degree of a node with respect to its community and the total degree of the node.  As the value of μ gets large, the community structure of network becomes ambiguous. 

Now, we can detect the community structure on the LFR network with our greedy algorithm employing LCI and F2, and then calculate the NMI to evaluate the performance of the algorithm. Figure 6(a) shows the NMI varying with the increase of the mixing parameter μ on the LFR networks; network parameters are as following: total number of nodes N=500, 1000, 2000 and 5000, average degree  ⟨ k⟩=20, γ=2.5, β=1.5. When μ is small, the NMI is close to 1. With the increase of μ, the community structure becomes more and more ambiguous and hard to detect, the NMI gradually decreases. Figure 6(a) shows that our method performs better on larger networks. The reason is, with the same average degree  ⟨ k⟩, larger networks usually contain more communities. Under the same value of μ, the external links from a node within a certain community tend to be distributed to different other communities. Relatively, the internal links from the same node will appear more concentrated, which makes the community structure more distinct and easy to detect. In figure 6(b), we compare the NMIs with N=500 for community detection algorithms based on different modularity functions, Q, F, M, R,and F2. Obviously, the algorithm based on F2 performs the best since it shows the highest NMI.

NMI can also be calculated for the real-world networks. Using the community structures suggested in <cit.> as references, our communities detected for the karate network, the dolphins network and the football network respectively show the following NMIs: 1 for karate, 0.8904 for dolphins, and 0.9429 for football (see table 1). Obviously communities detected by our method are all highly consistent with the reference communities suggested in previous literature. 






§ CONCLUSION


In this paper, we proposed a new community detection method to identify local communities within complex networks. We firstly suggested a new local centrality indicator (LCI) to extract local important nodes that are well distinguished from their neighbors. Compared with the global maximal degree and local maximal degree indicators<cit.>, our LCI extracts central nodes that can be directly connected but have different degrees. Then we proposed a new local modularity function F2.  F2 can overcome certain problems of other modularity functions such as the resolution limit problem. Both theoretical deductions and numerical simulations suggest that F2 identifies communities, as well as the widely-used modularity functions Q, M, F, R. In certain cases, F2 performs even better than Q, M, F and R. Incorporated to a greedy algorithm, LCI and F2 identify communities within a complex network  automatically. On both the real-world networks and the computer simulated benchmark networks, our method shows high performance of identifying community structures. 

Through proper revisions, our modularity function F2 can be easily extended to directed or weighted networks, or to deal with communities that have overlaps. With the development of big data, computation efficiency has become a coming demand. On the other hand, dynamical networks and dynamical community detection has also become a worthwhile research area. In interdisciplinary area, community detection has been applied to find the pathways between given diseases and drugs<cit.>, and to reveal the role of each part of a layered neural network by analyzing communities extracting from the trained network<cit.>. Community detection is also employed to mine user opinions from social networks<cit.>. Besides, modularity functions can be used to assess the training results for neural networks<cit.>. Our study on the modularity function F2 may hopefully lead to further researches that might be worth pursuing. 


Many local algorithms of community detection have been proposed. Among these algorithms, the greedy algorithm has attracted much attention. It has two key factors. One is the starting nodes of expansion, the other is the optimization function. These two factors are very useful to improve the effectiveness of community detection algorithm. Here, we designed a new local central indicator to measure the outstanding of a node relative to its neighbors. Compared with the global maximal degree and local maximal degree indicators<cit.>, it can find two central nodes connected directly which have different degrees. Besides, we have also proposed the new local modularity  F2. The modularity F2 can overcome some problems of other modularity functions such as resolution problems. Both theories and experiments suggest that the modularity F2 has better identification ability of communities than modularity functions Q, M, F, R.

In the greedy algorithm, the expansion process automatically determines the number of communities. The final community structure is obtained after the left nodes are allocated according to the central values of nodes. Experiments on both the ground truth networks and computer-generated networks show that the new algorithm has powerful ability to identify the community structure. Even though, It is sitll chanllenging to detect real community structure of networks. The more suitable central node identificaiton indicator and better modularity function are also worthy of futher development .

Our modularity function can be extend to the directed and weighted cases or is revised to partition the network with overlapping communities in the further researches. Due to the development of big data, the methods with higher efficiency are desired. Besides, the real network is dynamic, so the dynamic version of community detection methods is worth to explore.  Moreover, the community detection has been applied to the finding of the pathways for given diseases and drugs<cit.> and to reveal the role of each part of a layered neural network by analyzing communities extracting from the trained network<cit.>. Community detection is also employed to mine user opinions from social networks<cit.>. Besides, modularity has also been used to assess the training results for neural network<cit.>. We may dig out the more applied fields related to community detection. 




§ ACKNOWLEDGEMENTS

tocsectionAcknowledgements
This work was supported by the National Natural Science Foundation of China with Grant No. 61673085, 61703074, the "Thousand Talents Program" of Sichuan Province with Grant No.17QR003 , P.R. China and the fund of the Education Department of Sichuan Province with Grant No.13ZA0168.




§ APPENDIX. CHARACTERISTICS OF THE MODULARITY FUNCTION F2


(1) A random network can't be partitioned to two separated communities. When the whole network is considered as one community, F2_single=1. When it is divided into any two parts, which contain n_1 and n_2 nodes respectively, the modularity function F2 can be calculated as 




    [                                 F2_merge = [ n_1(n_1 - 1)p/n_1(n_1 - 1)p + n_1n_2p]^2 + [ n_2(n_2 - 1)p/n_2(n_2 - 1)p + n_1n_2p]^2; 1pt 1pt 1pt 1pt 1pt 1pt 1pt 1pt 1pt 1pt 1pt 1pt 1pt 1pt 1pt 1pt 1pt 1pt  = ( n_1 - 1/n_1 + n_2 - 1)^2 + ( n_2 - 1/n_2 + n_1 - 1)^2;               1pt 1pt 1pt 1pt 1pt 1pt 1pt 1pt 1pt 1pt 1pt 1pt 1pt 1pt 1pt 1pt  = n_1^2 + n_2^2 - 2n_1 - 2n_2 + 2/(n_1 + n_2 - 1)^2;                                   1pt 1pt 1pt 1pt 1pt 1pt 1pt 1pt 1pt 1pt 1pt 1pt 1pt 1pt 1pt  = 1 - 2n_1n_2 - 1/(n_1 + n_2 - 1)^2;                                                                       1pt 1pt 1pt 1pt 1pt 1pt 1pt 1pt 1pt 1pt 1pt 1pt 1pt 1pt  < 1 ]


(2) A complete network can't be partitioned to two communities, Obviously, the F2 for a complete network identified as a single community is F2_single=1.If
the network is divided to any two communities which include n_1 and n_2 nodes respectively, the F2 can be calculated as 




    [                                        F2_merge = [ n_1(n_1 - 1)/n_1(n_1 - 1) + n_1n_2]^2 + [ n_2(n_2 - 1)/n_2(n_2 - 1) + n_1n_2]^2; 1pt 1pt 1pt 1pt 1pt 1pt 1pt 1pt 1pt 1pt 1pt 1pt 1pt 1pt 1pt 1pt 1pt 1pt 
     = ( n_1 - 1/n_1 + n_2 - 1)^2 + ( n_2 - 1/n_2 + n_1 - 1)^2;                                                              1pt 1pt 1pt 1pt 1pt 1pt 1pt 1pt 1pt 1pt 1pt 1pt 1pt 1pt 1pt 1pt
    
    
     < 1 ]


(3) For a ring network constructed by l p-cliques, similar to the figure 2(a), the network can't two or more cliques into one community. If each community corresponds a single clique, the F2 is,


    F2_single = l ×[ p(p - 1)/p(p - 1) + 2]^2


If we merge h p-cliques into one community, the value of F2 becomes,


    [                                                       F2_merge = N/h[ p(p - 1)h + 2(h - 1)/p(p - 1)h + 2(h - 1) + 2]^2; 1pt 1pt 1pt 1pt 1pt 1pt 1pt 1pt 1pt 1pt 1pt 1pt 1pt 1pt 1pt 1pt 1pt 1pt  = N/h[ p(p - 1)h + 2(h - 1)/p(p - 1)h + 2h]^2;           1pt 1pt 1pt 1pt 1pt 1pt 1pt 1pt 1pt 1pt 1pt 1pt 1pt 1pt 1pt 1pt  = N[ p(p - 1)h + 2h - 2/h^3/p(p - 1) + 2]^2; 1pt 1pt 1pt 1pt 1pt 1pt 1pt 1pt 1pt 1pt 1pt 1pt 1pt 1pt 1pt≤ N[ p(p - 1) + 1/4/p(p - 1) + 2]^2 1pt 1pt 1pt 1pt (h ≥ 2);   1pt 1pt 1pt 1pt 1pt 1pt 1pt 1pt 1pt 1pt 1pt 1pt 1pt 1pt  = N[ p(p - 1) + 1 - 3p(p - 1)/4/p(p - 1) + 2]^2 1pt 1pt 1pt;             1pt 1pt 1pt 1pt 1pt 1pt 1pt 1pt 1pt 1pt 1pt 1pt 1pt 1pt  < N[ p(p - 1)/p(p - 1) + 2]^2 1pt 1pt 1pt (p ≥ 3) ]


(4) Communities with different scales can be identified by F2. As shown in figure 2(b), when two q-cliques are considered as two separated communities, the value of F2 is,


    [                                                                                      F2_single = [ p(p - 1)/p(p - 1) + 1]^2
     +[ p(p - 1)/p(p - 1) + 3]^2
     + 2 ×[ q(q - 1)/q(q - 1) + 2]^2; 1pt 1pt 1pt 1pt 1pt 1pt 1pt 1pt 1pt 1pt 1pt 1pt 1pt 1pt 1pt 1pt 1pt  = 
    [p(p - 1)/p(p - 1) + 1]^2
     +[ p(p - 1)/p(p - 1) + 3]^2
     + [q(q - 1)]^2 + [q(q - 1)] × [q(q - 1)]/[q(q - 1) + 2]^2 ]


However, if two q-cliques are merged into one community, the network has a F2 value


    [                                                                                                                    F2_merge =  [ p(p - 1)/p(p - 1) + 1]^2
     +[ p(p - 1)/p(p - 1) + 3]^2
     + [ 2q(q - 1) + 2/2q(q - 1) + 4]^2;                                                     1pt 1pt 1pt 1pt 1pt 1pt 1pt 1pt 1pt 1pt 1pt 1pt 1pt 1pt 1pt 1pt 1pt 1pt  = 
     [ p(p - 1)/p(p - 1) + 1]^2
     +[ p(p - 1)/p(p - 1) + 3]^2
     + [ q(q - 1) + 1/q(q - 1) + 2]^2;                                       1pt 1pt 1pt 1pt 1pt 1pt 1pt 1pt 1pt 1pt 1pt 1pt 1pt 1pt 1pt 1pt 1pt 1pt  =
     [ p(p - 1)/p(p - 1) + 1]^2
     +[ p(p - 1)/p(p - 1) + 3]^2
     + [q(q - 1)]^2 + 2q(q - 1) + 1/[q(q - 1) + 2]^2; 1pt 1pt 1pt 1pt 1pt 1pt 1pt 1pt 1pt 1pt 1pt 1pt 1pt 1pt 1pt 1pt 1pt  < 
     [ p(p - 1)/p(p - 1) + 1]^2
     +[ p(p - 1)/p(p - 1) + 3]^2
     + [q(q - 1)]^2 + [q(q - 1)] × [q(q - 1)]/[q(q - 1) + 2]^2 1pt 1pt 1pt 1pt 1pt 1pt (q≥ 3) ]





§ APPENDIX B. MODULARITY FUNCTIONS


(1) Modularity Q

The most popular modularity is the Newman's NG modularity Q <cit.> which is formulated as,


    Q =∑_i = 1^m [l_in(C_i)/L- d(C_i)/2L^2]


Where l_in(C_i) is the number of edges that all nodes are in community C_i. d(C_i) is the total degree of all nodes in C_i. L is the number of total edges in a network.

(2)  Modularity F

in paper <cit.>, the F function is defined,


    F = ∑_i = 1^m d_in(C_i)/(d_in(C_i) + d_out(C_i))^α


Where d_in(C_i) is the in-degree i.e. the twice number of edges in a community, and d_out(C_i)  indicate the out-degree which is the number of edges connecting nodes in a community with the nodes out of the community..

(3) Modularity M

Luo et al <cit.> proposed a modularity measure M which is defined as the ratio of the number of internal edges and the external edges of a community.


    M =∑_i = 1^m E_in(C_i)/E_out(C_i)


E_in(C_i) and E_out(C_i) indicates the number of internal edges and the external edges repectively.

(4) Modularity R

For a network, the known portion is denoted set D. D has two subsets, one is the core nodes set C which only include the nodes connected by internal edges. Another set is the boundary nodes set B. The nodes in B connect with one external node at least. Clauset defined the local modularity R as,


    R =∑_i = 1^m B_in(C_i)/B_in(C_i)+B_out(C_i)


Where B_in is the number of edges that connect boundary nodes and nodes in D. B_out is the number of edges which connect boudary nodes and the nodes out of D. 



§ APPENDIX B. THE NORMALIZED MUTUAL INFORMATION NMI


NMI is an evaluation indicator used to measure the performance of community detection algorithms. Given the confusion matrix N where rows and columns denote the reference communities and the found communities respectively. The element N_ij represents the number of nodes in the reference community i that appear in the found community j. N is the number of nodes in the network. The NMI is defined as follows,


    NMI =  - 2∑_i = 1^C_r∑_j = 1^C_fN_ijN/N_i.N_.j/∑_i = 1^C_rN_i.log (N_i./N) + ∑_j = 1^C_fN_.jlog (N_.j/N)


Where C_r, C_f indicate the number of reference communities and found communities. N_i. is the sum over row i of N_ij and N_.j is the sum over column j of  N_ij.
The NMI takes the maximal value 1 if the found communities are identical with the reference communities and it is 0 if the found communities are totally independent of reference communities.  It can measure the amount of information correctly extracted by the algorithm.





§ REFERENCES

tocsectionReferences

100


Mucha2010 Mucha O J Richardson T Macon k Porter M A and Onnela J P 2010 Proc. Natl. Acad. Sci.Science  328 876–878.
Zachary1977 Zachary W W 1977 J. Anthropol. Res. 33 452–473.

Girvan2002 Girvan M and Newman M 2002 Proc. Natl. Acad. Sci.  99 7821–7826.
Lusseau2004 Lusseau D and Newman M E J 2004 Proc. R. Soc. Lond B (Suppl.) 271 S477–S481.
Jonsson2006 Jonsson P F Cavanna T Zicha D and Bates P A 2006, BMC Bioinf.  7 2.
Newman2004a Newman M and Girvan M 2004 Physical review. E  69 026113.
Fortunato2010 Fortunato S 2010 Physics Reports  486 75–174.

Ciglan2013 Ciglan M Laclavík M and Nørvag K 2013 in Proceedings of the 19th ACM SIGKDD International Conference on
Knowledge Discovery and Data Mining. ACM  1007–1015.
Hakami2011 Hakami Zanjani A A and Darooneh A H 2011  Physical review. E  84 036109.

Shi2011 Shi J and Malik J, 2000 IEEE Trans.Pattern Anal. Mach. Intell. 22 888–905.

Donetti2004 Donetti L and  Mutildenoz M A 2004 J. Stat. Mech. P10012.
Capocci2005 Capocci A Servedio V D P Caldarelli G and Colaiori F. 2005 Physica A  352 669–672.
Jin2015 Jin J, Jin J, 2015  The annals of Statistics/ 43 57-89.
Newman2007 Newman, M E J and Leicht E A  2007  Proc. Natl. Acad. Sci. 104 9564–9569.
Zhou2003Zhou H 2003, Phys. Rev. E  67 061901.

Hu2008 Hu Y Chen H Zhang P Li M Di Z and Fan Y 2008 Phys. Rev. E 78 026121.



Srinivas2019 Srinivas S and Rajendran C 2019 Expert System with Applications  135 296–312.


Newman2004b Newman M E J 2004 Physical review. E  69 066133.
Clauset2004 Clauset A Newman M E J and Moore C 2004 Physical review. E  70 066111.
Saha2016 Saha S and SantoGhrera S P 2016 Information  7 1-16.
Chen2013 Chen Q Wu T T and Fang M 2013 Physica A  392 529–537.


Duch2005 Duch J and Arenas A 2005 Physical review. E  72 027104.
Blondel2008 Blondel V D Guillaume J L and Lambiotte R 2008 J. Stat. Mech. P10008.
Li2008 Li Z Zhang S Wang R S, Zhang X S and Chen L 2008 Physical review. E  77 036109.
Li2015 Li Z Zhang S Wang R-S, X-S Zhang and L Chen 2015 Physical review. E  91 019901.
Aason2005 Aaron C 2005 Physical review. E  72 026132.
Luo2008 Luo F Wang J Z and Promislow E 2008 IEEE/WIC/ACM International Conference on Web Intelligence  387–400.
Lancichinetti2009 Lancichinetti A, Fortunato S and  Kertész, János 2009 New Journal of Physics  11 19–44.
Kuncheva2004 Kuncheva L I and Hadjitodorov S T 2004 Systems, Man and Cybernetics IEEE Int. Conf. 2 1214.
lu2016 Lü L Y, Chen D B, Ren X L, Zhang Q M, Zhang Y C and Zhou T 2016 Physics Reports   650 1-63.
Blondel2008b Blondel V D Guillaume J L and Lambiotte R 2008 Physical review. E   77 036114.



Santo2007 Fortunato S and Barthélemy M 2007 Proc. Natl. Acad. Sci. U.S.A. 104 36–41.

Arenas2007 Arenas A, Fernández A and Gómez S 2007 New Journal of Physics  10 053039. 


Andrea2011 Andrea L and Santo F 2011 Physical review. E  84 066122.
Chen2013b Chen M Nguyen T and Szymanski B K 2013 ASE Human Journal  2 226–240.
Chen2014 Chen M Kuzmin K and Szymanski B K 2014 IEEE Trans. Computation Social System  1 46–65.
Dzamic2020 Džamić D Pei J Marić M Mladenović N and Pardalos P M 2020  Intl. Trans. in Op. Res.  27 245–266.
Guimera2004 Guimerà R Sales-Pardo M and Amaral L A N 2004 Physical review. E   70 025101.
Reichardt2006 Reichardt J and Bornholdt S 2006 Physical review. E   74 016110.




Zhang2014 Zhang P and Moore C 2014  Proc. Natl. Acad. Sci. 111 18144–18149.




Lancichinetti2008 Lancichinetti A, Fortunato S and Radicchi F 2008 Physical review. E   78 046110.



Pham2019 Pham M, Wilson S, Govindarajan H 2019  Bioinformatics. 857 

Watanabe2019 Watanabe, C., Hiramatsu, K. and Kashino K 2019  Neurocomputing 367 84–102.
Li2019 Li C Bai J Zhang L Tang H and Luo Y 2019  Information Sciences 504 61-83.


Watanabe2018 Watanabe C, Hiramatsu K and Kashino K 2018  Neural Networks 97 62–73.








