  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.
