|
0
|
1 -----------------------------------------------------------------------------
|
|
|
2
|
|
|
3 Community detection
|
|
|
4 Version 0.2 - not compatible with the previous version, see below.
|
|
|
5
|
|
|
6 Based on the article "Fast unfolding of community hierarchies in large networks"
|
|
|
7 Copyright (C) 2008 V. Blondel, J.-L. Guillaume, R. Lambiotte, E. Lefebvre
|
|
|
8
|
|
|
9
|
|
|
10 This file is part of Louvain algorithm.
|
|
|
11
|
|
|
12 Louvain algorithm is free software: you can redistribute it and/or modify
|
|
|
13 it under the terms of the GNU General Public License as published by
|
|
|
14 the Free Software Foundation, either version 3 of the License, or
|
|
|
15 (at your option) any later version.
|
|
|
16
|
|
|
17 Louvain algorithm is distributed in the hope that it will be useful,
|
|
|
18 but WITHOUT ANY WARRANTY; without even the implied warranty of
|
|
|
19 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
|
|
|
20 GNU General Public License for more details.
|
|
|
21
|
|
|
22 You should have received a copy of the GNU General Public License
|
|
|
23 along with Louvain algorithm. If not, see <http://www.gnu.org/licenses/>.
|
|
|
24
|
|
|
25 -----------------------------------------------------------------------------
|
|
|
26
|
|
|
27 Author : E. Lefebvre, adapted by J.-L. Guillaume
|
|
|
28 Email : jean-loup.guillaume@lip6.fr
|
|
|
29 Location : Paris, France
|
|
|
30 Time : February 2008
|
|
|
31
|
|
|
32 -----------------------------------------------------------------------------
|
|
|
33
|
|
|
34 Disclaimer:
|
|
|
35 If you find a bug, please send a bug report to jean-loup.guillaume@lip6.fr
|
|
|
36 including if necessary the input file and the parameters that caused the bug.
|
|
|
37 You can also send me any comment or suggestion about the program.
|
|
|
38
|
|
|
39 Note that the program is expecting a friendly use and therefore does not make
|
|
|
40 much verifications about the arguments.
|
|
|
41
|
|
|
42 -----------------------------------------------------------------------------
|
|
|
43
|
|
|
44
|
|
|
45 This package offers a set of functions to use in order to compute
|
|
|
46 communities on graphs weighted or unweighted. A typical sequence of
|
|
|
47 actions is:
|
|
|
48
|
|
|
49 1. Conversion from a text format (each line contains a couple "src dest")
|
|
|
50 ./convert -i graph.txt -o graph.bin
|
|
|
51 This program can also be used to convert weighted graphs (each line contain
|
|
|
52 a triple "src dest w") using -w option:
|
|
|
53 ./convert -i graph.txt -o graph.bin -w graph.weights
|
|
|
54 Finally, nodes can be renumbered from 0 to nb_nodes - 1 using -r option
|
|
|
55 (less space wasted in some cases):
|
|
|
56 ./convert -i graph.txt -o graph.bin -r
|
|
|
57
|
|
|
58
|
|
|
59 2. Computes communities and displays hierarchical tree:
|
|
|
60 ./community graph.bin -l -1 -v > graph.tree
|
|
|
61
|
|
|
62 To ensure a faster computation (with a loss of quality), one can use
|
|
|
63 the -q option to specify that the program must stop if the increase of
|
|
|
64 modularity is below epsilon for a given iteration or pass:
|
|
|
65 ./community graph.bin -l -1 -q 0.0001 > graph.tree
|
|
|
66
|
|
|
67 The program can deal with weighted networks using -w option:
|
|
|
68 ./community graph.bin -l -1 -w graph.weights > graph.tree
|
|
|
69 In this specific case, the convertion step must also use the -w option.
|
|
|
70
|
|
|
71 The program can also start with any given partition using -p option
|
|
|
72 ./community graph.bin -p graph.part -v
|
|
|
73
|
|
|
74
|
|
|
75 3. Displays information on the tree structure (number of hierarchical
|
|
|
76 levels and nodes per level):
|
|
|
77 ./hierarchy graph.tree
|
|
|
78
|
|
|
79 Displays the belonging of nodes to communities for a given level of
|
|
|
80 the tree:
|
|
|
81 ./hierarchy graph.tree -l 2 > graph_node2comm_level2
|
|
|
82
|
|
|
83 -----------------------------------------------------------------------------
|
|
|
84
|
|
|
85 Known bugs or restrictions:
|
|
|
86 - the number of nodes is stored on 4 bytes and the number of links on 8 bytes.
|
|
|
87
|
|
|
88 -----------------------------------------------------------------------------
|
|
|
89
|
|
|
90 Version history:
|
|
|
91 The following modifications have been made from version 0.1:
|
|
|
92 - weights are now stored using floats (integer in V0.1)
|
|
|
93 - degrees are stored on 8 bytes allowing large graphs to be decomposed
|
|
|
94 - weights are stored in a separate file, which allows disk usage reduction if
|
|
|
95 different weights are to be used on the same topology
|
|
|
96 - any given partition can be used as a seed for the algorithm rather than just
|
|
|
97 the trivial partition where each node belongs to its own community
|
|
|
98 - initial network can contain loops is network is considered weighted
|
|
|
99 - graph is not renumbered by default in the convert program
|
|
|
100 - an optional verbose mode has been added and the program is silent by default
|
|
|
101 - some portions of the code have been c++ improved (type * -> vector<type>)
|
|
|
102 These modifications imply that any binary graph file created with the previous
|
|
|
103 version of the code is not comptabile with this version. You must therefore
|
|
|
104 regenerate all the binary files.
|
|
|
105
|
|
|
106 Version 0.1:
|
|
|
107 - initial community detection algorithm
|
|
|
108
|
