## Revision 739fe075

View differences:

fiddle/heuristic-betweenness-centrality/betweenness_centrality.py
135 135
else:
136 136
betweenness = _accumulate_weight_basic(betweenness, S, P, sigma, s)
137 137

138
print 'betweenness = %s' % betweenness
138
print '@@@ betweenness = %s' % betweenness
139 139
if rescale:
140 140
betweenness = _rescale(betweenness, len(G),
141 141
normalized=normalized,
......
259 259
while S:
260 260
w = S.pop()
261 261
if w != s:
262
delta[w] += 1
262
delta[w] += 1 # this is the h, when w != s, then h(s, w) = 1
263 263
coeff = delta[w] / sigma[w]
264 264
for v in P[w]:
265 265
delta[v] += sigma[v] * coeff
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 sys
5 6
import pprint
6 7
import networkx as nx
7 8
import betweenness_centrality as centrality
......
169 170
self.cutpoints = cutpoints
170 171

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

175 175
self.reverse_Dv_B = [dict() for i in range(self.num_components)] # reverse link weight
......
247 247

248 248
self.Dv_B[i][point] = weight
249 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 250
print "Link Weight - For level %s: %s" % (level, self.Dv_B)
256 251

257 252
level += 1
......
275 270
if pair['type'] == 'component_vertex_pair':
276 271
B_index = pair['value'][0]
277 272
v = pair['value'][1]
278
print'  CV: %s %s' % (B_index, v)
279 273
size = len(self.bicomponents[B_index]) - 1;
280 274
all_cutpoints = self.bicomponents[B_index].intersection(self.cutpoints)
281 275
all_cutpoints.remove(v)
......
283 277
for cp in all_cutpoints:
284 278
285 279
size += self.num_vertices - self.get_link_weight(B_index, cp) - 1
280
# size += self.num_vertices - self.get_link_weight(B_index, cp)
286 281

287
282
283
284
288 285

289 286
# update Q
290 287
Q = self._find_unknown_weight_wrt_cutpoint(v, Q)
291 288

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

......
302 299
if self.get_link_weight(i, v) != - 1:
303 300
304 301

305
self.set_link_weight(B_index, v, self.num_vertices - 1 - size)
302
link_weight = self.num_vertices - 1 - size
303
304
306 305

307 306
# update Q
308 307
Q = self._find_unknown_weight_wrt_component(B_index, Q)
309 308

310
print self.Dv_B
309
310
""" If the old_value exist in self.Dv_B, then it must be equal to new value
311

312
Otherwise, do nothing
313
"""
314
print "VERIFICATION FOR (%s, %s)" % (B_index, v)
315
316
# -1 is unknown
317
if old_value != -1:
318
if old_value != value:
319
320
sys.exit()
321

311 322

312 323
def _inititalize_component_tree_weight(self):
313 324
Q = []
......
338 349
'value': (uncomputed_component_index.pop(), cutpoint)
339 350
}
340 351
Q.append(pair)
341
print "Append WRT Cutpoint %s" % pair
342 352
return Q
343 353

344 354
def _find_unknown_weight_wrt_component(self, comp_index, Q):
......
357 367
'value': (comp_index, cp)
358 368
}
359 369
Q.append(pair)
360
print "Append WRT Component %s" % pair
361 370
return Q
362 371

363 372
def __str__(self):
......
369 378
print [len(x) for x in bicomponents]
370 379

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

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

374 385
375 386

387
if not nx.is_connected(graph):
388
print "Graph is not connected"
389
# sys.exit()
390
else:
391
print "Graph is connected"
392

393

376 394
# Find biconnected components
377 395
analyse_biconnected_component(graph)
378 396

......
393 411

394 412
bc = HeuristicBetweennessCentrality(subgraphs, bicomponents, cutpoints, num_vertices, lw, tm)
395 413
bc.write(file_suffix)
396
# print bc
414
print bc
397 415

398 416
if __name__ == '__main__':
417
utility.initialize()
418
input_dir = os.path.join(MAIN_CODE_DIR, 'input')
419

