Modularity optimization in community detection of complex networks

¹  Academy of Mathematics and Systems Science, Chinese Academy of Sciences - Beijing, 100190, China
²  Department of Physics, The Pennsylvania State University - University Park, PA 16802, USA
³  Department of Electrical Engineering and Electronics, Osaka Sangyo University - Osaka 574-8530, Japan

Corresponding author: zxs@amt.ac.cn

Received: 8 March 2009
Accepted: 17 July 2009

Abstract

Detecting community structure in complex networks is a fundamental but challenging topic in network science. Modularity measures, such as widely used modularity function Q and recently suggested modularity density D, play critical roles as quality indices in partitioning a network into communities. In this letter, we reveal the complex behaviors of modularity optimization under different community definitions by an analytic study. Surprisingly, we find that in addition to the resolution limit of Q revealed in a recent study, both Q and D suffer from a more serious limitation, i.e. some derived communities do not satisfy the weak community definition or even the most weak community definition. Especially, the latter case, called as misidentification, implies that these communities may have sparser connection within them than between them, which violates the basic intuitive sense for a subgraph to be a community. Using a discrete convex optimization framework, we investigate the underlying causes for these limitations and provide insights on choices of the modularity measures in applications. Numerical experiments on artificial and real-life networks confirm the theoretical analysis.