Statistics
| Branch: | Revision:

root / fiddle / heuristic-betweenness-centrality / centrality_biconnected.py @ 3c6ce57c

History | View | Annotate | Download (14.2 KB)

1 8e44cb4f Quynh PX Nguyen
# Implement the section IV in Puzis 2012 paper
2
# Heuristic Betweenness Centrality - Partitioning to Bi-connected Components
3
4 181e7c50 Quynh PX Nguyen
import os
5 3c6ce57c Quynh PX Nguyen
import pprint
6 181e7c50 Quynh PX Nguyen
import networkx as nx
7
import betweenness_centrality as centrality
8 8e44cb4f Quynh PX Nguyen
import utility
9 181e7c50 Quynh PX Nguyen
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 3c6ce57c Quynh PX Nguyen
        """BC for non cutpoint
32 181e7c50 Quynh PX Nguyen
        """
33
        for i, subgraphs in enumerate(self.subgraphs):
34
            traffic_matrix = self.traffic_matrix[i]
35 3c6ce57c Quynh PX Nguyen
            results = centrality.weight_betweenness_centrality(subgraphs, traffic_matrix)
36 181e7c50 Quynh PX Nguyen
            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 3c6ce57c Quynh PX Nguyen
            # 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 181e7c50 Quynh PX Nguyen
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 3c6ce57c Quynh PX Nguyen
        print '*** betweenness = %s' % self.bc
78 181e7c50 Quynh PX Nguyen
        # Rescale the bc according to the original graph
79 3c6ce57c Quynh PX Nguyen
        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 181e7c50 Quynh PX Nguyen
        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 8e44cb4f Quynh PX Nguyen
                        if k == l:
134
                            continue
135 181e7c50 Quynh PX Nguyen
                        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 3c6ce57c Quynh PX Nguyen
        # self.compute_component_tree_weight()
174 181e7c50 Quynh PX Nguyen
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 3c6ce57c Quynh PX Nguyen
    def set_link_weight(self, comp_index, point, value):
196
        self.Dv_B[comp_index][point] = value
197
198 181e7c50 Quynh PX Nguyen
    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 3c6ce57c Quynh PX Nguyen
        print "Link Weight - For all the leaves: %s" % self.Dv_B
228 181e7c50 Quynh PX Nguyen
229
        # For other nodes in the block-cut tree
230
        level += 1
231
        while level <= max(len_B_cutpoints):
232 3c6ce57c Quynh PX Nguyen
            if level == 3:
233
                debugger()
234 181e7c50 Quynh PX Nguyen
            for (i, cp) in enumerate(B_cutpoints):
235
                if len_B_cutpoints[i] == level:
236
237
                    for point in cp:
238 3c6ce57c Quynh PX Nguyen
                        # 1st way
239 181e7c50 Quynh PX Nguyen
                        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 3c6ce57c Quynh PX Nguyen
                        weight = self.num_vertices - 1 - sum(weight_shared_comp)
247 181e7c50 Quynh PX Nguyen
248
                        self.Dv_B[i][point] = weight
249
250 3c6ce57c Quynh PX Nguyen
                        # # 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 181e7c50 Quynh PX Nguyen
            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 3c6ce57c Quynh PX Nguyen
    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
            print self.Dv_B
275
            pair = Q.pop(0)
276
            if pair['type'] == 'component_vertex_pair':
277
                B_index = pair['value'][0]
278
                v = pair['value'][1]
279
                print'  CV: %s %s' % (B_index, v)
280
                size = len(self.bicomponents[B_index]) - 1;
281
                all_cutpoints = self.bicomponents[B_index].intersection(self.cutpoints)
282
                all_cutpoints.remove(v)
283
284
                for cp in all_cutpoints:
285
                    if self.get_link_weight(B_index, cp) != -1:
286
                        size += self.num_vertices - self.get_link_weight(B_index, cp)
287
288
                self.set_link_weight(B_index, v, size)
289
290
                # update Q
291
                Q = self._find_unknown_weight_wrt_cutpoint(v, Q)
292
293
            if pair['type'] == 'vertex_component_pair':
294
                size = 1
295
                B_index = pair['value'][0]
296
                v = pair['value'][1]
297
                print'  vc: %s %s' % (B_index, v)
298
                shared_comp_indices = self._components_sharing_cutpoint(B_cutpoints, v)
299
                shared_comp_indices.remove(B_index)
300
301
302
                for i in shared_comp_indices:
