Revision 82c7c698

View differences:

fiddle/heuristic-betweenness-centrality/betweenness_centrality.py
113 113
```    else:
```
114 114
```        random.seed(seed)
```
115 115
```        nodes = random.sample(G.nodes(), k)
```
116
```    vertices = G.nodes()
```
116
```    vertices = sorted(G.nodes())
```
117 117

118
```    # print 'nodes = %s' % nodes
```
119
```    # print 'vertices = %s' % vertices
```
120 118
```    for s in nodes:
```
121
```        # single source shortest paths
```
122
```        # print '\nxxx _single_source_shortest_path'
```
123 119
```        if weight is None:  # use BFS
```
124 120
```            S, P, sigma = _single_source_shortest_path_basic(G, s)
```
125 121
```        else:  # use Dijkstra's algorithm
```
126 122
```            S, P, sigma = _single_source_dijkstra_path_basic(G, s, weight)
```
127 123

128
```        # print s
```
129
```        # print S
```
130
```        # print P
```
131
```        # print sigma
```
132 124
```        # accumulation
```
133 125
```        if traffic_matrix:
```
134 126
```            betweenness = _accumulate_weight(betweenness, S, P, sigma, s, traffic_matrix, vertices)
```
135 127
```        else:
```
136 128
```            betweenness = _accumulate_weight_basic(betweenness, S, P, sigma, s)
```
137 129

138
```    print '@@@ betweenness = %s' % betweenness
```
139 130
```    if rescale:
```
140 131
```        betweenness = _rescale(betweenness, len(G),
```
141 132
```                   normalized=normalized,
```
......
185 176
```    sigma = dict.fromkeys(G, 0.0)    # sigma[v]=0 for v in G
```
186 177
```    D = {}
```
187 178
```    sigma[s] = 1.0
```
188
```    print sigma
```
189 179
```    push = heappush
```
190 180
```    pop = heappop
```
191 181
```    seen = {s: 0}
```
......
225 215
```    delta = dict.fromkeys(S, 0)
```
226 216
```    while S:
```
227 217
```        w = S.pop()
```
228
```        print 'w = %s' % w
```
229 218
```        coeff = (1.0 + delta[w]) / sigma[w]
```
230
```        # coeff = (delta[w]) / sigma[w]
```
231 219
```        for v in P[w]:
```
232
```            print '\tv = %s' % v
```
233 220
```            h = _get_value_from_traffic_matrix(nodes, traffic_matrix, s, v)
```
234
```            print '\t h = %s' % h
```
235 221
```            delta[v] += sigma[v] * coeff + h
```
236
```        print 'delta = %s' % delta
```
237 222
```        if w != s:
```
238
```            # print h
```
239
```            # betweenness[w] += delta[w] * h
```
240 223
```            betweenness[w] += delta[w]
```
241
```            print 'betweenness = %s' % betweenness
```
242
```    return betweenness
```
243 224

244 225

245 226
```def _accumulate_weight_basic(betweenness, S, P, sigma, s):
```
......
254 235
```    .. [1] Rami Puzis
```
255 236
```       Optimization of NIDS Placement for Protection of Intercommunicating Critical Infrastructures
```
256 237
```    """
```
257
```    # betweenness[s] += len(S) - 1
```
258 238
```    delta = dict.fromkeys(S, 0)
```
259 239
```    while S:
```
260 240
```        w = S.pop()
```
......
265 245
```            delta[v] += sigma[v] * coeff
```
266 246
```        if w != s:
```
267 247
```            betweenness[w] += delta[w]
```
268
```            # print 'out betweenness = %s' % betweenness
```
269 248
```    return betweenness
```
270 249

271 250
```def _accumulate_weight(betweenness, S, P, sigma, s, traffic_matrix, nodes):
```
......
276 255
```    .. [1] Rami Puzis
```
277 256
```       Optimization of NIDS Placement for Protection of Intercommunicating Critical Infrastructures
```
278 257
```    """
```
279
```    # betweenness[s] += len(S) - 1
```
280 258
```    delta = dict.fromkeys(S, 0)
```
281 259
```    while S:
```
282
```        # print 'in betweenness = %s' % betweenness
```
283 260
```        w = S.pop()
```
284 261
```        h = _get_value_from_traffic_matrix(nodes, traffic_matrix, s, w)
```
285 262
```        delta[w] += h
```
286 263
```        coeff = delta[w] / sigma[w]
```
287
```        # print "  coeff = %s" % coeff
```
264

