Radicchi Filippo, Lancichinetti Andrea, Ramasco José J
Complex Networks Lagrange Laboratory, ISI Foundation, Turin, Italy.
Phys Rev E Stat Nonlin Soft Matter Phys. 2010 Aug;82(2 Pt 2):026102. doi: 10.1103/PhysRevE.82.026102. Epub 2010 Aug 4.
Communities are clusters of nodes with a higher than average density of internal connections. Their detection is of great relevance to better understand the structure and hierarchies present in a network. Modularity has become a standard tool in the area of community detection, providing at the same time a way to evaluate partitions and, by maximizing it, a method to find communities. In this work, we study the modularity from a combinatorial point of view. Our analysis (as the modularity definition) relies on the use of the configurational model, a technique that given a graph produces a series of randomized copies keeping the degree sequence invariant. We develop an approach that enumerates the null model partitions and can be used to calculate the probability distribution function of the modularity. Our theory allows for a deep inquiry of several interesting features characterizing modularity such as its resolution limit and the statistics of the partitions that maximize it. Additionally, the study of the probability of extremes of the modularity in the random graph partitions opens the way for a definition of the statistical significance of network partitions.
社区是内部连接密度高于平均水平的节点集群。对它们的检测对于更好地理解网络中存在的结构和层次至关重要。模块性已成为社区检测领域的标准工具，它同时提供了一种评估划分的方法，并且通过最大化模块性，还提供了一种寻找社区的方法。在这项工作中，我们从组合的角度研究模块性。我们的分析（如同模块性定义一样）依赖于配置模型的使用，这是一种给定一个图就能生成一系列保持度序列不变的随机副本的技术。我们开发了一种方法来枚举空模型划分，并可用于计算模块性的概率分布函数。我们的理论允许深入探究表征模块性的几个有趣特征，例如其分辨率极限以及使模块性最大化的划分的统计特性。此外，对随机图划分中模块性极值概率的研究为定义网络划分的统计显著性开辟了道路。