399 420
# filepath = MAIN_CODE_DIR + '/input/simple_house.edges'
400 421
# filepath = MAIN_CODE_DIR + '/input/simple2.edges'
401 422
# filepath = MAIN_CODE_DIR + '/input/simple.edges'
423
# filepath = MAIN_CODE_DIR + '/input/ninux_simplified.edges'
424
# filepath = MAIN_CODE_DIR + '/input/ninux_simplified_connected.edges'
402 425
filepath = MAIN_CODE_DIR + '/input/ninux_30_1.edges'
426
# filepath = MAIN_CODE_DIR + '/input/ninux_connected.edges'
427
# filepath = MAIN_CODE_DIR + '/input/ninux_unweighted.edges'
428
# filepath = MAIN_CODE_DIR + '/input/ninux_unweighted_simplified.edges'
429
# filepath = MAIN_CODE_DIR + '/input/ninux_unweighted_simplified_connected.edges'
403 430
# filepath = MAIN_CODE_DIR + '/input/simple3.edges'
404 431
# filepath = MAIN_CODE_DIR + '/input/simple4.edges'
432
# filepath = MAIN_CODE_DIR + '/input/simple5.edges'
405 433
file_suffix = 'edge_list'
406 434

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

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

410
# Brandess betweenness centrality
411
utility.brandes_betweenness_centrality(filepath, file_suffix)
441
# # Heuristic BC
442
# find_heuristic_bc(filepath)
412 443

413
# Heuristic BC
414
find_heuristic_bc(filepath)
fiddle/heuristic-betweenness-centrality/compare.py
29 29

30 30

31 31
if __name__ == '__main__':
32
filepath_prefixes = ['/output/networkx_', '/output/heuristic_']
32
filepath_prefixes = ['/output/networkx_', '/output/weight_basic_', '/output/heuristic_']
33 33
types = ['edge_list']
34 34
extension = '.csv'
35 35

......
38 38
filepaths = [MAIN_CODE_DIR + p + t + extension for p in filepath_prefixes]
39 39

40 40
41
41
42
42 43

43 44
sorted_nx_scores = sort_value_of_dictionary(nx_scores)
44 45

......
47 48
print "Compare"
48 49
with open(MAIN_CODE_DIR + '/output/score_summary_%s.txt' % t, 'w') as output:
49 50
for key, nx in sorted_nx_scores:
50
boost = boost_scores[key]
51
output.write('%s\t%s\t%s\n' % (key, nx, boost))
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 54

53 55