288 265
```        for v in P[w]:
```
289
```            # print "  v = %s" % v
```
290
```            # print "    h = %s" % h
```
291 266
```            delta[v] += sigma[v] * coeff
```
292
```            # print '  delta = %s' % delta
```
293 267
```        if w != s:
```
294 268
```            betweenness[w] += delta[w]
```
295
```            # print 'betweenness = %s' % betweenness
```
296 269
```    return betweenness
```
297 270

298 271

fiddle/heuristic-betweenness-centrality/centrality_biconnected.py
1 1
```# Implement the section IV in Puzis 2012 paper
```
2
```# straight_lineent the section IV in Puzis 2012 paper
```
2 3
```# Heuristic Betweenness Centrality - Partitioning to Bi-connected Components
```
3 4

4 5
```import os
```
......
36 37
```            results = centrality.weight_betweenness_centrality(subgraphs, traffic_matrix)
```
37 38
```            self.bc_components.append(results)
```
38 39

39
```            # print results
```
40

41 40
```    def calculate_bc_cutpoint(self):
```
42 41
```        self.bc_cutpoints = dict()
```
43 42

......
57 56
```            bc_locally = 0
```
58 57
```            for i, comp in enumerate(self.bicomponents):
```
59 58
```                if v in comp:
```
60
```                    # debugger()
```
61 59
```                    bc_locally += self.bc_components[i][v]
```
62
```            print 'locally = %s' % bc_locally
```
63 60
```            # self.bc_cutpoints[v] = bc_locally - bc_inter[v]
```
64 61
```            # TODO: do not minus the bc_inter
```
65 62
```            self.bc_cutpoints[v] = bc_locally
```
......
78 75
```        print '*** betweenness = %s' % self.bc
```
79 76
```        # Rescale the bc according to the original graph
```
80 77
```        factor = 1.0 / ((self.num_vertices - 1) * (self.num_vertices - 2))
```
78
```        # TODO: check the scaling factor, how much should it be?
```
81 79
```        # factor = 2.0 / (self.num_vertices*self.num_vertices - 3 * self.num_vertices + 2)
```
82 80
```        for key, value in self.bc.iteritems():
```
83 81
```            self.bc[key] = value * factor
```
......
145 143
```        self.h[comp_index][y_pos][x_pos] = value
```
146 144

147 145
```    def update(self, comp_index, x, y, value):
```
148
```        comp = self.bicomponents[comp_index]
```
146
```        comp = sorted(self.bicomponents[comp_index])
```
149 147
```        try:
```
150 148
```            x_pos = list(comp).index(x)
```
151 149
```            y_pos = list(comp).index(y)
```
......
178 176
```    def _components_sharing_cutpoint(self, B_cutpoints, point):
```
179 177
```        indices = list()
```
180 178
```        for i, cp in enumerate(B_cutpoints):
```
181
```            # debugger()
```
182 179
```            if point in cp:
```
183 180
```                indices.append(i)
```
184 181

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

227
```        print "Link Weight - For all the leaves: %s" % self.Dv_B
```
228

229 224
```        # For other nodes in the block-cut tree
```
230 225
```        level += 1
```
231 226
```        while level <= max(len_B_cutpoints):
```
......
247 242

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

250
```            print "Link Weight - For level %s: %s" % (level, self.Dv_B)
```
251

252 245
```            level += 1
```
253 246

254 247
```    def generate_reverse_link_weight(self):
```
......
277 270
```                for cp in all_cutpoints:
```
278 271
```                    if self.get_link_weight(B_index, cp) != -1:
```
279 272
```                        size += self.num_vertices - self.get_link_weight(B_index, cp) - 1
```
280
```                        # size += self.num_vertices - self.get_link_weight(B_index, cp)
```
281 273

282 274
```                link_weight = size
```
283 275
```                self._verify_link_weight(B_index, v, link_weight)
```
......
288 280

289 281
```            if pair['type'] == 'vertex_component_pair':
```
290 282
```                size = 0
```
291
```                # size = 1
```
292 283
```                B_index = pair['value'][0]
```
293 284
```                v = pair['value'][1]
```
294 285
```                shared_comp_indices = self._components_sharing_cutpoint(B_cutpoints, v)
```
......
311 302

312 303
```        Otherwise, do nothing
```
313 304
```        """
```
314
```        print "VERIFICATION FOR (%s, %s)" % (B_index, v)
```
315 305
```        old_value = self.get_link_weight(B_index, v)
```
316
```        # -1 is unknown
```
317
```        if old_value != -1:
```
306

307
```        if old_value != -1: # -1 is unknown
```
318 308
```            if old_value != value:
```
319 309
```                print "BUGS FOUND in _verify_link_weight()"
```
320 310
```                sys.exit()
```
......
378 368
```    print [len(x) for x in bicomponents]
```
379 369

