Efficient community detection of network flows for varying Markov times and bipartite networks
arXiv:1511.01540 · doi:10.1103/PhysRevE.93.032309
Abstract
Community detection of network flows conventionally assumes one-step dynamics on the links. For sparse networks and interest in large-scale structures, longer timescales may be more appropriate. Oppositely, for large networks and interest in small-scale structures, shorter timescales may be better. However, current methods for analyzing networks at different timescales require expensive and often infeasible network reconstructions. To overcome this problem, we introduce a method that takes advantage of the inner-workings of the map equation and evades the reconstruction step. This makes it possible to efficiently analyze large networks at different Markov times with no extra overhead cost. The method also evades the costly unipartite projection for identifying flow modules in bipartite networks.
arXiv comment8 pages, 4 figures, and 1 table
References in corpus (17)
- Community structure in social and biological networks
- Maps of random walks on complex networks reveal community structure
- The structure of scientific collaboration networks
- Comparing community structure identification
- Community detection algorithms: a comparative analysis
- Modularity and community detection in bipartite networks
- Multilevel compression of random walks on networks reveals hierarchical organization in large integrated systems
- Module identification in bipartite and directed networks
- Random Walks, Markov Processes and the Multiscale Modular Organization of Complex Networks
- Laplacian Dynamics and Multiscale Modular Structure in Networks
- Hierarchical Block Structures and High-resolution Model Selection in Large Networks
- Parsimonious module inference in large networks
- Efficiently inferring community structure in bipartite networks
- Markov dynamics as a zooming lens for multiscale community detection: non clique-like communities and the field-of-view limit
- Encoding dynamics for multiscale community detection: Markov time sweeping for the Map equation
- Compression of Flow Can Reveal Overlapping-Module Organization in Networks
- Hierarchical mutual information for the comparison of hierarchical community structures in complex networks
Cited by in corpus (14)
- Analysis of Network Clustering Algorithms and Cluster Quality Metrics at Scale
- Infomap Bioregions: Interactive mapping of biogeographical regions from species distributions
- Data-driven Computational Social Science: A Survey
- Mapping flows on hypergraphs
- Latent geometry of bipartite networks
- Mapping Flows on Bipartite Networks
- Generalized Markov stability of network communities
- Community Detection with the Map Equation and Infomap: Theory and Applications
- Towards a generalization of information theory for hierarchical partitions
- Detecting User Community in Sparse Domain via Cross-Graph Pairwise Learning
- The Atlas for the Aspiring Network Scientist
- Modular decomposition of Markov chain: detecting hierarchical organization of pervasive communities
- Flow-based Community Detection in Hypergraphs
- Single-trajectory map equation