Modularity optimization in community detection of complex networks

EPL, 87 (2009) 38002
DOI: 10.1209/0295-5075/87/38002
Modularity optimization in community detection of complex networksX. S. Zhang1, R. S. Wang2, Y. Wang1, J. Wang1, Y. Qiu1, L. Wang1 and L. Chen3

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

zxs@amt.ac.cn

received 8 March 2009; accepted in final form 17 July 2009; published August 2009
published online 20 August 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 Qrevealed 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.

PACS
89.75.Fb - Structures and organization in complex systems.
89.75.Hc - Networks and genealogical trees.
02.10.Ox - Combinatorics; graph theory.

epl.pdf (548.39 KB)

2014-7-3 11:25:33 上传

请查收。