# Mapping Higher-Order Network Flows in Memory and Multilayer Networks with Infomap
## 2 Modeling Network Flows
### Higher-Order Network Flows  
In higher-order network representations, more information than the previously visited physical node's outlinks are used to determine where flows go. Examples of higher-order network representations are memory, multilayer, and temporal networks. In memory networks, the flow direction depends on multiple previously visited nodes. Specifically, for a random walker that steps between physical nodes and generates a sequence of random variables \(X_{1},\ldots,X_{t}\), the transition probabilities for a higher-order flow model of order \(m\),  
\[P(X_{t}|X_{t-1},X_{t-2},\ldots)=P(X_{t}|X_{t-1},\ldots,X_{t-m}), \tag{4}\]  
depend on the \(m\) previously visited physical nodes. Assuming stationarity and \(m\) visited nodes from \(x_{-m}\)\(m\) steps ago to previously visited \(i\) in sequence \(\overrightarrow{x_{-m}x_{-m+1}\cdots x_{-2}i}\), the \(m\)th-order transition probabilities between physical nodes \(i\) and \(j\) correspond to first-order transition probabilities \(P(\overrightarrow{x_{-m}\cdots x_{-2}i}\rightarrow\overrightarrow{x_{-m+1} \cdots x_{-2}i})\) between state nodes \(\alpha_{i}=\overrightarrow{x_{-m}\cdots x_{-2}i}\) and \(\beta_{j}=\overrightarrow{x_{-m+1}\cdots x_{-2}i}\). We use subscript \(i\) in \(\alpha_{i}\) to highlight the state node's physical node. With link weights \(w_{\alpha_{i}\beta_{j}}\) between state nodes \(\alpha_{i}\) and \(\beta_{j}\), and total outlink weights \(w_{\alpha_{i}}=\sum_{\beta_{j}}w_{\alpha_{i}\beta_{j}}\), the transition probabilities for memory networks are  
\[P(\overrightarrow{x_{-m}\cdots x_{-1}i}\rightarrow\overrightarrow{x_{-m+1} \cdots x_{-1}i})=P_{\alpha_{i}\beta_{j}}=\frac{w_{\alpha_{i}\beta_{j}}}{w_{ \alpha_{i}}}. \tag{5}\]  
As in a first-order network representation, teleportation can ensure ergodic stationary visit rates \(\pi_{\alpha_{i}}\)[4]. In multilayer networks with the same physical nodes possibly present in multiple layers, the flow direction depends on both the previously visited physical node \(i\) and layer \(\alpha\in\{1,2,\ldots,l\}\). Similar to the memory representation, the multilayer transition probabilities between physical nodes \(i\) in layer \(\alpha\) and \(j\) in layer \(\beta\) correspond to first-order transition probabilities between states nodes \(\alpha_{i}\) and \(\beta_{j}\). In many cases, empirical interaction data only contain links within layers such that \(w_{\alpha_{i}\beta_{j}}\
eq 0\) only for \(\alpha=\beta\). Without data with links between layers, it is useful to couple layers by allowing a random walker to move between layers at a relax rate \(r\). With probability \(1-r\), a random walker follows a link of the physical node in the currently visited layer, and with probability \(r\) the random walker relaxes the layer constraint and follows any link of the physical node in any layer. In both cases, the random walker follows a link proportional to its weight. With total outlink weight \(w_{\alpha_{i}}=\sum_{\beta_{j}}w_{\alpha_{i}\beta_{j}}\) from physical node \(i\) in layer \(\alpha\), and total outlink weight \(w_{i}=\sum_{\alpha,\beta_{j}}w_{\alpha_{i}\beta_{j}}\) from physical node \(i\) across all layers, which both correspond to total intralayer outlink weights as long as there are only empirical links within layers, the transition probabilities for multilayer networks with modeled interlayer transitions are  
\[P\left(\alpha_{i}\rightarrow\beta_{j}\right)(r)=P_{\alpha_{i}\beta_{j}}(r)=(1 -r)\delta_{\alpha\beta}\frac{w_{\alpha_{i}\beta_{j}}}{w_{\alpha_{i}}}+r\frac{ \beta_{i}\beta_{j}}{w_{i}}, \tag{6}\]  
where \(\delta_{\alpha\beta}\) is the Kronecker delta, which is \(1\) if \(\alpha=\beta\) and \(0\) otherwise. In this way, the transition probabilities capture completely separated layers for relax rate \(r=0\) and completely aggregated layers for relax rate \(r=1\). The system under study and problem at hand should determine the relax rate. In practice, for relax rates in a wide range around \(0.25\), results are robust in many real multilayer networks [11].