Infomap code

Here we provide the source code to the Infomap algorithm for detecting communities in large networks with the map equation framework. See also GossipMap, a distributed version for billion-edge directed graphs implemented with GraphLab PowerGraph by Seung-Hee Bae and Bill Howe at University of Washington. We also provide significance clustering code.

1. Installation
   • Prerequisites
     • Linux
     • Mac OS X
     • Windows
   • Download and compile
2. Running
   • Options
   • Examples
     • As stand-alone
     • As C++ library
     • With other languages
       • With Python and Jupyter Notebook
       • With R
   • Tuning the result
     • Tuning the dynamics
     • Tuning the coding scheme
3. Input
   • Link list
   • Pajek
   • 3-gram
   • Multiplex
   • Bipartite
   • State
4. Output
   • .tree
   • .ftree
   • .map
   • .clu
5. Features
6. Benchmark
7. Algorithm
8. Troubleshooting

Installation

Infomap is a command line software written in C++ that runs in Linux, Mac OS X, and Windows with gcc installed.

Prerequisites

Infomap requires a working gcc or clang compiler.

Linux

In Ubuntu, for example, the metapackage build-essential installs the compiler as well as related packages. Install it from the terminal with

sudo apt-get install build-essential

Mac OS X

Since Mac OS X 10.9, the standard compiler tools are based on clang, which can be installed with

xcode-select --install

However, the current version lacks OpenMP support for parallelization. While the Makefile automatically skips the -fopenmap compiler flag if the standard compiler is clang, to get support for OpenMP you can manually install a gcc-based compiler. A simple way is to install Homebrew and type, for example, brew install gcc43 in the terminal.

Windows

We recommend running Infomap in bash on ubuntu on Windows 10. Follow this installation guide or this installation guide to enable the Linux Bash Shell in Windows 10. For example, install git with sudo apt-get install git. Then install the metapackage build-essential for the compiler and related packages with

sudo apt-get install build-essential

Without Windows 10, you can install MinGW/MSYS for a minimalist development environment. Follow the instructions on MinGW - Getting Started or download the complete MinGW-MSYS Bundle.

Download and compile

Infomap v0.x code can be downloaded here infomap-0.x.zip .

To extract the zipped archive and compile the source code in a Unix-like environment, open a terminal and type

cd [path/to/Infomap]
unzip infomap-0.x.zip
cd infomap-0.x
make

Substitute [path/to/Infomap] to the folder where Infomap was downloaded, such as ~/Downloads. With git installed, instead clone the source code with git clone -b v0.x https://github.com/mapequation/infomap.git. If you installed a custom compiler with, for example, brew install gcc43, replace the last command with CXX=g++-4.3 make.

Compilation error due to missing parallelization library. If there is a compilation error that references -lomp or -lpthread, the compiler probably can't find the OpenMP library which is used for parallelization. To compile without the OpenMP library, type make noomp. You can also try to compile with another compiler by calling for example CXX=g++-4.3 make. Please give us feedback if you have any troubles!

Running

Usage: ./Infomap [options] network_data dest

The optional arguments can be put anywhere, see the Options section for the available options. The network_data should point to a valid network file (see Input section) and dest to a directory where the Infomap should write its output files.

Options

Run Infomap with the options -h or --help to list the options below:

-h[+] --help [+]

Prints this help message. Use -hh to show advanced options.

-V --version

Display program version information.

-i<s> --input-format <s>

Specify input format ('pajek', 'link-list', 'states', '3gram', 'multilayer' or 'bipartite') to override format possibly implied by file extension.

--overlapping

Let nodes be part of different and overlapping modules. Applies to ordinary networks by first representing the memoryless dynamics with memory nodes.

-z --zero-based-numbering

Assume node numbers start from zero in the input file instead of one.

-k --include-self-links

Include links with the same source and target node. (Ignored by default.)

--complete-dangling-memory-nodes

Add first order links to complete dangling memory nodes.

--map

Print the top two-level modular network in the .map format.

--clu

Print the top cluster indices for each node.

--tree

Print the hierarchy in .tree format. (default true if no other output with cluster data)

--bftree

