Maps of sparse Markov chains efficiently reveal community structure in network flows with memory

Abstract

To better understand the flows of ideas or information through social and biological systems, researchers develop maps that reveal important patterns in network flows. In practice, network flow models have implied memoryless first-order Markov chains, but recently researchers have introduced higher-order Markov chain models with memory to capture patterns in multi-step pathways. Higher-order models are particularly important for effectively revealing actual, overlapping community structure, but higher-order Markov chain models suffer from the curse of dimensionality: their vast parameter spaces require exponentially increasing data to avoid overfitting and therefore make mapping inefficient already for moderate-sized systems. To overcome this problem, we introduce an efficient cross-validated mapping approach based on network flows modeled by sparse Markov chains. To illustrate our approach, we present a map of citation flows in science with research fields that overlap in multidisciplinary journals. Compared with currently used categories in science of science studies, the research fields form better units of analysis because the map more effectively captures how ideas flow through science.

arXiv comment7 pages, 5 figures, 1 table

References in corpus (6)

• Maps of random walks on complex networks reveal community structure
• Community detection algorithms: a comparative analysis
• Phase transitions in contagion processes mediated by recurrent mobility patterns
• Representing higher-order dependencies in networks
• Betweenness Preference: Quantifying Correlations in the Topological Dynamics of Temporal Networks
• Detecting Memory and Structure in Human Navigation Patterns Using Markov Chain Models of Varying Order

Cited by in corpus (5)

• Mapping higher-order network flows in memory and multilayer networks with Infomap
• Big data analyses reveal patterns and drivers of the movements of southern elephant seals
• Understanding Complex Systems: From Networks to Optimal Higher-Order Models
• Learning higher-order sequential structure with cloned HMMs
• Community Detection with the Map Equation and Infomap: Theory and Applications