|
0
|
1 // File: main_community.cpp
|
|
|
2 // -- community detection, sample main file
|
|
|
3 //-----------------------------------------------------------------------------
|
|
|
4 // Community detection
|
|
|
5 // Based on the article "Fast unfolding of community hierarchies in large networks"
|
|
|
6 // Copyright (C) 2008 V. Blondel, J.-L. Guillaume, R. Lambiotte, E. Lefebvre
|
|
|
7 //
|
|
|
8 // This program must not be distributed without agreement of the above mentionned authors.
|
|
|
9 //-----------------------------------------------------------------------------
|
|
|
10 // Author : E. Lefebvre, adapted by J.-L. Guillaume
|
|
|
11 // Email : jean-loup.guillaume@lip6.fr
|
|
|
12 // Location : Paris, France
|
|
|
13 // Time : February 2008
|
|
|
14 //-----------------------------------------------------------------------------
|
|
|
15 // see readme.txt for more details
|
|
|
16
|
|
|
17 #include <stdlib.h>
|
|
|
18 #include <math.h>
|
|
|
19 #include <string>
|
|
|
20 #include <iostream>
|
|
|
21 #include <fstream>
|
|
|
22 #include <sstream>
|
|
|
23 #include <vector>
|
|
|
24 #include <algorithm>
|
|
|
25
|
|
|
26 #include "graph_binary.h"
|
|
|
27 #include "community.h"
|
|
|
28
|
|
|
29 using namespace std;
|
|
|
30
|
|
|
31 char *filename = NULL;
|
|
|
32 char *filename_w = NULL;
|
|
|
33 char *filename_part = NULL;
|
|
|
34 int type = UNWEIGHTED;
|
|
|
35 int nb_pass = 0;
|
|
|
36 double precision = 0.000001;
|
|
|
37 int display_level = -2;
|
|
|
38 int k1 = 16;
|
|
|
39 int seed = 123;
|
|
|
40
|
|
|
41 bool verbose = false;
|
|
|
42
|
|
|
43 void
|
|
|
44 usage(char *prog_name, const char *more) {
|
|
|
45 cerr << more;
|
|
|
46 cerr << "usage: " << prog_name << " input_file [-w weight_file] [-p part_file] [-q epsilon] [-l display_level] [-v] [-h]" << endl << endl;
|
|
|
47 cerr << "input_file: file containing the graph to decompose in communities." << endl;
|
|
|
48 cerr << "-w file\tread the graph as a weighted one (weights are set to 1 otherwise)." << endl;
|
|
|
49 cerr << "-p file\tstart the computation with a given partition instead of the trivial partition." << endl;
|
|
|
50 cerr << "\tfile must contain lines \"node community\"." << endl;
|
|
|
51 cerr << "-q eps\ta given pass stops when the modularity is increased by less than epsilon." << endl;
|
|
|
52 cerr << "-l k\tdisplays the graph of level k rather than the hierachical structure." << endl;
|
|
|
53 cerr << "\tif k=-1 then displays the hierarchical structure rather than the graph at a given level." << endl;
|
|
|
54 cerr << "-v\tverbose mode: gives computation time, information about the hierarchy and modularity." << endl;
|
|
|
55 cerr << "-s\tseed for rundom number generator setting, integer(123 deafault)" << endl;
|
|
|
56 cerr << "-h\tshow this usage message." << endl;
|
|
|
57 exit(0);
|
|
|
58 }
|
|
|
59
|
|
|
60 void
|
|
|
61 parse_args(int argc, char **argv) {
|
|
|
62 if (argc<2)
|
|
|
63 usage(argv[0], "Bad arguments number\n");
|
|
|
64
|
|
|
65 for (int i = 1; i < argc; i++) {
|
|
|
66 if(argv[i][0] == '-') {
|
|
|
67 switch(argv[i][1]) {
|
|
|
68 case 'w':
|
|
|
69 type = WEIGHTED;
|
|
|
70 filename_w = argv[i+1];
|
|
|
71 i++;
|
|
|
72 break;
|
|
|
73 case 'p':
|
|
|
74 filename_part = argv[i+1];
|
|
|
75 i++;
|
|
|
76 break;
|
|
|
77 case 'q':
|
|
|
78 precision = atof(argv[i+1]);
|
|
|
79 i++;
|
|
|
80 break;
|
|
|
81 case 'l':
|
|
|
82 display_level = atoi(argv[i+1]);
|
|
|
83 i++;
|
|
|
84 break;
|
|
|
85 case 's':
|
|
|
86 seed = atoi(argv[i+1]);
|
|
|
87 i++;
|
|
|
88 break;
|
|
|
89 case 'k':
|
|
|
90 k1 = atoi(argv[i+1]);
|
|
|
91 i++;
|
|
|
92 break;
|
|
|
93 case 'v':
|
|
|
94 verbose=true;
|
|
|
95 break;
|
|
|
96 default:
|
|
|
97 usage(argv[0], "Unknown option\n");
|
|
|
98 }
|
|
|
99 } else {
|
|
|
100 if (filename==NULL)
|
|
|
101 filename = argv[i];
|
|
|
102 else
|
|
|
103 usage(argv[0], "More than one filename\n");
|
|
|
104 }
|
|
|
105 }
|
|
|
106 }
|
|
|
107
|
|
|
108 void
|
|
|
109 display_time(const char *str) {
|
|
|
110 time_t rawtime;
|
|
|
111 time ( &rawtime );
|
|
|
112 cerr << str << ": " << ctime (&rawtime);
|
|
|
113 }
|
|
|
114
|
|
|
115 int
|
|
|
116 main(int argc, char **argv) {
|
|
|
117 parse_args(argc, argv);
|
|
|
118 srand(seed);
|
|
|
119 time_t time_begin, time_end;
|
|
|
120 time(&time_begin);
|
|
|
121 if (verbose)
|
|
|
122 display_time("Begin");
|
|
|
123
|
|
|
124 Community c(filename, filename_w, type, -1, precision);
|
|
|
125 if (filename_part!=NULL)
|
|
|
126 c.init_partition(filename_part);
|
|
|
127 Graph g;
|
|
|
128 bool improvement=true;
|
|
|
129 double mod=c.modularity(), new_mod;
|
|
|
130 int level=0;
|
|
|
131
|
|
|
132 do {
|
|
|
133 if (verbose) {
|
|
|
134 cerr << "level " << level << ":\n";
|
|
|
135 display_time(" start computation");
|
|
|
136 cerr << " network size: "
|
|
|
137 << c.g.nb_nodes << " nodes, "
|
|
|
138 << c.g.nb_links << " links, "
|
|
|
139 << c.g.total_weight << " weight." << endl;
|
|
|
140 }
|
|
|
141
|
|
|
142 improvement = c.one_level();
|
|
|
143 new_mod = c.modularity();
|
|
|
144 if (++level==display_level)
|
|
|
145 g.display();
|
|
|
146 if (display_level==-1)
|
|
|
147 c.display_partition();
|
|
|
148 g = c.partition2graph_binary();
|
|
|
149 c = Community(g, -1, precision);
|
|
|
150
|
|
|
151 if (verbose)
|
|
|
152 cerr << " modularity increased from " << mod << " to " << new_mod << endl;
|
|
|
153
|
|
|
154 mod=new_mod;
|
|
|
155 if (verbose)
|
|
|
156 display_time(" end computation");
|
|
|
157
|
|
|
158 if (filename_part!=NULL && level==1) // do at least one more computation if partition is provided
|
|
|
159 improvement=true;
|
|
|
160 } while(improvement);
|
|
|
161
|
|
|
162 time(&time_end);
|
|
|
163 if (verbose) {
|
|
|
164 display_time("End");
|
|
|
165 cerr << "Total duration: " << (time_end-time_begin) << " sec." << endl;
|
|
|
166 }
|
|
|
167 cerr << new_mod << endl;
|
|
|
168 }
|
|
|
169
|