Print the tree including horizontal flow links in a streamable binary format.

-2 --two-level

Optimize a two-level partition of the network.

-u --undirected

Assume undirected links. (default)

-d --directed

Assume directed links.

-t --undirdir

Two-mode dynamics: Assume undirected links for calculating flow, but directed when minimizing codelength.

-s<n> --seed <n>

A seed (integer) to the random number generator.

-N<n> --num-trials <n>

The number of outer-most loops to run before picking the best solution. (Default: 1)

-F[+] --fast-hierarchical-solution [+]

Find top modules fast. Use -FF to keep all fast levels. Use -FFF to skip recursive part.

--inner-parallelization

Parallelize the innermost loop for greater speed. Note that this may give some accuracy tradeoff.

-v[+] --verbose [+]

Verbose output on the console. Add additional 'v' flags to increase verbosity up to -vvv.

--silent

No output on the console.

Advanced options:

Run Infomap with the options -hh to list the options below:

-h[+] --help [+]

Prints this help message. Use -hh to show advanced options.

-V --version

Display program version information.

-n --negate-next

Set the next (no-argument) option to false.

-i<s> --input-format <s>

Specify input format ('pajek', 'link-list', 'states', '3gram', 'multilayer' or 'bipartite') to override format possibly implied by file extension.

--with-memory

Use second order Markov dynamics and let nodes be part of different modules. Simulate memory from first-order data if not '3gram' input.

--multilayer-add-missing-nodes

Adjust multilayer network so that the same set of physical nodes exist in all layers.

--multiplex-add-missing-nodes

[Deprecated, use multilayer-add-missing-nodes] Adjust multilayer network so that the same set of physical nodes exist in all layers.

--skip-adjust-bipartite-flow

Skip distributing all flow from the bipartite nodes (first column) to the ordinary nodes (second column).

--overlapping

Let nodes be part of different and overlapping modules. Applies to ordinary networks by first representing the memoryless dynamics with memory nodes.

--hard-partitions

Don't allow overlapping modules in memory networks by keeping the memory nodes constrained into their physical nodes.

--non-backtracking

Use non-backtracking dynamics and let nodes be part of different and overlapping modules. Applies to ordinary networks by first representing the non-backtracking dynamics with memory nodes.

--without-iostream

Parse the input network data without the iostream library. Can be a bit faster, but not as robust.

-z --zero-based-numbering

Assume node numbers start from zero in the input file instead of one.

-k --include-self-links

Include links with the same source and target node. (Ignored by default.)

--complete-dangling-memory-nodes

Add first order links to complete dangling memory nodes.

-O<n> --node-limit <n>

Limit the number of nodes to read from the network. Ignore links connected to ignored nodes. (Default: 0)

--weight-threshold <n>

Limit the number of links to read from the network. Ignore links with less weight than the threshold. (Default: 0)

--pre-cluster-multiplex

Pre-cluster multiplex networks layer by layer.

-c<p> --cluster-data <p>

Provide an initial two-level (.clu format) or multi-layer (.tree format) solution.

--no-infomap

Don't run Infomap. Useful if initial cluster data should be preserved or non-modular data printed.

--out-name <s>

Use this name for the output files, like [output_directory]/[out-name].tree

-0 --no-file-output

Don't print any output to file.

--map

Print the top two-level modular network in the .map format.

--clu

Print the top cluster indices for each node.

--tree

Print the hierarchy in .tree format. (default true if no other output with cluster data)

--ftree

Print the hierarchy in .tree format and append the hierarchically aggregated network links.

--btree

Print the tree in a streamable binary format.

--bftree

Print the tree including horizontal flow links in a streamable binary format.

--node-ranks

Print the calculated flow for each node to a file.

--flow-network

Print the network with calculated flow values.

--pajek

Print the parsed network in Pajek format.

--print-state-network

Print the internal state network.

--expanded

Print the expanded network of memory nodes if possible.

--print-all-trials

Print result to file for all trials (if more than one), with the trial number in each file.

-2 --two-level

Optimize a two-level partition of the network.

-u --undirected

Assume undirected links. (default)

-d --directed

Assume directed links.

