## Revision 3673c3e8

View differences:

fiddle/heuristic-betweenness-centrality/betweenness_centrality.py
211 211
```        print "ERROR in get_value_from_traffic_matrix"
```
212 212
```        return -1
```
213 213

214
```def _accumulate_basic(betweenness, S, P, sigma, s, traffic_matrix, nodes):
```
215
```    delta = dict.fromkeys(S, 0)
```
216
```    while S:
```
217
```        w = S.pop()
```
218
```        coeff = (1.0 + delta[w]) / sigma[w]
```
219
```        for v in P[w]:
```
220
```            h = _get_value_from_traffic_matrix(nodes, traffic_matrix, s, v)
```
221
```            delta[v] += sigma[v] * coeff + h
```
222
```        if w != s:
```
223
```            betweenness[w] += delta[w]
```
224

225

226 214
```def _accumulate_weight_basic(betweenness, S, P, sigma, s):
```
227 215
```    r"""Accumlate the BC score.
```
228 216

......
235 223
```    .. [1] Rami Puzis
```
236 224
```       Optimization of NIDS Placement for Protection of Intercommunicating Critical Infrastructures
```
237 225
```    """
```
226
```    # betweenness[s] += len(S) - 1
```
238 227
```    delta = dict.fromkeys(S, 0)
```
239 228
```    while S:
```
240 229
```        w = S.pop()
```
241
```        if w != s:
```
242
```            delta[w] += 1 # this is the h, when w != s, then h(s, w) = 1
```
230
```        # if w != s:
```
231
```        delta[w] += 1 # this is the h, when w != s, then h(s, w) = 1
```
243 232
```        coeff = delta[w] / sigma[w]
```
244 233
```        for v in P[w]:
```
245 234
```            delta[v] += sigma[v] * coeff
```
......
255 244
```    .. [1] Rami Puzis
```
256 245
```       Optimization of NIDS Placement for Protection of Intercommunicating Critical Infrastructures
```
257 246
```    """
```
247
```    # betweenness[s] += len(S) - 1
```
258 248
```    delta = dict.fromkeys(S, 0)
```
259 249
```    while S:
```
260 250
```        w = S.pop()
```
261 251
```        h = _get_value_from_traffic_matrix(nodes, traffic_matrix, s, w)
```
262 252
```        delta[w] += h
```
253

263 254
```        coeff = delta[w] / sigma[w]
```
264 255

265 256
```        for v in P[w]:
```
fiddle/heuristic-betweenness-centrality/centrality_biconnected.py
12 12

13 13
```MAIN_CODE_DIR = os.environ.get('MAIN_CODE_DIR', '')
```
14 14

15

16 15
```class HeuristicBetweennessCentrality():
```
17 16
```    def __init__(self, subgraphs, bicomponents, cutpoints, num_vertices, link_weight, traffic_matrix):
```
18 17
```        self.subgraphs = subgraphs
```
......
200 199
```        else:
```
201 200
```            return 0
```
202 201

203
```    def generate_link_weight(self):
```
204
```        # How many cutpoints does this component have
```
205
```        B_plus_v = list()
```
206
```        B_cutpoints = list() # number of cutpoints in component B
```
207
```        for comp in self.bicomponents:
```
208
```            points = comp.intersection(self.cutpoints)
```
209
```            B_plus_v.append(comp.difference(points))
```
210
```            B_cutpoints.append(points)
```
211

212
```        len_B_plus_v = [len(x) for x in B_plus_v]
```
213
```        len_B_cutpoints = [len(x) for x in B_cutpoints]
```
214

215
```        # Calculate the Dv_B
```
216

217
```        # For the leaf in the block-cut tree
```
218
```        level = 1
```
219
```        for (i, cp) in enumerate(B_cutpoints):
```
220
```            if len_B_cutpoints[i] == level:
```
221
```                point = list(cp)[0] # there is only 1 element
```
222
```                self.Dv_B[i][point] = len_B_plus_v[i]
```
223

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

232
```                    for point in cp:
```
233
```                        # 1st way
```
234
```                        shared_comp_indices = self._components_sharing_cutpoint(B_cutpoints, point)
```
235
```                        shared_comp_indices.remove(i)
```
236
```                        weight_shared_comp = list()
```
237

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

241
```                        weight = self.num_vertices - 1 - sum(weight_shared_comp)
```
242

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

245
```            level += 1
```
246

247 202
```    def generate_reverse_link_weight(self):
```
248 203
```        for i, Dv_B_i in enumerate(self.Dv_B):
```
249 204
```            for key, value in Dv_B_i.iteritems():
```
......
258 213
```            B_cutpoints.append(points)
```
259 214