fiddle/heuristic-betweenness-centrality/gnuplot_script
1 1
set term postscript enhanced color
2 2
set terminal postscript eps
3
set output "./output/centrality_for_edge_list.ps"
3
set output "./output/centrality_for_edge_list.pdf"
4 4
set title "Centrality for edge_list"
5 5
set xlabel "Router (each integer corresponds to one router)"
6 6
set ylabel "Betweenness Centrality"
7 7
plot  "./output/score_summary_edge_list.txt" using 2 title 'networkx' pointtype 7 pointsize 0.7, \
8 8
"./output/score_summary_edge_list.txt" using 3 title 'weight basic' pointtype 5 pointsize 1,\
9
"./output/score_summary_edge_list.txt" using 4 title 'networkx - endpoints' pointtype 8 pointsize 0.5,\
9
"./output/score_summary_edge_list.txt" using 4 title 'heuristics' pointtype 8 pointsize 0.5,\
fiddle/heuristic-betweenness-centrality/input/ninux.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
16 57 1.0745
52
16 118 1.128
53
16 20 1.123
54
16 88 1.089
55
16 61 1.0
56
17 43 1.0
57
17 45 1.071
58
18 113 1.027
59
18 58 1.042
60
19 79 1.133
61
19 48 1.0
62
19 84 1.0
63
19 94 1.027
64
19 55 1.191
65
19 116 1.118
66
21 22 1.1575
67
22 124 1.3625
68
23 72 1.085
69
24 90 1.0
70
25 39 1.164
71
26 70 1.133
72
26 72 1.113
73
26 89 1.058
74
27 44 1.0
75
28 87 1.0
76
29 49 1.0
77
30 118 1.0
78
31 38 1.143
79
31 47 1.0
80
32 45 1.386
81
32 95 1.0
82
33 109 1.191
83
34 45 1.0
84
34 86 1.0
85
35 122 1.0
86
35 69 1.0
87
36 43 1.012
88
37 97 1.118
89
37 66 1.0
90
37 68 1.191
91
37 107 1.335
92
37 54 1.066
93
38 48 1.335
94
38 77 1.231
95
39 112 1.004
96
39 103 1.5
97
39 89 2.254
98
39 87 1.3455
99
42 45 1.153
100
43 102 1.328
101
43 70 1.0
102
43 50 1.0
103
44 74 1.0
104
44 71 1.032
105
44 108 1.148
106
44 120 1.158
107
44 92 1.0
108
45 115 1.036
109
46 106 1.0
110
48 120 1.0
111
49 113 1.027
112
51 89 1.0
113
52 109 1.677
114
55 122 1.027
115
56 109 1.042
116
57 114 3.399
117
57 72 1.269
118
60 109 1.0
119
60 86 1.0
120
65 97 1.335
121
67 98 1.042
122
71 87 1.0
123
72 84 1.269
124
73 84 1.0
125
76 97 1.118
126
77 99 1.226
127
79 99 1.0
128
80 97 2.788
129
81 87 1.0
130
83 92 1.0
131
85 97 1.0
132
86 100 1.0
133
86 97 1.143
134
91 92 1.042
135
92 96 1.042
136
93 113 1.027
137
94 99 1.066
138
97 98 1.783
139
97 99 1.301
140
97 109 1.0
141
98 102 1.0
142
101 112 1.004
143
110 116 1.0
144
112 125 1.004
145
119 122 1.0
146
120 120 1.0
147
122 123 1.0
fiddle/heuristic-betweenness-centrality/input/ninux_30_1.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
16 57 1.0745
52
16 118 1.128
53
16 20 1.123
54
16 88 1.089
55
16 61 1.0
56
17 43 1.0
57
17 45 1.071
58
18 113 1.027
59
18 58 1.042
60
19 79 1.133
61
19 48 1.0
62
19 84 1.0
63
19 94 1.027
64
19 55 1.191
65
19 116 1.118
66
21 22 1.1575
67
22 124 1.3625
68
23 72 1.085
69
24 90 1.0
70
25 39 1.164
71
26 70 1.133
72
26 72 1.113
73
26 89 1.058
74
27 44 1.0
75
28 87 1.0
76
29 49 1.0
77
30 118 1.0
78
31 38 1.143
79
31 47 1.0
80
32 45 1.386
81
32 95 1.0
82
33 109 1.191
83
34 45 1.0
84
34 86 1.0
85
35 122 1.0
86
35 69 1.0
87
36 43 1.012
88
37 97 1.118
89
37 66 1.0
90
37 68 1.191
91
37 107 1.335
92
37 54 1.066
93
38 48 1.335
94
38 77 1.231
95
39 112 1.004
96
39 103 1.5
97
39 89 2.254
98
39 87 1.3455
99
42 45 1.153
100
43 102 1.328
101
43 70 1.0
102
43 50 1.0
103
44 74 1.0
104
44 71 1.032
105
44 108 1.148
106
44 120 1.158
107
44 92 1.0
108
45 115 1.036
109
46 106 1.0
110
48 120 1.0
111
49 113 1.027
112
51 89 1.0
113
52 109 1.677
114
55 122 1.027
115
56 109 1.042
116
57 114 3.399
117
57 72 1.269
118
60 109 1.0
119
60 86 1.0
120
65 97 1.335
121
67 98 1.042
122
71 87 1.0
123
72 84 1.269
124
73 84 1.0
125
76 97 1.118
126
77 99 1.226
127
79 99 1.0
128
80 97 2.788
129
81 87 1.0
130
83 92 1.0
131
85 97 1.0
132
86 100 1.0
133
86 97 1.143
134
91 92 1.042
135
92 96 1.042
136
93 113 1.027
137
94 99 1.066
138
97 98 1.783
139
97 99 1.301
140
97 109 1.0
141
98 102 1.0
142
101 112 1.004
143
110 116 1.0
144
112 125 1.004
145
119 122 1.0
146
120 120 1.0
147
122 123 1.0
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
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
fiddle/heuristic-betweenness-centrality/input/ninux_unweighted.edges
1
1   9   1
2
0   43  1
3
4   16  1
4
6   7   1
5
19  93  1
6
5   52  1
7
4   43  1
8
7   75  1
9
1   64  1
10
1   8   1
11
1   82  1
12
1   1   1
13
1   21  1
14
1   104 1
15
1   41  1
16
1   112 1
17
1   117 1
18
1   59  1
19
1   124 1
20
1   62  1
21
2   122 1
22
3   26  1
23
3   90  1
24
4   4   1
25
4   44  1
26
4   52  1
27
4   53  1
28
4   90  1
29
4   10  1
30
6   6   1
31
6   103 1
32
6   46  1
33
6   40  1
34
6   114 1
35
6   121 1
36
7   111 1
37
7   63  1
38
8   22  1
39
9   102 1
40
10  17  1
41
10  70  1
42
11  39  1
43
12  113 1
44
13  43  1
45
14  105 1
46
14  118 1
47
15  35  1
48
15  86  1
49
16  39  1
50
16  78  1
51
16  57  1
52
16  118 1
53
16  20  1
54
16  88  1
55
16  61  1
56
17  43  1
57
17  45  1
58
18  113 1
59
18  58  1
60
19  79  1
61
19  48  1
62
19  84  1
63
19  94  1
64
19  55  1
65
19  116 1
66
21  22  1
67
22  124 1
68
23  72  1
69
24  90  1
70
25  39  1
71
26  70  1
72
26  72  1
73
26  89  1
74
27  44  1
75
28  87  1
76
29  49  1
77
30  118 1
78
31  38  1
79
31  47  1
80
32  45  1
81
32  95  1
82
33  109 1
83
34  45  1
84
34  86  1
85
35  122 1
86
35  69  1
87
36  43  1
88
37  97  1
89
37  66  1
90
37  68  1
91
37  107 1
92
37  54  1
93
38  48  1
94
38  77  1
95
39  112 1
96
39  103 1
97
39  89  1
98
39  87  1
99
42  45  1
100
43  102 1
101
43  70  1
102
43  50  1
103
44  74  1
104
44  71  1
105
44  108 1
106
44  120 1
107
44  92  1
108
45  115 1
109
46  106 1
110
48  120 1
111
49  113 1
112
51  89  1
113
52  109 1
114
55  122 1
115
56  109 1
116
57  114 1
117
57  72  1
118
60  109 1
119
60  86  1
120
65  97  1
121
67  98  1
122
71  87  1
123
72  84  1
124
73  84  1
125
76  97  1
126
77  99  1
127
79  99  1
128
80  97  1
129
81  87  1
130
83  92  1
131
85  97  1
132
86  100 1
133
86  97  1
134
91  92  1
135
92  96  1
136
93  113 1
137
94  99  1
138
97  98  1
139
97  99  1
140
97  109 1
141
98  102 1
142
101 112 1
143
110 116 1
144
112 125 1
145
119 122 1
146
120 120 1
147
122 123 1
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
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
fiddle/heuristic-betweenness-centrality/input/simple5.edges
1
1 2 1
2
2 3 1
3
3 4 1
4
3 5 1
5
4 5 1
fiddle/heuristic-betweenness-centrality/utility.py
1 1
import os
2 2
import networkx as nx
3
import matplotlib.pyplot as plt
3 4
import betweenness_centrality as centrality
4 5

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

8
def initialize():
9
"""
10
Create all necessary folder
11
"""
12
output_dir = os.path.join(MAIN_CODE_DIR, 'output')
13
if not os.path.isdir(output_dir):
14
os.makedirs(output_dir)
15

16
visualization_dir = os.path.join(output_dir, 'visualization')
17
if not os.path.isdir(visualization_dir):
18
os.makedirs(visualization_dir)
19

7 20
def weight_betweenness_centrality(filepath, file_suffix):
8 21
9 22

......
32 45

33 46
with open(MAIN_CODE_DIR + filepath, 'w') as output:
34 47
for node, bc in score.iteritems():
35
output.write('%s, %s\n' % (node, bc))
48
output.write('%s, %s\n' % (node, bc))
49

50

51
def plot_graph(output_filepath, graph, title=""):
52
plt.figure(1, figsize=(15, 10))
53
plt.title(title)
54
pos=nx.spring_layout(graph)
55
colors=range(20)
56
nx.draw(graph, pos, node_size=300, with_label=True)
57
nx.draw_networkx_labels(graph,pos,font_size=10,font_family='sans-serif')
58
plt.savefig(output_filepath)
59
plt.close()
60
# plt.show()

Also available in: Unified diff