# Mapping Higher-Order Network Flows in Memory and Multilayer Networks with Infomap
## 4 Infomap
Rather than multiple community-detections algorithms for a range of network representations, the map equation's search algorithm Infomap can be applied to general higher-order network flows described by sparse memory networks. A sparse memory network uses abstract state nodes to describe higher-order dynamics and physical nodes to represent a system's objects. This distinction makes all the difference. The flexible sparse memory network can efficiently describe higher-order network flows of various types such as flows in memory and multilayer networks or their combinations. Simplifying and highlighting important patterns in these flows with the map equation and Infomap open for more effective analysis of complex systems. \begin{table}
\begin{tabular}{l l l l l l l l l l l} \hline
**Quaters** & \(m\) & \(I\) & \(N_{P}\) & \(N_{S}\) & \(N_{L}\) & \(H\) & \(D\) & \(P\) & \(A\) & **Time** \\ \hline \(1+2+3+4\) & 1 & 1 & 438 & 438 & 9681 & 5.1 & 2.0 & 1.0 & 1.0 & 0.016 s \\ \(1+2,3+4\) & 1 & 2 & 438 & 861 & 34,384 & 5.1 & 2.0 & 1.2 & 1.0 & 0.063 s \\ \(1,2,3,4\) & 1 & 4 & 438 & 1683 & 121,749 & 5.0 & 2.0 & 4.0 & 1.0 & 0.14 s \\ \(1+2+3+4\) & 2 & 1 & 438 & 9681 & 181,326 & 3.8 & 2.4 & 13 & 3.7 & 1.7 s \\ \(1+2,3+4\) & 2 & 2 & 438 & 17,203 & 614,472 & 3.8 & 3.0 & 15 & 3.8 & 10 s \\ \(1,2,3,4\) & 2 & 4 & 438 & 30,489 & 2,014,650 & 3.7 & 3.0 & 13 & 3.3 & 27 s \\ \(1+2+3+4\) & 3 & 1 & 432 & 180,900 & 465,456 & 1.1 & 4.0 & 25 & 5.7 & 8.2 min \\ \(1+2,3+4\) & 3 & 2 & 432 & 307,904 & 1,406,605 & 0.95 & 3.0 & 32 & 5.0 & 22 min \\ \(1,2,3,4\) & 3 & 4 & 432 & 507,054 & 4,112,089 & 0.91 & 3.0 & 19 & 3.8 & 52 min \\ \hline \end{tabular}
\end{table} 
Table 1: Mapping higher-order network flows from air traffic data. Sparse memory networks corresponding to Markov order \(m=\)1, 2, and 3 in one layer with data from quarters \(1+2+3+4\), in two layers with data from quarters \(1+2\) and \(3+4\), and in four layers with data from quarters \(1\), 2, 3, and 4, respectively. We report the number of physical node \(N_{P}\), state nodes \(N_{S}\), and links \(N_{L}\). The entropy rate \(H\) measures the number of bits required to predict where flows are going. \(D\) is the node weighted average depth of nodes in the multilevel clustering. The perplexity \(P\) of the module size distribution measures the effective number of modules, and the physical node weighted average of the perplexity of module assignments. \(A\) is the effective number of module assignments per physical node. Finally, the time corresponds to runs without parallelization on a 3.60 GHz desktop computer. We use relax rate \(r=0.25\) and all values are medians of ten runs with Infomap

**Acknowledgments:** We are grateful to [PERSON] and [PERSON] for helpful discussions. [PERSON] was supported by the Swedish Research Council grant 2016-00796. **Author Contributions:** [PERSON], [PERSON], and [PERSON] conceived and designed the experiments; [PERSON] performed the experiments. [PERSON], [PERSON], and [PERSON] analyzed the data and wrote the paper. **Conflicts of Interest:** The authors declare no conflict of interest. ## Appendix A Running Infomap

### Infomap Syntax

To run Infomap on a network, use the command

./Infomap [options] network_data dest

The option network_data should point to a valid network file and dest to a directory where Infomap should write the output files. If no option is given, Infomap will assume an undirected network and try to cluster it hierarchically. Optional arguments, including directed or undirected links, two-level or multilevel solutions, or various input formats, can be put anywhere. Run./Infomap --help for a list and explanation of supported arguments. ### Clustering a Multilayer Network

The multilayer network in Figure 4a can be described with the multilayer network format in fig3a.net below and clustered for relax rate \(r=0.4\) with the command

./Infomap --input -format multilayer --multilayer-relax-rate 0.4 fig3a.net.