Modularity and Mutual Information in Networks: Two Sides of the Same Coin.

Community structure is an important feature of many networks. One of the most popular ways to capture community structure is using a quantitative measure, modularity, which can serve as both a standard benchmark comparing different community detection algorithms, and a optimization objective for detecting communities. Previous works on modularity mainly focus on the approximation method for modularity maximization to detect communities, or minor modifications to the definition. In this paper, we study modularity from an information-theoretical perspective and show that modularity and mutual information in networks are essentially the same. The main contribution is that we develop a family of generalized modularity measure, $f$-Modularity, which includes the original modularity as a special case. At a high level, we show the significance of community structure is equivalent to the amount of information contained in the network. On the one hand, $f$-Modularity has an information-theoretical interpretation and enjoys the desired properties of mutual information measure. On the other hand, quantifying community structure also provides an approach to estimate the mutual information between discrete random samples with a large value space but given only limited samples. We demonstrate the algorithm for optimizing $f$-Modularity in a relatively general case, and validate it through experimental results on simulated networks. We also apply $f$-Modularity to real-world market networks. Our results bridge two important fields, complex network and information theory, and also shed light on the design of measures on community structure in the future.