303
                    if self.get_link_weight(i, v) != - 1:
304
                        size += self.get_link_weight(i, v)
305
306
                self.set_link_weight(B_index, v, self.num_vertices - 1 - size)
307
308
                # update Q
309
                Q = self._find_unknown_weight_wrt_component(B_index, Q)
310
311
    def _inititalize_component_tree_weight(self):
312
        Q = []
313
        for i, comp in enumerate(self.bicomponents):
314
            current_cutpoints = self.cutpoints.intersection(comp)
315
            if len(current_cutpoints) == 1:
316
                Q.append({
317
                    'type': 'component_vertex_pair',
318
                    'value': (i, list(current_cutpoints)[0]) # (B_i, cutpoint) = (i-th component, the cutpoint name)
319
                    })
320
            for cp in current_cutpoints:
321
                self.set_link_weight(i, cp, -1)
322
        return Q
323
324
    def _find_unknown_weight_wrt_cutpoint(self, cutpoint, Q):
325
        for i, Dv_B_comp in enumerate(self.Dv_B):
326
            for cp, value in Dv_B_comp.iteritems():
327
                if value == -1:
328
                    pair = {
329
                        'type': 'vertex_component_pair',
330
                        'value': (i, cp)
331
                    }
332
                    Q.append(pair)
333
        return Q
334
335
    def _find_unknown_weight_wrt_component(self, comp_index, Q):
336
        Dv_B_comp = self.Dv_B[comp_index]
337
        for cp, value in Dv_B_comp.iteritems():
338
            if value == -1:
339
                pair = {
340
                    'type': 'component_vertex_pair',
341
                    'value': (comp_index, cp)
342
                }
343
                Q.append(pair)
344
        return Q
345
346 181e7c50 Quynh PX Nguyen
347
    def __str__(self):
348
        return str(self.Dv_B)
349
350
def analyse_biconnected_component(graph):
351
    bicomponents = list(nx.biconnected_components(graph))
352
    print bicomponents
353
    print [len(x) for x in bicomponents]
354
355 3c6ce57c Quynh PX Nguyen
def find_heuristic_bc(filepath):
356
    pp = pprint.PrettyPrinter(indent=4)
357 181e7c50 Quynh PX Nguyen
358
    graph = nx.read_weighted_edgelist(filepath)
359
360
    # Find biconnected components
361
    analyse_biconnected_component(graph)
362
363
    subgraphs = list(nx.biconnected_component_subgraphs(graph))
364
    bicomponents = list(nx.biconnected_components(graph))
365
    component_edges = list(nx.biconnected_component_edges(graph))
366
    cutpoints = set(nx.articulation_points(graph))
367
368
    num_vertices = nx.number_of_nodes(graph)
369
370
    lw = LinkWeight(graph, bicomponents, cutpoints)
371
    print 'link weight: '
372 3c6ce57c Quynh PX Nguyen
    print(lw)
373
374
    # tm = TrafficMatrix(bicomponents, cutpoints, lw)
375
    # print 'traffic matrix:'
376
    # pp.pprint(tm.h)
377 181e7c50 Quynh PX Nguyen
378 3c6ce57c Quynh PX Nguyen
    # bc = HeuristicBetweennessCentrality(subgraphs, bicomponents, cutpoints, num_vertices, lw, tm)
379
    # bc.write(file_suffix)
380
    # # print bc
381 181e7c50 Quynh PX Nguyen
382 3c6ce57c Quynh PX Nguyen
if __name__ == '__main__':
383
    # filepath = MAIN_CODE_DIR + '/input/simple_house.edges'
384
    # filepath = MAIN_CODE_DIR + '/input/simple2.edges'
385
    # filepath = MAIN_CODE_DIR + '/input/simple.edges'
386
    # filepath = MAIN_CODE_DIR + '/input/ninux_30_1.edges'
387
    # filepath = MAIN_CODE_DIR + '/input/simple3.edges'
388
    filepath = MAIN_CODE_DIR + '/input/simple4.edges'
389
    file_suffix = 'edge_list'
390
391
    # Weight betweenness centrality
392
    utility.weight_betweenness_centrality(filepath, file_suffix)
393
394
    # Brandess betweenness centrality
395
    utility.brandes_betweenness_centrality(filepath, file_suffix)
396 181e7c50 Quynh PX Nguyen
397 3c6ce57c Quynh PX Nguyen
    # Heuristic BC
398
    find_heuristic_bc(filepath)