parallelized version of walktrap
Branch: master
Clone or download
Fetching latest commit…
Cannot retrieve the latest commit at this time.
Permalink
Type Name Latest commit message Commit time
Failed to load latest commit information.
walktrap02.xcodeproj
communities.cpp
communities.h
communities.o
example.net
geo_10_3.net
graph.cpp
graph.h
graph.o
heap.cpp
heap.h
heap.o
license.txt
makefile
readme.txt
walktrap
walktrap.cpp
walktrap.o

readme.txt

       #=======================================#
       #  WalkTrap v0.2                        #
       #  Copyright (C) 2004-2005 Pascal Pons  #
       #=======================================#


1) DESCRIPTION
   ===========

WalkTrap is a C++ program that finds community structure of a network.
It is based on the fact that a random walker tends to be trapped in dense
part of a network corresponding to communities.


2) AUTHOR & COPYRIGHT
   ==================

This program is copyright (C) 2004-2005 by Pascal Pons:
    Email:	pons@liafa.jussieu.fr
    Web page:	http://www.liafa.jussieu.fr/~pons/

Collaborator: Matthieu Latapy
    Email:	latapy@liafa.jussieu.fr
    Web page:	http://www.liafa.jussieu.fr/~latapy/

This program is free software; you can redistribute it and/or modify
it under the terms of the GNU General Public License as published by
the Free Software Foundation; either version 2 of the License, or
(at your option) any later version.

This program is distributed in the hope that it will be useful,
but WITHOUT ANY WARRANTY; without even the implied warranty of
MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
GNU General Public License for more details.

You should have received a copy of the GNU General Public License
along with this program (gpl.txt); if not, write to the Free Software
Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA  02111-1307  USA


3) USAGE
   =====

compiling:
    To compile the program type the command "make".
    If you do have not the "make" utility try : 
    "g++ -O3 walktrap.cpp graph.cpp communities.cpp -o communities"
    This program requires the C++ Standard Template Library and has been
    tested with gcc 3.2.3

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

input_file:
    The file in which the network is stored.
    If this parameter is omitted, stdin is used.
    Be careful that the input format has changed since version 0.1

    INPUT FORMAT: (see example.net)
    The format is 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" available on my web page
    http://www.liafa.jussieu.fr/~pons/. 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)

output_file:
    The file in which the community structure will be stored.
    If this parameter is omitted, stdout is used.

    OUTPUT FORMAT:
    according to the options the output may contain :
    - The list of the first communities containing a single vertex.
    - The successive merging of communities with
	- the modularity Q of the partition obtained at this step.
	- the value of delta_sigma that has been chosen for this merging.
	- the vertices that belong to the new community.
	- the description of the whole partition.
    - The partition with the best modularity (-b option)
    - More partitions asked by user with the options -p

index_file:
    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.

options:
    -s	: (silent) 

    -tx	: set the length of random walks to x. Default value is t = 4.

    -dx : set to x the detail level of the output (1 <= d <= 5).
	  d  = 1 nothing is written.
	  d >= 2 the successive mergings of the communities are written.
	  d >= 3 the modularity Q and the value of delta_sigma are written.
	  d >= 4 the new community is written at each step.
	  d >= 5 the whole partition is written at each step.
	  If ommited default value is d = 2.


    -b	: at the end of the process, print the partition that corresponds
	  to the best value of the modularity.

    -px	: at the end of the process, print the whole partition that 
	  corresponds to x communities. This option can be used several
	  times.

    -mx : limit the memory usage of the program to x MB. This option is
	  very useful for very large networks. But the algorithm runs 
	  slower with less memory.

    -h	: print the command line usage.

examples:
    "walktrap network.dat -o communities.txt -t5 -b"
    read network from file "network.dat" and writes the community structure
    found in file "communities.txt". The computation is done with random
    walks of length 5 and the best modularity partition is printed.

    "walktrap example.net -o test -d1 -p3"
    only the partition into 3 communities computed by the program is printed.

    "walktrap example.net -o test2 -m400" 
    the program will never use more that 400MB of memory.

    "walktrap example.net -d1 -s -b"
    only the best modularity partition is printed to the screen.

4) MORE INFORMATION
   ================

more information is available in the paper:
Matthieu Latapy and Pascal Pons, 'Computing communities in large networks
using random walks', submitted preprint to which this program actually is
associated.

It may be dowloaded, as well as the source code and material for WalkTrap
on: http://www.liafa.jussieu.fr/~pons/

5) COMMENTS & BUG REPORT
   =====================

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.

6) HISTORY
   =======

v0.2 (June 2005)
new features :
    - support of weighted networks (input format has been modified)
    - an efficient memory manager has been implemented
    - many optimizations on the probability vectors storage and computation
    - some heuristic optimizations in the merging process
    - a heap structure has been implemented to store the distances 
      between communities.

v0.1 (November 2004)
first public version of Walktrap.

					June 7th, 2005. Pascal Pons.