380 370
```def find_heuristic_bc(filepath):
```
381
```    filename = os.splitext(os.path.basename(filepath))[0]
```
371
```    filename = os.path.splitext(os.path.basename(filepath))[0]
```
382 372

383 373
```    pp = pprint.PrettyPrinter(indent=4)
```
384 374

......
390 380
```    else:
```
391 381
```        print "Graph is connected"
```
392 382

393

394 383
```    # Find biconnected components
```
395 384
```    analyse_biconnected_component(graph)
```
396 385

......
402 391
```    num_vertices = nx.number_of_nodes(graph)
```
403 392

404 393
```    lw = LinkWeight(graph, bicomponents, cutpoints)
```
405
```    print 'link weight: '
```
406
```    print(lw)
```
407 394

408 395
```    tm = TrafficMatrix(bicomponents, cutpoints, lw)
```
409
```    print 'traffic matrix:'
```
410
```    pp.pprint(tm.h)
```
411 396

412 397
```    bc = HeuristicBetweennessCentrality(subgraphs, bicomponents, cutpoints, num_vertices, lw, tm)
```
413 398
```    bc.write(file_suffix)
```
414 399
```    print bc
```
415 400

401
```def test_isomorphic_graphs(filepath1, filepath2):
```
402
```    graph1 = nx.read_weighted_edgelist(filepath1)
```
403
```    graph2 = nx.read_weighted_edgelist(filepath2)
```
404
```    print "Isomorphic = %s" % nx.is_isomorphic(graph1, graph2)
```
405

406

416 407
```if __name__ == '__main__':
```
417 408
```    utility.initialize()
```
418
```    input_dir = os.path.join(MAIN_CODE_DIR, 'input')
```
409
```    f1 = MAIN_CODE_DIR + '/input/9_vertices_green.edges'
```
410
```    f2 = MAIN_CODE_DIR + '/input/9_vertices_blue.edges'
```
411
```    test_isomorphic_graphs(f1, f2)
```
419 412

420 413
```    # filepath = MAIN_CODE_DIR + '/input/simple_house.edges'
```
421 414
```    # filepath = MAIN_CODE_DIR + '/input/simple2.edges'
```
422 415
```    # filepath = MAIN_CODE_DIR + '/input/simple.edges'
```
423 416
```    # filepath = MAIN_CODE_DIR + '/input/ninux_simplified.edges'
```
424 417
```    # filepath = MAIN_CODE_DIR + '/input/ninux_simplified_connected.edges'
```
425
```    filepath = MAIN_CODE_DIR + '/input/ninux_30_1.edges'
```
418
```    # filepath = MAIN_CODE_DIR + '/input/ninux_simplified_connected2.edges'
```
419
```    # filepath = MAIN_CODE_DIR + '/input/ninux_simplified_connected3.edges'
```
420
```    # filepath = MAIN_CODE_DIR + '/input/9_vertices_green.edges'
```
421
```    # filepath = MAIN_CODE_DIR + '/input/9_vertices_blue.edges'
```
422
```    # filepath = MAIN_CODE_DIR + '/input/simple_loop.edges'
```
423
```    # filepath = MAIN_CODE_DIR + '/input/straight_line.edges'
```
426 424
```    # filepath = MAIN_CODE_DIR + '/input/ninux_connected.edges'
```
427 425
```    # filepath = MAIN_CODE_DIR + '/input/ninux_unweighted.edges'
```
428 426
```    # filepath = MAIN_CODE_DIR + '/input/ninux_unweighted_simplified.edges'
```
......
430 428
```    # filepath = MAIN_CODE_DIR + '/input/simple3.edges'
```
431 429
```    # filepath = MAIN_CODE_DIR + '/input/simple4.edges'
```
432 430
```    # filepath = MAIN_CODE_DIR + '/input/simple5.edges'
```
431

432
```    filepath = MAIN_CODE_DIR + '/input/ninux.edges'
```
433 433
```    file_suffix = 'edge_list'
```
434 434

435
```    # # Weight betweenness centrality
```
436
```    # utility.weight_betweenness_centrality(filepath, file_suffix)
```
435
```    # Weight betweenness centrality
```
436
```    utility.weight_betweenness_centrality(filepath, file_suffix)
```
437 437

438
```    # # Brandess betweenness centrality
```
439
```    # utility.brandes_betweenness_centrality(filepath, file_suffix)
```
438
```    # Brandess betweenness centrality
```
439
```    utility.brandes_betweenness_centrality(filepath, file_suffix)
```
440 440

441
```    # # Heuristic BC
```
442
```    # find_heuristic_bc(filepath)
```
441
```    # Heuristic BC
```
442
```    find_heuristic_bc(filepath)
```
443 443

