Modularity (networks)

For other uses, see Modularity.

Example of modularity measurement and colouring on a scale-free network.

Modularity is a measure of the structure of networks or graphs which measures the strength of division of a network into modules (also called groups, clusters or communities). Networks with high modularity have dense connections between the nodes within modules but sparse connections between nodes in different modules. Modularity is often used in optimization methods for detecting community structure in networks. Biological networks, including animal brains, exhibit a high degree of modularity. However, modularity maximization is not statistically consistent, and finds communities in its own null model, i.e. fully random graphs, and therefore it cannot be used to find statistically significant community structures in empirical networks. Furthermore, it has been shown that modularity suffers a resolution limit and, therefore, it is unable to detect small communities.

Motivation

Many scientifically important problems can be represented and empirically studied using networks. For example, biological and social patterns, the World Wide Web, metabolic networks, food webs, neural networks and pathological networks are real world problems that can be mathematically represented and topologically studied to reveal some unexpected structural features. ^[1] Most of these networks possess a certain community structure that has substantial importance in building an understanding regarding the dynamics of the network. For instance, a closely connected social community will imply a faster rate of transmission of information or rumor among them than a loosely connected community. Thus, if a network is represented by a number of individual nodes connected by links which signify a certain degree of interaction between the nodes, communities are defined as groups of densely interconnected nodes that are only sparsely connected with the rest of the network. Hence, it may be imperative to identify the communities in networks since the communities may have quite different properties such as node degree, clustering coefficient, betweenness, centrality, ^[2] etc., from that of the average network. Modularity is one such measure, which when maximized, leads to the appearance of communities in a given network.

Definition

Modularity is the fraction of the edges that fall within the given groups minus the expected fraction if edges were distributed at random. The value of the modularity for unweighted and undirected graphs lies in the range ${\displaystyle [-1/2,1]}$. ^[3] It is positive if the number of edges within groups exceeds the number expected on the basis of chance. For a given division of the network's vertices into some modules, modularity reflects the concentration of edges within modules compared with random distribution of links between all nodes regardless of modules.

There are different methods for calculating modularity. ^[1] In the most common version of the concept, the randomization of the edges is done so as to preserve the degree of each vertex. Consider a graph with ${\displaystyle n}$ nodes and ${\displaystyle m}$ links (edges) such that the graph can be partitioned into two communities using a membership variable ${\displaystyle s}$. If a node ${\displaystyle v}$ belongs to community 1, ${\displaystyle s_{v}=1}$, or if ${\displaystyle v}$ belongs to community 2, ${\displaystyle s_{v}=-1}$. Let the adjacency matrix for the network be represented by ${\displaystyle A}$, where ${\displaystyle A_{vw}=0}$ means there's no edge (no interaction) between nodes ${\displaystyle v}$ and ${\displaystyle w}$ and ${\displaystyle A_{vw}=1}$ means there is an edge between the two. Also for simplicity we consider an undirected network. Thus ${\displaystyle A_{vw}=A_{wv}}$. (It is important to note that multiple edges may exist between two nodes, but here we assess the simplest case).

Modularity ${\displaystyle Q}$ is then defined as the fraction of edges that fall within group 1 or 2, minus the expected number of edges within groups 1 and 2 for a random graph with the same node degree distribution as the given network.

The expected number of edges shall be computed using the concept of a configuration model. ^[4] The configuration model is a randomized realization of a particular network. Given a network with ${\displaystyle n}$ nodes, where each node ${\displaystyle v}$ has a node degree ${\displaystyle k_{v}}$, the configuration model cuts each edge into two halves, and then each half edge, called a stub, is rewired randomly with any other stub in the network, even allowing self-loops (which occur when a stub is rewired to another stub from the same node) and multiple-edges between the same two nodes. Thus, even though the node degree distribution of the graph remains intact, the configuration model results in a completely random network.

Expected Number of Edges Between Nodes

Now consider two nodes ${\displaystyle v}$ and ${\displaystyle w}$, with node degrees ${\displaystyle k_{v}}$ and ${\displaystyle k_{w}}$ respectively, from a randomly rewired network as described above. We calculate the expected number of full edges between these nodes.

