Hierarchical Block Structures and High-Resolution Model Selection in Large Networks
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 stat...
| Main Author: | |
|---|---|
| Format: | Article |
| Language: | English |
| Published: |
American Physical Society
2014-03-01
|
| Series: | Physical Review X |
| Online Access: | http://doi.org/10.1103/PhysRevX.4.011047 |
| _version_ | 1818984605802299392 |
|---|---|
| author | Tiago P. Peixoto |
| author_facet | Tiago P. Peixoto |
| author_sort | Tiago P. Peixoto |
| collection | DOAJ |
| description | 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. |
| first_indexed | 2024-12-20T18:21:40Z |
| format | Article |
| id | doaj.art-bc45992e808d42f4b843c40ed339cffc |
| institution | Directory Open Access Journal |
| issn | 2160-3308 |
| language | English |
| last_indexed | 2024-12-20T18:21:40Z |
| publishDate | 2014-03-01 |
| publisher | American Physical Society |
| record_format | Article |
| series | Physical Review X |
| spelling | doaj.art-bc45992e808d42f4b843c40ed339cffc2022-12-21T19:30:15ZengAmerican Physical SocietyPhysical Review X2160-33082014-03-014101104710.1103/PhysRevX.4.011047Hierarchical Block Structures and High-Resolution Model Selection in Large NetworksTiago P. PeixotoDiscovering 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.http://doi.org/10.1103/PhysRevX.4.011047 |
| spellingShingle | Tiago P. Peixoto Hierarchical Block Structures and High-Resolution Model Selection in Large Networks Physical Review X |
| title | Hierarchical Block Structures and High-Resolution Model Selection in Large Networks |
| title_full | Hierarchical Block Structures and High-Resolution Model Selection in Large Networks |
| title_fullStr | Hierarchical Block Structures and High-Resolution Model Selection in Large Networks |
| title_full_unstemmed | Hierarchical Block Structures and High-Resolution Model Selection in Large Networks |
| title_short | Hierarchical Block Structures and High-Resolution Model Selection in Large Networks |
| title_sort | hierarchical block structures and high resolution model selection in large networks |
| url | http://doi.org/10.1103/PhysRevX.4.011047 |
| work_keys_str_mv | AT tiagoppeixoto hierarchicalblockstructuresandhighresolutionmodelselectioninlargenetworks |