Statistics
| Branch: | Revision:

root / fiddle / heuristic-betweenness-centrality / centrality_biconnected.py @ 3673c3e8

History | View | Annotate | Download (12.1 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, subgraphs, bicomponents, cutpoints, num_vertices, link_weight, traffic_matrix):
17
        self.subgraphs = subgraphs
18
        self.bicomponents = bicomponents
19
        self.cutpoints = cutpoints
20
        self.num_vertices = num_vertices
21
        self.link_weight = link_weight
22
        self.traffic_matrix = traffic_matrix
23

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

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

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

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

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

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

    
54
        for v in self.cutpoints:
55
            bc_locally = 0
56
            for i, comp in enumerate(self.bicomponents):
57
                if v in comp:
58
                    bc_locally += self.bc_components[i][v]
59
            # self.bc_cutpoints[v] = bc_locally - bc_inter[v]
60
            # TODO: do not minus the bc_inter
61
            self.bc_cutpoints[v] = bc_locally
62

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

    
70
        # Add the bc for cutpoint vertices
71
        for key, value in self.bc_cutpoints.iteritems():
72
            self.bc[key] = value
73

    
74
        print '*** betweenness = %s' % self.bc
75
        # Rescale the bc according to the original graph
76
        factor = 1.0 / ((self.num_vertices - 1) * (self.num_vertices - 2))
77
        # TODO: check the scaling factor, how much should it be?
78
        # factor = 2.0 / (self.num_vertices*self.num_vertices - 3 * self.num_vertices + 2)
79
        for key, value in self.bc.iteritems():
80
            self.bc[key] = value * factor
81

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

    
88
    def __str__(self):
89
        return str(self.bc)
90

    
91

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

    
99
        self.h = list()
100
        self.generate_empty_traffic_matrix()
101
        self.generate_traffic_matrix()
102

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

    
111
            self.h.append(matrix)
112

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

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

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

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

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

    
153
        self.simple_update(comp_index, x_pos, y_pos, value)
154

    
155
    def __str__(self):
156
        return str(self.h)
157

    
158
    def __getitem__(self, key):
159
        return self.h[key]
160

    
161

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

    
169
        self.Dv_B = [dict() for i in range(self.num_components)] # link weight
170
        self.compute_component_tree_weight()
171

    
172
        self.reverse_Dv_B = [dict() for i in range(self.num_components)] # reverse link weight
173
        self.generate_reverse_link_weight()
174

    
175
    def _components_sharing_cutpoint(self, B_cutpoints, point):
176
        indices = list()
177
        for i, cp in enumerate(B_cutpoints):
178
            if point in cp:
179
                indices.append(i)
180

    
181
        return indices
182

    
183
    def get_link_weight(self, comp_index, point):
184
        Dv_B_comp = self.Dv_B[comp_index]
185

    
186
        if point in Dv_B_comp:
187
            return Dv_B_comp[point]
188
        else:
189
            return 0
190

    
191
    def set_link_weight(self, comp_index, point, value):
192
        self.Dv_B[comp_index][point] = value
193

    
194
    def get_reverse_link_weight(self, comp_index, point):
195
        reverse_Dv_B_comp = self.reverse_Dv_B[comp_index]
196

    
197
        if point in reverse_Dv_B_comp:
198
            return reverse_Dv_B_comp[point]
199
        else:
200
            return 0
201

    
202
    def generate_reverse_link_weight(self):
203
        for i, Dv_B_i in enumerate(self.Dv_B):
204
            for key, value in Dv_B_i.iteritems():
205
                self.reverse_Dv_B[i][key] = self.num_vertices - 1 - self.get_link_weight(i, key)
206

    
207
    def compute_component_tree_weight(self):
208
        """Follows exactly the Algorithm 1 [Puzis 2012]
209
        """
210
        B_cutpoints = list() # number of cutpoints in component B
211
        for comp in self.bicomponents:
212
            points = comp.intersection(self.cutpoints)
213
            B_cutpoints.append(points)
214

    
215
        Q = self._inititalize_component_tree_weight()
216
        print "finish initialization\n"
217
        while Q:
218
            pair = Q.pop(0)
219
            if pair['type'] == 'component_vertex_pair':
220
                B_index = pair['value'][0]
221
                v = pair['value'][1]
222
                size = len(self.bicomponents[B_index]) - 1;
223
                all_cutpoints = self.bicomponents[B_index].intersection(self.cutpoints)
224
                all_cutpoints.remove(v)
225

    
226
                for cp in all_cutpoints:
227
                    if self.get_link_weight(B_index, cp) != -1:
228
                        size += self.num_vertices - self.get_link_weight(B_index, cp) - 1
229

    
230
                link_weight = size
231
                self._verify_link_weight(B_index, v, link_weight)
232
                self.set_link_weight(B_index, v, link_weight)
233

    
234
                # update Q
235
                Q = self._find_unknown_weight_wrt_cutpoint(v, Q)
236

    
237
            if pair['type'] == 'vertex_component_pair':
238
                size = 0
239
                B_index = pair['value'][0]
240
                v = pair['value'][1]
241
                shared_comp_indices = self._components_sharing_cutpoint(B_cutpoints, v)
242
                shared_comp_indices.remove(B_index)
243

    
244

    
245
                for i in shared_comp_indices:
246
                    if self.get_link_weight(i, v) != - 1:
247
                        size += self.get_link_weight(i, v)
248

    
249
                link_weight = self.num_vertices - 1 - size
250
                self._verify_link_weight(B_index, v, link_weight)
251
                self.set_link_weight(B_index, v, link_weight)
252

    
253
                # update Q
254
                Q = self._find_unknown_weight_wrt_component(B_index, Q)
255

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

259
        Otherwise, do nothing
260
        """
261
        old_value = self.get_link_weight(B_index, v)
262

    
263
        if old_value != -1: # -1 is unknown
264
            if old_value != value:
265
                print "BUGS FOUND in _verify_link_weight()"
266
                sys.exit()
267

    
268

    
269
    def _inititalize_component_tree_weight(self):
270
        Q = []
271
        for i, comp in enumerate(self.bicomponents):
272
            current_cutpoints = self.cutpoints.intersection(comp)
273
            if len(current_cutpoints) == 1:
274
                Q.append({
275
                    'type': 'component_vertex_pair',
276
                    'value': (i, list(current_cutpoints)[0]) # (B_i, cutpoint) = (i-th component, the cutpoint name)
277
                    })
278
                print "added component_vertex_pair(%s, %s)" % (i, list(current_cutpoints)[0])
279
            for cp in current_cutpoints:
280
                self.set_link_weight(i, cp, -1)
281
        return Q
282

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

    
286
        # Cut-point v such that the weights of all but one of its links in T are already computed.
287
        num_of_uncomputed_weight = 0
288
        uncomputed_component_index = []
289

    
290
        for i, Dv_B_comp in enumerate(self.Dv_B):
291
            if cutpoint in Dv_B_comp:
292
                if Dv_B_comp[cutpoint] == -1:
293
                    num_of_uncomputed_weight += 1
294
                    print "    %i" % i
295
                    uncomputed_component_index.append(i)
296
                if num_of_uncomputed_weight > 1:
297
                    break
298

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

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

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

    
327
    def __str__(self):
328
        return str(self.Dv_B)
329