# Mapping Higher-Order Network Flows in Memory and Multilayer Networks with Infomap
## 4 Infomap  
To find the best modular description of network flows according to the map equation, we have developed the stochastic and fast search algorithm called Infomap. Infomap can operate on standard, multilayer, memory, and sparse memory networks with unweighted or weighted and undirected or directed links, and identify two-level or multilevel and non-overlapping or overlapping clusterings. Infomap takes advantage of parallelization with OpenMP and there is also a distributed version implemented with GraphLab PowerGraph for standard networks [33]. In principle, the search algorithm can optimize other objectives than the map equation to find other types of community structures. Recent versions of Infomap operate on physical nodes and state nodes. Each state node has a unique state id and is assigned to a physical id, which can be the same for many state nodes. Infomap only uses physical nodes and state nodes for higher-order network flow representations, such as multilayer, memory, and sparse memory networks, and physical nodes alone when they are sufficient to represent first-order network flows in standard networks. To balance accuracy and speed, Infomap uses some repeatedly and recursively applied stochastic subroutine algorithms. For example, the multilevel clustering (Algorithm 1) and two-level clustering (Algorithm 2) algorithms first repeatedly aggregate nodes in modules (Algorithm 3) to optimize the map equation (Algorithm 4) and then repeatedly and recursively fine-tune (Algorithm 5) and coarse-tune (Algorithm 6) the results. Together with complete restarts, these tuning algorithms avoid local minima and improve accuracy. By default, Infomap tries to find a multilevel clustering of a network (Algorithm 1). ```
1 functionMultilevelPartition(NetworkG)
2M\(\leftarrow\)partition(\(G\))(Algorithm 2)
3M\(\leftarrow\)repeatedSuperModules(\(G\), \(M\))(Algorithm 7)
4M\(\leftarrow\)repeatedSubModules(\(G\), \(M\))(Algorithm 8)
5 returnM
```  
**Algorithm 1**Multilevel clustering  
```
1 functionMultilevelPartition(NetworkG)
2M\(\leftarrow\)partition(\(G\))(Algorithm 2)
3M\(\leftarrow\)rep


```
1 functionpartition(Network G)
2 Let \(L\) be the current code length
3 Let \(I_{max}^{T}\) be a maximum number of iterations
4 Let \(I_{max}^{T}\) be a maximum number of iterations
5 M = repeatedNodeAggregation(G) (Algorithm 3)
6\(L_{old}\gets L(\mathsf{M})\)
7\(I^{T}\gets 0\)
8 repeat
9\(I^{T}\gets I^{T}+1\)
10 if\(I\) is odd then
11 M = FineTune(G,M) (Algorithm 5)
12 else
13 M = CoarseTune(G,M) (Algorithm 6)
14\(\delta L\gets L(\mathsf{M})-L_{old}\)
15\(L_{old}\gets L(\mathsf{M})\)
16 until\(\delta L>-\epsilon\)or\(I^{T}=I_{max}^{T}\)
```
**Algorithm 2** Two-level clustering

### Two-Level Clustering

The complete two-level clustering algorithm improves the repeated node aggregation algorithm (Algorithm 3) by breaking up modules of sub-optimally aggregated nodes. That is, once the algorithm assigns nodes to the same module, they are forced to move jointly when Infomap rebuilds the network, and what was an optimal move early in the algorithm might have the opposite effect later in the algorithm. Similarly, two or more modules that merge together and form a single module when the algorithm rebuilds the network can never be separated again in the repeated node aggregation algorithm. Therefore, the accuracy can be improved by breaking up modules of the final state of the repeated node aggregation algorithm and trying to move individual nodes or smaller submodules into new or neighboring modules. The two-level clustering algorithm (Algorithm 2) performs this refinement by iterating fine-tuning (Algorithm 5) and coarse-tuning (Algorithm 6). ### Repeated Node Aggregation

The repeated node aggregation in Algorithm 3 follows closely the machinery of the Louvain method [34]. While the Louvain method seeks to maximize the modularity score, which fundamentally operates on link density rather than network flows, its repeated node aggregation machinery is effective also for optimizing other objectives than the modularity score.