root / fiddle / heuristicbetweennesscentrality / centrality_biconnected.py @ 24a4abf9
History  View  Annotate  Download (14.9 KB)
1 
# Implement the section IV in Puzis 2012 paper


2 
# Heuristic Betweenness Centrality  Partitioning to Biconnected Components

3  
4 
import os 
5 
import pprint 
6 
import networkx as nx 
7 
import betweenness_centrality as centrality 
8 
import utility 
9 
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 
"""BC for non cutpoint

32 
"""

33 
for i, subgraphs in enumerate(self.subgraphs): 
34 
traffic_matrix = self.traffic_matrix[i]

35 
results = centrality.weight_betweenness_centrality(subgraphs, traffic_matrix) 
36 
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 
# 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  
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 
print '*** betweenness = %s' % self.bc 
78 
# Rescale the bc according to the original graph

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

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 cutpoints

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 
if k == l:

134 
continue

135 
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 
self.compute_component_tree_weight()

174  
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 
def set_link_weight(self, comp_index, point, value): 
196 
self.Dv_B[comp_index][point] = value

197  
198 
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 blockcut 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 
print "Link Weight  For all the leaves: %s" % self.Dv_B 
228  
229 
# For other nodes in the blockcut tree

230 
level += 1

231 
while level <= max(len_B_cutpoints): 
232 
if level == 3: 
233 
debugger() 
234 
for (i, cp) in enumerate(B_cutpoints): 
235 
if len_B_cutpoints[i] == level:

236  
237 
for point in cp: 
238 
# 1st way

239 
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 
weight = self.num_vertices  1  sum(weight_shared_comp) 
247  
248 
self.Dv_B[i][point] = weight

249  
250 
# # 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 
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 
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 
pair = Q.pop(0)

275 
if pair['type'] == 'component_vertex_pair': 
276 
B_index = pair['value'][0] 
277 
v = pair['value'][1] 
278 
print' CV: %s %s' % (B_index, v) 
279 
size = len(self.bicomponents[B_index])  1; 
280 
all_cutpoints = self.bicomponents[B_index].intersection(self.cutpoints) 
281 
all_cutpoints.remove(v) 
282  
283 
for cp in all_cutpoints: 
284 
if self.get_link_weight(B_index, cp) != 1: 
285 
size += self.num_vertices  self.get_link_weight(B_index, cp)  1 
286  
287 
self.set_link_weight(B_index, v, size)

288  
289 
# update Q

290 
Q = self._find_unknown_weight_wrt_cutpoint(v, Q)

291  
292 
if pair['type'] == 'vertex_component_pair': 
293 
size = 0

294 
B_index = pair['value'][0] 
295 
v = pair['value'][1] 
296 
print' vc: %s %s' % (B_index, v) 
297 
shared_comp_indices = self._components_sharing_cutpoint(B_cutpoints, v)

298 
shared_comp_indices.remove(B_index) 
299  
300  
301 
for i in shared_comp_indices: 
302 
if self.get_link_weight(i, v) !=  1: 
303 
size += self.get_link_weight(i, v)

304  
305 
self.set_link_weight(B_index, v, self.num_vertices  1  size) 
306  
307 
# update Q

308 
Q = self._find_unknown_weight_wrt_component(B_index, Q)

309  
310 
print self.Dv_B 
311  
312 
def _inititalize_component_tree_weight(self): 
313 
Q = [] 
314 
for i, comp in enumerate(self.bicomponents): 
315 
current_cutpoints = self.cutpoints.intersection(comp)

316 
if len(current_cutpoints) == 1: 
317 
Q.append({ 
318 
'type': 'component_vertex_pair', 
319 
'value': (i, list(current_cutpoints)[0]) # (B_i, cutpoint) = (ith component, the cutpoint name) 
320 
}) 
321 
for cp in current_cutpoints: 
322 
self.set_link_weight(i, cp, 1) 
323 
return Q

