Research Article: Global vs local modularity for network community detection

Date Published: October 29, 2018

Publisher: Public Library of Science

Author(s): Shi Chen, Zhi-Zhong Wang, Liang Tang, Yan-Ni Tang, Yuan-Yuan Gao, Hui-Jia Li, Ju Xiang, Yan Zhang, Sergio Gómez.

http://doi.org/10.1371/journal.pone.0205284

Abstract

Community structures are ubiquitous in various complex networks, implying that the networks commonly be composed of groups of nodes with more internal links and less external links. As an important topic in network theory, community detection is of importance for understanding the structure and function of the networks. Optimizing statistical measures for community structures is one of most popular strategies for community detection in complex networks. In the paper, by using a type of self-loop rescaling strategy, we introduced a set of global modularity functions and a set of local modularity functions for community detection in networks, which are optimized by a kind of the self-consistent method. We carefully compared and analyzed the behaviors of the modularity-based methods in community detection, and confirmed the superiority of the local modularity for detecting community structures on large-size and heterogeneous networks. The local modularity can more quickly eliminate the first-type limit of modularity, and can eliminate or alleviate the second-type limit of modularity in networks, because of the use of the local information in networks. Moreover, we tested the methods in real networks. Finally, we expect the research can provide useful insight into the problem of community detection in complex networks.

Partial Text

Community structures are ubiquitous in various complex networks, examples including the biological networks, social networks and technological networks [1]. This means that the networks generally consist of communities (or modules) with dense internal connections and sparse external connections. Generally, the communities (or modules) in networks are closely related to functional units in real-world networks, such as cycles and pathways in metabolic networks and protein complexes in the protein-protein interaction networks [1, 2], and they may have quite different topological properties from those at the level of the entire networks [2–5] and affect the dynamics in the networks[6]. Therefore, identifying the communities is of importance for understanding the structures and functions of the networks.

The difference between the local and global modularity depends on the level of the local connectivity of communities in networks under study, while the difference between CM and ER depends on the heterogeneity in networks. To compare the behaviors of various modularity (Table 1), we conducted extensive simulations by tuning various parameters (Table 2). We use the normalized mutual information (NMI) to evaluate the performance of different modularity for detecting communities in the networks [22]. NMI can reflect the similarity between two community divisions, revealing the amount of extracted community information in a network with known community structures. NMI=1 if two community divisions are matched perfectly, and NMI<1 otherwise. Optimizing statistical measures for community structures is one of most important strategies for community detection in complex networks. In the paper, by using a type of self-loop rescaling strategy, we introduced a set of global modularity functions and a set of local modularity functions for community detection in networks. By a kind of the self-consistent method, the modularity functions are optimized for community detection.   Source: http://doi.org/10.1371/journal.pone.0205284

 

0 0 vote
Article Rating
Subscribe
Notify of
guest
0 Comments
Inline Feedbacks
View all comments