Statistics
| Branch: | Revision:

root / fiddle / heuristic-betweenness-centrality / centrality_biconnected.py @ 24a4abf9

History | View | Annotate | Download (14.9 KB)

1
# Implement the section IV in Puzis 2012 paper
2
# Heuristic Betweenness Centrality - Partitioning to Bi-connected Components
3

    
4
import os
5
import pprint
6
import networkx as nx
7
import betweenness_centrality as centrality
8
import utility
9
from pdb import set_trace as debugger
10

    
11
MAIN_CODE_DIR = os.environ.get('MAIN_CODE_DIR', '')
12

    
13

    
14
class HeuristicBetweennessCentrality():
15
    def __init__(self, subgraphs, bicomponents, cutpoints, num_vertices, link_weight, traffic_matrix):
16
        self.subgraphs = subgraphs
17
        self.bicomponents = bicomponents
18
        self.cutpoints = cutpoints
19
        self.num_vertices = num_vertices
20
        self.link_weight = link_weight
21
        self.traffic_matrix = traffic_matrix
22

    
23
        self.bc_components = list()
24
        self.calculate_bc_non_cutpoint()
25
        self.calculate_bc_cutpoint()
26

    
27
        self.bc = dict()
28
        self.finalize()
29

    
30
    def calculate_bc_non_cutpoint(self):
31
        """BC for non cutpoint
32
        """
33
        for i, subgraphs in enumerate(self.subgraphs):
34
            traffic_matrix = self.traffic_matrix[i]
35
            results = centrality.weight_betweenness_centrality(subgraphs, traffic_matrix)
36
            self.bc_components.append(results)
37

    
38
            # print results
39

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

    
43
        bc_inter = dict()
44
        for v in self.cutpoints:
45
            inter = 0
46
            for i, comp in enumerate(self.bicomponents):
47
                if v in comp:
48
                    inter += self.link_weight.get_link_weight(i, v
49
                        ) * self.link_weight.get_reverse_link_weight(i, v)
50
            bc_inter[v] = inter
51

    
52
        print 'XXXX bc_components = %s' % self.bc_components
53
        print 'XXXX inter = %s' % bc_inter
54

    
55
        for v in self.cutpoints:
56
            bc_locally = 0
57
            for i, comp in enumerate(self.bicomponents):
58
                if v in comp:
59
                    # debugger()
60
                    bc_locally += self.bc_components[i][v]
61
            print 'locally = %s' % bc_locally
62
            # self.bc_cutpoints[v] = bc_locally - bc_inter[v]
63
            # TODO: do not minus the bc_inter
64
            self.bc_cutpoints[v] = bc_locally
65

    
66
    def finalize(self):
67
        # Add the bc for non cutpoint vertices
68
        for bc_component in self.bc_components:
69
            for key, value in bc_component.iteritems():
70
                if key not in self.bc:
71
                    self.bc[key] = value
72

    
73
        # Add the bc for cutpoint vertices
74
        for key, value in self.bc_cutpoints.iteritems():
75
            self.bc[key] = value
76

    
77
        print '*** betweenness = %s' % self.bc
78
        # Rescale the bc according to the original graph
79
        factor = 1.0 / ((self.num_vertices - 1) * (self.num_vertices - 2))
80
        # factor = 2.0 / (self.num_vertices*self.num_vertices - 3 * self.num_vertices + 2)
81
        for key, value in self.bc.iteritems():
82
            self.bc[key] = value * factor
83

    
84
    def write(self, file_suffix=''):
85
        filepath = '/output/heuristic_%s.csv'  % file_suffix
86
        with open(MAIN_CODE_DIR + filepath, 'w') as output:
87
            for node, centrality in self.bc.iteritems():
88
                output.write('%s, %s\n' % (node, centrality))
89

    
90
    def __str__(self):
91
        return str(self.bc)
92

    
93

    
94
class TrafficMatrix():
95
    def __init__(self, bicomponents, cutpoints, link_weight):
96
        self.bicomponents = bicomponents
97
        self.cutpoints = cutpoints
98
        self.num_components = len(bicomponents)
99
        self.link_weight = link_weight
100

    
101
        self.h = list()
102
        self.generate_empty_traffic_matrix()
103
        self.generate_traffic_matrix()
104

    
105
    def generate_empty_traffic_matrix(self):
106
        for i in range(self.num_components):
107
            l = len(self.bicomponents[i])
108
            matrix = [[1 for x in range(l)] for y in range(l)]
109
            # update the main diagonal
110
            for x in range(l):
111
                matrix[x][x] = 0
112

    
113
            self.h.append(matrix)
114

    
115
    def generate_traffic_matrix(self):
116
        # Update the value when one vertex is a cut-point, another vertex is not a cut-point
117
        for i, components in enumerate(self.bicomponents):
118
            normal_points = components.difference(self.cutpoints)
119
            cutpoints = self.cutpoints.intersection(components)
