Statistics
| Branch: | Revision:

root / globecomm / heuristic_bc / centrality_biconnected.py @ bd3d6dca

History | View | Annotate | Download (12 KB)

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

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

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

    
15
class HeuristicBetweennessCentrality():
16
    def __init__(self, graph):
17

    
18
        if not nx.is_connected(graph):
19
            print "Graph is not connected"
20
            sys.exit()
21
        else:
22
            print "Graph is connected"
23

    
24
        subgraphs, bicomponents, cutpoints, num_vertices, link_weight, traffic_matrix):
25

    
26

    
27
        self.subgraphs = list(nx.biconnected_component_subgraphs(graph))
28
        self.bicomponents = list(nx.biconnected_components(graph))
29
        self.cutpoints = set(nx.articulation_points(graph))
30
        self.num_vertices = nx.number_of_nodes(graph)
31
        self.link_weight = LinkWeight(graph, bicomponents, cutpoints)
32
        self.traffic_matrix = LinkWeight(graph, bicomponents, cutpoints)RR
33

    
34
        self.bc_components = list()
35
        self.calculate_bc_non_cutpoint()
36
        self.calculate_bc_cutpoint()
37

    
38
        self.bc = dict()
39
        self.finalize()
40

    
41
    def calculate_bc_non_cutpoint(self):
42
        """BC for non cutpoint
43
        """
44
        for i, subgraph in enumerate(self.subgraphs):
45
            traffic_matrix = self.traffic_matrix[i]
46
            cut_without = self.num_vertices - nx.number_of_nodes(subgraph)
47
            results = centrality.weight_betweenness_centrality(subgraph, traffic_matrix, cut_without)
48
            self.bc_components.append(results)
49

    
50
    def calculate_bc_cutpoint(self):
51
        self.bc_cutpoints = dict()
52

    
53
        bc_inter = dict()
54
        for v in self.cutpoints:
55
            inter = 0
56
            for i, comp in enumerate(self.bicomponents):
57
                if v in comp:
58
                    inter += self.link_weight.get_link_weight(i, v
59
                        ) * self.link_weight.get_reverse_link_weight(i, v)
60
            bc_inter[v] = inter
61

    
62
        print 'XXXX bc_components = %s' % self.bc_components
63
        print 'XXXX inter = %s' % bc_inter
64

    
65
        for v in self.cutpoints:
66
            bc_locally = 0
67
            for i, comp in enumerate(self.bicomponents):
68
                if v in comp:
69
                    bc_locally += self.bc_components[i][v]
70
            self.bc_cutpoints[v] = bc_locally - bc_inter[v]
71
            # TODO: do not minus the bc_inter
72
            # self.bc_cutpoints[v] = bc_locally
73

    
74
    def finalize(self):
75
        # Add the bc for non cutpoint vertices
76
        for bc_component in self.bc_components:
77
            for key, value in bc_component.iteritems():
78
                if key not in self.bc:
79
                    self.bc[key] = value
80

    
81
        # Add the bc for cutpoint vertices
82
        for key, value in self.bc_cutpoints.iteritems():
83
            self.bc[key] = value
84

    
85
        # Rescale the bc according to the original graph
86
        factor = 1.0 / ((self.num_vertices - 1) * (self.num_vertices - 2))
87
        # TODO: check the scaling factor, how much should it be?
88
        # factor = 2.0 / (self.num_vertices*self.num_vertices - 3 * self.num_vertices + 2)
89
        for key, value in self.bc.iteritems():
90
            self.bc[key] = value * factor
91

    
92
    def write(self, file_suffix=''):
93
        filepath = '/output/heuristic_%s.csv'  % file_suffix
94
        with open(MAIN_CODE_DIR + filepath, 'w') as output:
95
            for node, centrality in self.bc.iteritems():
96
                output.write('%s, %s\n' % (node, centrality))
97

    
98
    def __str__(self):
99
        return str(self.bc)
100

    
101

    
102
class TrafficMatrix():
103
    def __init__(self, bicomponents, cutpoints, link_weight):
104
        self.bicomponents = bicomponents
105
        self.cutpoints = cutpoints
106
        self.num_components = len(bicomponents)
107
        self.link_weight = link_weight
108

    
109
        self.h = list()
110
        self.generate_empty_traffic_matrix()
111
        self.generate_traffic_matrix()
112

    
113
    def generate_empty_traffic_matrix(self):
114
        for i in range(self.num_components):
