Multi-Step Comunity v0.1

Multi-Step Comunity is community detection program written in C++ by Thomas Aynaud. It aims at finding communities that have a high average modularity. It is published under the GNU General Public License.



COMPILING

To compile the program type the command "make". It builds two executables, com_dyn and hierarch. com_dyn finds multi-step communities and hierarch build time decomposition.


USAGE

Command line usage:

	To compute the best average partition on the entire graph
	./com_dyn graph.txt > graph.com_dyn

	To compute the hierarchical time decomposition
	./hierarch graph.txt > graph.hierarch

	For a connex version (timesteps grouped together are always adjacent):
	./hierarch graph.txt --connex > graph.hierarch
	
	


INPUT FORMAT:

The input file is the list of snapshots. It starts with one line containing the number of snapshot, then one line for each node then it starts enumerating snapshot. Snapshots are separated by a marker and then contain one line for each edge with src and destination. The marker is -1 or -2 weight. For example:

3                    -> number of snapshots
0                    -> list of nodes
1
2
3
4
-2 1               -> marker of the first snapshot, its weight is 1
0 1                -> there is an edge between 0 and 1
0 2
0 3
1 2
1 3
-2 4               -> marker of the second snapshot, its weight is 4
0 1
0 2
1 2
1 3
1 4
2 3
3 4
-2 1               -> marker of the third snapshot, its weight is 1
0 4
0 1               -> end of the file.


OUTPUT FORMAT:
com_dyn:
the standard output contains one line per node containing node name and its community.
the standard error contains some information like modularity or progress

0 2
1 1
2 1
3 3
4 1
5 0
6 0
7 0
8 1
9 2
10 3
11 0
12 1
13 1
14 1
15 2

hierarch:
Each line of the standard output contains two time windows separated by a space. For each time window, if it has at least two timesteps, they are separated by a comma.
The standard error contains progress information.
For example:

2, 3,
4, 2,3,
6, 7,
5, 2,3,4,
1, 2,3,4,5,
6,7, 1,2,3,4,5,
8, 9,
17, 18,
16, 17,18,
13, 14,
12, 13,14,
11, 12,13,14,
10, 11,12,13,14,
15, 10,11,12,13,14,
8,9, 10,11,12,13,14,15,
19, 16,17,18,
1,2,3,4,5,6,7, 8,9,10,11,12,13,14,15,
20, 16,17,18,19,
1,2,3,4,5,6,7,8,9,10,11,12,13,14,15, 16,17,18,19,20,

OPTIONS:

    com_dyn :
        none
    hierarch:
        --connex force to group consecutive time windows.


MORE INFORMATION

More information about the algorithm is available in the paper: Multi-Step Community Detection and Hierarchical Time Segmentation in Evolving Networks (with Jean-Loup Guillaume).


COMMENTS & BUG REPORT

If you find a bug, please send a bug report to thomas.aynaud@lip6.fr including the input file and the parameters that caused the bug.

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