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