# Mapping Higher-Order Network Flows in Memory and Multilayer Networks with Infomap
## 3 Mapping Network Flows
### The Map Equation for First-Order Network Flows  
When simplifying and highlighting network flows with possibly nested modules, the map equation measures how well a modular description compresses the flows [29]. Because compressing data is dual to finding regularities in the data [30], minimizing the modular description length of network flows is dual to finding modular regularities in the network flows. For describing movements within and between modules, the map equation uses code books that connect node visits, module exits, and module entries with code words. To estimate the shortest average description length of each code book, the map equation takes advantage of [PERSON]'s source coding theorem and measures the Shannon entropy of the code word use rates [30]. Moreover, the map equation uses a hierarchically nested code structure designed such that the description can be compressed if the network has modules in which a random walker tends to stay for a long time. Therefore, with a random walker as a proxy for real flows, minimizing the map equation over all possible network clusterings reveals important modular regularities in network flows. In detail, the map equation measures the minimum average description length for a multilevel map \(\mathsf{M}\) of \(N\) physical nodes clustered into \(M\) modules, for which each module \(m\) has a submap \(\mathsf{M}_{m}\) with \(M_{m}\) submodules, for which each submodule \(mn\) has a submap \(\mathsf{M}_{mn}\) with \(M_{mn}\) submodules, and so on (Figure 3). In each submodule \(mn\ldots o\) at the finest level, the code word use rate for exiting a module is  
\[q_{mn\ldots o\curvearrow}=\sum_{ \begin{subarray}{c}i\in\mathsf{M}_{mn\ldots o }\\ j\
otin M_{mn\ldots o}\end{subarray} }\pi_{i}P_{ij}\text{ (Figure \ref{fig:m_mand the total code word use rate for also visiting nodes in a module is  
\[p_{mn\ldots o}^{\curvearrow}=q_{mn\ldots o\curvearrow}+\sum_{i\in\mathsf{M}_{mn \ldots o}}\pi_{i}. \tag{12}\]  
such that the average code word length is  
\[H(\mathcal{P}_{mn\ldots o})=-\frac{q_{mn\ldots o\curvearrow}}{p_{mn\ldots o }^{\curvearrow}}\log\frac{q_{mn\ldots o\curvearrow}}{p_{mn\ldots o}^{ \curvearrow}}-\sum_{i\in\mathsf{M}_{mn\ldots o}}\frac{\pi_{i}}{p_{mn\ldots o }^{\curvearrow}}\log\frac{\pi_{i}}{p_{mn\ldots o}^{\curvearrow}}. \tag{13}\]  
Weighting the average code word length of the code book for module \(mn\ldots o\) at the finest level by its use rate gives the contribution to the description length,  
\[L(\mathsf{M}_{mn\ldots o})=p_{mn\ldots o}^{\curvearrow}H(\mathcal{P}_{mn \ldots o}). \tag{14}\]  
In each submodule \(m\) at intermediate levels, the code word use rate for exiting to a coarser level is  
\[q_{m\curvearrow}=\sum_{ \begin{subarray}{c}i\in\mathsf{M}_{m}\\ j\in\mathsf{M}_{m}\end{subarray} }\pi_{i}P_{ij}, \tag{15}\]  
and for entering the \(M_{m}\) submodules \(\mathsf{M}_{mn}\) at a finer level is  
\[q_{mn\curvearrow}=\sum_{ \begin{subarray}{c}i\
ot\in\mathsf{M}_{mn}\\ j\in\mathsf{M}_{mn}\end{subarray} }\pi_{i}P_{ij}\text{ (Figure \ref{fig:  
which gives the average code word length  
\[H(\mathcal{Q})=-\sum_{m=1}^{M}\frac{q_{m,\curvearrow}}{q_{\curvearrow}}\log \frac{q_{m,\curvearrow}}{q_{\curvearrow}}. \tag{22}\]  
Weighting the average code word length of the code book at the coarsest level by its use rate, and adding the description lengths of submodules at finer levels from Equation (19) in a recursive fashion, gives the multilevel map equation [31]  
\[L(\mathsf{M})=q_{\curvearrow}H(\mathcal{Q})+\sum_{m=1}^{M}L(\mathsf{M}_{m}). \tag{23}\]  
To find the multilevel map that best represents flows in a network, we seek the multilevel clustering of the network that minimizes the multilevel map equation over all possible multilevel clusterings of the network (see Algorithm 1 in Section 4). While there are several advantages with the multilevel description, including potentially better compression and effectively eliminated resolution limit [32], for simplicity researchers often choose two-level descriptions.