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 Biconnected 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 cutpoint, another vertex is not a cutpoint

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 cutpoints

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) = (ith 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 