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