Modularity spectra, eigen-subspaces, and structure of weighted graphs

Modularity spectra, eigen-subspaces, and structure of weighted graphs Marianna Bolla ∗ Institute of Mathematics, Budapest University of Technology and Economics and Intra-University Centre for Telecommunications and Informatics, Debrecen Abstract The role of the normalized modularity matrix in finding homogeneous cuts will be presented. We also discuss the testability of the structural eigenvalues and that of the subspace spanned by the corresponding eigenvectors of this matrix. In the presence of a spectral gap between the k−1 largest absolute value eigenvalues and the remainder of the spectrum, this in turn implies the testability of the sum of the inner variances of the kclusters that are obtained by applying the k-means algorithm for the appropriately chosen vertex representatives. Key words: Normalized modularity, Volume regularity, Spectral clustering, Testable weighted graph parameters, Structural eigenvalues, Spectral subspaces 1 Introduction The purpose of this paper is to summarize the spectral properties and testability of the spectrum and spectral subspaces of the normalized modularity matrix introduced in [9] to find regular vertex partitions. We will generalize the Laplacian based spectral clustering methods to recover so-called volume regular cluster pairs such that the information flow between the pairs and within the clusters is as homogeneous as possible. For this purpose, we take into consideration both ends of the normalized Laplacian spectrum, i.e., large absolute value, so-called structural eigenvalues of our normalized modularity matrix introduced just for this convenience. ∗Research supported by the Hungarian National Research Grant OTKA-KTIA 77778 and by the T´ AMOP-4.2.2.C-11/1/KONV-2012-0001 project, supported by the European Union, co-financed by the European Social Fund. Email address: [email protected] (Marianna Bolla). Preprint submitted to Elsevier 30 April 2013 In Theorem 3, we estimate the constant of volume regularity in terms of the gap between the structural and other eigenvalues, and the k-variance of the optimal vertex representatives constructed by the eigenvectors corresponding to the structural eigenvalues. Here we give a more detailed proof of this statement than in [10]. This theorem implies that for a general edge-weighted graph, the existence of k−1 structural eigenvalues of the normalized modularity matrix, separated from 0, is indication of a k-cluster structure such that the clusterpairs are volume regular with constant depending on the spectral gap and the above k-variance. The clusters themselves can be recovered by applying the k-means algorithm for the vertex representatives. Hence, Theorem 3 implies that spectral clustering of the vertices into kparts gives satisfactory partition in the sense of volume regularity. Furthermore, in Theorems 8 and 10, we prove the testability of the structural eigenvalues and the corresponding eigen-subspace of the normalized modularity matrix in the sense of [12]. In view of this, spectral clustering methods can be performed on a smaller part of the underlying graph and give good approximation for the cluster structure. 2 Preliminaries Throughout the paper, we use the general framework of an edge-weighted graph. Let G=Gn= (V, W) be an edge-weighted graph on vertex-set V (|V|=n) and n×nsymmetric weight-matrix Wof non-negative real entries and zero diagonal. We will call the numbers di=Pn j=1 wij (i= 1, . . . , n) generalized degrees, and the diagonal matrix D=diag (d1, . . . , dn)degree matrix. In this and the next section, without loss of generality, Vol(V) = 1 will be assumed, where the volume of the vertex-subset U⊆Vis Vol(U) = Pi∈Udi. In the sequel, we only consider connected graphs, which means that Wis irreducible. In [9], we defined the normalized version of the modularity matrix (introduced in [21]) as MD=D−1/2WD−1/2−√d√dT, where √d= (√d1,...,√dn)T, and we called it normalized modularity matrix. The spectrum of this matrix is in the [-1,1] interval, and 0 is always an eigenvalue with unit-norm eigenvector √d. Indeed, in [5] we proved that 1 is a single eigenvalue of D−1/2WD−1/2with corresponding unit-norm eigenvector √d, provided our graph is connected. This becomes a zero eigenvalue of MDwith the same eigenvector, whence 1 cannot be an eigenvalue of MDif Gis connected. In fact, the introduction of this matrix is rather technical, the spectral gap, further, Lemma 1 and Theorem 3 can better be formulated with it. It can also be obtained from the normalized Laplacian by subtracting it from the identity and depriving of its trivial factor. Normalized Laplacian was used for spectral clustering in several 2 papers (e.g., [3,5,6,14,20]), the idea of which can be summarized by means of the spectral decomposition of the normalized modularity matrix. We introduce the following notation: the weighted cut between the vertex-subsets X, Y ⊆V is w(X, Y ) = Pi∈XPj∈Ywij. We will frequently refer to the following facts. (a) The spectral decomposition of MDsolves the following quadratic placement problem. For a given positive integer k(1 < k < n), we want to minimize Qk=Pi<j wijkri−rjk2on the conditions n X i=1 dirirT i=Ik−1and n X i=1 diri=0(1) where the vectors r1,...,rnare (k−1)-dimensional representatives of the vertices, which form the row vectors of the n×(k−1) matrix X. Denote the eigenvalues of MD, in decreasing order, by 1 > λ1≥ ··· ≥ λn≥ −1 with corresponding unit-norm, pairwise orthogonal eigenvectors u1,...,un. In [5], we proved that the minimum of Qksubject to (1) is k−1−Pk−1 i=1 λiand is attained by the representation such that the optimum vertex representatives r∗ 1,...,r∗ nare row vectors of the matrix X∗= (D−1/2u1,...,D−1/2uk−1). Instead of X, the augmented n×kmatrix ˜ Xcan as well be used, which is obtained from Xby inserting the column x0=1of all 1’s. In fact, x0=D−1/2u0, where u0=√dis the eigenvector corresponding to the eigenvalue 1 of D−1/2WD−1/2. Then Qk=tr (D1/2˜ X)T(In−D−1/2WD−1/2)(D1/2˜ X), and minimizing Qkon the constraint (1) is equivalent to minimizing the above expression subject to ˜ XTD˜ X=Ik. This problem is the continuous relaxation of minimizing Qk(Pk) = tr (D1/2˜ X(Pk))T(In−D−1/2WD−1/2)(D1/2˜ X(Pk)) over the set of k-partitions Pk= (V1, . . . , Vk) of the vertices such that Pkis planted into ˜ Xin the way that the columns of ˜ X(Pk) are so-called normalized partition-vectors belonging to Pk. Namely, the coordinates of the ith column are zeros, except those indexing vertices of Vi, which are equal to 1 √Vol(Vi)(i= 1, . . . , k). In fact, this is the normalized cut problem, which is discussed in [20] for k= 2, further, in [3] and [6] for a general k, and the solution is based on the above continuous relaxation. (b) Now, let us maximize the normalized Newman–Girvan modularity of Ginduced by Pk, defined in [9] as Mk(Pk) = k X a=1 1 Vol(Va)X i,j∈Va (wij −didj) = k X a=1 w(Va, Va) Vol(Va)−1 over the set Pkof the k-partitions of V. It is easy to see that Mk(Pk) = 3 k−1−Qk(Pk), and hence, the above task has the same spectral relaxation as the normalized cut problem. Let Mk= maxPk∈PkMk(Pk) denote the maximum k-way normalized Newman-Girvan modularity of the weighted graph G. (c) Finally, from the above considerations it is straightforward that Mk≤ Pk−1 i=1 λi, or equivalently, the minimum normalized k-way cut is at least the the sum of the k−1 smallest positive normalized Laplacian eigenvalues. As for the minimum normalized k-way cut, in [6] we also gave an upper estimate by constant times the sum of the k−1 smallest positive normalized Laplacian eigenvalues, which constant depends on the so-called k-variance of the vertex representatives defined in the following way. S2 k(X) = min Pk∈Pk S2 k(X, Pk) = min Pk=(V1,...,Vk) k X a=1 X j∈Va djkrj−cak2(2) where ca=1 Vol(Va)Pj∈Vadjrjis the weighted center of cluster Vaand r1, . . . ,rn∈Rk−1are rows of X. (The augmented ˜ Xwould give the same kvariance.) The constant of our estimation depended on S2 k(X∗), and it was close to 1 if this k-variance of the optimum (k−1)-dimensional vertex representatives was small enough. Note that S2 k(X, Pk) is the objective function of the weighted k-means algorithm. In this way, we showed that large positive eigenvalues of the normalized modularity matrix are responsible for clusters with high intraand low inter-cluster densities. Likewise, maximizing Qk(Pk) instead of minimizing over Pk, small negative eigenvalues of the normalized modularity matrix are responsible for clusters with low intraand high inter-cluster densities (see [9]). Our idea is that taking into account eigenvalues from both ends of the normalized modularity spectrum, we can recover so-called regular cluster pairs. For this purpose, we use the notion of volume regularity to be introduced in the next section. 3 Normalized modularity and volume regularity With the normalized modularity matrix, the well-known Expander Mixing Lemma (for simple graphs see, e.g., [17]) is formulated for edge-weighted graphs in the following way (see [8]). Lemma 1 Provided Vol(V) = 1, for all X, Y ⊆V, |w(X, Y )−Vol(X)Vol(Y)| ≤ kMDk·qVol(X)Vol(Y), where kMDkdenotes the spectral norm of the normalized modularity matrix of G= (V, W). 4 Since the spectral gap of Gis 1 −kMDk, a large spectral gap indicates small discrepancy as a quasi-random property discussed in [15]. If there is a gap not at the ends of the spectrum, we want to partition the vertices into clusters so that a relation similar to the above property for the edge-densities between the cluster pairs would hold. For this purpose, we use a slightly modified version of the volume regularity’s notion introduced in [2]. Definition 2 Let G= (V, W)be an edge-weighted graph with Vol(V)=1. The disjoint pair A, B ⊆Vis α-volume regular if for all X⊆A,Y⊆Bwe have |w(X, Y )−ρ(A, B)Vol(X)Vol(Y)| ≤ αqVol(A)Vol(B), where ρ(A, B) = w(A,B) Vol(A)Vol(B)is the relative inter-cluster density of (A, B). In the ideal k-cluster case, let us consider the following generalized random simple graph model: given the partition (V1, . . . , Vk) of V(|V|=n), vertices i∈Vaand j∈Vbare connected with probability pab, independently of each other, 1 ≤a, b ≤k. We can think of the probability pab as the inter-cluster density of the pair (Va, Vb). Since generalized random graphs can be viewed as edge-weighted graphs with a special block-structure burdened with random noise, based on [7], we are able to give the following spectral characterization of them. Fixing k, and tending with nto infinity in such a way that the cluster sizes grow at the same rate, there exists a positive number θ < 1, independent of n, such that for every 0 < τ < 1/2 there are exactly k−1 eigenvalues of MDgreater than θ−n−τ, while all the others are at most n−τin absolute value. Further, the k-variance of the vertex representatives constructed by the k−1 transformed structural eigenvectors is O(n−2τ), and the cluster pairs are α-volume regular with any small α, almost surely. Note that generalized quasirandom graphs defined in [18] are deterministic counterparts of generalized random graphs with the same spectral properties. Theorem 3 Let G= (V, W)be a connected edge-weighted graph on nvertices, with generalized degrees d1, . . . , dnand degree matrix D. Assume that Vol(V) = 1, and there are no dominant vertices, i.e., di= Θ(1/n),i= 1, . . . , n, as n→ ∞. Let the eigenvalues of MD, enumerated in decreasing absolute values, be 1≥ |µ1| ≥ ··· ≥ |µk−1|> ε ≥ |µk| ≥ ··· ≥ |µn|= 0. The partition (V1, . . . , Vk)of Vis defined so that it minimizes the weighted k-variance S2 k(X∗)of the optimum vertex representatives – defined in (2) – obtained as row vectors of the n×(k−1) matrix X∗of column vectors D−1/2ui, where uiis the unit-norm eigenvector corresponding to µi(i= 1, . . . , k −1). Assume that there is a constant 0< K ≤1 ksuch that |Vi| ≥ Kn,i= 1, . . . , k. With the notation s=qS2 k(X∗), the (Vi, Vj)pairs are O(√2ks +ε)-volume regular (i6=j)and for the clusters Vi(i= 1, . . . , k)the following holds: for 5 all X, Y ⊂Vi, |w(X, Y )−ρ(Vi)Vol(X)Vol(Y)|=O(√2ks +ε)Vol(Vi), where ρ(Vi) = w(Vi,Vi) Vol2(Vi)is the relative intra-cluster density of Vi. Note that, in Section 2, we indexed the eigenvalues of MDin non-increasing order and denoted them by λ’s. The set of all λi’s is the same as that of all µi’s. Nonetheless, we need a different notation for the eigenvalues indexed in decreasing order of their absolute values. Recall that 1 cannot be an eigenvalue of MDif Gis connected. Consequently, |µ1|= 1 can be if and only if µ1=−1, i.e., if Gis bipartite. For example, if the conditions of the above theorem hold with k= 2 and µ1=−1 (|µi| ≤ ε,i≥2), then our graph is a bipartite expander discussed in [1] in details. For the proof we need the definition of the cut norm of a matrix (see e.g., [16]) and the relation between it and the spectral norm. Definition 4 The cut norm of the real matrix Awith row-set Row and columnset Col is kAk= max R⊂Row, C⊂Col X i∈RX j∈C aij . Lemma 5 For every m×nreal matrix A, kAk≤√mnkAk, where the right hand side contains the spectral norm, i.e. the largest singular value of A. PROOF. kAk= max x∈{0,1}m,y∈{0,1}n|xTAy|= max x∈{0,1}m,y∈{0,1}n (x kxk)TA(y kyk)·kxk·kyk| ≤√mn max kxk=1,kyk=1 |xTAy|=√mnkAk, since for x∈ {0,1}m,kxk ≤ √m, and for y∈ {0,1}n,kyk ≤ √n.2 The definition of the cut norm and the result of the above lemma naturally extends to symmetric matrices with m=n, the spectral norm of which is the maximum of absolute values of their eigenvalues. PROOF. (Theorem 3). Recall that the spectrum of D−1/2WD−1/2differs from that of MDonly in the following: it contains the eigenvalue µ0= 1 with 6 corresponding unit-norm eigenvector u0=√dinstead of the eigenvalue 0 of MDwith the same eigenvector. If Gis connected, 1 is a simple eigenvalue. The optimum (k−1)-dimensional representatives of the vertices are row vectors of the matrix X∗= (x∗ 1,...,x∗ k−1), where x∗ i=D−1/2ui(i= 1, . . . , k −1). The representatives can as well be regarded as k-dimensional ones, as inserting the vector x∗ 0=D−1/2u0=1will not change the k-variance s2=S2 k(X∗). Assume that the minimum k-variance is attained on the k-partition (V1, . . . , Vk) of the vertices. By an easy analysis of variance argument (see [5]) it follows that s2= k−1 X i=0 dist2(ui, F),(3) where F=Span {D1/2z1,...,D1/2zk}with the so-called normalized partition vectors z1,...,zkof coordinates zji =1 √Vol(Vi)if j∈Viand 0, otherwise (i= 1, . . . , k). Note that the vectors D1/2z1,...,D1/2zkform an orthonormal system. By considerations proved in [5], we can find another orthonormal system v0,...,vk−1∈Fsuch that s2≤ k−1 X i=0 kui−vik2≤2s2(4) (v0=u0, since u0∈F). We approximate the matrix D−1/2WD−1/2= Pn−1 i=0 µiuiuT iby the rank kmatrix Pk−1 i=0 µivivT iwith the following accuracy (in spectral norm):      n−1 X i=0 µiuiuT i− k−1 X i=0 µivivT i    ≤ k−1 X i=0 |µi|·  uiuT i−vivT i  +     n−1 X i=k µiuiuT i     (5) which can be estimated from above with Pk−1 i=0 sin αi+ε≤Pk−1 i=0 kui−vik+ε≤ √2ks+ε, where αiis the angle between uiand vi, and for it, sin αi 2=1 2kui−vik holds, i= 0, . . . , k −1. Based on these considerations and relation between the cut norm and the spectral norm (see Lemma 5), the densities to be estimated in the defining formula of volume regularity can be written in terms of stepwise constant vectors in the following way. The vectors yi:= D−1/2viare stepwise constants on the partition (V1, . . . , Vk), i= 0, . . . , k −1. The matrix Pk−1 i=0 λiyiyT iis therefore a symmetric block-matrix on k×kblocks belonging to the above partition of the vertices. Let ˆwab denote its entries in the (a, b) block (a, b = 1, . . . , k). Using (5), the rank kapproximation of the matrix Wis performed with the following accuracy of the perturbation E: kEk=     W−D( k−1 X i=0 µiyiyT i)D     =     D1/2(D−1/2WD−1/2− k−1 X i=0 µivivT i)D1/2     . 7 Therefore, the entries of W– for i∈Va,j∈Vb– can be decomposed as wij =didjˆwab +ηij, where the cut norm of the n×nsymmetric error matrix E= (ηij) restricted to Va×Vb(otherwise it contains entries all zeros) and denoted by Eab, is estimated as follows: kEabk≤nkEabk ≤ n·kD1/2 ak·(√2ks +ε)·kD1/2 bk ≤n·v u u tc1 Vol(Va) |Va|·v u u tc1 Vol(Vb) |Vb|·(√2ks +ε) =c1·sn |Va|·sn |Vb|·qVol(Va)qVol(Vb)(√2ks +ε) ≤c1·1 KqVol(Va)qVol(Vb)(√2ks +ε) =cqVol(Va)qVol(Vb)(√2ks +ε). Here the diagonal matrix Dacontains the diagonal part of Drestricted to Va, otherwise zeros, and the constant cdoes not depend on n. Consequently, for a, b = 1, . . . , k and X⊆Va,Y⊆Vb: |w(X, Y )−ρ(Va, Vb)Vol(X)Vol(Y)|= X i∈XX j∈Y (didjˆwab +ηij)−Vol(X)Vol(Y) Vol(Va)Vol(Vb)X i∈VaX j∈Vb (didjˆwab +ηij) = X i∈XX j∈Y ηij −Vol(X)Vol(Y) Vol(Va)Vol(Vb)X i∈VaX j∈Vb ηij≤2c(√2ks +ε)qVol(Va)Vol(Vb), that gives the required statement both in the a6=band a=bcase. 2 Note that in the k= 2 special case, due to a theorem proved in [5], the 2-variance of the optimum 1-dimensional representatives can be directly estimated from above by the gap between the two largest absolute value eigenvalues of MD, and hence, the statement of Theorem 3 simplifies, see [8]. For a general k, we can make the following considerations. Assume that the normalized modularity spectrum (with decreasing absolute values) of G= (V, W) satisfies 1≥ |µ1| ≥ ··· ≥ |µk−1| ≥ θ > ε ≥ |µk| ≥ ··· ≥ |µn|= 0. Our purpose is to estimate swith the gap δ:= θ−ε. We will use the notation of the proof of Theorem 3 and apply the results of [4] for the perturbation of 8 spectral subspaces of the symmetric matrices A= n−1 X i=0 µiuiuT iand B= k−1 X i=0 µivivT i in the following situation. The subsets S1={µk, . . . , µn−1}and S2={µ0, . . . , µk−1} of the eigenvalues of D−1/2WD−1/2are separated by an annulus, where dist(S1, S2) = δ > 0. Denote by PAand PBthe projections onto the spectral subspaces of Aand Bspanned by the eigenvectors corresponding to the eigenvalues in S1 and S2, respectively: PA(S1) = n−1 X j=k ujuT j,PB(S2) = k−1 X i=0 vivT i. Then Theorem VII.3.4 of [4] implies that kPAPBkF≤1 δkPA(A−B)PBkF,(6) where k.kFdenotes the Frobenius norm. On the left hand side, kPAPBkF= qPk−1 i=0 sin2αi, and in view of kui−vik= 2 sin αi 2and (4), this is between √3 2s and s. On the right hand side, PAAPB−PABPB= (PAA)PB−PA(PBB) = k−1 X i=0 n−1 X j=k (µj−µi)uT j(ui−vi)ujvT i, where the Frobenius norm of the rank 1 matrices ujvT iis 1, and the inner product uT j(ui−vi) is the smaller if the ui’s and the vi’s are the closer (i= 1, . . . , k −1). Therefore, by the inequality (6), sis the smaller if δis the larger and the |µj−µi|differences for i= 0, . . . , k −1; j=k, . . . , n −1 are closer to δ. If |µk|=εis small, then |µ1|,...,|µk−1|should be close to each other (µ0= 1 does not play an important role because of u0=v0). 4 Testability of the normalized modularity spectrum and eigensubspaces Authors of [12] defined the testability of simple graph parameters and proved equivalent notions of this testability. They also anticipated that their results remain valid if they consider weighted graph sequences (Gn) with edge-weights in the [0,1] interval and no dominant vertex-weights αi(Gn)>0 (i= 1, . . . , n), i.e., maxiαi(Gn) αGn→0 as n→ ∞, where αGn=Pn i=1 αi(Gn). To this end, in [11], we slightly modified the definition of a testable graph parameter for weighted graphs in the following way. 9 and the spectral decomposition of its normalized modularity matrix runs in polynomial time in the reduced number of the vertices. Under the vertexand cluster-balance conditions this method can give quite good approximations for the multiway cuts and helps us to find the number of clusters and identify the cluster structure. In addition, taking into account both the positive and negative, large absolute value eigenvalues together with eigenvectors, regular cuts can also be detected, as the investigated spectral characteristics give good estimates for the volume regularity’s constant of the cluster pairs by Theorem 3. Such regular cuts are of importance in social or biological networks, e.g., if we want to find equally functioning synapses of the brain. Acknowledgements We thank the anonymous referee for his/her constructive comments. References [1] Alon, N., 1986 Eigenvalues and expanders, Combinatorica 6(1986), 83-96. [2] Alon, N., Coja-Oghlan, A., Han, H., Kang, M., R¨odl, V., and Schacht, M., Quasi-randomness and algorithmic regularity for graphs with general degree distributions, Siam J. Comput. 39 (6) (2010), 2336-2362. [3] Azran, A. and Ghahramani, Z., Spectral methods for automatic multiscale data clustering, in Proceedings of the CVPR Conference (2006), pp. 190-197. [4] Bhatia, R., Matrix Analysis, Springer, New York, 1997. [5] Bolla, M. and Tusn´ady, G., Spectra and optimal partitions of weighted graphs, Discret. Math. 128 (1994), 1-20. [6] Bolla, M. and Moln´ar-S´aska, G., Isoperimetric properties of weighted graphs related to Laplacian spectrum and canonical correlations, Studia Sci. Math. Hun. 39 (2002), 425-441. [7] Bolla, M., Recognizing linear structure in noisy matrices, Lin. Alg. Appl. 402 (2005), 228-244. [8] Bolla, M., Beyond the expanders, International Journal of Combinatorics, Paper 787596 (2011). [9] Bolla, M., Penalized versions of the Newman–Girvan modularity and their relation to multiway cuts and k-means clustering, Physical Review E 84, 016108 (2011). 16 [10] Bolla, M., Spectra and structure of weighted graphs, Electronic Notes in Discret. Math. 38 (2011), 149-154. [11] Bolla, M., K´oi, T., Kr´amli, A., Testability of minimum balanced multiway cut densities, Discret. Appl. Math. 160 (2012), 1019–1027. [12] Borgs, C., Chayes, J. T., Lov´asz, L., T.-S´os, V., and Vesztergombi, K., Convergent Sequences of Dense Graphs I: Subgraph Frequencies, Metric Properties and Testing, Advances in Math. 219 (2008), 1801-1851. [13] Borgs, C., Chayes, J. T., Lov´asz, L., T.-S´os, V., and Vesztergombi, K., Convergent Sequences of Dense Graphs II: Multiway Cuts and Statistical Physics, Annals of Math. 176, 151–219. [14] Chung, F., Spectral Graph Theory, CBMS Regional Conference Series in Mathematics 92, American Mathematical Society, 1997. [15] Chung, F. and Graham, R., Quasi-random graphs with given degree sequences, Random Structures and Algorithms 12 (2008), 1-19. [16] Frieze, A. and Kannan, R., Quick approximation to matrices and applications. Combinatorica 19 (1999), 175–220. [17] Hoory, S., Linial, N., and Widgerson, A., Expander graphs and their applications, Bulletin (New series) of the American Mathematical Society 43 (4) (2006), 439-561. [18] Lov´asz, L. and T.-S´os, V., Generalized quasirandom graphs, J. Comb. Theory B. 98 (2008), 146-163. [19] Lov´asz L, L. and Szegedy, B., Finitely forcible graphons, J. Comb. Theory B. 101 (2011), 269–301. [20] Meil˘a, M. and Shi, J., Learning segmentation by random walks, in Proceedings of the NIPS (Neural Information Processing Systems) 13 Conference, T. K. Leen, T. G. Dietterich, and V. Tresp eds, MIT Press, Cambridge (2001), pp. 873-879. [21] Newman, M. E. J., Finding community structure in networks using the eigenvectors of matrices, Physical Review E 74, 036104 (2006). [22] Reichardt, J. and Bornholdt, S., Partitioning and modularity of graphs with arbitrary degree distribution, Physical Review E 76, 015102(R) (2007). [23] R´enyi, A., On measures of dependence, Acta Math. Acad. Sci. Hungar. 10 (1959), 441-451. 17