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 |
|