Hierarchical Block Structures and High-Resolution Model Selection in Large Networks
Hierarchical Block Structures and High-Resolution Model Selection in Large Networks
复制标题
DOI：
10.1103/physrevx.4.011047
复制
发表时间：
2014-03-24
影响因子：
12.5
通讯作者：
Peixoto, Tiago P.
中科院分区：
文献类型：
--
作者：
Peixoto, Tiago P.
发现和表征经验网络中的大规模拓扑特征是理解复杂系统如何运作的关键步骤。然而，大多数现有的方法用于获得网络的模块化结构遭受严重的问题，如被遗忘的统计证据支持所发现的模式，这导致无法分离的实际结构从噪声。除此之外，人们还观察到社区大小的分辨率限制，当网络变大时，较小但定义良好的集群无法检测到。这种现象发生在非常流行的模块化优化方法中，这种方法缺乏内置的统计验证，但也发生在基于统计推断和模型选择的更有原则的方法中，这些方法确实以形式上正确的方式结合了统计验证。在这里，我们构建了一个嵌套生成模型，通过在多个尺度上完整描述整个网络层次结构，能够避免这种限制，并能够在远远超出当前方法的水平上检测模块化结构。即使有这种增加的分辨率，该方法是基于简约的原则，并能够从噪声中分离信号，从而不会导致虚假模块的识别，即使在稀疏网络。此外，它完全概括了其他方法，因为它不限于纯粹的混合模式，有向或无向图，以及特设的层次结构，如二叉树。尽管它的一般特征，该方法是易于处理的，可以与先进的社区检测技术相结合，产生一个有效的算法，规模非常大的网络。
Discovering and characterizing the large-scale topological features in empirical networks are crucial steps in understanding how complex systems function. However, most existing methods used to obtain the modular structure of networks suffer from serious problems, such as being oblivious to the statistical evidence supporting the discovered patterns, which results in the inability to separate actual structure from noise. In addition to this, one also observes a resolution limit on the size of communities, where smaller but well-defined clusters are not detectable when the network becomes large. This phenomenon occurs for the very popular approach of modularity optimization, which lacks built-in statistical validation, but also for more principled methods based on statistical inference and model selection, which do incorporate statistical validation in a formally correct way. Here, we construct a nested generative model that, through a complete description of the entire network hierarchy at multiple scales, is capable of avoiding this limitation and enables the detection of modular structure at levels far beyond those possible with current approaches. Even with this increased resolution, the method is based on the principle of parsimony, and is capable of separating signal from noise, and thus will not lead to the identification of spurious modules even on sparse networks. Furthermore, it fully generalizes other approaches in that it is not restricted to purely assortative mixing patterns, directed or undirected graphs, and ad hoc hierarchical structures such as binary trees. Despite its general character, the approach is tractable and can be combined with advanced techniques of community detection to yield an efficient algorithm that scales well for very large networks.