Robustness modularity in complex networks

Abstract

A basic question in network community detection is how modular a given network is. This is usually addressed by evaluating the quality of partitions detected in the network. The Girvan-Newman (GN) modularity function is the standard way to make this assessment, but it has a number of drawbacks. Most importantly, it is not clearly interpretable, given that the measure can take relatively large values on partitions of random networks without communities. Here we propose a new measure based on the concept of robustness: modularity is the probability to find trivial partitions when the structure of the network is randomly perturbed. This concept can be implemented for any clustering algorithm capable of telling when a group structure is absent. Tests on artificial and real graphs reveal that robustness modularity can be used to assess and compare the strength of the community structure of different networks. We also introduce two other quality functions: modularity difference, a suitably normalized version of the GN modularity; information modularity, a measure of distance based on information compression. Both measures are strongly correlated with robustness modularity, and are promising options as well.

arXiv comment17 pages, 16 figures. Code to calculated the proposed measures is freely available here: https://github.com/filipinascimento/RModularity

References in corpus (16)

• Emergence of scaling in random networks
• Fast unfolding of communities in large networks
• Community structure in social and biological networks
• Finding and evaluating community structure in networks
• Community detection in graphs
• Maps of random walks on complex networks reveal community structure
• Benchmark graphs for testing community detection algorithms
• Resolution limit in community detection
• Spatial Networks
• Stochastic blockmodels and community structure in networks
• Community detection in networks: A user guide
• Modularity from Fluctuations in Random Graphs and Complex Networks
• Robustness of community structure in networks
• Parsimonious module inference in large networks
• Community Detection in Bipartite Networks with Stochastic Blockmodels
• Mapping flows on sparse networks with missing links