-t --undirdir

Two-mode dynamics: Assume undirected links for calculating flow, but directed when minimizing codelength.

--outdirdir

Two-mode dynamics: Count only ingoing links when calculating the flow, but all when minimizing codelength.

-w --rawdir

Two-mode dynamics: Assume directed links and let the raw link weights be the flow.

-e --recorded-teleportation

If teleportation is used to calculate the flow, also record it when minimizing codelength.

-o --to-nodes

Teleport to nodes instead of to links, assuming uniform node weights if no such input data.

-p<f> --teleportation-probability <f>

The probability of teleporting to a random node or link. (Default: 0.15)

-y<f> --self-link-teleportation-probability <f>

Additional probability of teleporting to itself. Effectively increasing the code rate, generating more and smaller modules. (Default: -1)

--markov-time <f>

Scale link flow with this value to change the cost of moving between modules. Higher for less modules. (Default: 1)

--variable-markov-time

Scale link flow per node inversely proportional to the node exit entropy to easier split connected hubs and keep long chains together.

--preferred-number-of-modules <n>

Stop merge or split modules if preferred number of modules is reached. (Default: 0)

--multilayer-relax-rate <f>

The probability to relax the constraint to move only in the current layer and instead move to a random layer where the same physical node is present. If negative, the inter-links have to be provided. (Default: -1)

--multilayer-js-relax-rate <f>

The probability to relax the constraint to move only in the current layer and instead move to a random layer where the same physical node is present and proportional to the out-link similarity measured by the Jensen-Shannon divergence. If negative, the inter-links have to be provided. (Default: -1)

--multilayer-js-relax-limit <f>

The minimum out-link similarity measured by the Jensen-Shannon divergence to relax to other layer. From 0 to 1. No limit if negative. (Default: -1)

--multilayer-relax-limit <n>

The number of neighboring layers in each direction to relax to. If negative, relax to any layer. (Default: -1)

--multiplex-relax-rate <f>

[Deprecated, use multilayer-relax-rate] The probability to relax the constraint to move only in the current layer and instead move to a random layer where the same physical node is present. If negative, the inter-links have to be provided. (Default: -1)

--multiplex-js-relax-rate <f>

[Deprecated, use multilayer-js-relax-rate] The probability to relax the constraint to move only in the current layer and instead move to a random layer where the same physical node is present and proportional to the out-link similarity measured by the Jensen-Shannon divergence. If negative, the inter-links have to be provided. (Default: -1)

--multiplex-js-relax-limit <f>

[Deprecated, use multilayer-js-relax-limit] The minimum out-link similarity measured by the Jensen-Shannon divergence to relax to other layer. From 0 to 1. No limit if negative. (Default: -1)

--multiplex-relax-limit <n>

[Deprecated, use multilayer-relax-limit] The number of neighboring layers in each direction to relax to. If negative, relax to any layer. (Default: -1)

-s<n> --seed <n>

A seed (integer) to the random number generator.

-N<n> --num-trials <n>

The number of outer-most loops to run before picking the best solution. (Default: 1)

-m<f> --min-improvement <f>

Minimum codelength threshold for accepting a new solution. (Default: 1e-10)

-a --random-loop-limit

Randomize the core loop limit from 1 to 'core-loop-limit'

-M<n> --core-loop-limit <n>

Limit the number of loops that tries to move each node into the best possible module (Default: 10)

-L<n> --core-level-limit <n>

Limit the number of times the core loops are reapplied on existing modular network to search bigger structures. (Default: 0)

-T<n> --tune-iteration-limit <n>

Limit the number of main iterations in the two-level partition algorithm. 0 means no limit. (Default: 0)

-U<f> --tune-iteration-threshold <f>

Set a codelength improvement threshold of each new tune iteration to 'f' times the initial two-level codelength. (Default: 1e-05)

--fast-first-iteration

Move nodes to strongest connected module in the first iteration instead of minimizing the map equation.

-C --fast-coarse-tune

Try to find the quickest partition of each module when creating sub-modules for the coarse-tune part.

-A --alternate-coarse-tune-level

Try to find different levels of sub-modules to move in the coarse-tune part.

