## Revision 3c6ce57c fiddle/heuristic-betweenness-centrality/centrality_biconnected.py

View differences:

fiddle/heuristic-betweenness-centrality/centrality_biconnected.py
2 2
```# Heuristic Betweenness Centrality - Partitioning to Bi-connected Components
```
3 3

4 4
```import os
```
5
```import pprint
```
5 6
```import networkx as nx
```
6 7
```import betweenness_centrality as centrality
```
7 8
```import utility
```
......
27 28
```        self.finalize()
```
28 29

29 30
```    def calculate_bc_non_cutpoint(self):
```
30
```        """BCen for non cutpoint
```
31
```        """BC for non cutpoint
```
31 32
```        """
```
32 33
```        for i, subgraphs in enumerate(self.subgraphs):
```
33 34
```            traffic_matrix = self.traffic_matrix[i]
```
34
```            results = centrality.betweenness_centrality(subgraphs, traffic_matrix, endpoints=True)
```
35
```            results = centrality.weight_betweenness_centrality(subgraphs, traffic_matrix)
```
35 36
```            self.bc_components.append(results)
```
36 37

37 38
```            # print results
```
......
58 59
```                    # debugger()
```
59 60
```                    bc_locally += self.bc_components[i][v]
```
60 61
```            print 'locally = %s' % bc_locally
```
61
```            self.bc_cutpoints[v] = bc_locally - bc_inter[v]
```
62
```            # self.bc_cutpoints[v] = bc_locally - bc_inter[v]
```
63
```            # TODO: do not minus the bc_inter
```
64
```            self.bc_cutpoints[v] = bc_locally
```
62 65

63 66
```    def finalize(self):
```
64 67
```        # Add the bc for non cutpoint vertices
```
......
71 74
```        for key, value in self.bc_cutpoints.iteritems():
```
72 75
```            self.bc[key] = value
```
73 76

77
```        print '*** betweenness = %s' % self.bc
```
74 78
```        # Rescale the bc according to the original graph
```
75
```        factor = 2.0 / (self.num_vertices*self.num_vertices - 3 * self.num_vertices + 2)
```
79
```        factor = 1.0 / ((self.num_vertices - 1) * (self.num_vertices - 2))
```
80
```        # factor = 2.0 / (self.num_vertices*self.num_vertices - 3 * self.num_vertices + 2)
```
76 81
```        for key, value in self.bc.iteritems():
```
77 82
```            self.bc[key] = value * factor
```
78 83

......
84 89

85 90
```    def __str__(self):
```
86 91
```        return str(self.bc)
```
87
```        # for bc_component in self.bc_components:
```
88
```        #     print bc_component
```
89 92

90 93

91 94
```class TrafficMatrix():
```
......
167 170

168 171
```        self.Dv_B = [dict() for i in range(self.num_components)] # link weight
```
169 172
```        self.generate_link_weight()
```
173
```        # self.compute_component_tree_weight()
```
170 174

171 175
```        self.reverse_Dv_B = [dict() for i in range(self.num_components)] # reverse link weight
```
172 176
```        self.generate_reverse_link_weight()
```
......
181 185
```        return indices
```
182 186

183 187
```    def get_link_weight(self, comp_index, point):
```
184
```        print "Dv_B = %s" % str(self.Dv_B)
```
185

186 188
```        Dv_B_comp = self.Dv_B[comp_index]
```
187 189

188 190
```        if point in Dv_B_comp:
```
......
190 192
```        else:
```
191 193
```            return 0
```
192 194

195
```    def set_link_weight(self, comp_index, point, value):
```
196
```        self.Dv_B[comp_index][point] = value
```
197

193 198
```    def get_reverse_link_weight(self, comp_index, point):
```
194 199
```        reverse_Dv_B_comp = self.reverse_Dv_B[comp_index]
```
195 200

......
207 212
```            B_plus_v.append(comp.difference(points))
```
208 213
```            B_cutpoints.append(points)
```
209 214

210
```        print 'B_cutpoints %s' % str(B_cutpoints)
```
211 215
```        len_B_plus_v = [len(x) for x in B_plus_v]
```
212 216
```        len_B_cutpoints = [len(x) for x in B_cutpoints]
```
213 217

......
220 224
```                point = list(cp)[0] # there is only 1 element
```
221 225
```                self.Dv_B[i][point] = len_B_plus_v[i]
```
222 226

223
```        print 'B_cutpoints %s' % str(B_cutpoints)
```
227
```        print "Link Weight - For all the leaves: %s" % self.Dv_B
```
224 228