fiddle/heuristic-betweenness-centrality/compare.py
46 46
```        # write to file
```
47 47
```        # FORMAT: ip_address    networkx_centrality     boost_centrality
```
48 48
```        print "Compare"
```
49
```        vertices_with_mismatched_score = list()
```
49 50
```        with open(MAIN_CODE_DIR + '/output/score_summary_%s.txt' % t, 'w') as output:
```
50 51
```            for key, nx in sorted_nx_scores:
```
51
```                weight_basic = weight_basic_scores[key]
```
52
```                heuristic = heuristic_scores[key]
```
53
```                output.write('%s\t%s\t%s\t%s\n' % (key, nx, weight_basic, heuristic))
```
52
```                weight_basic = float(weight_basic_scores[key])
```
53
```                heuristic = float(heuristic_scores[key])
```
54
```                nx = float(nx)
```
55

56

57
```                if heuristic != weight_basic:
```
58
```                    vertices_with_mismatched_score.append(key)
```
59

60
```                output.write('%s\t%.4f\t%.4f\t%.4f\n' % (key, nx, weight_basic, heuristic))
```
61

62
```        print "Vertices with mismatched score between WBBC and HBC: %s" % len(vertices_with_mismatched_score)
```
63

64
```        print sorted(vertices_with_mismatched_score)
```
65

54 66

55 67

