# Mapping Higher-Order Network Flows in Memory and Multilayer Networks with Infomap
## 1 Introduction  
To connect structure and dynamics in complex systems, researchers model, for example, people navigating the web [1], rumors wandering around among citizens [2], and passengers traveling through airports [3], as flows on networks with random walkers. Take an air traffic network as an example. In a standard network approach, nodes represent airports, links represent flights, and random walkers moving on the links between the nodes represent passengers. This dynamical process corresponds to a first-order Markov model of network flows: a passenger arriving in an airport will randomly continue to an airport proportional to the air traffic volume to that airport. That means, for example, that two passengers who arrive in Las Vegas, one from San Francisco and one from New York, will have the same probability to fly to New York next. In reality, however, passengers are more likely to return to where they come from [4]. Accordingly, describing network flows with a first-order Markov model suffers from memory loss and washes out significant dynamical patterns [5; 6; 7] (Figure 1a). Similarly, aggregating flow pathways from multiple sources, such as different airlines or seasons in the air traffic example, into a single network can distort both the topology of the network and the dynamics on the network [8; 9; 10; 11] (Figure 1c,d). As a consequence, the actual patterns in the data, such as pervasively overlapping modules in air traffic and social networks [12], cannot be identified with community-detection algorithms that operate on first-order network flows [4]. To take advantage of higher-order network flows, researchers have therefore developed different representations, models, and community-detectionalgorithms that broadly fall into two research topics: memory networks and multilayer networks. In memory networks, higher-order network flows can represent multistep pathways such as flight itineraries [4; 13; 14; 15], and in multilayer networks, they can represent temporal or multi-source data such as multiseason air traffic [8; 11; 16; 17] (Figure 1b). Whereas memory networks can capture where flows move to depending on where they come from (Figure 1e), multilayer networks can capture where flows move to depending on the current layer (Figure 1f). Because memory and multilayer networks originate from different research topics in network science, revealing their flow modules have been considered as disparate community detection problems. With the broad spectrum of higher-order network representations required to best describe diverse complex systems, the apparent need for specialized community-detection methods raises the question: How can we reveal communities in higher-order network flows with a general approach? Here we show that describing higher-order network flows with so-called sparse memory networks and identifying modules with long flow persistence times, such as groups of airports that contain frequently traveled routes, provides a general solution to reveal modular patterns in higher-order flows through complex systems. When modeling flows in conventional networks, a single node type both represents a complex system's objects and describes the flows with the nodes' links (Figure 1c,d). Sparse memory networks, however, discriminate physical nodes, which represent a complex system's objects, from state nodes, which describe a complex system's internal flows  
Figure 1: Going beyond standard network representations makes it possible to take advantage of richer interaction data. **(a)** Standard methods shoehorn interaction data about a complex system into an often unweighted and undirected network, which limits what regularities can be detected; **(b)** Modeling and mapping higher-order network flows can break this detectability limit; **(c)** System flows from two data sources between objects. The black arrow shows how flows can come to the center object; **(d)** The system represented as an undirected network with nodes for the objects.