Eur. Phys. J. B (2013) 86: 330
https://doi.org/10.1140/epjb/e2013-40169-1

Regular Article

Bad communities with high modularity

Faculty of Engineering, Aristotle University of Thessaloniki, 54124 Thessaloniki, Greece

^a e-mail: kehagiat@auth.gr

Received: 27 February 2013
Received in final form: 10 May 2013
Published online: 24 July 2013

Abstract

In this paper we discuss some problematic aspects of Newman and Girvan’s modularity function Q_N. Given a graph G, the modularity of G can be written as Q_N = Q_f − Q₀, where Q_f is the intracluster edge fraction of G and Q₀ is the expected intracluster edge fraction of the null model, i.e., a randomly connected graph with same expected degree distribution as G. It follows that the maximization of Q_N must accomodate two factors pulling in opposite directions:Q_f favors a small number of clusters and Q₀ favors many balanced (i.e., with approximately equal degrees) clusters. In certain cases the Q₀ term can cause overestimation of the true cluster number; this is the opposite of the well-known underestimation effect caused by the “resolution limit” of modularity. We illustrate the overestimation effect by constructing families of graphs with a “natural” community structure which, however, does not maximize modularity. In fact, we show there exist graphs G with a “natural clustering” V of G and another, balanced clustering U of G such that (i) the pair (G,U) has higher modularity than (G,V) and (ii) V and U are arbitrarily different.