fiddle/heuristic-betweenness-centrality/input/8_vertices_black.edges
1
```43 99 1
```
2
```99 77 1
```
3
```77 120 1
```
4
```120 26 1
```
5
```26 72 1
```
6
```72 19 1
```
7
```19 55 1
```
8
```99 19 1
```
fiddle/heuristic-betweenness-centrality/input/8_vertices_blue.edges
1
```1 2 1
```
2
```2 3 1
```
3
```3 4 1
```
4
```4 5 1
```
5
```5 6 1
```
6
```6 7 1
```
7
```7 8 1
```
8
```2 7 1
```
fiddle/heuristic-betweenness-centrality/input/ninux_simplified.edges
1
```1 9 1.256
```
2
```0 43 1.0
```
3
```4 16 1.191
```
4
```6 7 1.0
```
5
```19 93 1.0
```
6
```5 52 1.0
```
7
```4 43 1.1695
```
8
```7 75 1.0
```
9
```1 64 1.133
```
10
```1 8 1.1805
```
11
```1 82 1.0
```
12
```1 1 1.0
```
13
```1 21 1.5335
```
14
```1 104 2.107
```
15
```1 41 1.0
```
16
```1 112 1.593
```
17
```1 117 1.0
```
18
```1 59 1.0
```
19
```1 124 1.7425
```
20
```1 62 1.946
```
21
```2 122 1.0
```
22
```3 26 1.063
```
23
```3 90 1.118
```
24
```4 4 1.0
```
25
```4 44 1.058
```
26
```4 52 1.113
```
27
```4 53 1.148
```
28
```4 90 1.0
```
29
```4 10 1.118
```
30
```6 6 1.0
```
31
```6 103 1.294
```
32
```6 46 1.0
```
33
```6 40 1.0
```
34
```6 114 1.045
```
35
```6 121 1.032
```
36
```7 111 1.0
```
37
```7 63 1.0
```
38
```8 22 1.4655
```
39
```9 102 1.128
```
40
```10 17 1.274
```
41
```10 70 1.594
```
42
```11 39 1.1995
```
43
```12 113 1.0
```
44
```13 43 1.0
```
45
```14 105 1.0
```
46
```14 118 1.0
```
47
```15 35 1.22
```
48
```15 86 1.196
```
49
```16 39 1.023
```
50
```16 78 1.378
```
1
```17 45 1.071
```
2
```18 113 1.027
```
3
```18 58 1.042
```
4
```19 79 1.133
```
5
```19 48 1.0
```
6
```19 84 1.0
```
7
```19 94 1.027
```
8
```19 55 1.191
```
9
```19 116 1.118
```
10
```21 22 1.1575
```
11
```22 124 1.3625
```
12
```23 72 1.085
```
13
```24 90 1.0
```
14
```25 39 1.164
```
15
```26 70 1.133
```
16
```26 72 1.113
```
17
```26 89 1.058
```
18
```27 44 1.0
```
19
```28 87 1.0
```
20
```29 49 1.0
```
21
```30 118 1.0
```
22
```31 38 1.143
```
23
```31 47 1.0
```
24
```32 45 1.386
```
25
```32 95 1.0
```
26
```33 109 1.191
```
27
```34 45 1.0
```
28
```34 86 1.0
```
29
```35 122 1.0
```
30
```35 69 1.0
```
31
```36 43 1.012
```
32
```37 97 1.118
```
33
```37 66 1.0
```
34
```37 68 1.191
```
35
```37 107 1.335
```
36
```37 54 1.066
```
37
```38 48 1.335
```
38
```38 77 1.231
```
39
```39 112 1.004
```
40
```39 103 1.5
```
41
```39 89 2.254
```
42
```39 87 1.3455
```
43
```42 45 1.153
```
44
```43 102 1.328
```
45
```43 70 1.0
```
46
```43 50 1.0
```
47
```44 74 1.0
```
48
```44 71 1.032
```
49
```44 108 1.148
```
50
```44 120 1.158
```
51
```44 92 1.0
```
52
```45 115 1.036
```
53
```46 106 1.0
```
54
```48 120 1.0
```
55
```49 113 1.027
```
56
```51 89 1.0
```
57
```52 109 1.677
```
58
```55 122 1.027
```
59
```56 109 1.042
```
60
```57 114 3.399
```
61
```57 72 1.269
```
62
```60 109 1.0
```
63
```60 86 1.0
```
64
```65 97 1.335
```
65
```67 98 1.042
```
66
```71 87 1.0
```
67
```72 84 1.269
```
68
```73 84 1.0
```
69
```76 97 1.118
```
70
```77 99 1.226
```
71
```79 99 1.0
```
72
```80 97 2.788
```
73
```81 87 1.0
```
74
```83 92 1.0
```
75
```85 97 1.0
```
76
```86 100 1.0
```
77
```86 97 1.143
```
78
```91 92 1.042
```
79
```92 96 1.042
```
80
```93 113 1.027
```
81
```94 99 1.066
```
82
```97 98 1.783
```
83
```97 99 1.301
```
84
```97 109 1.0
```
85
```98 102 1.0
```
86
```101 112 1.004
```
87
```110 116 1.0
```
88
```112 125 1.004
```
89
```119 122 1.0
```
90
```120 120 1.0
```
91
```122 123 1.0
```
fiddle/heuristic-betweenness-centrality/input/ninux_simplified_connected.edges
1
```1 9 1.256
```
2
```0 43 1.0
```
3
```4 16 1.191
```
4
```6 7 1.0
```
5
```19 93 1.0
```
6
```5 52 1.0
```
7
```4 43 1.1695
```
8
```7 75 1.0
```
9
```1 64 1.133
```
10
```1 8 1.1805
```
11
```1 82 1.0
```
12
```1 1 1.0
```
13
```1 21 1.5335
```
14
```1 104 2.107
```
15
```1 41 1.0
```
16
```1 112 1.593
```
17
```1 117 1.0
```
18
```1 59 1.0
```
19
```1 124 1.7425
```
20
```1 62 1.946
```
21
```2 122 1.0
```
22
```3 26 1.063
```
23
```3 90 1.118
```
24
```4 4 1.0
```
25
```4 44 1.058
```
26
```4 52 1.113
```
27
```4 53 1.148
```
28
```4 90 1.0
```
29
```4 10 1.118
```
30
```6 6 1.0
```
31
```6 103 1.294
```
32
```6 46 1.0
```
33
```6 40 1.0
```
34
```6 114 1.045
```
35
```6 121 1.032
```
36
```7 111 1.0
```
37
```7 63 1.0
```
38
```8 22 1.4655
```
39
```9 102 1.128
```
40
```10 17 1.274
```
41
```10 70 1.594
```
42
```11 39 1.1995
```
43
```12 113 1.0
```
44
```13 43 1.0
```
45
```14 105 1.0
```
46
```14 118 1.0
```
47
```15 35 1.22
```
48
```15 86 1.196
```
49
```16 39 1.023
```
50
```16 78 1.378
```
51
```1 3 1
```
52
```1 2 1
```
53
```1 4 1
```
54
```1 7 1
```
55
```4 15 1
```
56
```4 16 1
```
57
```4 14 1
```
58
```4 12 1
```
59
```4 11 1
```
60
```4 10 1
```
61
```4 9 1
```
62
```4 19 1
```
1
```19 48 1.0
```
2
```19 55 1.191
```
3
```43 26 1.0
```
4
```26 72 1.113
```
5
```48 77 1.231
```
6
```26 120 1.158
```
7
```48 120 1.0
```
8
```72 19 1.269
```
9
```77 99 1.226
```
10
```19 99 1.066
```
11
```43 99 1.301
```
fiddle/heuristic-betweenness-centrality/input/ninux_unweighted_simplified.edges
1
```1   9   1
```
2
```0   43  1
```
3
```4   16  1
```
4
```6   7   1
```
5
```5   52  1
```
6
```4   43  1
```
7
```7   75  1
```
8
```1   8   1
```
9
```1   82  1
```
10
```1   1   1
```
11
```1   21  1
```
12
```1   104 1
```
13
```1   59  1
```
14
```1   124 1
```
15
```1   62  1
```
16
```4   4   1
```
17
```4   44  1
```
18
```4   52  1
```
19
```4   90  1
```
20
```4   10  1
```
21
```6   6   1
```
1
```1 2 1
```
2
```1 3 1
```
3
```2 4 1
```
4
```2 5 1
```
5
```3 6 1
```
6
```3 7 1
```
7
```4 8 1
```
8
```5 8 1
```
9
```5 7 1
```
10
```5 9 1
```
11
```6 8 1
```
fiddle/heuristic-betweenness-centrality/input/ninux_unweighted_simplified_connected.edges
1
```1   9   1
```
2
```0   43  1
```
3
```4   16  1
```
4
```6   7   1
```
5
```5   52  1
```
6
```4   43  1
```
7
```7   75  1
```
8
```1   8   1
```
9
```1   82  1
```
10
```1   1   1
```
11
```1   21  1
```
12
```1   104 1
```
13
```1   59  1
```
14
```1   124 1
```
15
```1   62  1
```
16
```4   4   1
```
17
```4   44  1
```
18
```4   52  1
```
19
```4   90  1
```
20
```4   10  1
```
21
```6   6   1
```
22
```1   4   1
```
23
```1   7   1
```
1
```17  45  1
```
2
```19  79  1
```
3
```19  48  1
```
4
```19  84  1
```
5
```19  94  1
```
6
```19  55  1
```
7
```26  70  1
```
8
```26  72  1
```
9
```26  89  1
```
10
```31  38  1
```
11
```32  45  1
```
12
```34  45  1
```
13
```34  86  1
```
14
```38  48  1
```
15
```38  77  1
```
16
```39  89  1
```
17
```39  87  1
```
18
```43  102 1
```
19
```43  70  1
```
20
```44  71  1
```
21
```44  120 1
```
22
```48  120 1
```
23
```60  109 1
```
24
```60  86  1
```
25
```71  87  1
```
26
```72  84  1
```
27
```73  84  1
```
28
```76  97  1
```
29
```77  99  1
```
30
```79  99  1
```
31
```86  100 1
```
32
```86  97  1
```
33
```94  99  1
```
34
```97  98  1
```
35
```97  99  1
```
36
```97  109 1
```
37
```98  102 1
```
38
```120 120 1
```
fiddle/heuristic-betweenness-centrality/input/ninux_wrong_result.txt
1
```19 79 1.133
```
2
```19 48 1.0
```
3
```19 84 1.0
```
4
```19 94 1.027
```
5
```19 55 1.191
```
6
```43 26 1.0
```
7
```26 72 1.113
```
8
```26 89 1.058
```
9
```38 48 1.335
```
10
```38 77 1.231
```
11
```39 89 2.254
```
12
```39 87 1.3455
```
13
```43 102 1
```
14
```102 98 1
```
15
```44 71 1.032
```
16
```44 120 1.158
```
17
```48 120 1.0
```
18
```71 87 1.0
```
19
```72 84 1.269
```
20
```77 99 1.226
```
21
```79 99 1.0
```
22
```94 99 1.066
```
23
```97 99 1.301
```
24
```97 102 1
```
25
```120 120 1.0
```
26