260 215
```        Q = self._inititalize_component_tree_weight()
```
216
```        print "finish initialization\n"
```
261 217
```        while Q:
```
262 218
```            pair = Q.pop(0)
```
263 219
```            if pair['type'] == 'component_vertex_pair':
```
......
319 275
```                    'type': 'component_vertex_pair',
```
320 276
```                    'value': (i, list(current_cutpoints)[0]) # (B_i, cutpoint) = (i-th component, the cutpoint name)
```
321 277
```                    })
```
278
```                print "added component_vertex_pair(%s, %s)" % (i, list(current_cutpoints)[0])
```
322 279
```            for cp in current_cutpoints:
```
323 280
```                self.set_link_weight(i, cp, -1)
```
324 281
```        return Q
```
325 282

326 283
```    def _find_unknown_weight_wrt_cutpoint(self, cutpoint, Q):
```
284
```        print "_find_unknown_weight_wrt_cutpoint %s" % cutpoint
```
285

327 286
```        # Cut-point v such that the weights of all but one of its links in T are already computed.
```
328 287
```        num_of_uncomputed_weight = 0
```
329 288
```        uncomputed_component_index = []
```
......
332 291
```            if cutpoint in Dv_B_comp:
```
333 292
```                if Dv_B_comp[cutpoint] == -1:
```
334 293
```                    num_of_uncomputed_weight += 1
```
294
```                    print "    %i" % i
```
335 295
```                    uncomputed_component_index.append(i)
```
296
```                if num_of_uncomputed_weight > 1:
```
297
```                    break
```
298

336 299
```        if num_of_uncomputed_weight == 1:
```
337 300
```            pair = {
```
338 301
```                'type': 'vertex_component_pair',
```
339 302
```                'value': (uncomputed_component_index.pop(), cutpoint)
```
340 303
```            }
```
304
```            print "      Added vertex_component_pair (%s, %s)" % pair['value'];
```
341 305
```            Q.append(pair)
```
342 306
```        return Q
```
343 307

......
356 320
```                        'type': 'component_vertex_pair',
```
357 321
```                        'value': (comp_index, cp)
```
358 322
```                    }
```
323
```                    print "Added component_vertex_pair (%s, %s)" % pair['value'];
```
359 324
```                    Q.append(pair)
```
360 325
```        return Q
```
361 326

362 327
```    def __str__(self):
```
363 328
```        return str(self.Dv_B)
```
364 329

365
```def analyse_biconnected_component(graph):
```
366
```    bicomponents = list(nx.biconnected_components(graph))
```
367
```    print bicomponents
```
368
```    print [len(x) for x in bicomponents]
```
369

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

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

375
```    graph = nx.read_weighted_edgelist(filepath)
```
376

377
```    if not nx.is_connected(graph):
```
378
```        print "Graph is not connected"
```
379
```        # sys.exit()
```
380
```    else:
```
381
```        print "Graph is connected"
```
382

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

386
```    subgraphs = list(nx.biconnected_component_subgraphs(graph))
```
387
```    bicomponents = list(nx.biconnected_components(graph))
```
388
```    component_edges = list(nx.biconnected_component_edges(graph))
```
389
```    cutpoints = set(nx.articulation_points(graph))
```
390

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

393
```    lw = LinkWeight(graph, bicomponents, cutpoints)
```
394

395
```    tm = TrafficMatrix(bicomponents, cutpoints, lw)
```
396

397
```    bc = HeuristicBetweennessCentrality(subgraphs, bicomponents, cutpoints, num_vertices, lw, tm)
```
398
```    bc.write(file_suffix)
```
399
```    print bc
```
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

407
```if __name__ == '__main__':
```
408
```    utility.initialize()
```
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)
```
412

413
```    # filepath = MAIN_CODE_DIR + '/input/simple_house.edges'
```
414
```    # filepath = MAIN_CODE_DIR + '/input/simple2.edges'
```
415
```    # filepath = MAIN_CODE_DIR + '/input/simple.edges'
```
416
```    # filepath = MAIN_CODE_DIR + '/input/ninux_simplified.edges'
```
417
```    # filepath = MAIN_CODE_DIR + '/input/ninux_simplified_connected.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'
```
424
```    # filepath = MAIN_CODE_DIR + '/input/ninux_connected.edges'
```
425
```    # filepath = MAIN_CODE_DIR + '/input/ninux_unweighted.edges'
```
426
```    # filepath = MAIN_CODE_DIR + '/input/ninux_unweighted_simplified.edges'
```
427
```    # filepath = MAIN_CODE_DIR + '/input/ninux_unweighted_simplified_connected.edges'
```
428
```    # filepath = MAIN_CODE_DIR + '/input/simple3.edges'
```
429
```    # filepath = MAIN_CODE_DIR + '/input/simple4.edges'
```
430
```    # filepath = MAIN_CODE_DIR + '/input/simple5.edges'
```
431

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

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)
```
440

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