120

    
121
            for cutpoint in cutpoints:
122
                for normal_point in normal_points:
123
                    communication_intensity = self.link_weight.get_reverse_link_weight(i, cutpoint) + 1
124
                    self.update(i, cutpoint, normal_point, communication_intensity)
125

    
126
        # Update the value when both vertices are cut-points
127
        for i, components in enumerate(self.bicomponents):
128
            cutpoints = list(self.cutpoints.intersection(components))
129
            len_cutpoints = len(cutpoints)
130
            if len_cutpoints > 1:
131
                for k in range(len_cutpoints - 1):
132
                    for l in range(1, len_cutpoints):
133
                        if k == l:
134
                            continue
135
                        communication_intensity = (
136
                            self.link_weight.get_reverse_link_weight(i, cutpoints[k]) + 1) * (
137
                            self.link_weight.get_reverse_link_weight(i, cutpoints[l]) + 1
138
                        )
139
                        self.update(i, cutpoints[k], cutpoints[l], communication_intensity)
140

    
141
    def simple_update(self, comp_index, x_pos, y_pos, value):
142
        self.h[comp_index][x_pos][y_pos] = value
143
        # to keep the symmetric property of Traffic Matrix
144
        self.h[comp_index][y_pos][x_pos] = value
145

    
146
    def update(self, comp_index, x, y, value):
147
        comp = self.bicomponents[comp_index]
148
        try:
149
            x_pos = list(comp).index(x)
150
            y_pos = list(comp).index(y)
151
        except:
152
            debugger()
153
            a = 2
154

    
155
        self.simple_update(comp_index, x_pos, y_pos, value)
156

    
157
    def __str__(self):
158
        return str(self.h)
159

    
160
    def __getitem__(self, key):
161
        return self.h[key]
162

    
163

    
164
class LinkWeight():
165
    def __init__(self, graph, bicomponents, cutpoints):
166
        self.num_vertices = nx.number_of_nodes(graph)
167
        self.bicomponents = bicomponents
168
        self.num_components = len(bicomponents)
169
        self.cutpoints = cutpoints
170

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

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

    
178
    def _components_sharing_cutpoint(self, B_cutpoints, point):
179
        indices = list()
180
        for i, cp in enumerate(B_cutpoints):
181
            # debugger()
182
            if point in cp:
183
                indices.append(i)
184

    
185
        return indices
186

    
187
    def get_link_weight(self, comp_index, point):
188
        Dv_B_comp = self.Dv_B[comp_index]
189

    
190
        if point in Dv_B_comp:
191
            return Dv_B_comp[point]
192
        else:
193
            return 0
194

    
195
    def set_link_weight(self, comp_index, point, value):
196
        self.Dv_B[comp_index][point] = value
197

    
198
    def get_reverse_link_weight(self, comp_index, point):
199
        reverse_Dv_B_comp = self.reverse_Dv_B[comp_index]
200

    
201
        if point in reverse_Dv_B_comp:
202
            return reverse_Dv_B_comp[point]
203
        else:
204
            return 0
205

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

    
215
        len_B_plus_v = [len(x) for x in B_plus_v]
216
        len_B_cutpoints = [len(x) for x in B_cutpoints]
217

    
218
        # Calculate the Dv_B
219

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

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

    
229
        # For other nodes in the block-cut tree
230
        level += 1
231
        while level <= max(len_B_cutpoints):
232
            if level == 3:
233
                debugger()
234
            for (i, cp) in enumerate(B_cutpoints):
235
                if len_B_cutpoints[i] == level:
236

    
237
                    for point in cp:
238
                        # 1st way
239
                        shared_comp_indices = self._components_sharing_cutpoint(B_cutpoints, point)
240
                        shared_comp_indices.remove(i)
241
                        weight_shared_comp = list()
242

    
243
                        for index in shared_comp_indices:
244
                            weight_shared_comp.append(self.get_link_weight(index, point))
245

    
246
                        weight = self.num_vertices - 1 - sum(weight_shared_comp)
247

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

    
257
            level += 1
258

    
259
    def generate_reverse_link_weight(self):
260
        for i, Dv_B_i in enumerate(self.Dv_B):
261
            for key, value in Dv_B_i.iteritems():
262
                self.reverse_Dv_B[i][key] = self.num_vertices - 1 - self.get_link_weight(i, key)
263

    
264
    def compute_component_tree_weight(self):
265
        """Follows exactly the Algorithm 1 [Puzis 2012]
266
        """
267
        B_cutpoints = list() # number of cutpoints in component B
268
        for comp in self.bicomponents:
269
            points = comp.intersection(self.cutpoints)
270
            B_cutpoints.append(points)
271

    
272
        Q = self._inititalize_component_tree_weight()
273
        while Q:
274
            pair = Q.pop(0)
275
            if pair['type'] == 'component_vertex_pair':
276
                B_index = pair['value'][0]
277
                v = pair['value'][1]
278
                print'  CV: %s %s' % (B_index, v)
