Efficient community detection of network flows for varying Markov times and bipartite networks

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.

8 pages, 4 figures, and 1 table

References in corpus (7)

• Maps of random walks on complex networks reveal community structure
• Comparing community structure identification
• Modularity and community detection in bipartite networks
• Multilevel compression of random walks on networks reveals hierarchical organization in large integrated systems
• Random Walks, Markov Processes and the Multiscale Modular Organization of Complex Networks
• Parsimonious module inference in large 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