fiddle/heuristic-betweenness-centrality/gnuplot_script
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
```plot  "./output/score_summary_edge_list.txt" using 2 title 'networkx' pointtype 7 pointsize 0.7, \
```
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 'heuristics' pointtype 8 pointsize 0.5,\
```
7
```plot  "./output/score_summary_edge_list.txt" using 2 title 'networkx (not include source nor target)' pointtype 5 pointsize 1, \
```
8
```      "./output/score_summary_edge_list.txt" using 3 title 'networkx (include only target)' pointtype 7 pointsize 0.8,\
```
9
```      "./output/score_summary_edge_list.txt" using 4 title 'heuristics (include only target)' pointtype 2 pointsize 0.5,\
```
fiddle/heuristic-betweenness-centrality/script.sh
1 1
```export MAIN_CODE_DIR="/home/quynh/Thesis/quynhnguyen-ms/fiddle/heuristic-betweenness-centrality"
```
2 2
```# python visualize.py
```
3
```python centrality_biconnected.py
```
3
```python main.py
```
4 4
```python compare.py
```
5 5

6 6
```gnuplot gnuplot_script
```
fiddle/heuristic-betweenness-centrality/utility.py
1
```import json
```
1 2
```import os
```
2 3
```import networkx as nx
```
3 4
```import matplotlib.pyplot as plt
```
......
17 18
```    if not os.path.isdir(visualization_dir):
```
18 19
```        os.makedirs(visualization_dir)
```
19 20

20
```def weight_betweenness_centrality(filepath, file_suffix):
```
21
```    graph = nx.read_weighted_edgelist(filepath)
```
22

21
```def weight_betweenness_centrality(graph, file_suffix):
```
23 22
```    score = centrality.weight_betweenness_centrality(graph, rescale=True)
```
24 23
```    filepath = '/output/weight_basic_%s.csv'  % file_suffix
```
25 24

......
27 26
```        for node, bc in score.iteritems():
```
28 27
```            output.write('%s, %s\n' % (node, bc))
```
29 28

30
```def brandes_betweenness_centrality(filepath, file_suffix):
```
31
```    graph = nx.read_weighted_edgelist(filepath)
```
32

33
```    score = nx.betweenness_centrality(graph)
```
29
```def brandes_betweenness_centrality(graph, file_suffix):
```
30
```    score = nx.betweenness_centrality(graph, endpoints=False)
```
31
```    # score = nx.betweenness_centrality(graph, endpoints=True)
```
34 32
```    filepath = '/output/networkx_%s.csv'  % file_suffix
```
35 33

36 34
```    with open(MAIN_CODE_DIR + filepath, 'w') as output:
```
37 35
```        for node, bc in score.iteritems():
```
38 36
```            output.write('%s, %s\n' % (node, bc))
```
39 37

40
```def brandes_betweenness_centrality_endpoints(filepath, file_suffix):
```
41
```    graph = nx.read_weighted_edgelist(filepath)
```
42

38
```def brandes_betweenness_centrality_endpoints(graph, file_suffix):
```
43 39
```    score = nx.betweenness_centrality(graph, endpoints=True)
```
44 40
```    filepath = '/output/heuristic_%s.csv'  % file_suffix
```
45 41

......
47 43
```        for node, bc in score.iteritems():
```
48 44
```            output.write('%s, %s\n' % (node, bc))
```
49 45

46
```def read_complex_json(filepath):
```
47
```    """Returns a graph object
```
48
```    """
```
49
```    edges = []
```
50
```    with open(filepath) as f:
```
51
```        doc = json.loads(f.read())
```
52
```        topologies = doc["topology"]
```
53
```        for connection in topologies:
```
54
```            source = connection['lastHopIP']
```
55
```            target = connection['destinationIP']
```
56
```            cost = connection['neighborLinkQuality']
```
57
```            edges.append((source, target, {'weight': cost}))
```
58

59
```    graph = nx.Graph()
```
60
```    print "Edges = %i\n" % len(edges)
```
61
```    graph.add_edges_from(edges)
```
62
```    return graph
```
63

50 64

51 65
```def plot_graph(output_filepath, graph, title=""):
```
52 66
```    plt.figure(1, figsize=(15, 10))
```

Also available in: Unified diff