Let us consider each of the ${\displaystyle k_{v}}$ stubs of node ${\displaystyle v}$ and create associated indicator variables ${\displaystyle I_{i}^{(v,w)}}$ for them, ${\displaystyle i=1,\ldots ,k_{v}}$, with ${\displaystyle I_{i}^{(v,w)}=1}$ if the ${\displaystyle i}$-th stub happens to connect to one of the ${\displaystyle k_{w}}$ stubs of node ${\displaystyle w}$ in this particular random graph. If it does not, then ${\displaystyle I_{i}^{(v,w)}=0}$. Since the ${\displaystyle i}$-th stub of node ${\displaystyle v}$ can connect to any of the ${\displaystyle 2m-1}$ remaining stubs with equal probability, and since there are ${\displaystyle k_{w}}$ stubs it can connect to associated with node ${\displaystyle w}$, evidently

${\displaystyle p(I_{i}^{(v,w)}=1)=E[I_{i}^{(v,w)}]={\frac {k_{w}}{2m-1}}}$

The total number of full edges ${\displaystyle J_{vw}}$ between ${\displaystyle v}$ and ${\displaystyle w}$ is just ${\displaystyle J_{vw}=\sum _{i=1}^{k_{v}}I_{i}^{(v,w)}}$, so the expected value of this quantity is

${\displaystyle E[J_{vw}]=E\left[\sum _{i=1}^{k_{v}}I_{i}^{(v,w)}\right]=\sum _{i=1}^{k_{v}}E[I_{i}^{(v,w)}]=\sum _{i=1}^{k_{v}}{\frac {k_{w}}{2m-1}}={\frac {k_{v}k_{w}}{2m-1}}}$

Many texts then make the following approximations, for random networks with a large number of edges. When ${\displaystyle m}$ is large, they drop the subtraction of ${\displaystyle 1}$ in the denominator above and simply use the approximate expression ${\displaystyle {\frac {k_{v}k_{w}}{2m}}}$ for the expected number of edges between two nodes. Additionally, in a large random network, the number of self-loops and multi-edges is vanishingly small. ^[5] Ignoring self-loops and multi-edges allows one to assume that there is at most one edge between any two nodes. In that case, ${\displaystyle J_{vw}}$ becomes a binary indicator variable, so its expected value is also the probability that it equals ${\displaystyle 1}$, which means one can approximate the probability of an edge existing between nodes ${\displaystyle v}$ and ${\displaystyle w}$ as ${\displaystyle {\frac {k_{v}k_{w}}{2m}}}$.

Modularity

Hence, the difference between the actual number of edges between node ${\displaystyle v}$ and ${\displaystyle w}$ and the expected number of edges between them is

${\displaystyle A_{vw}-{\frac {k_{v}k_{w}}{2m}}}$

Summing over all node pairs gives the equation for modularity, ${\displaystyle Q}$. ^[1]

${\displaystyle Q={\frac {1}{2m}}\sum _{vw}\left[A_{vw}-{\frac {k_{v}k_{w}}{2m}}\right]{\frac {s_{v}s_{w}+1}{2}}}$

(3)

It is important to note that Eq. 3 holds good for partitioning into two communities only. Hierarchical partitioning (i.e. partitioning into two communities, then the two sub-communities further partitioned into two smaller sub communities only to maximize Q) is a possible approach to identify multiple communities in a network. Additionally, (3) can be generalized for partitioning a network into c communities. ^[6]

${\displaystyle Q={\frac {1}{(2m)}}\sum _{vw}\left[A_{vw}-{\frac {k_{v}k_{w}}{(2m)}}\right]\delta (c_{v},c_{w})=\sum _{i=1}^{c}(e_{ii}-a_{i}^{2})}$

(4)

where e_ij is the fraction of edges with one end vertices in community i and the other in community j:

${\displaystyle e_{ij}=\sum _{vw}{\frac {A_{vw}}{2m}}1_{v\in c_{i}}1_{w\in c_{j}}}$

and a_i is the fraction of ends of edges that are attached to vertices in community i:

${\displaystyle a_{i}={\frac {k_{i}}{2m}}=\sum _{j}e_{ij}}$

Example of multiple community detection

We consider an undirected network with 10 nodes and 12 edges and the following adjacency matrix.

Fig 1. Sample Network corresponding to the Adjacency matrix with 10 nodes, 12 edges.

Fig 2. Network partitions that maximize Q. Maximum Q=0.4896

Node ID	1	2	3	4	5	6	7	8	9	10
1	0	1	1	0	0	0	0	0	0	1
2	1	0	1	0	0	0	0	0	0	0
3	1	1	0	0	0	0	0	0	0	0
4	0	0	0	0	1	1	0	0	0	1
5	0	0	0	1	0	1	0	0	0	0
6	0	0	0	1	1	0	0	0	0	0
7	0	0	0	0	0	0	0	1	1	1
8	0	0	0	0	0	0	1	0	1	0
9	0	0	0	0	0	0	1	1	0	0
10	1	0	0	1	0	0	1	0	0	0

