Compression of Flow Can Reveal Overlapping-Module Organization in Networks
arXiv:1105.0812 · doi:10.1103/PhysRevX.1.021025
Abstract
To better understand the overlapping modular organization of large networks with respect to flow, here we introduce the map equation for overlapping modules. In this information-theoretic framework, we use the correspondence between compression and regularity detection. The generalized map equation measures how well we can compress a description of flow in the network when we partition it into modules with possible overlaps. When we minimize the generalized map equation over overlapping network partitions, we detect modules that capture flow and determine which nodes at the boundaries between modules should be classified in multiple modules and to what degree. With a novel greedy search algorithm, we find that some networks, for example, the neural network of C. Elegans, are best described by modules dominated by hard boundaries, but that others, for example, the sparse European road network, have a highly overlapping modular organization.
arXiv comment11 pages
References in corpus (17)
- Statistical mechanics of complex networks
- The structure and function of complex networks
- Finding and evaluating community structure in networks
- Community detection in graphs
- Fast algorithm for detecting community structure in networks
- Uncovering the overlapping community structure of complex networks in nature and society
- Maps of random walks on complex networks reveal community structure
- Link communities reveal multiscale complexity in networks
- The worldwide air transportation network: Anomalous centrality, community structure, and cities' global roles
- Quantifying social group evolution
- Finding statistically significant communities in networks
- Benchmarks for testing community detection algorithms on directed and weighted graphs with overlapping communities
- The map equation
- Line Graphs, Link Partitions and Overlapping Communities
- Multilevel compression of random walks on networks reveals hierarchical organization in large integrated systems
- Finding instabilities in the community structure of complex networks
- Map equation for link community
Cited by in corpus (11)
- Community detection in networks: A user guide
- Spectral entropies as information-theoretic tools for complex network comparison
- Model selection and hypothesis testing for large-scale network models with overlapping groups
- Encoding dynamics for multiscale community detection: Markov time sweeping for the Map equation
- Efficient community detection of network flows for varying Markov times and bipartite networks
- Multi-scale analysis of the European airspace using network community detection
- Hierarchical communities in the walnut structure of the Japanese production network
- Multilayer Network Science: from Cells to Societies
- Laplacian paths in complex networks: information core emerges from entropic transitions
- The Minimum Description Length Principle for Pattern Mining: A Survey
- A novel framework to analyze complex network dynamics