Modularity (networks)

Modularity is one measure of the structure of networks or graphs. It was designed to measure 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. However, it has been shown that modularity suffers a resolution limit and, therefore, it is unable to detect small communities. Biological networks, including animal brains, exhibit a high degree of modularity. l = ∑ u k u = 2 m {displaystyle l=sum _{u}k_{u}=2m}     (1) Q = 1 2 m ∑ v w [ A v w − k v k w 2 m ] s v s w + 1 2 {displaystyle Q={frac {1}{2m}}sum _{vw}left{frac {s_{v}s_{w}+1}{2}}}     (3) Q = 1 ( 2 m ) ∑ v w [ A v w − k v k w ( 2 m ) ] δ ( c v , c w ) = ∑ i = 1 c ( e i i − a i 2 ) {displaystyle Q={frac {1}{(2m)}}sum _{vw}leftdelta (c_{v},c_{w})=sum _{i=1}^{c}(e_{ii}-a_{i}^{2})}     (4) Modularity is one measure of the structure of networks or graphs. It was designed to measure 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. However, it has been shown that modularity suffers a resolution limit and, therefore, it is unable to detect small communities. Biological networks, including animal brains, exhibit a high degree of modularity. 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. 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 lies in the range [ − 1 , 1 ] {displaystyle } . 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}} . (It is important to note that multiple edges may exist between two nodes, but here we assess the simplest case).