27
```21 vertices - 18 wrong vertices ['102', '120', '19', '26', '38', '39', '43', '44', '48', '71', '72', '79', '84', '87', '89', '94', '97', '99']
```
28

29

30
```19 79 1.133
```
31
```19 48 1.0
```
32
```19 84 1.0
```
33
```19 94 1.027
```
34
```19 55 1.191
```
35
```43 26 1.0
```
36
```26 72 1.113
```
37
```26 89 1.058
```
38
```38 48 1.335
```
39
```38 77 1.231
```
40
```39 89 2.254
```
41
```39 87 1.3455
```
42
```43 102 1
```
43
```44 71 1.032
```
44
```44 120 1.158
```
45
```48 120 1.0
```
46
```71 87 1.0
```
47
```72 84 1.269
```
48
```77 99 1.226
```
49
```79 99 1.0
```
50
```94 99 1.066
```
51
```97 99 1.301
```
52
```97 102 1
```
53
```120 120 1.0
```
54

55
```['120', '19', '26', '38', '39', '43', '44', '48', '71', '72', '77', '79', '84', '87', '89', '94', '97', '99']
```
56

57
```19 79 1.133
```
58
```19 48 1.0
```
59
```19 84 1.0
```
60
```19 94 1.027
```
61
```19 55 1.191
```
62
```43 26 1.0
```
63
```26 72 1.113
```
64
```26 89 1.058
```
65
```38 48 1.335
```
66
```38 77 1.231
```
67
```87 89 2.254
```
68
```43 102 1
```
69
```71 120 1.158
```
70
```48 120 1.0
```
71
```71 87 1.0
```
72
```72 84 1.269
```
73
```77 99 1.226
```
74
```79 99 1.0
```
75
```94 99 1.066
```
76
```97 99 1.301
```
77
```97 102 1
```
78
```120 120 1.0
```
79