324  
325 
def _find_unknown_weight_wrt_cutpoint(self, cutpoint, Q): 
326 
# Cutpoint v such that the weights of all but one of its links in T are already computed.

327 
num_of_uncomputed_weight = 0

328 
uncomputed_component_index = [] 
329  
330 
for i, Dv_B_comp in enumerate(self.Dv_B): 
331 
if cutpoint in Dv_B_comp: 
332 
if Dv_B_comp[cutpoint] == 1: 
333 
num_of_uncomputed_weight += 1

334 
uncomputed_component_index.append(i) 
335 
if num_of_uncomputed_weight == 1: 
336 
pair = { 
337 
'type': 'vertex_component_pair', 
338 
'value': (uncomputed_component_index.pop(), cutpoint)

339 
} 
340 
Q.append(pair) 
341 
print "Append WRT Cutpoint %s" % pair 
342 
return Q

343  
344 
def _find_unknown_weight_wrt_component(self, comp_index, Q): 
345 
# Component B such that weights of all but one of its links in T are already computed.

346 
Dv_B_comp = self.Dv_B[comp_index]

347 
values = Dv_B_comp.values() 
348  
349 
# Check if 1 value appear only 1 time

350 
flag = False

351 
minus_one_value = [x for x in values if x == 1] 
352 
if len(minus_one_value) == 1: 
353 
for cp, value in Dv_B_comp.iteritems(): 
354 
if value == 1: 
355 
pair = { 
356 
'type': 'component_vertex_pair', 
357 
'value': (comp_index, cp)

358 
} 
359 
Q.append(pair) 
360 
print "Append WRT Component %s" % pair 
361 
return Q

362  
363 
def __str__(self): 
364 
return str(self.Dv_B) 
365  
366 
def analyse_biconnected_component(graph): 
367 
bicomponents = list(nx.biconnected_components(graph))

368 
print bicomponents

369 
print [len(x) for x in bicomponents] 
370  
371 
def find_heuristic_bc(filepath): 
372 
pp = pprint.PrettyPrinter(indent=4)

373  
374 
graph = nx.read_weighted_edgelist(filepath) 
375  
376 
# Find biconnected components

377 
analyse_biconnected_component(graph) 
378  
379 
subgraphs = list(nx.biconnected_component_subgraphs(graph))

380 
bicomponents = list(nx.biconnected_components(graph))

381 
component_edges = list(nx.biconnected_component_edges(graph))

382 
cutpoints = set(nx.articulation_points(graph))

383  
384 
num_vertices = nx.number_of_nodes(graph) 
385  
386 
lw = LinkWeight(graph, bicomponents, cutpoints) 
387 
print 'link weight: ' 
388 
print(lw) 
389  
390 
tm = TrafficMatrix(bicomponents, cutpoints, lw) 
391 
print 'traffic matrix:' 
392 
pp.pprint(tm.h) 
393  
394 
bc = HeuristicBetweennessCentrality(subgraphs, bicomponents, cutpoints, num_vertices, lw, tm) 
395 
bc.write(file_suffix) 
396 
# print bc

397  
398 
if __name__ == '__main__': 
399 
# filepath = MAIN_CODE_DIR + '/input/simple_house.edges'

400 
# filepath = MAIN_CODE_DIR + '/input/simple2.edges'

401 
# filepath = MAIN_CODE_DIR + '/input/simple.edges'

402 
filepath = MAIN_CODE_DIR + '/input/ninux_30_1.edges'

403 
# filepath = MAIN_CODE_DIR + '/input/simple3.edges'

404 
# filepath = MAIN_CODE_DIR + '/input/simple4.edges'

405 
file_suffix = 'edge_list'

406  
407 
# Weight betweenness centrality

408 
utility.weight_betweenness_centrality(filepath, file_suffix) 
409  
410 
# Brandess betweenness centrality

411 
utility.brandes_betweenness_centrality(filepath, file_suffix) 
412  
413 
# Heuristic BC

414 
find_heuristic_bc(filepath) 