Mercurial > repos > petr-novak > repeatrxplorer

comparison louvain/community.cpp @ 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 // 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