115
            l = len(self.bicomponents[i])
116
            matrix = [[1 for x in range(l)] for y in range(l)]
117
            # update the main diagonal
118
            for x in range(l):
119
                matrix[x][x] = 0
120

    
121
            self.h.append(matrix)
122

    
123
    def generate_traffic_matrix(self):
124
        # Update the value when one vertex is a cut-point, another vertex is not a cut-point
125
        for i, components in enumerate(self.bicomponents):
126
            normal_points = components.difference(self.cutpoints)
127
            cutpoints = self.cutpoints.intersection(components)
128

    
129
            for cutpoint in cutpoints:
130
                for normal_point in normal_points:
131
                    communication_intensity = self.link_weight.get_reverse_link_weight(i, cutpoint) + 1
132
                    self.update(i, cutpoint, normal_point, communication_intensity)
133

    
134
        # Update the value when both vertices are cut-points
135
        for i, components in enumerate(self.bicomponents):
136
            cutpoints = list(self.cutpoints.intersection(components))
137
            len_cutpoints = len(cutpoints)
138
            if len_cutpoints > 1:
139
                for k in range(len_cutpoints - 1):
140
                    for l in range(1, len_cutpoints):
141
                        if k == l:
142
                            continue
143
                        communication_intensity = (
144
                            self.link_weight.get_reverse_link_weight(i, cutpoints[k]) + 1) * (
145
                            self.link_weight.get_reverse_link_weight(i, cutpoints[l]) + 1
146
                        )
147
                        self.update(i, cutpoints[k], cutpoints[l], communication_intensity)
148

    
149
    def simple_update(self, comp_index, x_pos, y_pos, value):
150
        self.h[comp_index][x_pos][y_pos] = value
151
        # to keep the symmetric property of Traffic Matrix
152
        self.h[comp_index][y_pos][x_pos] = value
153

    
154
    def update(self, comp_index, x, y, value):
155
        comp = sorted(self.bicomponents[comp_index])
156
        try:
157
            x_pos = list(comp).index(x)
158
            y_pos = list(comp).index(y)
159
        except:
160
            debugger()
161
            a = 2
162

    
163
        self.simple_update(comp_index, x_pos, y_pos, value)
164

    
165
    def __str__(self):
166
        return str(self.h)
167

    
168
    def __getitem__(self, key):
169
        return self.h[key]
170

    
171

    
172
class LinkWeight():
173
    def __init__(self, graph, bicomponents, cutpoints):
174
        self.num_vertices = nx.number_of_nodes(graph)
175
        self.bicomponents = bicomponents
176
        self.num_components = len(bicomponents)
177
        self.cutpoints = cutpoints
178

    
179
        self.Dv_B = [dict() for i in range(self.num_components)] # link weight
180
        self.compute_component_tree_weight()
181

    
182
        self.reverse_Dv_B = [dict() for i in range(self.num_components)] # reverse link weight
183
        self.generate_reverse_link_weight()
184

    
185
    def _components_sharing_cutpoint(self, B_cutpoints, point):
186
        indices = list()
187
        for i, cp in enumerate(B_cutpoints):
188
            if point in cp:
189
                indices.append(i)
190

    
191
        return indices
192

    
193
    def get_link_weight(self, comp_index, point):
194
        Dv_B_comp = self.Dv_B[comp_index]
195

    
196
        if point in Dv_B_comp:
197
            return Dv_B_comp[point]
198
        else:
199
            return 0
200

    
201
    def set_link_weight(self, comp_index, point, value):
202
        self.Dv_B[comp_index][point] = value
203

    
204
    def get_reverse_link_weight(self, comp_index, point):
205
        reverse_Dv_B_comp = self.reverse_Dv_B[comp_index]
206

    
207
        if point in reverse_Dv_B_comp:
208
            return reverse_Dv_B_comp[point]
209
        else:
210
            return 0
211

    
212
    def generate_reverse_link_weight(self):
213
        for i, Dv_B_i in enumerate(self.Dv_B):
214
            for key, value in Dv_B_i.iteritems():
215
                self.reverse_Dv_B[i][key] = self.num_vertices - 1 - self.get_link_weight(i, key)
216

    
217
    def compute_component_tree_weight(self):
218
        """Follows exactly the Algorithm 1 [Puzis 2012]
219
        """
220
        B_cutpoints = list() # number of cutpoints in component B
221
        for comp in self.bicomponents:
222
            points = comp.intersection(self.cutpoints)
223
            B_cutpoints.append(points)
224

    
225
        Q = self._inititalize_component_tree_weight()
226
        while Q:
227
            pair = Q.pop(0)
228
            if pair['type'] == 'component_vertex_pair':
229
                B_index = pair['value'][0]
230
                v = pair['value'][1]
231
                size = len(self.bicomponents[B_index]) - 1;
232
                all_cutpoints = self.bicomponents[B_index].intersection(self.cutpoints)
233
                all_cutpoints.remove(v)
234

    
235
                for cp in all_cutpoints:
236
                    if self.get_link_weight(B_index, cp) != -1:
237
                        size += self.num_vertices - self.get_link_weight(B_index, cp) - 1
238

    
239
                link_weight = size
240
                self._verify_link_weight(B_index, v, link_weight)
241
                self.set_link_weight(B_index, v, link_weight)
242

    
243
                # update Q
244
                Q = self._find_unknown_weight_wrt_cutpoint(v, Q)
245

    
246
            if pair['type'] == 'vertex_component_pair':
247
                size = 0
248
                B_index = pair['value'][0]
249
                v = pair['value'][1]
250
                shared_comp_indices = self._components_sharing_cutpoint(B_cutpoints, v)
251
                shared_comp_indices.remove(B_index)
252

    
253

    
254
                for i in shared_comp_indices:
255
                    if self.get_link_weight(i, v) != - 1:
256
                        size += self.get_link_weight(i, v)
257

    
258
                link_weight = self.num_vertices - 1 - size
259
                self._verify_link_weight(B_index, v, link_weight)
260
                self.set_link_weight(B_index, v, link_weight)
261

    
262
                # update Q
263
                Q = self._find_unknown_weight_wrt_component(B_index, Q)
264

    
265
    def _verify_link_weight(self, B_index, v, value):
266
        """ If the old_value exist in self.Dv_B, then it must be equal to new value
267

268
        Otherwise, do nothing
269
        """
270
        old_value = self.get_link_weight(B_index, v)
271

    
272
        if old_value != -1: # -1 is unknown
273
            if old_value != value:
274
                print "BUGS FOUND in _verify_link_weight()"
275
                sys.exit()
276

    
277

    
278
    def _inititalize_component_tree_weight(self):
279
        Q = []
280
        for i, comp in enumerate(self.bicomponents):
281
            current_cutpoints = self.cutpoints.intersection(comp)
282
            if len(current_cutpoints) == 1:
283
                Q.append({
284
                    'type': 'component_vertex_pair',
285
                    'value': (i, list(current_cutpoints)[0]) # (B_i, cutpoint) = (i-th component, the cutpoint name)
286
                    })
287
            for cp in current_cutpoints:
288
                self.set_link_weight(i, cp, -1)
289
        return Q
290

    
291
    def _find_unknown_weight_wrt_cutpoint(self, cutpoint, Q):
292
        num_of_uncomputed_weight = 0
293
        uncomputed_component_index = []
294

    
295
        for i, Dv_B_comp in enumerate(self.Dv_B):
296
            if cutpoint in Dv_B_comp:
297
                if Dv_B_comp[cutpoint] == -1:
298
                    num_of_uncomputed_weight += 1
299
                    uncomputed_component_index.append(i)
300
                if num_of_uncomputed_weight > 1:
301
                    break
302

    
303
        if num_of_uncomputed_weight == 1:
304
            pair = {
305
                'type': 'vertex_component_pair',
306
                'value': (uncomputed_component_index.pop(), cutpoint)
307
            }
308
            Q.append(pair)
309
        return Q
310

    
311
    def _find_unknown_weight_wrt_component(self, comp_index, Q):
312
        # Component B such that weights of all but one of its links in T are already computed.
313
        Dv_B_comp = self.Dv_B[comp_index]
314
        values = Dv_B_comp.values()
315

    
316
        # Check if -1 value appear only 1 time
317
        flag = False
318
        minus_one_value = [x for x in values if x == -1]
319
        if len(minus_one_value) == 1:
320
            for cp, value in Dv_B_comp.iteritems():
321
                if value == -1:
322
                    pair = {
323
                        'type': 'component_vertex_pair',
324
                        'value': (comp_index, cp)
325
                    }
326
                    Q.append(pair)
327
        return Q
328

    
329
    def __str__(self):
330
        return str(self.Dv_B)
331