-S<n> --coarse-tune-level <n>

Set the recursion limit when searching for sub-modules. A level of 1 will find sub-sub-modules. (Default: 1)

-F[+] --fast-hierarchical-solution [+]

Find top modules fast. Use -FF to keep all fast levels. Use -FFF to skip recursive part.

-l[+] --low-memory [+]

Prioritize memory efficient algorithms before fast. Use -ll to optimize even more, but this may give approximate results.

--inner-parallelization

Parallelize the innermost loop for greater speed. Note that this may give some accuracy tradeoff.

--reset-options-before-recursion

Reset options tuning the speed and accuracy before the recursive part.

--show-bipartite-nodes

[Deprecated, see --hide-bipartite-nodes] Include the bipartite nodes in the output (now default).

--hide-bipartite-nodes

Hide the bipartite nodes in the output.

-v[+] --verbose [+]

Verbose output on the console. Add additional 'v' flags to increase verbosity up to -vvv.

--silent

No output on the console.

Argument types are defined as:

• <n> - a positive integer
• <f> - a floating point number
• <p> - a path to a file or directory
• <s> - a string matching one of the listed keys

[+] means that the option can be repeated

Examples

As stand-alone

mkdir output
./Infomap ninetriangles.net output/ -N 10 --tree --bftree

Here, we first create a new directory where we want the put the results, and feed that to Infomap together with an input network and an option. Now Infomap will try to parse the file ninetriangles.net as an undirected network, partition it hierarchically and write the best result out of 10 attempts to the output directory, both in the human readable .tree format and the binary .bftree format, which can be loaded into the Network Navigator.

./Infomap ninetriangles.net output/ -N 10 --directed --two-level --clu --map

Here, Infomap will treat the network as directed and try to find the optimal two-level partition with respect to the flow. This will also create an output .clu file with the cluster indices, and a .map file with the modular network that can be visualized using the Map Generator.

Multiplex

Multiplex networks describes a set of networks with corresponding nodes but different link structures, and possibly also an inter-network link structure (see multiplex format). If no inter-link data is provided, or if the relax rate is explicitly set, the inter-link structure will be generated by relaxing the layer constraints of the intra-network links.

There are two ways to provide a multiplex network to Infomap:

./Infomap multiplex-network.net output/ -i multiplex

or

./Infomap network1.net network2.net [... networkN.net] output/

where network1.net to networkN.net are ordinary networks in the Pajek or link list format.

As C++ library

To see a minimal example on how Infomap can be run as a library, check the files example.cpp and Makefile in the examples/cpp/minimal directory, and run by typing:

cd examples/cpp/minimal
make
./example

The included directory example/cpp/Infomap-igraph-interface-library/ contains an example on how to write a small interface library to simplify integration with other network libraries, here igraph. Example code to use that is included in the examples/cpp/igraph directory.

With other languages

With Python and Jupyter Notebook

To run Infomap from the included python example code, type:

cd examples/python
make
python example-networkx.py

The make command first calls make python in the Infomap base directory, which uses swig and setuptools to compile Infomap to a python module. Then that module is copied to the current example directory to be easily imported in the included python code.

The example-networkx.py code depends on the NetworkX module, which can be installed by typing pip install networkx using the pip tool.

To run Infomap from the included Jupyter notebook, first compile Infomap to a python module as described above, then install Jupyter by typing pip install jupyter using the pip tool, and finally start the notebook server and open the example notebook in examples/python by typing:

jupyter notebook infomap-examples.ipynb

With R

Assuming R is installed, you can run Infomap from from the included R example code, type:

cd examples/R
make
R
source("example-minimal.R")

The make command first calls make R in the Infomap base directory, which uses swig to generate wrapper code for R and R CMD SHLIB to compile Infomap as a shared library. The library can then be loaded in an R environment by calling source("load-infomap.R"), which is called by the example files.

The example-igraph.R code gives a more complete example, depending on the igraph R package to generate a network and to plot the communities found by Infomap.

Tuning the result

