Mercurial > repos > petr-novak > repeatrxplorer

comparison louvain/readme.txt @ 0:1d1b9e1b2e2f draft

Find changesets by keywords (author, files, the commit message), revision number or hash, or revset expression.
Uploaded
author petr-novak
date Thu, 19 Dec 2019 10:24:45 -0500
parents
children
comparison
equal deleted inserted replaced
-1:000000000000 0:1d1b9e1b2e2f
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