80
```['102', '120', '19', '26', '38', '43', '48', '77', '79', '84', '87', '89', '94', '97', '99']
```
81

82
```19 79 1.133
```
83
```19 48 1.0
```
84
```19 84 1.0
```
85
```19 94 1.027
```
86
```19 55 1.191
```
87
```43 26 1.0
```
88
```26 72 1.113
```
89
```26 89 1.058
```
90
```38 48 1.335
```
91
```38 77 1.231
```
92
```87 89 2.254
```
93
```43 102 1
```
94
```87 120 1.158
```
95
```48 120 1.0
```
96
```72 84 1.269
```
97
```77 99 1.226
```
98
```79 99 1.0
```
99
```94 99 1.066
```
100
```97 99 1.301
```
101
```97 102 1
```
102

103
```['102', '120', '19', '26', '38', '43', '48', '77', '79', '84', '87', '89', '94', '97', '99']
```
104

105

106
```19 79 1.133
```
107
```19 48 1.0
```
108
```19 84 1.0
```
109
```19 94 1.027
```
110
```19 55 1.191
```
111
```43 26 1.0
```
112
```26 72 1.113
```
113
```26 89 1.058
```
114
```38 48 1.335
```
115
```38 77 1.231
```
116
```43 97 1
```
117
```89 120 1.158
```
118
```48 120 1.0
```
119
```72 84 1.269
```
120
```77 99 1.226
```
121
```79 99 1.0
```
122
```94 99 1.066
```
123
```97 99 1.301
```
124

125
```['19', '26', '38', '43', '48', '77', '79', '84', '89', '94', '97', '99']
```
126

127

128
```19 79 1.133
```
129
```19 48 1.0
```
130
```19 84 1.0
```
131
```19 94 1.027
```
132
```19 55 1.191
```
133
```43 26 1.0
```
134
```26 72 1.113
```
135
```26 89 1.058
```
136
```48 77 1.231
```
137
```43 97 1
```
138
```89 120 1.158
```
139
```48 120 1.0
```
140
```72 84 1.269
```
141
```77 99 1.226
```
142
```79 99 1.0
```
143
```94 99 1.066
```
144
```97 99 1.301
```
145

146
```['120', '19', '26', '43', '48', '77', '79', '84', '89', '94', '97', '99']
```
147

148
```19 79 1.133
```
149
```19 48 1.0
```
150
```19 94 1.027
```
151
```19 55 1.191
```
152
```43 26 1.0
```
153
```26 72 1.113
```
154
```26 89 1.058
```
155
```48 77 1.231
```
156
```43 97 1
```
157
```89 120 1.158
```
158
```48 120 1.0
```
159
```72 19 1.269
```
160
```77 99 1.226
```
161
```79 99 1.0
```
162
```94 99 1.066
```
163
```97 99 1.301
```
164

165
```total = 13 vertices ['120', '19', '26', '43', '48', '72', '77', '79', '89', '94', '97', '99']
```
166

167
```19 79 1.133
```
168
```19 48 1.0
```
169
```19 94 1.027
```
170
```19 55 1.191
```
171
```43 26 1.0
```
172
```26 72 1.113
```
173
```48 77 1.231
```
174
```43 97 1
```
175
```26 120 1.158
```
176
```48 120 1.0
```
177
```72 19 1.269
```
178
```77 99 1.226
```
179
```79 99 1.0
```
180
```94 99 1.066
```
181
```97 99 1.301
```
182

183
```total = 12 vertices ['120', '19', '26', '43', '48', '72', '79', '94', '97', '99']
```
184

185
```19 79 1.133
```
186
```19 48 1.0
```
187
```19 94 1.027
```
188
```19 55 1.191
```
189
```43 26 1.0
```
190
```26 72 1.113
```
191
```48 77 1.231
```
192
```26 120 1.158
```
193
```48 120 1.0
```
194
```72 19 1.269
```
195
```77 99 1.226
```
196
```79 99 1.0
```
197
```94 99 1.066
```
198
```43 99 1.301
```
199