225 229
```        # For other nodes in the block-cut tree
```
226 230
```        level += 1
```
227 231
```        while level <= max(len_B_cutpoints):
```
232
```            if level == 3:
```
233
```                debugger()
```
228 234
```            for (i, cp) in enumerate(B_cutpoints):
```
229 235
```                if len_B_cutpoints[i] == level:
```
230 236

231 237
```                    for point in cp:
```
232
```                        print 'cutpoints = %s' % cp
```
238
```                        # 1st way
```
233 239
```                        shared_comp_indices = self._components_sharing_cutpoint(B_cutpoints, point)
```
234 240
```                        shared_comp_indices.remove(i)
```
235
```                        print 'shared indices %s' % shared_comp_indices
```
236 241
```                        weight_shared_comp = list()
```
237 242

238 243
```                        for index in shared_comp_indices:
```
239 244
```                            weight_shared_comp.append(self.get_link_weight(index, point))
```
240 245

241
```                        print 'weight shared comp %s' % str(weight_shared_comp)
```
242
```                        weight = num_vertices - 1 - sum(weight_shared_comp)
```
246
```                        weight = self.num_vertices - 1 - sum(weight_shared_comp)
```
243 247

244 248
```                        self.Dv_B[i][point] = weight
```
245 249

250
```                        # # 2nd way
```
251
```                        # sum_of_connected_vertices = 0
```
252
```                        # for point_temp in cp:
```
253
```                        #     if point_temp != point:
```
254
```                        #         sum_of_connected_vertices += self.num_vertices -
```
255
```            print "Link Weight - For level %s: %s" % (level, self.Dv_B)
```
256

246 257
```            level += 1
```
247 258

248 259
```    def generate_reverse_link_weight(self):
```
......
250 261
```            for key, value in Dv_B_i.iteritems():
```
251 262
```                self.reverse_Dv_B[i][key] = self.num_vertices - 1 - self.get_link_weight(i, key)
```
252 263

253
```        print 'reverse = %s' % self.reverse_Dv_B
```
264
```    def compute_component_tree_weight(self):
```
265
```        """Follows exactly the Algorithm 1 [Puzis 2012]
```
266
```        """
```
267
```        B_cutpoints = list() # number of cutpoints in component B
```
268
```        for comp in self.bicomponents:
```
269
```            points = comp.intersection(self.cutpoints)
```
270
```            B_cutpoints.append(points)
```
271

272
```        Q = self._inititalize_component_tree_weight()
```
273
```        while Q:
```
274
```            print self.Dv_B
```
275
```            pair = Q.pop(0)
```
276
```            if pair['type'] == 'component_vertex_pair':
```
277
```                B_index = pair['value'][0]
```
278
```                v = pair['value'][1]
```
279
```                print'  CV: %s %s' % (B_index, v)
```
280
```                size = len(self.bicomponents[B_index]) - 1;
```
281
```                all_cutpoints = self.bicomponents[B_index].intersection(self.cutpoints)
```
282
```                all_cutpoints.remove(v)
```
283

284
```                for cp in all_cutpoints:
```
285
```                    if self.get_link_weight(B_index, cp) != -1:
```
286
```                        size += self.num_vertices - self.get_link_weight(B_index, cp)
```
287

288
```                self.set_link_weight(B_index, v, size)
```
289

290
```                # update Q
```
291
```                Q = self._find_unknown_weight_wrt_cutpoint(v, Q)
```
292

293
```            if pair['type'] == 'vertex_component_pair':
```
294
```                size = 1
```
295
```                B_index = pair['value'][0]
```
296
```                v = pair['value'][1]
```
297
```                print'  vc: %s %s' % (B_index, v)
```
298
```                shared_comp_indices = self._components_sharing_cutpoint(B_cutpoints, v)
```
299
```                shared_comp_indices.remove(B_index)
```
300

301

302
```                for i in shared_comp_indices:
```
303
```                    if self.get_link_weight(i, v) != - 1:
```
304
```                        size += self.get_link_weight(i, v)
```
305

306
```                self.set_link_weight(B_index, v, self.num_vertices - 1 - size)
```
307

308
```                # update Q
```
309
```                Q = self._find_unknown_weight_wrt_component(B_index, Q)
```
310

311
```    def _inititalize_component_tree_weight(self):
```
312
```        Q = []
```
313
```        for i, comp in enumerate(self.bicomponents):
```
314
```            current_cutpoints = self.cutpoints.intersection(comp)
```
315
```            if len(current_cutpoints) == 1:
```
316
```                Q.append({
```
317
```                    'type': 'component_vertex_pair',
```
318
```                    'value': (i, list(current_cutpoints)[0]) # (B_i, cutpoint) = (i-th component, the cutpoint name)
```
319
```                    })
```
320
```            for cp in current_cutpoints:
```
321
```                self.set_link_weight(i, cp, -1)
```
322
```        return Q
```
323

