# Mapping Higher-Order Network Flows in Memory and Multilayer Networks with Infomap
## 2 Modeling Network Flows
### Representing Memory and Multilayer Networks with Sparse Memory Network  
To illustrate that sparse memory networks can represent both memory and multilayer networks, we use a schematic network with five physical nodes (Figure 2a). The network represents five individuals, with the center node's two friends to the left and two colleagues to the right. We imagine that the multistep pathway data come from two sources, say a Facebook conversation thread among the friends illustrated with the top sequence above the network and the solid pathway on the network, and an email conversation thread among the colleagues illustrated with the bottom sequence and the dashed pathway. For simplicity, the pathway among the friends stays among the friends and steps between friends with equal probability. The pathway among the colleagues behaves in corresponding way. We first represent these pathway data with a memory and a multilayer network, and then show that both can be represented with a sparse memory network. We can represent multistep pathways with links between state nodes in physical nodes. For a memory network representation of a second-order Markov model, each state node captures which physical node the flows come from. For example, the highlighted pathway step in Figure 2a corresponds to a link between state node \(\varepsilon_{i}\) in physical node \(i\)--capturing flows coming to physical node \(i\) from physical node \(j\)--and state node \(\gamma^{\prime}_{k}\) in physical node \(k\)--capturing flows coming to physical node \(k\) from physical node \(i\) (Figure 2b). In this way, random walker movements between state nodes can capture higher-order network flows between observable physical nodes. We can represent multistep pathways with links between state nodes in layers. First, we can map all state nodes that represent flows coming from a specific physical node onto the same layer. For example, we map red state nodes \(\varepsilon_{i}\) and \(\varepsilon^{\prime}_{k}\) for flows coming from red physical node \(j\) to physical nodes \(i\) and \(k\), respectively, in Figure 2b onto the red layer \(\varepsilon\) at the bottom in Figure 2c. This mapping gives one-to-one correspondence between the memory network and the multilayer network. Therefore we call it a multilayer memory network. An alternative and more standard multilayer representation exploits that the pathway data come from two sources and uses one layer for each data source (Figure 2d). Network flows are first-order when constrained to move within individual layers and higher-order when free to move within and between layers. The highlighted pathway step in Figure 2a now corresponds to a step in layer \(\eta\) between state node \(\eta_{i}\) and state node \(\eta_{k}\)--capturing flows remaining among friends. Again, random walker movements between state nodes can capture higher-order network flows between observable physical nodes. Figure 2: Modeling higher-order network flows with sparse memory networks. (**a**) Multistep pathway data from two sources illustrated on a network with five physical nodes; (**b**) The pathway data modeled with a second-order Markov model on a memory network, where state nodes capture where flows come from; (**c**) The memory network represented as a multilayer network where layers, one for each physical node, capture where flows come from; (**d**) The pathway data modeled on a two-layer network, one layer for each data source; (**e**) Both memory and multilayer networks mapped on a sparse memory network with no redundant state nodes. The black link highlights the same step in all representations. See also the dynamic storyboard available on www.mapequation.org/apps/sparse-memory-network. In our multistep pathway example from two sources, a full second-order model in the memory network is not required and partly redundant to describe the network flows. We can model the same pathways with a more compact description.