The communities in the graph are represented by the red, green and blue node clusters in Fig 1. The optimal community partitions are depicted in Fig 2.

Matrix formulation

An alternative formulation of the modularity, useful particularly in spectral optimization algorithms, is as follows. ^[1] Define ${\displaystyle S_{vr}}$ to be ${\displaystyle 1}$ if vertex ${\displaystyle v}$ belongs to group ${\displaystyle r}$ and ${\displaystyle 0}$ otherwise. Then

${\displaystyle \delta (c_{v},c_{w})=\sum _{r}S_{vr}S_{wr}}$

and hence

${\displaystyle Q={\frac {1}{2m}}\sum _{vw}\sum _{r}\left[A_{vw}-{\frac {k_{v}k_{w}}{2m}}\right]S_{vr}S_{wr}={\frac {1}{2m}}\mathrm {Tr} (\mathbf {S} ^{\mathrm {T} }\mathbf {BS} ),}$

where ${\displaystyle S}$ is the (non-square) matrix having elements ${\displaystyle S_{v}}$ and ${\displaystyle B}$ is the so-called modularity matrix, which has elements

${\displaystyle B_{vw}=A_{vw}-{\frac {k_{v}k_{w}}{2m}}.}$

All rows and columns of the modularity matrix sum to zero, which means that the modularity of an undivided network is also always ${\displaystyle 0}$.

For networks divided into just two communities, one can alternatively define ${\displaystyle s_{v}=\pm 1}$ to indicate the community to which node ${\displaystyle v}$ belongs, which then leads to

${\displaystyle Q={1 \over 4m}\sum _{vw}B_{vw}s_{v}s_{w}={1 \over 4m}\mathbf {s} ^{\mathrm {T} }\mathbf {Bs} ,}$

where ${\displaystyle s}$ is the column vector with elements ${\displaystyle s_{v}}$. ^[1]

This function has the same form as the Hamiltonian of an Ising spin glass, a connection that has been exploited to create simple computer algorithms, for instance using simulated annealing, to maximize the modularity. The general form of the modularity for arbitrary numbers of communities is equivalent to a Potts spin glass and similar algorithms can be developed for this case also. ^[7]

Overfitting

Although the method of modularity maximization is motivated by computing a deviation from a null model, this deviation is not computed in a statistically consistent manner. ^[8] Because of this, the method notoriously finds high-scoring communities in its own null model ^[9] (the configuration model), which by definition cannot be statistically significant. Because of this, the method cannot be used to reliably obtain statistically significant community structure in empirical networks.

Resolution limit

Modularity compares the number of edges inside a cluster with the expected number of edges that one would find in the cluster if the network were a random network with the same number of nodes and where each node keeps its degree, but edges are otherwise randomly attached. This random null model implicitly assumes that each node can get attached to any other node of the network. This assumption is however unreasonable if the network is very large, as the horizon of a node includes a small part of the network, ignoring most of it. Moreover, this implies that the expected number of edges between two groups of nodes decreases if the size of the network increases. So, if a network is large enough, the expected number of edges between two groups of nodes in modularity's null model may be smaller than one. If this happens, a single edge between the two clusters would be interpreted by modularity as a sign of a strong correlation between the two clusters, and optimizing modularity would lead to the merging of the two clusters, independently of the clusters' features. So, even weakly interconnected complete graphs, which have the highest possible density of internal edges, and represent the best identifiable communities, would be merged by modularity optimization if the network were sufficiently large. ^[10] For this reason, optimizing modularity in large networks would fail to resolve small communities, even when they are well defined. This bias is inevitable for methods like modularity optimization, which rely on a global null model. ^[11]

Multiresolution methods

There are two main approaches which try to solve the resolution limit within the modularity context: the addition of a resistance r to every node, in the form of a self-loop, which increases (r>0) or decreases (r<0) the aversion of nodes to form communities; ^[12] or the addition of a parameter γ>0 in front of the null-case term in the definition of modularity, which controls the relative importance between internal links of the communities and the null model. ^[7] Optimizing modularity for values of these parameters in their respective appropriate ranges, it is possible to recover the whole mesoscale of the network, from the macroscale in which all nodes belong to the same community, to the microscale in which every node forms its own community, hence the name multiresolution methods. However, it has been shown that these methods have limitations when communities are very heterogeneous in size. ^[13]

