Modularity optimization in community detection of complex networks Export

@article{citeulike:5687617, 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.}, author = {Zhang, X. S. and Wang, R. S. and Wang, Y. and Wang, J. and Qiu, Y. and Wang, L. and Chen, L.}, citeulike-article-id = {5687617}, citeulike-linkout-0 = {http://dx.doi.org/10.1209/0295-5075/87/38002}, doi = {10.1209/0295-5075/87/38002}, journal = {EPL (Europhysics Letters)}, keywords = {graphs, modularity, network, optimization}, number = {3}, pages = {38002+}, posted-at = {2009-09-16 15:16:20}, priority = {2}, title = {Modularity optimization in community detection of complex networks}, url = {http://dx.doi.org/10.1209/0295-5075/87/38002}, volume = {87}, year = {2009} }

TY - JOUR ID - citeulike:5687617 L3 - citeulike-article-id:5687617 N2 - 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. IS - 3 JF - EPL (Europhysics Letters) TI - Modularity optimization in community detection of complex networks VL - 87 SP - 38002 KW - graphs KW - modularity KW - network KW - optimization AU - Zhang, XS AU - Wang, RS AU - Wang, Y AU - Wang, J AU - Qiu, Y AU - Wang, L AU - Chen, L PY - 2009/// UR - http://dx.doi.org/10.1209/0295-5075/87/38002 ER -