Walktrap v0.2

WalkTrap is community detection program written in C++ by Pascal Pons. It is based on the fact that a random walker tends to be trapped in dense part of a network corresponding to communities. It is published under the GNU General Public License.
Download Walktrap: Source code Win32 executable



To compile the program type the command "make". If you do not have the "make" utility try : "g++ -O3 walktrap.cpp communities.cpp graph.cpp heap.cpp -o walktrap".

Command line usage:walktrap [input_file] [-o output_file] [-i index_file] [options]


If one of these parameters is omitted, the standard input is used.

INPUT FORMAT: the input file must be a list of undirected weighted edges. The vertices must be encoded as consecutive integers starting from 0. Each line contains two vertices and a weight (separated by spaces or tabulations) that define a weighted edge. The weight may be omitted, in this case a default weight equal to 1.0 is considered. The multi-edges will be considered as a single edge which weight is the sum of the corresponding weights. A comment line starts with "#"

The format is less flexible than the format used in version 0.1 but it allows considering weighted networks as well as unweighted networks. You can use the graph converter tool Gconvert. It handles different formats and can generate an index of the real name of the vertices that can be used in the output (see index_file section)


If this parameter is omitted, stdout is used.

OUTPUT FORMAT: according to the options the output may contain:


If you wish to keep the real name of the vertices in the output, you can specify an index file.

INDEX FORMAT: The index is a list of the real name of the vertices. Each line begins with a vertex number (as in the input file) followed by its real name that may be an arbitrary string. All the vertices must be defined once.


Usage examples:


More information about the algorithm is available in the paper: Computing communities in large networks using random walks (with Matthieu Latapy).


If you find a bug, please send a bug report to pons@liafa.jussieu.fr including the input file and the parameters that caused the bug.

You can also send me any comment or suggestion about the program.

Back to home page