279
                size = len(self.bicomponents[B_index]) - 1;
280
                all_cutpoints = self.bicomponents[B_index].intersection(self.cutpoints)
281
                all_cutpoints.remove(v)
282

    
283
                for cp in all_cutpoints:
284
                    if self.get_link_weight(B_index, cp) != -1:
285
                        size += self.num_vertices - self.get_link_weight(B_index, cp) - 1
286

    
287
                self.set_link_weight(B_index, v, size)
288

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

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

    
300

    
301
                for i in shared_comp_indices:
302
                    if self.get_link_weight(i, v) != - 1:
303
                        size += self.get_link_weight(i, v)
304

    
305
                self.set_link_weight(B_index, v, self.num_vertices - 1 - size)
306

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

    
310
            print self.Dv_B
311

    
312
    def _inititalize_component_tree_weight(self):
313
        Q = []
314
        for i, comp in enumerate(self.bicomponents):
315
            current_cutpoints = self.cutpoints.intersection(comp)
316
            if len(current_cutpoints) == 1:
317
                Q.append({
318
                    'type': 'component_vertex_pair',
319
                    'value': (i, list(current_cutpoints)[0]) # (B_i, cutpoint) = (i-th component, the cutpoint name)
320
                    })
321
            for cp in current_cutpoints:
322
                self.set_link_weight(i, cp, -1)
323
        return Q
324

    
325
    def _find_unknown_weight_wrt_cutpoint(self, cutpoint, Q):
326
        # Cut-point v such that the weights of all but one of its links in T are already computed.
327
        num_of_uncomputed_weight = 0
328
        uncomputed_component_index = []
329

    
330
        for i, Dv_B_comp in enumerate(self.Dv_B):
331
            if cutpoint in Dv_B_comp:
332
                if Dv_B_comp[cutpoint] == -1:
333
                    num_of_uncomputed_weight += 1
334
                    uncomputed_component_index.append(i)
335
        if num_of_uncomputed_weight == 1:
336
            pair = {
337
                'type': 'vertex_component_pair',
338
                'value': (uncomputed_component_index.pop(), cutpoint)
339
            }
340
            Q.append(pair)
341
            print "Append WRT Cutpoint %s" % pair
342
        return Q
343

    
344
    def _find_unknown_weight_wrt_component(self, comp_index, Q):
345
        # Component B such that weights of all but one of its links in T are already computed.
346
        Dv_B_comp = self.Dv_B[comp_index]
347
        values = Dv_B_comp.values()
348

    
349
        # Check if -1 value appear only 1 time
350
        flag = False
351
        minus_one_value = [x for x in values if x == -1]
352
        if len(minus_one_value) == 1:
353
            for cp, value in Dv_B_comp.iteritems():
354
                if value == -1:
355
                    pair = {
356
                        'type': 'component_vertex_pair',
357
                        'value': (comp_index, cp)
358
                    }
359
                    Q.append(pair)
360
                    print "Append WRT Component %s" % pair
361
        return Q
362

    
363
    def __str__(self):
364
        return str(self.Dv_B)
365

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

    
371
def find_heuristic_bc(filepath):
372
    pp = pprint.PrettyPrinter(indent=4)
373

    
374
    graph = nx.read_weighted_edgelist(filepath)
375

    
376
    # Find biconnected components
377
    analyse_biconnected_component(graph)
378

    
379
    subgraphs = list(nx.biconnected_component_subgraphs(graph))
380
    bicomponents = list(nx.biconnected_components(graph))
381
    component_edges = list(nx.biconnected_component_edges(graph))
382
    cutpoints = set(nx.articulation_points(graph))
383

    
384
    num_vertices = nx.number_of_nodes(graph)
385

    
386
    lw = LinkWeight(graph, bicomponents, cutpoints)
387
    print 'link weight: '
388
    print(lw)
389

    
390
    tm = TrafficMatrix(bicomponents, cutpoints, lw)
391
    print 'traffic matrix:'
392
    pp.pprint(tm.h)
393

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

    
398
if __name__ == '__main__':
399
    # filepath = MAIN_CODE_DIR + '/input/simple_house.edges'
400
    # filepath = MAIN_CODE_DIR + '/input/simple2.edges'
401
    # filepath = MAIN_CODE_DIR + '/input/simple.edges'
402
    filepath = MAIN_CODE_DIR + '/input/ninux_30_1.edges'
403
    # filepath = MAIN_CODE_DIR + '/input/simple3.edges'
404
    # filepath = MAIN_CODE_DIR + '/input/simple4.edges'
405
    file_suffix = 'edge_list'
406

    
407
    # Weight betweenness centrality
408
    utility.weight_betweenness_centrality(filepath, file_suffix)
409

    
410
    # Brandess betweenness centrality
411
    utility.brandes_betweenness_centrality(filepath, file_suffix)
412

    
413
    # Heuristic BC
414
    find_heuristic_bc(filepath)