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. 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, 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 [ − 1 / 2 , 1 ] {\displaystyle [-1/2,1]} . 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. 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 n {\displaystyle n} nodes and m {\displaystyle m} links (edges) such that the graph can be partitioned into two communities using a membership variable s {\displaystyle s} . If a node v {\displaystyle v} belongs to community 1, s v = 1 {\displaystyle s_{v}=1} , or if v {\displaystyle v} belongs to community 2, s v = − 1 {\displaystyle s_{v}=-1} . Let the adjacency matrix for the network be represented by A {\displaystyle A} , where A v w = 0 {\displaystyle A_{vw}=0} means there's no edge (no interaction) between nodes v {\displaystyle v} and w {\displaystyle w} and A v w = 1 {\displaystyle A_{vw}=1} means there is an edge between the two. Also for simplicity we consider an undirected network. Thus A v w = A w v {\displaystyle A_{vw}=A_{wv}} . (Multiple edges may exist between two nodes, but here we assess the simplest case). Modularity Q {\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. The configuration model is a randomized realization of a particular network. Given a network with n {\displaystyle n} nodes, where each node v {\displaystyle v} has a node degree k v {\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.
… excerpt ends here. Continue reading the full article.