Infomap decomposes a network into modules by optimally compressing a description of information flows on the network. To model this flow of information, we release a random walker on the network and encodes its steps and module exits. To tune the modular solution, you can therefore tune the dynamics of the random walker, or the encoding scheme.

Tuning the dynamics

Some relevant options here are --directed, --undirdir, --rawdir, --teleportation-probability, --to-nodes and --include-self-links.

Tuning the coding scheme

Relevant options are --recorded-teleportation and --markov-time. With --recorded-teleportation, the solution captures the blurring effect of the random teleportation, typically needed on directed networks to reach a stationary solution. To minimize this artificial effect, we therefore no longer use the option by default.

The --markov-time defines how many steps the random walker takes before its position is encoded (default 1). Shorter Markov times than 1 mean that the average transition rate of a random walker is lower than the encoding rate of its position, such that the same node will be encoded multiple times in a row. As a result, the map equation will favor more and smaller modules. Oppositely, longer Markov times mean that the average transition rate is higher than the encoding rate, such that not every node on the trajectory will be encoded, and the map equation will favor fewer and larger modules. Read more in Efficient community detection of network flows for varying Markov times and bipartite networks.

Input

Currently, Infomap understands three different file formats for the input network data, a minimal link list format, the standard Pajek format, and a 3-gram format for second-order dynamics. Specify the input format to Infomap with the -i or --input-format flag together with pajek or link-list as its argument. If no input format is specified, Infomap will try to parse the file by this assumption:

• .net - Pajek format
• .txt - Link list format

Link list format

A link list is a minimal format to describe a network by only specifying a set of links:

# A network in link list format
1 2 1
1 3 1
2 3 2
3 5 0.5
...

Each line corresponds to the triad source target weight which describes a weighted link between the nodes with specified numbers. The weight can be any non-negative value. If omitted, the link weight will default to 1. The first node are assumed to start from 1^* and the total number of nodes will be determined by the maximum node number.

Pajek format

The Pajek format specifies both the nodes and the links in two different sections of the file:

# A network in Pajek format
*Vertices 27
1 "1"
2 "2"
3 "3"
4 "4"
...
*Edges 33
1 2 1
1 3 1
1 4 1
2 3 1
...

The node section must start with *Vertices N and the link section with *Edges N or *Arcs N (case insensitive), where N is the number of nodes or links. The characters within each quotation mark defines the corresponding node name. Weights can be given to nodes by adding a third column with positive numbers, and the list of links are treated the same as for a link list.

3-gram format

The 3-gram format contains information about second-order dynamics and is similar to the pajek format but the links are defined by at least three columns, from through to [weight]:

# A network in 3-gram format
*Vertices 27
1 "1"
2 "2"
3 "3"
4 "4"
...
*3grams 33
1 1 2 1
2 1 2 1
3 1 2 1
1 2 1 1
...

The node section format follows exactly the Pajek format, but the link section must begin with *3grams N or *Arcs N (case insensitive), where N is the number of links. Because pathways are inherently directed, the links are assumed to be directed by default.

Incomplete links

You can mix the trigrams with bigrams, i.e. ordinary links, by setting the first column to -1. Infomap will then try to match those links with the existing trigrams to spread out the weight proportinally to the weigh of the matched links.

There are three ways to match an incomplete link -1 2 3, in priority order:

Exact match:

x 2 3 -> x 2 3

Partial match:

x 2 y -> x 2 3

Shifted match:

x y 2 -> y 2 3

If no matches are found, a self-link 2 2 3 is created if self-links are allowed.

Multiplex format

In a multiplex network, each physical node can exist in a number of layers, with different link structure for each layer. A general multiplex format follows the Pajek layout, but with the links defined between nodes for each layer:

# A network in a general multiplex format
*Vertices 4
1 "Node 1"
2 "Node 2"
3 "Node 3"
4 "Node 4"
*Multiplex
# layer node layer node [weight]
1 1 1 2 2
1 1 2 2 1
1 2 1 1 1
1 3 2 2 1
2 2 1 3 1
2 3 2 2 1
2 4 2 1 2
2 4 1 2 1

The weight column is optional. Links without the last column will get weight 1.0 by default.

If no heading (beginning with *) is given, the multiplex format assumes *Multiplex link format:

# A network in a general multiplex format
# layer node layer node [weight]
1 1 1 2 2
1 1 2 2 1
1 2 1 1 1
1 3 2 2 1
2 2 1 3 1
2 3 2 2 1
2 4 2 1 2
2 4 1 2 1

The multiplex format above gives full control of the dynamics, and no other movements are encoded. However, it is often useful to consider a dynamics in which a random walker moves within a layer and with a given relax rate jumps to another layer without recording this movement, such that the constraints from moving in different layers can be gradually relaxed. The format below explicitely divides the links into two groups, links within layers (intra-layer links) and links between layers (inter-layer links). For the first group, the second layer column can be omitted. For the second group, the second node can be omitted, as a shorthand for an unrecorded jump between layers. That is, each inter-layer link layer1 node1 layer2 is expanded to weighted multiplex links layer1 node1 layer2 node2, one for each node2 that node1 is connected to in layer2 with weight proportional to the weight of the link between node1 and node2 in layer2. In this way, the random walker seamlessly switches to a different layer at a rate proportional to the inter-layer link weight to that layer, and the encoded dynamics correspond to relaxed layer constraints (see the interactive storyboard for illustration). To define links like this, use the *Intra and *Inter headings:

# A network in multiplex format
*Intra
# layer node node weight
1 1 2 1
1 2 1 1
1 2 3 1
1 3 2 1
1 3 1 1
1 1 3 1
1 2 4 1
1 4 2 1
2 4 5 1
2 5 4 1
2 5 6 1
2 6 5 1
2 6 4 1
2 4 6 1
2 3 6 1
2 6 3 1
*Inter
# layer node layer weight
1 3 2
2 3 1
1 4 2
2 4 1

If no inter links are provided, the inter links will be generated from the intra link structure by relaxing the layer constraints on those links.

Bipartite format

The bipartite network format uses prefixes f and n for features and nodes, respectively. The bipartite network can be provided both with node names:

# A bipartite network with node names
*Vertices 5
1 "Node 1"
2 "Node 2"
3 "Node 3"
4 "Node 4"
5 "Node 5"
*Edges 6
# feature node [weight]
f1 n1 2
f1 n2 2
f1 n3 1
f2 n3 1
f2 n4 2
f2 n5 2

and in the link list format:

# A bipartite network in link list format
# feature node [weight]
f1 n1 2
f1 n2 2
f1 n3 1
f2 n3 1
f2 n4 2
f2 n5 2

Node names can be provided under f and n for features and nodes, respectively. In the link list format, for example, it takes the form:

State format

The state format describes the exact network used internally by Infomap. It can model both ordinary networks and memory networks of variable order as illustrated in this notebook.

# A network in state format
*Vertices 4
1 "PRE"
2 "SCIENCE"
3 "PRL"
4 "BIO"
*States
1 2 "1 2"
2 3 "2 3"
3 2 "4 2"
4 4 "2 4"
*Links
1 2
3 4

The *Vertices section is optional and follows the Pajek format. It is used to name the physical nodes. The *States section describes all internal nodes with the format uniqueId physicalId [name], where name is optional. The unique index is referenced in the *Links section, and the physical index of the node is optionally referenced in the *Vertices section. The *Links section describes all links as from to [weight], where from and to references the first index in the *States section.

The example state network above is equivalent to the 3-gram network below:

# A 3-gram network equivalent to the state network above
*Vertices 4
1 "PRE"
2 "SCIENCE"
3 "PRL"
4 "BIO"
*3grams
1 2 3
4 2 4

Output

Tree format

The resulting hierarchy will be written to a file with the extension .tree (plain text file) and corresponds to the best hierarchical partition (shortest description length) of the attempts. The output format has the pattern:

# Codelength = 3.48419 bits.
1:1:1 0.0384615 "7" 6
1:1:2 0.0384615 "8" 7
1:1:3 0.0384615 "9" 8
1:2:1 0.0384615 "4" 3
1:2:2 0.0384615 "5" 4
...

