This article has an erratum: [erratum]
Volume 87, Number 3, August 2009
|Number of page(s)||6|
|Section||Interdisciplinary Physics and Related Areas of Science and Technology|
|Published online||20 August 2009|
Modularity optimization in community detection of complex networks
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
Corresponding author: email@example.com
Accepted: 17 July 2009
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.
PACS: 89.75.Fb – Structures and organization in complex systems / 89.75.Hc – Networks and genealogical trees / 02.10.Ox – Combinatorics; graph theory
© EPLA, 2009
Current usage metrics show cumulative count of Article Views (full-text article views including HTML views, PDF and ePub downloads, according to the available data) and Abstracts Views on Vision4Press platform.
Data correspond to usage on the plateform after 2015. The current usage metrics is available 48-96 hours after online publication and is updated daily on week days.
Initial download of the metrics may take a while.