正在加载图片...
The Method of Optimal Modularity reformulation of the modularity in terms of the spectral prop- Suppose then that we are given, or discover, the structure of erties of the network of interest some network and that we want to determine whether there Suppose our network contains n vertices. For a particular exists any natural division of its vertices into nonoverlapping division of the network into two groups let s;=1 if vertex i groups or communities, where these communities may be of any belongs to group l and s=-I if it belongs to group 2. And let the number of edges between vertice es i and j be Ai, which will Let us approach this question in stages and focus initially on normally be 0 or 1, although larger values are possible in the problem of whether any good division of the network exists networks where multiple edges are allowed. (The quantities A, into just two communities. Perhaps the most obvious way to are the elements of the so-called adjacency matrix. )At the same tackle this problem is to look for divisions of the vertices into two time, the expected number of edges between vertices i and jif the groups. This"minimum cut"approach is the approach most degrees of the vertices and m=2>, k is the total number of edges often adopted in the graph-partitioning literature. Howeve discussed above, the community structure problem differs cru- Ay-kki /2m over all pairs of vertices i,j that fall in the same nities are not normally known in advance. If community sizes are erving that the quantity ;(sp;+ 1)is 1 ifi andj are in the unconstrained then we are, for instance, at liberty to select the and 0 otherwise, we can then express the modularity as trivial division of the network that puts all of the vertices in one of our two groups and none in the other, which guarantees we Qm∑(4-2)+D-m∑(4 will have zero intergroup edges. This division is, in a sense optimal, but clearly it does not tell us anything of any worth. We can,if we want, artificially forbid this solution, but then a division [1 that puts just one vertex in one group and the rest in the other where the second equality follows from the observation that will often be optimal, and so forth The problem is that simply counting edges is not a good way to ki= Ey Ai. The leading factor of 1/4m is merely conv al: it is included for compatibility with the previous uantify the intuitive concept of community structure. A good definition of modularity(17) division of a network into communities is not merely one in which Eq. 1 can conveniently be written in matrix form there are few edges between communities: it is one in which there are fewer than expected edges between communities. If the number of edges between two groups is only what one would expect on the Q [2] asis of random chance then few thoughtful observers would claim this constitutes evidence of meaningful community structure. On where s is the column vector whose elements are the S; and we the other hand, if the number of edges between groups is signifi- have defined a real symmetric matrix B with elements cantly less than we expect by chance, or equivalent if the number within groups is significantly more, then it is reasonable to conclude kki 3 that something interesting is going on. This idea, that true community structure in a network corre sponds to a statistically surprising arrangement of edges, can be which we call the modularity matrix. Much of our attention in quantified by using the measure known as modularity (17). The this article will be devoted to the properties of this matrix. For dges falling within groups minus the expected number in an columns sum to zero, so that it always has an eigenvector equivalent network with edges placed at random. (A precise (1, 1, I,.. )with eigenvalue zero. This observation is reminiscent mathematical formulation is given below.) The modularity can be either positive or negative, with basis for one of the best-known methods of graph partitioning sitive values indicating the possible presence of community spectral partitioning(21, 22), and has the same property. And structure. Thus, one can search for community structure pre indeed, the methods presented here have many similarities to cisely by looking for the divisions of a network that have positive, as wey partitioning, although there are some crucial differences IV The evidence so far suggests that this approach, of looking for Given Eq. 2, we proceed by writing s as a linear combination of the normalized eigenvectors u; of B so that s= 2i-1 a;u; with divisions with high modularity, is a very effective way to tackle ai=us. Then we find the problem. For instance, Guimera and Amaral(12) and later Danon et al. ( 8)optimized modularity over possible partitions of computer-generated test networks by using simulated annealing 1 In direct comparisons using standard measures, Danon et al Q=n2aB2a=切m2(吗s)3B.4 found that this method outperformed all other methods for community detection of which they were aware, in most cases by where B, is the eigenvalue of B corresponding to eigenvector u, an impressive margin. On the basis of such results we consider Let us assume that the eigenvalues are labeled in maximization of the modularity to be perhaps the definitive order, B1==.2, We want to maximize the modularity current method of community detection, being at the same time by choosing an appropriate division of the network, or equiva based on sensible statistical principles and highly effective in lently by choosing the value of the index vector s. This means practice. Unfortunately, optimization by simulated annealing is choosing s so as to concentrate as much weight as possible in not a workable approach for the large network problems facing terms of the sum in Eq. 4 involving the larg most todays scientists, because it demands too much computational eigenvalues. If there were no other constraints on our choice of effort. A number of alternative heuristic methods have been s(apart from normalization), this would be an easy task: we estigated, such as greedy algorithms(18)and extremal opti- would simply chose s proportional to the eigenvector un. This mization(19). Here we take a different approach based on a places all of the weight in the term involving the largest 8578iwww.pnas.org/cgi/doi/10.1073/pnas.060160210The Method of Optimal Modularity Suppose then that we are given, or discover, the structure of some network and that we want to determine whether there exists any natural division of its vertices into nonoverlapping groups or communities, where these communities may be of any size. Let us approach this question in stages and focus initially on the problem of whether any good division of the network exists into just two communities. Perhaps the most obvious way to tackle this problem is to look for divisions of the vertices into two groups so as to minimize the number of edges running between the groups. This ‘‘minimum cut’’ approach is the approach most often adopted in the graph-partitioning literature. However, as discussed above, the community structure problem differs crucially from graph partitioning in that the sizes of the communities are not normally known in advance. If community sizes are unconstrained then we are, for instance, at liberty to select the trivial division of the network that puts all of the vertices in one of our two groups and none in the other, which guarantees we will have zero intergroup edges. This division is, in a sense, optimal, but clearly it does not tell us anything of any worth. We can, if we want, artificially forbid this solution, but then a division that puts just one vertex in one group and the rest in the other will often be optimal, and so forth. The problem is that simply counting edges is not a good way to quantify the intuitive concept of community structure. A good division of a network into communities is not merely one in which there are few edges between communities; it is one in which there are fewer than expected edges between communities. If the number of edges between two groups is only what one would expect on the basis of random chance, then few thoughtful observers would claim this constitutes evidence of meaningful community structure. On the other hand, if the number of edges between groups is significantly less than we expect by chance, or equivalent if the number within groups is significantly more, then it is reasonable to conclude that something interesting is going on. This idea, that true community structure in a network corresponds to a statistically surprising arrangement of edges, can be quantified by using the measure known as modularity (17). The modularity is, up to a multiplicative constant, the number of edges falling within groups minus the expected number in an equivalent network with edges placed at random. (A precise mathematical formulation is given below.) The modularity can be either positive or negative, with positive values indicating the possible presence of community structure. Thus, one can search for community structure precisely by looking for the divisions of a network that have positive, and preferably large, values of the modularity (18). The evidence so far suggests that this approach, of looking for divisions with high modularity, is a very effective way to tackle the problem. For instance, Guimera` and Amaral (12) and later Danon et al. (8) optimized modularity over possible partitions of computer-generated test networks by using simulated annealing. In direct comparisons using standard measures, Danon et al. found that this method outperformed all other methods for community detection of which they were aware, in most cases by an impressive margin. On the basis of such results we consider maximization of the modularity to be perhaps the definitive current method of community detection, being at the same time based on sensible statistical principles and highly effective in practice. Unfortunately, optimization by simulated annealing is not a workable approach for the large network problems facing today’s scientists, because it demands too much computational effort. A number of alternative heuristic methods have been investigated, such as greedy algorithms (18) and extremal optimization (19). Here we take a different approach based on a reformulation of the modularity in terms of the spectral properties of the network of interest. Suppose our network contains n vertices. For a particular division of the network into two groups let si 1 if vertex i belongs to group 1 and si 1 if it belongs to group 2. And let the number of edges between vertices i and j be Aij, which will normally be 0 or 1, although larger values are possible in networks where multiple edges are allowed. (The quantities Aij are the elements of the so-called adjacency matrix.) At the same time, the expected number of edges between vertices i and j if edges are placed at random is kikj2m, where ki and kj are the degrees of the vertices and m 1 2 i ki is the total number of edges in the network. Thus the modularity Q is given by the sum of Aij kikj2m over all pairs of vertices i,j that fall in the same group. Observing that the quantity 1 2 (sisj 1) is 1 if i and j are in the same group and 0 otherwise, we can then express the modularity as Q 1 4m ij Aij kikj 2m sisj 1 1 4m ij Aij kikj 2msisj, [1] where the second equality follows from the observation that 2m i ki ij Aij. The leading factor of 14m is merely conventional: it is included for compatibility with the previous definition of modularity (17). Eq. 1 can conveniently be written in matrix form as Q 1 4m sTBs, [2] where s is the column vector whose elements are the si and we have defined a real symmetric matrix B with elements Bij Aij kikj 2m , [3] which we call the modularity matrix. Much of our attention in this article will be devoted to the properties of this matrix. For the moment, note that the elements of each of its rows and columns sum to zero, so that it always has an eigenvector (1,1,1, . . .) with eigenvalue zero. This observation is reminiscent of the matrix known as the graph Laplacian (20), which is the basis for one of the best-known methods of graph partitioning, spectral partitioning (21, 22), and has the same property. And indeed, the methods presented here have many similarities to spectral partitioning, although there are some crucial differences as well, as we will see. Given Eq. 2, we proceed by writing s as a linear combination of the normalized eigenvectors ui of B so that s i1 n aiui with ai ui T s. Then we find Q 1 4m i aiui T B j ajuj 1 4m i1 n ui T s 2 i, [4] where i is the eigenvalue of B corresponding to eigenvector ui. Let us assume that the eigenvalues are labeled in decreasing order, 1 2 n. We want to maximize the modularity by choosing an appropriate division of the network, or equivalently by choosing the value of the index vector s. This means choosing s so as to concentrate as much weight as possible in terms of the sum in Eq. 4 involving the largest (most positive) eigenvalues. If there were no other constraints on our choice of s (apart from normalization), this would be an easy task: we would simply chose s proportional to the eigenvector u1. This places all of the weight in the term involving the largest 8578 www.pnas.orgcgidoi10.1073pnas.0601602103 Newman