|
0
|
1 // File: community.h
|
|
|
2 // -- community detection source 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 "community.h"
|
|
|
18
|
|
|
19 using namespace std;
|
|
|
20
|
|
|
21 Community::Community(char * filename, char * filename_w, int type, int nbp, double minm) {
|
|
|
22 g = Graph(filename, filename_w, type);
|
|
|
23 size = g.nb_nodes;
|
|
|
24
|
|
|
25 neigh_weight.resize(size,-1);
|
|
|
26 neigh_pos.resize(size);
|
|
|
27 neigh_last=0;
|
|
|
28
|
|
|
29 n2c.resize(size);
|
|
|
30 in.resize(size);
|
|
|
31 tot.resize(size);
|
|
|
32
|
|
|
33 for (int i=0 ; i<size ; i++) {
|
|
|
34 n2c[i] = i;
|
|
|
35 tot[i] = g.weighted_degree(i);
|
|
|
36 in[i] = g.nb_selfloops(i);
|
|
|
37 }
|
|
|
38
|
|
|
39 nb_pass = nbp;
|
|
|
40 min_modularity = minm;
|
|
|
41 }
|
|
|
42
|
|
|
43 Community::Community(Graph gc, int nbp, double minm) {
|
|
|
44 g = gc;
|
|
|
45 size = g.nb_nodes;
|
|
|
46
|
|
|
47 neigh_weight.resize(size,-1);
|
|
|
48 neigh_pos.resize(size);
|
|
|
49 neigh_last=0;
|
|
|
50
|
|
|
51 n2c.resize(size);
|
|
|
52 in.resize(size);
|
|
|
53 tot.resize(size);
|
|
|
54
|
|
|
55 for (int i=0 ; i<size ; i++) {
|
|
|
56 n2c[i] = i;
|
|
|
57 in[i] = g.nb_selfloops(i);
|
|
|
58 tot[i] = g.weighted_degree(i);
|
|
|
59 }
|
|
|
60
|
|
|
61 nb_pass = nbp;
|
|
|
62 min_modularity = minm;
|
|
|
63 }
|
|
|
64
|
|
|
65 void
|
|
|
66 Community::init_partition(char * filename) {
|
|
|
67 ifstream finput;
|
|
|
68 finput.open(filename,fstream::in);
|
|
|
69
|
|
|
70 // read partition
|
|
|
71 while (!finput.eof()) {
|
|
|
72 unsigned int node, comm;
|
|
|
73 finput >> node >> comm;
|
|
|
74
|
|
|
75 if (finput) {
|
|
|
76 int old_comm = n2c[node];
|
|
|
77 neigh_comm(node);
|
|
|
78
|
|
|
79 remove(node, old_comm, neigh_weight[old_comm]);
|
|
|
80
|
|
|
81 unsigned int i=0;
|
|
|
82 for ( i=0 ; i<neigh_last ; i++) {
|
|
|
83 unsigned int best_comm = neigh_pos[i];
|
|
|
84 float best_nblinks = neigh_weight[neigh_pos[i]];
|
|
|
85 if (best_comm==comm) {
|
|
|
86 insert(node, best_comm, best_nblinks);
|
|
|
87 break;
|
|
|
88 }
|
|
|
89 }
|
|
|
90 if (i==neigh_last)
|
|
|
91 insert(node, comm, 0);
|
|
|
92 }
|
|
|
93 }
|
|
|
94 finput.close();
|
|
|
95 }
|
|
|
96
|
|
|
97 // inline void
|
|
|
98 // Community::remove(int node, int comm, double dnodecomm) {
|
|
|
99 // assert(node>=0 && node<size);
|
|
|
100
|
|
|
101 // tot[comm] -= g.weighted_degree(node);
|
|
|
102 // in[comm] -= 2*dnodecomm + g.nb_selfloops(node);
|
|
|
103 // n2c[node] = -1;
|
|
|
104 // }
|
|
|
105
|
|
|
106 // inline void
|
|
|
107 // Community::insert(int node, int comm, double dnodecomm) {
|
|
|
108 // assert(node>=0 && node<size);
|
|
|
109
|
|
|
110 // tot[comm] += g.weighted_degree(node);
|
|
|
111 // in[comm] += 2*dnodecomm + g.nb_selfloops(node);
|
|
|
112 // n2c[node]=comm;
|
|
|
113 // }
|
|
|
114
|
|
|
115 void
|
|
|
116 Community::display() {
|
|
|
117 for (int i=0 ; i<size ; i++)
|
|
|
118 cerr << " " << i << "/" << n2c[i] << "/" << in[i] << "/" << tot[i] ;
|
|
|
119 cerr << endl;
|
|
|
120 }
|
|
|
121
|
|
|
122
|
|
|
123 double
|
|
|
124 Community::modularity() {
|
|
|
125 double q = 0.;
|
|
|
126 double m2 = (double)g.total_weight;
|
|
|
127
|
|
|
128 for (int i=0 ; i<size ; i++) {
|
|
|
129 if (tot[i]>0)
|
|
|
130 q += (double)in[i]/m2 - ((double)tot[i]/m2)*((double)tot[i]/m2);
|
|
|
131 }
|
|
|
132
|
|
|
133 return q;
|
|
|
134 }
|
|
|
135
|
|
|
136 void
|
|
|
137 Community::neigh_comm(unsigned int node) {
|
|
|
138 for (unsigned int i=0 ; i<neigh_last ; i++)
|
|
|
139 neigh_weight[neigh_pos[i]]=-1;
|
|
|
140 neigh_last=0;
|
|
|
141
|
|
|
142 pair<vector<unsigned int>::iterator, vector<float>::iterator> p = g.neighbors(node);
|
|
|
143
|
|
|
144 unsigned int deg = g.nb_neighbors(node);
|
|
|
145
|
|
|
146 neigh_pos[0]=n2c[node];
|
|
|
147 neigh_weight[neigh_pos[0]]=0;
|
|
|
148 neigh_last=1;
|
|
|
149
|
|
|
150 for (unsigned int i=0 ; i<deg ; i++) {
|
|
|
151 unsigned int neigh = *(p.first+i);
|
|
|
152 unsigned int neigh_comm = n2c[neigh];
|
|
|
153 double neigh_w = (g.weights.size()==0)?1.:*(p.second+i);
|
|
|
154
|
|
|
155 if (neigh!=node) {
|
|
|
156 if (neigh_weight[neigh_comm]==-1) {
|
|
|
157 neigh_weight[neigh_comm]=0.;
|
|
|
158 neigh_pos[neigh_last++]=neigh_comm;
|
|
|
159 }
|
|
|
160 neigh_weight[neigh_comm]+=neigh_w;
|
|
|
161 }
|
|
|
162 }
|
|
|
163 }
|
|
|
164
|
|
|
165 void
|
|
|
166 Community::partition2graph() {
|
|
|
167 vector<int> renumber(size, -1);
|
|
|
168 for (int node=0 ; node<size ; node++) {
|
|
|
169 renumber[n2c[node]]++;
|
|
|
170 }
|
|
|
171
|
|
|
172 int final=0;
|
|
|
173 for (int i=0 ; i<size ; i++)
|
|
|
174 if (renumber[i]!=-1)
|
|
|
175 renumber[i]=final++;
|
|
|
176
|
|
|
177
|
|
|
178 for (int i=0 ; i<size ; i++) {
|
|
|
179 pair<vector<unsigned int>::iterator, vector<float>::iterator> p = g.neighbors(i);
|
|
|
180
|
|
|
181 int deg = g.nb_neighbors(i);
|
|
|
182 for (int j=0 ; j<deg ; j++) {
|
|
|
183 int neigh = *(p.first+j);
|
|
|
184 cout << renumber[n2c[i]] << " " << renumber[n2c[neigh]] << endl;
|
|
|
185 }
|
|
|
186 }
|
|
|
187 }
|
|
|
188
|
|
|
189 void
|
|
|
190 Community::display_partition() {
|
|
|
191 vector<int> renumber(size, -1);
|
|
|
192 for (int node=0 ; node<size ; node++) {
|
|
|
193 renumber[n2c[node]]++;
|
|
|
194 }
|
|
|
195
|
|
|
196 int final=0;
|
|
|
197 for (int i=0 ; i<size ; i++)
|
|
|
198 if (renumber[i]!=-1)
|
|
|
199 renumber[i]=final++;
|
|
|
200
|
|
|
201 for (int i=0 ; i<size ; i++)
|
|
|
202 cout << i << " " << renumber[n2c[i]] << endl;
|
|
|
203 }
|
|
|
204
|
|
|
205
|
|
|
206 Graph
|
|
|
207 Community::partition2graph_binary() {
|
|
|
208 // Renumber communities
|
|
|
209 vector<int> renumber(size, -1);
|
|
|
210 for (int node=0 ; node<size ; node++) {
|
|
|
211 renumber[n2c[node]]++;
|
|
|
212 }
|
|
|
213
|
|
|
214 int final=0;
|
|
|
215 for (int i=0 ; i<size ; i++)
|
|
|
216 if (renumber[i]!=-1)
|
|
|
217 renumber[i]=final++;
|
|
|
218
|
|
|
219 // Compute communities
|
|
|
220 vector<vector<int> > comm_nodes(final);
|
|
|
221 for (int node=0 ; node<size ; node++) {
|
|
|
222 comm_nodes[renumber[n2c[node]]].push_back(node);
|
|
|
223 }
|
|
|
224
|
|
|
225 // Compute weighted graph
|
|
|
226 Graph g2;
|
|
|
227 g2.nb_nodes = comm_nodes.size();
|
|
|
228 g2.degrees.resize(comm_nodes.size());
|
|
|
229
|
|
|
230 int comm_deg = comm_nodes.size();
|
|
|
231 for (int comm=0 ; comm<comm_deg ; comm++) {
|
|
|
232 map<int,float> m;
|
|
|
233 map<int,float>::iterator it;
|
|
|
234
|
|
|
235 int comm_size = comm_nodes[comm].size();
|
|
|
236 for (int node=0 ; node<comm_size ; node++) {
|
|
|
237 pair<vector<unsigned int>::iterator, vector<float>::iterator> p = g.neighbors(comm_nodes[comm][node]);
|
|
|
238 int deg = g.nb_neighbors(comm_nodes[comm][node]);
|
|
|
239 for (int i=0 ; i<deg ; i++) {
|
|
|
240 int neigh = *(p.first+i);
|
|
|
241 int neigh_comm = renumber[n2c[neigh]];
|
|
|
242 double neigh_weight = (g.weights.size()==0)?1.:*(p.second+i);
|
|
|
243
|
|
|
244 it = m.find(neigh_comm);
|
|
|
245 if (it==m.end())
|
|
|
246 m.insert(make_pair(neigh_comm, neigh_weight));
|
|
|
247 else
|
|
|
248 it->second+=neigh_weight;
|
|
|
249 }
|
|
|
250 }
|
|
|
251 g2.degrees[comm]=(comm==0)?m.size():g2.degrees[comm-1]+m.size();
|
|
|
252 g2.nb_links+=m.size();
|
|
|
253
|
|
|
254
|
|
|
255 for (it = m.begin() ; it!=m.end() ; it++) {
|
|
|
256 g2.total_weight += it->second;
|
|
|
257 g2.links.push_back(it->first);
|
|
|
258 g2.weights.push_back(it->second);
|
|
|
259 }
|
|
|
260 }
|
|
|
261
|
|
|
262 return g2;
|
|
|
263 }
|
|
|
264
|
|
|
265
|
|
|
266 bool
|
|
|
267 Community::one_level() {
|
|
|
268 bool improvement=false ;
|
|
|
269 int nb_moves;
|
|
|
270 int nb_pass_done = 0;
|
|
|
271 double new_mod = modularity();
|
|
|
272 double cur_mod = new_mod;
|
|
|
273
|
|
|
274 vector<int> random_order(size);
|
|
|
275 for (int i=0 ; i<size ; i++)
|
|
|
276 random_order[i]=i;
|
|
|
277 for (int i=0 ; i<size-1 ; i++) {
|
|
|
278 int rand_pos = rand()%(size-i)+i;
|
|
|
279 int tmp = random_order[i];
|
|
|
280 random_order[i] = random_order[rand_pos];
|
|
|
281 random_order[rand_pos] = tmp;
|
|
|
282 }
|
|
|
283
|
|
|
284 // repeat while
|
|
|
285 // there is an improvement of modularity
|
|
|
286 // or there is an improvement of modularity greater than a given epsilon
|
|
|
287 // or a predefined number of pass have been done
|
|
|
288 do {
|
|
|
289 cur_mod = new_mod;
|
|
|
290 nb_moves = 0;
|
|
|
291 nb_pass_done++;
|
|
|
292
|
|
|
293 // for each node: remove the node from its community and insert it in the best community
|
|
|
294 for (int node_tmp=0 ; node_tmp<size ; node_tmp++) {
|
|
|
295 // int node = node_tmp;
|
|
|
296 int node = random_order[node_tmp];
|
|
|
297 int node_comm = n2c[node];
|
|
|
298 double w_degree = g.weighted_degree(node);
|
|
|
299
|
|
|
300 // computation of all neighboring communities of current node
|
|
|
301 neigh_comm(node);
|
|
|
302 // remove node from its current community
|
|
|
303 remove(node, node_comm, neigh_weight[node_comm]);
|
|
|
304
|
|
|
305 // compute the nearest community for node
|
|
|
306 // default choice for future insertion is the former community
|
|
|
307 int best_comm = node_comm;
|
|
|
308 double best_nblinks = 0.;
|
|
|
309 double best_increase = 0.;
|
|
|
310 for (unsigned int i=0 ; i<neigh_last ; i++) {
|
|
|
311 double increase = modularity_gain(node, neigh_pos[i], neigh_weight[neigh_pos[i]], w_degree);
|
|
|
312 if (increase>best_increase) {
|
|
|
313 best_comm = neigh_pos[i];
|
|
|
314 best_nblinks = neigh_weight[neigh_pos[i]];
|
|
|
315 best_increase = increase;
|
|
|
316 }
|
|
|
317 }
|
|
|
318
|
|
|
319 // insert node in the nearest community
|
|
|
320 insert(node, best_comm, best_nblinks);
|
|
|
321
|
|
|
322 if (best_comm!=node_comm)
|
|
|
323 nb_moves++;
|
|
|
324 }
|
|
|
325
|
|
|
326 double total_tot=0;
|
|
|
327 double total_in=0;
|
|
|
328 for (unsigned int i=0 ; i<tot.size() ;i++) {
|
|
|
329 total_tot+=tot[i];
|
|
|
330 total_in+=in[i];
|
|
|
331 }
|
|
|
332
|
|
|
333 new_mod = modularity();
|
|
|
334 if (nb_moves>0)
|
|
|
335 improvement=true;
|
|
|
336
|
|
|
337 } while (nb_moves>0 && new_mod-cur_mod>min_modularity);
|
|
|
338
|
|
|
339 return improvement;
|
|
|
340 }
|
|
|
341
|
