Combinatorial approach to modularity.
Combinatorial approach to modularity.
复制标题
DOI：
10.1103/physreve.82.026102
复制
发表时间：
2010-04
期刊：
影响因子：
--
通讯作者：
F. Radicchi;Andrea Lancichinetti;J. Ramasco
中科院分区：
文献类型：
--
作者：
F. Radicchi;Andrea Lancichinetti;J. Ramasco
社区是具有高于平均密度的内部连接的节点集群。它们的检测对于更好地理解网络中存在的结构和层次结构具有重要意义。模块化已经成为社区检测领域的标准工具，同时提供了一种评估分区的方法，并通过最大化它来找到社区。在这项工作中，我们从组合的角度来研究模块性。我们的分析（作为模块化定义）依赖于使用的配置模型，一种技术，给定一个图产生一系列的随机副本保持度序列不变。我们开发了一种方法，列举了空模型分区，并可以用来计算模块度的概率分布函数。我们的理论允许深入调查的几个有趣的功能模块化，如其分辨率限制和统计的分区，最大化it.Additionally，极端的随机图分区的模块化的概率的研究开辟了道路的定义网络分区的统计意义。
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.