200
```11 vertices ['120', '19', '26', '43', '48', '72', '77', '79', '94', '99']
```
201

202
```19 79 1.133
```
203
```19 48 1.0
```
204
```19 55 1.191
```
205
```43 26 1.0
```
206
```26 72 1.113
```
207
```48 77 1.231
```
208
```26 120 1.158
```
209
```48 120 1.0
```
210
```72 19 1.269
```
211
```77 99 1.226
```
212
```79 99 1.0
```
213
```19 99 1.066
```
214
```43 99 1.301
```
215

216
```['120', '19', '26', '43', '48', '72', '77', '99']
```
217

218
```19 48 1.0
```
219
```19 55 1.191
```
220
```43 26 1.0
```
221
```26 72 1.113
```
222
```48 77 1.231
```
223
```26 120 1.158
```
224
```48 120 1.0
```
225
```72 19 1.269
```
226
```77 99 1.226
```
227
```19 99 1.066
```
228
```43 99 1.301
```
229

230
```['120', '19', '26', '43', '48', '72', '77', '99']
```
231

232

233
```19 48 1.0
```
234
```19 55 1.191
```
235
```43 26 1.0
```
236
```26 72 1.113
```
237
```48 77 1.231
```
238
```26 120 1.158
```
239
```48 120 1.0
```
240
```72 19 1.269
```
241
```77 99 1.226
```
242
```19 99 1.066
```
243
```43 99 1.301
```
244

245
```Vertices with mismatched score between WBBC and HBC: 8
```
246
```['120', '19', '26', '43', '48', '72', '77', '99']
```
247

248

249
```43 99 1.301
```
250
```43 26 1.0
```
251
```77 99 1.226
```
252
```19 99 1.066
```
253
```26 120 1.158
```
254
```26 72 1.113
```
255
```48 77 1.231
```
256
```72 19 1.269
```
257
```19 48 1.0
```
258
```19 55 1.191
```
259
```48 120 1.0
```
260

261
```Vertices with mismatched score between WBBC and HBC: 7
```
262
```['19', '26', '43', '48', '72', '77', '99']
```
263

264
```==> I don't understand why just by simply shuffling the order of edges, we would have 2 different results.
```
fiddle/heuristic-betweenness-centrality/input/simple_loop.edges
1
```1 2 1
```
2
```2 3 1
```
3
```3 4 1
```
4
```4 1 1
```
5
```1 5 1
```
6
```5 6 1
```
7
```6 7 1
```
8
```7 3 1
```
9
```1 8 1
```
10
```8 9 1
```
11
```9 10 1
```
12
```10 11 1
```
13
```11 12 1
```
14
```12 3 1
```
15
```10 14 1
```
16
```14 15 1
```
17
```15 6 1
```
18
```1 16 1
```
fiddle/heuristic-betweenness-centrality/input/straight_line.edges
1
```1 2 1
```
2
```2 3 1
```
3
```3 4 1
```
4
```4 5 1
```
5
```5 6 1
```
fiddle/heuristic-betweenness-centrality/script.sh
1 1
```export MAIN_CODE_DIR="/home/quynh/Thesis/quynhnguyen-ms/fiddle/heuristic-betweenness-centrality"
```
2
```# python visualize.py
```
2 3
```python centrality_biconnected.py
```
3 4
```python compare.py
```
4 5

fiddle/heuristic-betweenness-centrality/visualize.py
1
```import os
```
2
```import networkx as nx
```
3
```import utility
```
4

5
```MAIN_CODE_DIR = os.environ.get('MAIN_CODE_DIR', '')
```
6

7
```def visualize_all_inputs(input_dir):
```
8
```    files = list()
```
9
```    # Find all the inputs with .edges
```
10
```    for file in os.listdir(input_dir):
```
11
```        if file.endswith('.edges'):
```
12
```            files.append(file)
```
13

14
```    output_dir = os.path.join(MAIN_CODE_DIR, 'output/visualization')
```
15
```    output_suffix = ".png"
```
16

17
```    for file in files:
```
18
```        filepath = os.path.join(input_dir, file)
```
19
```        graph = nx.read_weighted_edgelist(filepath)
```
20

21
```        filename = os.path.splitext(os.path.basename(file))[0]
```
22
```        output_path = os.path.join(output_dir, filename + output_suffix)
```
23

24
```        utility.plot_graph(output_path, graph, title=filepath)
```
25

26

27
```if __name__ == '__main__':
```
28
```    utility.initialize()
```
29
```    input_dir = os.path.join(MAIN_CODE_DIR, 'input')
```
30
```    visualize_all_inputs(input_dir)
```

Also available in: Unified diff