Software Tools

There are a couple of software tools available that are able to compute clusterings in graphs with good modularity.

Original implementation of the multi-level Louvain method. ^[14]

The Leiden algorithm which additionally avoids unconnected communities. ^[15]

The Vienna Graph Clustering (VieClus) algorithm, a parallel memetic algorithm. ^[16]

See also

• Complex network
• Community structure
• Null model
• Percolation theory

References

1. Newman, M. E. J. (2006). "Modularity and community structure in networks". Proceedings of the National Academy of Sciences of the United States of America. 103 (23): 8577–8696. arXiv: physics/0602124 . Bibcode:2006PNAS..103.8577N. doi: 10.1073/pnas.0601602103 . PMC   1482622 . PMID   16723398.
2. Newman, M. E. J. (2007). Palgrave Macmillan, Basingstoke (ed.). "Mathematics of networks". The New Palgrave Encyclopedia of Economics (2 ed.).
3. Brandes, U.; Delling, D.; Gaertler, M.; Gorke, R.; Hoefer, M.; Nikoloski, Z.; Wagner, D. (February 2008). "On Modularity Clustering". IEEE Transactions on Knowledge and Data Engineering. 20 (2): 172–188. doi:10.1109/TKDE.2007.190689. S2CID   150684.
4. van der Hofstad, Remco (2013). "Chapter 7" (PDF). Random Graphs and Complex Networks. Archived (PDF) from the original on 2013-12-18. Retrieved 2013-12-08.
5. "NetworkScience". Albert-László Barabási. Archived from the original on 2020-03-05. Retrieved 2020-03-20.
6. Clauset, Aaron and Newman, M. E. J. and Moore, Cristopher (2004). "Finding community structure in very large networks". Phys. Rev. E. 70 (6): 066111. arXiv: cond-mat/0408187 . Bibcode:2004PhRvE..70f6111C. doi:10.1103/PhysRevE.70.066111. PMID   15697438. S2CID   8977721.
7. Joerg Reichardt & Stefan Bornholdt (2006). "Statistical mechanics of community detection". Physical Review E. 74 (1): 016110. arXiv: cond-mat/0603718 . Bibcode:2006PhRvE..74a6110R. doi:10.1103/PhysRevE.74.016110. PMID   16907154. S2CID   792965.
8. Peixoto, Tiago P. (2021). "Descriptive vs. inferential community detection: pitfalls, myths and half-truths". arXiv: 2112.00183 .
9. Guimera, Roger; Sales-Pardo, Marta (August 19, 2004), "Modularity from fluctuations in random graphs and complex networks", Physical Review, 70 (2): 025101, arXiv: cond-mat/0403660 , Bibcode:2004PhRvE..70b5101G, doi:10.1103/PhysRevE.70.025101, PMC   2441765 , PMID   15447530
10. Santo Fortunato & Marc Barthelemy (2007). "Resolution limit in community detection". Proceedings of the National Academy of Sciences of the United States of America. 104 (1): 36–41. arXiv: physics/0607100 . Bibcode:2007PNAS..104...36F. doi: 10.1073/pnas.0605965104 . PMC   1765466 . PMID   17190818.
11. J.M. Kumpula; J. Saramäki; K. Kaski & J. Kertész (2007). "Limited resolution in complex network community detection with Potts model approach". European Physical Journal B. 56 (1): 41–45. arXiv: cond-mat/0610370 . Bibcode:2007EPJB...56...41K. doi:10.1140/epjb/e2007-00088-4. S2CID   4411525.
12. Alex Arenas, Alberto Fernández and Sergio Gómez (2008). "Analysis of the structure of complex networks at different resolution levels". New Journal of Physics. 10 (5): 053039. arXiv: physics/0703218 . Bibcode:2008NJPh...10e3039A. doi:10.1088/1367-2630/10/5/053039. S2CID   11544197.
13. Andrea Lancichinetti & Santo Fortunato (2011). "Limits of modularity maximization in community detection". Physical Review E. 84 (6): 066122. arXiv: 1107.1155 . Bibcode:2011PhRvE..84f6122L. doi:10.1103/PhysRevE.84.066122. PMID   22304170. S2CID   16180375.
14. First implementation of Louvain algorithm, archived from the original on 2021-03-17, retrieved 2020-11-30
15. Leiden algorithm repository, 15 December 2021, archived from the original on 26 November 2020, retrieved 30 November 2020
16. Vienna graph clustering repository, 13 April 2021, archived from the original on 21 October 2020, retrieved 30 November 2020