Introduction
Many networks, including Internet, citation networks, transportation networks, email networks, and social and biochemical networks, display community structure which consists of groups of nodes within which connections are denser than between them [1]. Detecting and characterizing such community structure, which is known as community detection, is one of the fundamental issues in the study of network systems. Community detection has been shown to reveal latent yet meaningful structure in networks such as groups in online and contact-based social networks, functional modules in protein–protein interaction networks, groups of customers with similar interests in online retailer user networks, groups of scientists in interdisciplinary collaboration networks, etc. [2].
In the last decade, the most popular community detection methods have been to maximize the quality metric known as modularity [1], [3]–[4][5] over all possible partitions of a network. Such modularity optimization algorithms include greedy algorithms [6]–[7][8][9], spectral methods [3], [10]–[11][12][13][14][15], extremal optimization (EO) [16], simulated annealing (SA) [17]–[18][19][20], sampling technique [21], and mathematical programming [22]. Modularity measures the difference between the actual fraction of edges within the community and such fraction expected in a randomized graph with the same number of nodes and the same degree sequence. It is widely used as a measurement of strength of the community structures detected by the community detection algorithms. However, modularity maximization has two opposite yet coexisting problems. In some cases, it tends to split large communities into two or more small communities [23], [24]. In other cases, it tends to form large communities by merging communities that are smaller than a certain threshold which depends on the total number of edges in the network and on the degree of inter-connectivity between the communities. The latter problem is also known as the resolution limit problem [23]–[24][25].
To solve these two issues of modularity, several community quality metrics were introduced, including Modularity Density
Review of Modularity Related Literature
In this section, we first review the definition of modularity and the corresponding optimization approaches. Then, we discuss the two opposite yet coexisting problems of modularity maximization. Finally, we overview several community quality measurements proposed to solve the resolution limit problem and then discuss Modularity Density (
A. Definition of Modularity
Comparing results of different network partitioning algorithms can be challenging, especially when network structure is not known beforehand. A concept of modularity defined in [1] provides a measure of the quality of a particular partitioning of a network. Modularity (
Formally, modularity (
Q = \sum\limits_{{c_i} \in C} \left[{{{\vert {E_{{c_i}}^{{\rm in}}} \vert} \over {\vert E \vert}} - {{\left({{{2\vert {E_{{c_i}}^{{\rm in}}} \vert + \vert {E_{{c_i}}^{{\rm out}}} \vert} \over {2\vert E \vert}}} \right)}^2}} \right]\eqno{\hbox{(1)}}where Modularity can also be expressed in the following form [3]:
Q = {1 \over {2\vert E\vert}}\sum\limits_{ij} \left[{{A_{ij}} - {{{k_i}{k_j}} \over {2\vert E\vert}}} \right]{\delta _{{c_i},{c_j}}}\eqno{\hbox{(2)}}where Since larger
The modularity measure defined above is suitable only for undirected and unweighted networks. However, this definition can be naturally extended to apply to directed networks as well as to weighted networks. Weighted and directed networks contain more information than undirected and unweighted ones. While this additional information makes such networks more valuable, it also makes them more difficult to analyze.
The revised definition of modularity that works for directed networks is as follows [4]:
Q = {1 \over {\vert E\vert}}\sum\limits_{ij} \left[{{A_{ij}} - {{k_i^{{\rm in}}k_j^{{\rm out}}} \over {\vert E\vert}}} \right]{\delta _{{c_i},{c_j}}}\eqno{\hbox{(3)}}where Although many networks can be regarded as binary, i.e., as either having an edge between a pair of nodes or not having it, there are many other networks for which it would be natural to treat edges as having a certain degree of strength or weight.
The same general techniques that have been developed for unweighted networks are applied to its weighted counterparts in [5] by mapping weighted networks onto multigraphs. For non-negative integer weights, an edge with weight
It is necessary to point out that the notion of degree of a node should also be extended for the weighted graphs. In this case, degree of a node is defined as the sum of weights of all edges incident to this node.
It is shown in [5] that the same definitions of modularity that were given above hold for the weighted networks as well, if we treat
B. Modularity Optimization Approaches
In the literature, a high value of modularity (
1. Greedy Algorithms
The first greedy algorithm was proposed by Newman [6]. It is a agglomerative hierarchical clustering method. Initially, every node belongs to its own community, creating altogether
\Delta {Q_{{c_i},{c_j}}} = 2\left({{{\vert{E_{{c_i},{c_j}}}\vert} \over {2\vert E\vert}} - {{\vert{E_{{c_i}}}\vert\vert{E_{{c_j}}}\vert} \over {4\vert E{\vert^2}}}} \right),\eqno{\hbox{(4)}}where Although Newman's algorithm [6] is much faster than the algorithm of Newman and Girvan [1] whose complexity is
However, Wakita and Tsurumi [8] observed that the greedy algorithm proposed by Clauset et al. is not scalable to networks with sizes larger than 500 000 nodes. They found that the computational inefficiency arises from merging communities in an unbalanced manner, which yields very unbalanced dendrograms. In such cases, the relation
Another type of greedy modularity optimization algorithm different from those above was proposed by Blondel et al., and it is usually referred to as Louvain [9]. It is divided into two phases that are repeated iteratively. Initially, every node belongs to the community of itself, so there are
After the first phase, Louvain reaches a local maximum of
2. Spectral Methods
There are two categories of spectral algorithms for maximizing modularity: 1) based on the modularity matrix [3], [10], [11]; and 2) based on the Laplacian matrix of a network [12]–[13][14].
a) Modularity optimization using the eigenvalues and eigenvectors of the modularity matrix [3], [10], [11]
Modularity (
\eqalignno{Q &= {1 \over {4\vert E\vert}}\sum\limits_{ij} \left({{A_{ij}} - {{{k_i}{k_j}} \over {2\vert E\vert}}} \right)({s_i}{s_j} + 1) \cr &= {1 \over {4\vert E\vert}}\sum\limits_{ij} \left({{A_{ij}} - {{{k_i}{k_j}} \over {2\vert E\vert}}} \right){s_i}{s_j} = {1 \over {4\vert E\vert}}{{\mbi {s}}^T}{\mbi {Bs}} &\hbox{(5)}}where {B_{ij}} = {A_{ij}} - {{{k_i}{k_j}} \over {2\vert E\vert}}.\eqno{\hbox{(6)}}Representing
Q = {1 \over {4\vert E\vert}}\sum\limits_i {a_i}{{\mbi {u}}_{\mbi {i}}}^T{\mbi {B}}\sum\limits_j {a_j}{{\mbi {u}}_{\mbi {j}}} = {1 \over {4\vert E\vert}}\sum\limits_i a_i^2{\beta _i}\eqno{\hbox{(7)}}where \eqalignno{\Delta Q &= {1 \over {2\vert E\vert}}\left[{{1 \over 2}\sum\limits_{i,j \in c} {B_{ij}}({s_i}{s_j} + 1) - \sum\limits_{i,j \in c} {B_{ij}}} \right] \cr &= {1 \over {4\vert E\vert}}{{\mbi {s}}^T}{{\mbi {B}}^{(c)}}{\mbi {s}} &\hbox{(8)}}B_{ij}^{(c)} = {B_{ij}} - {\delta _{ij}}\sum\limits_{k \in c} {B_{ik}}.\eqno{\hbox{(9)}}Then, the same spectral method can be applied to
However, the spectral algorithm described above has two drawbacks. First, it divides a network into more than two communities by repeated division instead of getting all the communities directly in a single step. Second, it only uses the leading eigenvector of the modularity matrix and ignores all the others, losing all the useful information contained in those eigenvectors. Newman later proposed to divide a network into a set of communities
{S_{i,c}} = \left\{\matrix{{1,} \hfill & {\hbox{if node}\ i \ \hbox{belongs to community}\ c} \hfill\cr {0,} \hfill & {\hbox{otherwise}} \hfill\cr } \right.\eqno{\hbox{(10)}}then the modularity (Q = {1 \over {2\vert E\vert}}\sum\limits_{i,j = 1}^{\vert V\vert} \sum\limits_{c \in C} {B_{ij}}{S_{i,c}}{S_{j,c}} = {1 \over {2\vert E\vert}}{\rm Tr}({{\mbi {S}}^T}{\mbi {BS}})\eqno{\hbox{(11)}}Q = {1 \over {2\vert E\vert}}\sum\limits_{i = 1}^{\vert V\vert} \sum\limits_{c \in C} {\beta _i}{({{\mbi {u}}_{\mbi {i}}}^T{{\mbi {s}}_{\mbi {c}}})^2}.\eqno{\hbox{(12)}}Then, obtaining
\eqalignno{Q & = {1 \over {2\vert E\vert}}\left({\vert V\vert\alpha + {\rm Tr}[{{\mbi {S}}^T}{\mbi {U}}({\Sigmab } - \alpha {\mbi {I}}){{\mbi {U}}^T}{\mbi {S}}]} \right) \cr &= {1 \over {2\vert E\vert}}\left({\vert V\vert\alpha + \sum\limits_{j = 1}^{\vert V\vert} \sum\limits_{c \in C} ({\beta _j} - \alpha){{\left[{\sum\limits_{i = 1}^{\vert V\vert} {U_{ij}}{S_{i,c}}} \right]}^2}} \right)\cr & &\hbox{(13)}}where {[{{\mbi {r}}_{\mbi {i}}}]_j} = \sqrt {{\beta _j} - \alpha } {U_{ij}}\eqno{\hbox{(14)}}Q \simeq \mathtilde{Q} = {1 \over {2\vert E\vert}}\left({\vert V\vert\alpha + \sum\limits_{c \in C} \vert{{\mbi {R}}_{\mbi {c}}}{\vert^2}} \right)\eqno{\hbox{(15)}}{{\mbi {R}}_{\mbi {c}}} = \sum\limits_{i \in c} {{\mbi {r}}_{\mbi {i}}}.\eqno{\hbox{(16)}}Thus, the community detection problem is equivalent to choosing such a division of nodes into
Although [10] explored using multiple leading eigenvectors of the modularity matrix, it did not pursue it in detail beyond a two-eigenvector approach for bipartitioning [3], [10]. Richardson et al. [11] provided a extension of these recursive bipartitioning methods by considering the best two-way or three-way division at each recursive step to more thoroughly explore the promising partitions. To reduce the number of partitions considered for the eigenvector-pair tripartitioning, the authors adopted a divide-and-conquer method and as a result yielded an efficient approach whose computational complexity is competitive with the two-eigenvector bipartitioning method.
b) Modularity optimization using the eigenvalues and eigenvectors of the Laplacian matrix [12]–[13][14]
Given a partition
Q \propto {\rm Tr}({{\mbi {S}}^T}({\mbi W} - \mathtilde{\mbi D}){\mbi {S}}) = - {\rm Tr}({{\mbi {S}}^T}{{\mbi {L}}_{\mbi {Q}}}{\mbi {S}})\eqno{\hbox{(17)}}where {{\mbi {L}}_{\bf Q}}{\mbi {S}} = {\mbi {S}}{\Lambdabmit} \eqno{\hbox{(18)}}Based on the above analysis, White and Smyth proposed two clustering algorithms, named “Algorithm Spectral-1” and “Algorithm Spectral-2,” to search for a partition
“Algorithm Spectral-2” starts with a single community (
However, the two algorithms described above, especially “Algorithm Spectral-1,” scale poorly to large networks because of running
Ruan and Zhang later [14] proposed QCUT algorithm whose name is derived from modularity (
c) Equivalence of two categories of spectral algorithms for maximizing modularity [15]
Newman [15] showed that with hyperellipsoid relaxation, the spectral modularity maximization method using the eigenvalues and eigenvectors of the modularity matrix can be formulated as the spectral algorithm that relies on the eigenvalues and eigenvectors of Laplacian matrix. This formulation indicates that the above two kinds of modularity optimization approaches are equivalent. Starting with (5) for the division of a network into two groups, first the discreteness of
\sum\limits_i {k_i}s_i^2 = 2\vert E\vert.\eqno{\hbox{(19)}}Then, the relaxed modularity maximization problem can be easily solved by setting the first derivative of (5) with respect to
\sum\limits_j {B_{ij}}{s_j} = \lambda {k_i}{s_i}\eqno{\hbox{(20)}}or in matrix notation {\mbi {Bs}} = \lambda {\mbi {Ds}}\eqno{\hbox{(21)}}Q = {1 \over {4\vert E\vert}}\sum\limits_{ij} {B_{ij}}{s_i}{s_j} = {\lambda \over {4\vert E\vert}}\sum\limits_i {k_i}s_i^2 = {\lambda \over 2}.\eqno{\hbox{(22)}}Therefore, to achieve the highest value of
\sum\limits_j {A_{ij}}{s_j} = {k_i}\left({\lambda {s_i} + {1 \over {2\vert E\vert}}\sum\limits_j {k_j}{s_j}} \right)\eqno{\hbox{(23)}}or in matrix notion as {\mbi {As}} = {\mbi {D}}\left({\lambda {\mbi {s}} + {{{{\mbi {k}}^T}{\mbi {s}}} \over {2\vert E\vert}}{\bf 1}} \right)\eqno{\hbox{(24)}}{\mbi {As}} = \lambda {\mbi {Ds}}.\eqno{\hbox{(25)}}Again,
({{\mbi {D}}^{- 1/2}}{\mbi {A}}{{\mbi {D}}^{- 1/2}}){\mbi {u}} = \lambda {\mbi {u}}.\eqno{\hbox{(26)}}The matrix
3. Extremal Optimization
Duch and Arenas [16] proposed a modularity optimization algorithm based on the EO [29]. EO optimizes a global variable by improving extremal local variables. Here, the global variable is modularity (
{q_i} = {k_{i,c}} - {k_i}{{\vert{E_c}\vert} \over {2\vert E\vert}}\eqno{\hbox{(27)}}where {\lambda _i} = {{{q_i}} \over {{k_i}}} = {{{k_{i,c}}} \over {{k_i}}} - {{\vert{E_c}\vert} \over {2\vert E\vert}}\eqno{\hbox{(28)}}The algorithm starts by randomly splitting the network into two partitions of equal number of nodes, where communities are the connected components in each partition. Then, at each iteration, it moves the node with the lowest fitness from its own community to another community. The shift changes the community structure, so the fitness of many other nodes needs to be recomputed. The process repeats until it cannot increase
4. Simulated Annealing
SA [30] is a probabilistic procedure for the global optimization problem of locating a good approximation to the global optimum of a given function in a large search space. This technique was adopted in [17]–[18][19][20] to maximize modularity (
5. Sampling Techniques
Sales-Pardo et al. [21] proposed a “box-clustering” method to extract the hierarchical organization of networks. This approach consists of two steps: 1) estimating the similarity, called “node affinity,” between nodes and forming the node affinity matrix; and 2) deriving hierarchical community structure from the affinity matrix. The affinity between two nodes is the probability that they are classified into the same community in the local maxima partitions of modularity. The set of local maxima partitions, called
The sample generation procedure is repeated until the affinity matrix has converged to its asymptotic value. Empirically, the total number of samples needed is proportional to the size of the network. Before proceeding to the second step, the algorithm assesses whether the network has a significant community structure or not. It is done by computing the
6. Mathematical Programming
Agarwal and Kempe [22] formulated the modularity maximization problem as a linear program and vector program which has the advantage of providing a posteriori performance guarantees. First, modularity maximization can be transformed into the integer program
\eqalignno{& {\hbox{Maximize} {1 \over {2\vert E\vert}}\sum\limits_{ij} {B_{ij}}(1 - {x_{ij}})} \cr& \hbox{subject to}\ {x_{ik}} \leq {x_{ij}} + {x_{jk}}, \quad \hbox{for all}\ i,j,k \cr &\qquad\qquad {x_{ij}} \in \{0,1\}, \quad \hbox{for all}\ i,j &\hbox{(29)}}where \eqalignno{& \hbox{Maximize} {1 \over {4\vert E\vert}}\sum\limits_{ij} {B_{ij}}(1 + {s_i}{s_j}) \cr &\hbox{subject to}\ s_i^2 = 1, \quad \hbox{for all}\ i &\hbox{(30)}}C. Resolution Limit
Since its inception, the modularity has been used extensively as the measure of the quality of partitions produced by community detection algorithms. In fact, if we adopt modularity as a quality measure of communities, the task of discovering communities is essentially turned into the task of finding the network partitioning with an optimal value of modularity.
However as properties of the modularity were studied, it was discovered that in some cases it fails to detect small communities. There is a certain threshold [25], such that a community of the size below it will not be detected even if it is a complete subgraph connected to the rest of the graph with a single edge. This property of modularity has been known as the resolution limit.
Although the resolution limit prevents detection of small communities, the actual value of the threshold depends on the total number of edges in the network and on the degree of interconnectedness between communities. In fact, the resolution limit can reach the values comparable to the size of the entire network causing formation of a few giant communities (or even a single community) and failing to detect smaller communities within them. It makes interpreting the results of community detection very difficult because it is impossible to tell beforehand whether a community is well-formed or if it can be further split into subcommunities.
Considering modularity as a function of the total number of edges
The above arguments can also be applied to weighted networks. In this case,
By introducing an additional parameter
m = \sqrt {{{\vert E\vert} \over \epsilon}}.\eqno{\hbox{(31)}}Correspondingly, any community for which its size
\vert{c_i}\vert \lt \sqrt {{{\vert E\vert\epsilon } \over 2}} - \epsilon \eqno{\hbox{(32)}}may not be resolved.Introduction of
D. Resolving the Resolution Limit Problem
There have been extensive studies done on how to mitigate the consequences of the modularity resolution limit. The main approaches followed are described below.
Localized modularity measure (LQ) [33] is based on the observation that the resolution limit problem is caused by modularity being a global measure since it assumes that edges between any pairs of nodes are equally likely, including connectivity between the communities. However, in many networks, the majority of communities have edges to only a few other communities, i.e., exhibit a local community connectivity.
Thus, a local version of the modularity measure for a directed network is defined as
{\rm LQ} = \sum\limits_{{c_i} \in C} \left[{{{\vert {E_{{c_i}}^{{\rm in}}} \vert} \over {\vert {E_{{c_i}}^{{\rm neighb}}} \vert}} - {{\left({{{\vert {E_{{c_i}}^{{\rm in}}} \vert + \vert {E_{{c_i}}^{{\rm out}}} \vert} \over {\vert {E_{{c_i}}^{{\rm neighb}}} \vert}}} \right)}^2}} \right]\eqno{\hbox{(33)}}where Unlike traditional modularity (
Arenas et al. proposed a multiple resolution method [34] which is based on the idea that it might be possible to look at the detected community structure at different scales. From this perspective, the modularity resolution limit is not a problem but a feature. It allows choosing a desired resolution level to achieve the required granularity of the output community structure using the original definition of modularity.
The multiple resolution method is based on the definition of modularity given by (1). The modularity resolution limit depends on the total weight
Caution should be exercised when altering the weights of edges in the network to avoid changing its topological characteristics. To ensure this, a rescaled adjacency matrix can be defined as
{\mbi {A_r}} = {\mbi {A}} + r{\mbi {I}}\eqno{\hbox{(34)}}where Optimizing the modularity for the rescaled topology
{Q_r} = \sum\limits_{{c_i} \in C} \left[{{{2\vert {E_{{c_i}}^{{\rm in}}} \vert + r\vert {{c_i}} \vert} \over {2\vert E \vert + r\vert V \vert}} - {{\left({{{\vert{E_{{c_i}}}\vert + r\vert {{c_i}} \vert} \over {2\vert E \vert + r\vert V \vert}}} \right)}^2}} \right]\eqno{\hbox{(35)}}where Parameter
Further studies of the multiple resolution approach revealed that it suffers from two major issues outlined in [35]. First, when the value of the resolution parameter
The hierarchical multiresolution method proposed by Granell et al. in [36] overcomes the limitations of the multiple resolution method on networks with very different scales of communities. It achieves that by introducing a new hierarchical multiresolution scheme that works even in cases of community detection near the modularity resolution limit. The main idea underlying this method is based on performing multiple resolution community detection on essential parts of the network, thus analyzing each part independently.
The method operates iteratively by first placing all nodes in a single community. Then, it finds the minimum value of the resistance parameter
Another approach to leveraging the results of modularity optimization has been introduced by Chakraborty et al. in [27]. It is based on the observation that a simple change to the order of nodes in a network can significantly affect the community structure. However, a closer examination of the communities produced in different runs of a certain community detection algorithm reveals that for many networks the same invariant groups of nodes are consistently assigned to the same communities. Such groups of nodes are called constant communities. The percentage of constant communities varies depending on the network. Constant communities are detected by trying different node permutations while preserving the degree sequence of the nodes. For networks that have strong community structure, the constant communities detected can be adopted as a pre-processing step before performing modularity optimization. This can lead to higher modularity values and lower variability in results, thus improving the overall quality of community detection.
In the study [37] by Li et al., a new quantitative measure for community detection is introduced. It offers several improvements over the modularity (
D = \sum\limits_{{c_i} \in C} {{2\vert {E_{{c_i}}^{{\rm in}}} \vert - \vert {E_{{c_i}}^{{\rm out}}} \vert} \over {\vert {{c_i}} \vert}}.\eqno{\hbox{(36)}}The quality of the communities found is then described by the value of the modularity density (
The modularity density (
Traag et al. in [38] introduce a rigorous definition of the resolution-limit-free method for which considering any induced subgraph of the original graph does not cause the detected community structure to change. In other words, if there is an optimal partitioning of a network (with respect to some objective function), and for each subgraph induced by the partitioning it is also optimal, then such objective function is called resolution-limit-free. An objective function is called additive for a certain partitioning if it is equal to the sum of the values of this objective function for each of the subgraphs induced by the partitioning.
Based on these two definitions, it is proved that if an objective function is additive and there are two optimal partitions, then any combination of these partitions is also optimal. In case of a complete graph, if an objective function is resolution-limit-free, then an optimal partitioning either contains all the nodes (i.e., there is only one community which includes all nodes) or consists of communities of size 1 (i.e., each node forms a community of its own). A more general statement for arbitrary objective functions is also true: if an objective function has local weights (i.e., weights that do not change when considering subgraphs), then it is resolution-limit-free. Although the converse is not true, there is only a relatively small number of special cases when methods with nonlocal weights are resolution-limit-free.
The authors then analyze resolution-limit-free within the framework of the first principle Potts model [39]
{\cal H} = - \sum\limits_{ij} ({{a_{ij}}{A_{ij}} - {b_{ij}}({1 - {A_{ij}}})}){\delta _{{c_i},{c_j}}}\eqno{\hbox{(37)}}where Given the definition of
However, all of the above approaches are aimed at solving only the resolution limit problem. Work done by Chen et al. in [23] and [24] adopts a different definition of modularity density which simultaneously addresses two problems of modularity. It is done by mixing two additional components, Split Penalty (SP) and the community density, into the well-known definition of modularity. Community density includes internal community density and pair-wise community density. SP is the fraction of edges that connect nodes of different communities
{\rm SP} = \sum\limits_{{c_i} \in C} \left[{\sum\limits_{{\scriptstyle {c_j} \in C \atop \scriptstyle {c_j} \ne {c_i}} } {{\vert{E_{{c_i},{c_j}}}\vert} \over {2\vert E\vert}}} \right].\eqno{\hbox{(38)}}The value of SP is subtracted from modularity, while the value of the community density is added to modularity and SP. Introducing SP resolves the issue of favoring small communities. Community density eliminates the problem of favoring large communities (also known as the resolution limit problem). The Modularity Density (
\eqalignno{{Q_{ds}} &= \sum\limits_{{c_i} \in C} \left[{{\vert E_{{c_i}}^{{\rm in}}\vert} \over {\vert E\vert}}{d_{{c_i}}} - {{\left({{{2\vert E_{{c_i}}^{{\rm in}}\vert + \vert E_{{c_i}}^{{\rm out}}\vert} \over {2\vert E\vert}}{d_{{c_i}}}} \right)}^2}\right. \cr & \qquad\left. - \sum\limits_{{c_j} \in C{c_j} \ne {c_i}} {{\vert{E_{{c_i},{c_j}}}\vert} \over {2\vert E\vert}}{d_{{c_i},{c_j}}} \right] \cr {d_{{c_i}}} &= {2\vert E_{{c_i}}^{{\rm in}}\vert \over \vert{c_i}\vert(\vert{c_i}\vert - 1)}\cr {d_{{c_i},{c_j}}} &= {{\vert{E_{{c_i},{c_j}}}\vert} \over {\vert{c_i}\vert\vert{c_j}\vert}}. &\hbox{(39)}}where Modularity Density (
Maximizing Modularity Density Qds
In our previous papers [23], [24], we have given the definition of Modularity Density (
A. Greedy Algorithm Fails to Optimize Qds
In this section, we show why the greedy agglomerative algorithm increasing
For example, in the network example in Fig. 1, the initial values of
B. Fine-Tuned Algorithm
In this part, we describe a fine-tuned community detection algorithm that iteratively improves a community quality metric
Algorithm 1 Split_Communities (G C
1: Initialize comWeights
2: //Get the metric value for each community.
3:
4: for
5:
6:
7:
8:
9: //Form
10: splitTwoCom.addAll(nodeIds);
11: for
12: splitOneCom.add(nodeIds
13: splitTwoCom.remove(nodeIds
14: Calculate
15:
16: if
17:
18:
19: end if
20: end for
21: if
22: Clear splitOneCom and splitTwoCom;
23: splitOneCom.addAll(nodeIds
24: splitTwoCom.addAll(nodeIds
25: newC.add(splitOneCom);
26: newC.add(splitTwoCom);
27: else
28: newC.add(
29: end if
30: end for
31: return newC
In the split stage, the algorithm will split a community
First, we calculate the Fiedler vector which is the eigenvector of the network Laplacian matrix
The outline of the split stage is shown in Algorithm 1. The input is a network and a community list, and the output is a list of communities after splitting. The initialization part has
Algorithm 2 Merge_Communities (G C
1: Initialize comWeights
2: //Get the metric value for each community.
3:
4: for
5: for
6: //Doesn't consider disconnected communities.
7: if
8: continue;
9: end if
10: Calculate
11:
12: //Record the merging information with
13: if
14: mergedInfos.put([
15: end if
16: end for
17: end for
18: //Merge the community with the one that improves the value of the quality metric the most
19: while mergedInfos.hasNext() do
20:
21: if !mergedComs.containsKey(comId1) && !mergedComs.containsKey(comId2) then
22: mergedComs.put(comId1,comId2);
23: mergedComs.put(comId2,comId1);
24: end if
25: end while
26: for
27:
28: if mergedComs.containsKey(
29:
30: if
31:
32: end if
33: end if
34: newC.add(
35: end for
36: return newC;
In the merging stage, the algorithm will merge a community to its connected communities if the merging improves the value of the quality metric. If there are many mergers possible for a community, the one, unmerged so far, which improves the quality metric the most is chosen. Hence, each community will only be merged at most once in each stage. The outline of the merging stage is shown in Algorithm 2. The input is a network and a community list, and the output is a list of communities after merging. The initialization part has the complexity
Algorithm 3 Fine-tuned_Algorithm (G C
1:
2:
3:
4: while
5:
6:
7:
8:
9:
10: end while
11: return
The fine-tuned algorithm repeatedly carries out those two alternating stages until neither splitting nor merging can improve the value of the quality metric or until the total number of communities discovered does not change after one full iteration. Algorithm 3 shows the outline of the fine-tuned algorithm. It can detect the community structure of a network by taking a list with a single community of all the nodes in the network as the input. It can also improve the community detection results of other algorithms by taking a list with their communities as the input. Let the number of iteration of the fine-tuned algorithm be denoted as
Experimental Results
In this section, we first introduce several popular measurements for evaluating the quality of the results of community detection algorithms. Denoting the greedy algorithm of modularity maximization proposed by Newman [7] as Greedy
In Section II-B-2, we have shown that the modularity maximization approach using the eigenvectors of the Laplacian matrix is equivalent to the one using the eigenvectors of the modularity matrix. This implies that the split stage of our Fine-tuned
A. Evaluation Metrics
The quality evaluation metrics we consider here can be divided into three categories: 1) Variation of Information (VI) [45] and Normalized Mutual Information (NMI) [46] based on information theory; 2) F-measure [47] and Normalized Van Dongen metric (NVD) [48] based on cluster matching; and 3) Rand Index (RI) [49], Adjusted Rand Index (ARI) [50], and Jaccard Index (JI) [51] based on pair counting.
1. Information Theory-Based Metrics
Given partitions
\eqalignno{{{\rm VI}(C,C^\prime)} &= H(C) + H(C^\prime) - 2I(C,C^\prime) \cr & = H(C,C^\prime) - I(C,C^\prime) &\hbox{(40)}}where {\rm NMI}(C,C^\prime) = {{2I(C,C^\prime)} \over {H(C) + H(C^\prime)}}.\eqno{\hbox{(41)}}Using the definitions
\eqalignno{H(C) &= - \sum\limits_{{c_i} \in C} p({c_i})\log p({c_i}) = - \sum\limits_{{c_i} \in C} {{\vert{c_i}\vert} \over {\vert V\vert}}\log {{\vert{c_i}\vert} \over {\vert V\vert}} &\hbox{(42)} \cr H(C,C^\prime) &= - \sum\limits_{{c_i} \in C,{c^\prime_j} \in C^\prime} p({c_i},{c^\prime_j})\log p({c_i},{c^\prime_j}) \cr & = - \sum\limits_{{c_i} \in C,{c^\prime_j} \in C^\prime} {{\vert{c_i} \cap {c^\prime_j}\vert} \over {\vert V\vert}}\log \left({{{\vert{c_i} \cap {c^\prime_j}\vert} \over {\vert V\vert}}} \right) &\hbox{(43)}}we can express VI and NMI as a function of counts only as follows: \eqalignno{{\rm VI}(C,C^\prime) &= - {1 \over {\vert V\vert}}\sum\limits_{{c_i} \in C,{c^\prime_j} \in C^\prime} \vert{c_i} \cap {c^\prime_j}\vert\log \left({{{\vert{c_i} \cap {c^\prime_j}{\vert^2}} \over {\vert{c_i}\vert\vert{c^\prime_j}\vert}}} \right) &\hbox{(44)} \cr {\rm NMI}(C,C^\prime) &= {{- 2\sum\nolimits_{{c_i} \in C,{c^\prime_j} \in C^\prime} {{{\vert{c_i} \cap {c_j^\prime}\vert} \over {\vert V\vert}}\log \left({{{\vert{c_i} \cap {c^\prime_j}\vert\vert V\vert} \over {\vert{c_i}\vert\vert{c^\prime_j}\vert}}} \right)} } \over {\sum\nolimits_{{c_i} \in C} {{{\vert{c_i}\vert} \over {\vert V\vert}}\log {{\vert{c_i}\vert} \over {\vert V\vert}} + \sum\limits_{{c^\prime_j} \in C^\prime} {{\vert{c^\prime_j}\vert} \over {\vert V\vert}}\log {{\vert{c^\prime_j}\vert} \over {\vert V\vert}}}}}&\hbox{(45)}}2. Clustering Matching-Based Metrics
Measurements based on clustering matching aim at finding the largest overlaps between pairs of communities of two partitions
F\hbox{-measure}(C,C^\prime) = {1 \over {\vert V\vert}}\sum\limits_{{c_i} \in C} \vert{c_i}\vert \max \limits_{{c^\prime_j} \in C^\prime} {{2\vert{c_i} \cap {c^\prime_j}\vert} \over {\vert{c_i}\vert + \vert{c^\prime_j}\vert}}.\eqno{\hbox{(46)}}NVD is given by \eqalignno{{\rm NVD}(C,C^\prime) &= 1 - {1 \over {2\vert V\vert}}\left(\sum\limits_{{c_i} \in C} \max \limits_{{c^\prime_j} \in C^\prime} \vert{c_i} \cap {c^\prime_j}\vert \right. \cr &\quad\left. + \sum\limits_{{c^\prime_j} \in C^\prime} \max \limits_{{c_i} \in C} \vert{c^\prime_j} \cap {c_i}\vert \right). &\hbox{(47)}}3. Pair Counting-Based Metrics
Metrics based on pair counting count the number of pairs of nodes that are classified (in the same community or in different communities) in two partitions
{\rm RI}(C,C^\prime) = {{{a_{11}} + {a_{00}}} \over A}.\eqno{\hbox{(48)}}Denote
{\rm ARI}(C,C^\prime) = {{{a_{11}} - M} \over {{1 \over 2}\left[{({a_{11}} + {a_{10}}) + ({a_{11}} + {a_{01}})} \right] - M}}.\eqno{\hbox{(49)}}The JI [51] which is the ratio of the number of node pairs placed in the same community in both partitions to the number of node pairs that are placed in the same group in at least one partition is defined as
{\rm JI}(C,C^\prime) = {{{a_{11}}} \over {{a_{11}} + {a_{10}} + {a_{01}}}}.\eqno{\hbox{(50)}}Each of these three metrics quantifies the similarity between two partitions
B. Real Networks
In this section, we first evaluate the performance of Greedy
1. Zachary's Karate Club Network
We first compare the performance of Greedy
Table I presents the metric values of the community structures detected by the three algorithms on this network. It shows that Fine-tuned
In addition, analyzing the intermediate results of Fine-tuned
2. American College Football Network
We apply the three algorithms also to the American college football network [53] which represents the schedule of games between college football teams in a single season. The teams are divided into 12 “conferences” with intra-conference games being more frequent than inter-conference games. Those conferences could be treated as the ground truth communities whose structure is shown in Fig. 3(a).
Table II presents the metric values of the community structures detected by the three algorithms. It shows that Fine-tuned
Moreover, we apply Fine-tuned
3. PGP Network
We then apply the three algorithms on PGP network [54]. It is the giant component of the network of users of the PGP algorithm for secure information interchange. It has 10 680 nodes and 24 316 edges.
Table IV presents the metric values of the community structures detected by the three algorithms. Since this network does not have ground truth communities, we only calculate
4. AS Level Internet
The last real network dataset that is adopted to evaluate the three algorithms is AS level Internet. It is a symmetrized snapshot of the structure of the Internet at the level of autonomous systems, reconstructed from Border Gateway Protocol (BGP) tables posted by the University of Oregon Route Views Project. This snapshot was created by Mark Newman from data for July 22, 2006 and has not been previously published. It has 22 963 nodes and 48 436 edges.
Table V presents the metric values of the community structures detected by the three algorithms. Since this network does not have ground truth communities either, we only calculate
C. Synthetic Networks
1. Clique Network
We now apply the three algorithms to the classical network example [23]–[24][25], displayed in Fig. 4, which illustrates modularity (
Table VI presents the metric values of the community structures detected by the three algorithms. It shows that Greedy
2. LFR Benchmark Networks
To further compare the performance of Greedy
Tables VIII –X show the metric values of the community structures detected with Greedy
In summary, the seven measurements based on ground truth communities are all consistent with
We then take the community detection results of Greedy
Conclusion
In this paper, we review the definition of modularity and its corresponding maximization methods. Moreover, we show that modularity optimization has two opposite but coexisting issues. We also review several community quality metrics proposed to solve the resolution limit problem. We then discuss our Modularity Density (
ACKNOWLEDGEMENT
The views and conclusions contained in this document are those of the authors and should not be interpreted as representing the official policies either expressed or implied of the Army Research Laboratory or the U.S. Government.