324
```    def _find_unknown_weight_wrt_cutpoint(self, cutpoint, Q):
```
325
```        for i, Dv_B_comp in enumerate(self.Dv_B):
```
326
```            for cp, value in Dv_B_comp.iteritems():
```
327
```                if value == -1:
```
328
```                    pair = {
```
329
```                        'type': 'vertex_component_pair',
```
330
```                        'value': (i, cp)
```
331
```                    }
```
332
```                    Q.append(pair)
```
333
```        return Q
```
334

335
```    def _find_unknown_weight_wrt_component(self, comp_index, Q):
```
336
```        Dv_B_comp = self.Dv_B[comp_index]
```
337
```        for cp, value in Dv_B_comp.iteritems():
```
338
```            if value == -1:
```
339
```                pair = {
```
340
```                    'type': 'component_vertex_pair',
```
341
```                    'value': (comp_index, cp)
```
342
```                }
```
343
```                Q.append(pair)
```
344
```        return Q
```
345

254 346

255 347
```    def __str__(self):
```
256 348
```        return str(self.Dv_B)
```
......
260 352
```    print bicomponents
```
261 353
```    print [len(x) for x in bicomponents]
```
262 354

263
```if __name__ == '__main__':
```
264
```    filepath = MAIN_CODE_DIR + '/input/simple.edges'
```
265
```    file_suffix = 'edge_list'
```
355
```def find_heuristic_bc(filepath):
```
356
```    pp = pprint.PrettyPrinter(indent=4)
```
266 357

267
```    # Brandes betweenness centrality
```
268
```    utility.brandes_betweenness_centrality(filepath, file_suffix)
```
269

270
```    # Heuristic betweenness centrality
```
271 358
```    graph = nx.read_weighted_edgelist(filepath)
```
272 359

273 360
```    # Find biconnected components
```
......
276 363
```    subgraphs = list(nx.biconnected_component_subgraphs(graph))
```
277 364
```    bicomponents = list(nx.biconnected_components(graph))
```
278 365
```    component_edges = list(nx.biconnected_component_edges(graph))
```
279
```    # cutpoints = list(nx.articulation_points(graph))
```
280 366
```    cutpoints = set(nx.articulation_points(graph))
```
281 367

282 368
```    num_vertices = nx.number_of_nodes(graph)
```
283 369

284 370
```    lw = LinkWeight(graph, bicomponents, cutpoints)
```
285 371
```    print 'link weight: '
```
286
```    print lw
```
372
```    print(lw)
```
373

374
```    # tm = TrafficMatrix(bicomponents, cutpoints, lw)
```
375
```    # print 'traffic matrix:'
```
376
```    # pp.pprint(tm.h)
```
287 377

288
```    tm = TrafficMatrix(bicomponents, cutpoints, lw)
```
289
```    print tm
```
378
```    # bc = HeuristicBetweennessCentrality(subgraphs, bicomponents, cutpoints, num_vertices, lw, tm)
```
379
```    # bc.write(file_suffix)
```
380
```    # # print bc
```
290 381

382
```if __name__ == '__main__':
```
383
```    # filepath = MAIN_CODE_DIR + '/input/simple_house.edges'
```
384
```    # filepath = MAIN_CODE_DIR + '/input/simple2.edges'
```
385
```    # filepath = MAIN_CODE_DIR + '/input/simple.edges'
```
386
```    # filepath = MAIN_CODE_DIR + '/input/ninux_30_1.edges'
```
387
```    # filepath = MAIN_CODE_DIR + '/input/simple3.edges'
```
388
```    filepath = MAIN_CODE_DIR + '/input/simple4.edges'
```
389
```    file_suffix = 'edge_list'
```
390

391
```    # Weight betweenness centrality
```
392
```    utility.weight_betweenness_centrality(filepath, file_suffix)
```
393

394
```    # Brandess betweenness centrality
```
395
```    utility.brandes_betweenness_centrality(filepath, file_suffix)
```
291 396

292
```    bc = HeuristicBetweennessCentrality(subgraphs, bicomponents, cutpoints, num_vertices, lw, tm)
```
293
```    bc.write(file_suffix)
```
294
```    print bc
```
397
```    # Heuristic BC
```
398
```    find_heuristic_bc(filepath)
```

Also available in: Unified diff