Modularity optimization in community detection of complex networks
Modularity optimization in community detection of complex networks
复制标题
DOI：
10.1209/0295-5075/87/38002
复制
发表时间：
2009-08
期刊：
影响因子：
--
通讯作者：
X. Zhang;R. Wang;Y. Wang;J. Wang;Y. Qiu;L. Wang;L. Chen
中科院分区：
文献类型：
--
作者：
X. Zhang;R. Wang;Y. Wang;J. Wang;Y. Qiu;L. Wang;L. Chen
发现复杂网络中的社团结构是网络科学中的一个基本而又具有挑战性的课题。模块性度量，如广泛使用的模块性函数Q和最近提出的模块性密度D，在将网络划分为社区时作为质量指标起着关键作用。在这封信中，我们揭示了复杂的行为的模块化优化在不同的社区定义的分析研究。令人惊讶的是，我们发现，除了在最近的研究中揭示的分辨率限制Q，Q和D遭受更严重的限制，即一些衍生社区不满足弱社区定义，甚至最弱社区定义。特别是，后一种情况，称为误识别，意味着这些社区可能有稀疏的连接，比他们之间的，这违反了基本的直觉意义上的子图是一个社区。使用离散凸优化框架，我们调查这些限制的根本原因，并提供在应用程序中的模块化措施的选择的见解。人工和现实生活中的网络的数值实验证实了理论分析。
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.