Each row (except the first one, which summarizes the result) begins with the multilevel module assignments of a node. The module assignments are colon separated from coarse to fine level, and all modules within each level are sorted by the total flow (PageRank) of the nodes they contain. Further, the integer after the last colon is the rank within the finest-level module, the decimal number is the amount of flow in that node, i.e. the steady state population of random walkers, the content within quotation marks is the node name, and finally, the last integer is the index of the node in the original network file.

FTree format

The Tree format with an appended section of links with the flow between nodes within the same parent. The file is saved with the extension .ftree (plain text file), and begins with the node hierarchy formatted as the Tree format, followed by the links formatted as:

*Links undirected
#*Links path exitFlow numEdges numChildren
*Links root 0.0 6 5
1 2 0.0128205
1 3 0.0128205
2 4 0.0128205
3 4 0.0128205
3 5 0.0128205
4 5 0.0128205
*Links 1 0.025641 3 3
1 2 0.0128205
1 3 0.0128205
2 3 0.0128205
*Links 1:1 0.0384615 3 3
1 2 0.0128205
1 3 0.0128205
2 3 0.0128205
*Links 1:2 0.0384615 3 3
1 2 0.0128205
1 3 0.0128205
2 3 0.0128205
...

First is a line stating undirected or directed links. Then each module is identified by the path field, followed by all links between child nodes of that module. The path is a colon separated path in the tree from the root to finest-level modules. The links are sorted by flow within each module. Links exiting the module are not included, but the flow on those links is aggregated to exitFlow. The number of edges and child nodes within each module is also included in the module header line, as defined in the commented line above. (Lines starting with # are treated as comments and are ignored when parsed.)

Map format

A .map file (plain text file) describes the best two-level partition (shortest description length) of the attempts. The format has the pattern:

# modules: 4
# modulelinks: 4
# nodes: 16
# links: 20
# codelength: 3.32773
*Directed
*Modules 4
1 "Node 13,..." 0.25 0.0395432
2 "Node 5,..." 0.25 0.0395432
3 "Node 9,..." 0.25 0.0395432
4 "Node 1,..." 0.25 0.0395432
*Nodes 16
1:1 "Node 13" 0.0820133
1:2 "Node 14" 0.0790863
1:3 "Node 16" 0.0459137
1:4 "Node 15" 0.0429867
2:1 "Node 5" 0.0820133
2:2 "Node 6" 0.0790863
2:3 "Node 8" 0.0459137
2:4 "Node 7" 0.0429867
3:1 "Node 9" 0.0820133
3:2 "Node 10" 0.0790863
3:3 "Node 12" 0.0459137
3:4 "Node 11" 0.0429867
4:1 "Node 1" 0.0820133
4:2 "Node 2" 0.0790863
4:3 "Node 4" 0.0459137
4:4 "Node 3" 0.0429867
*Links 4
1 4 0.0395432
2 3 0.0395432
3 1 0.0395432
4 2 0.0395432
...

This file contains the necessary information to generate a visual map in the Map Generator. The names under *Modules are derived from the node with the highest flow volume within the module and 0.25 0.0395432 represent, respectively, the aggregated flow volume of all nodes within the module and the per step exit flow from the module. The nodes are listed with their module assignments together with their flow volumes. Finally, all links between the modules are listed in order from high flow to low flow.

Clu format

A .clu file (plain text file) describes the best two-level partition (shortest description length) of the attempts. The format has the pattern:

# node cluster flow:
4 1 0.4
3 1 0.1
1 2 0.2
2 2 0.1
5 2 0.05
8 2 0.05
7 3 0.05
6 3 0.05

If the .clu file is used as an input clustering to Infomap or the apps, the flow column will not be used and may be omitted. Even the node column may be omitted, in which case it assumes an implicit column of naturally ordered integers starting from one.

Binary tree formats

The resulting hierarchy can be written to a compact binary format using the --btree or --bftree flag. The former includes only the tree, while the latter also includes the horizontal flow links between nodes on each level of the tree. The data is written in a breath-first pattern to be streamable, which the Network Navigator utilizes to be able to show the top modular structure of the network before the deeper parts of the tree are loaded.

Troubleshooting

Don't hesitate to contact us if you have questions or comments about the code.