Revision 3c6ce57c fiddle/heuristicbetweennesscentrality/centrality_biconnected.py
fiddle/heuristicbetweennesscentrality/centrality_biconnected.py  

2  2 
# Heuristic Betweenness Centrality  Partitioning to Biconnected Components 
3  3  
4  4 
import os 
5 
import pprint 

5  6 
import networkx as nx 
6  7 
import betweenness_centrality as centrality 
7  8 
import utility 
...  ...  
27  28 
self.finalize() 
28  29  
29  30 
def calculate_bc_non_cutpoint(self): 
30 
"""BCen for non cutpoint


31 
"""BC for non cutpoint 

31  32 
""" 
32  33 
for i, subgraphs in enumerate(self.subgraphs): 
33  34 
traffic_matrix = self.traffic_matrix[i] 
34 
results = centrality.betweenness_centrality(subgraphs, traffic_matrix, endpoints=True)


35 
results = centrality.weight_betweenness_centrality(subgraphs, traffic_matrix)


35  36 
self.bc_components.append(results) 
36  37  
37  38 
# print results 
...  ...  
58  59 
# debugger() 
59  60 
bc_locally += self.bc_components[i][v] 
60  61 
print 'locally = %s' % bc_locally 
61 
self.bc_cutpoints[v] = bc_locally  bc_inter[v] 

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 

62  65  
63  66 
def finalize(self): 
64  67 
# Add the bc for non cutpoint vertices 
...  ...  
71  74 
for key, value in self.bc_cutpoints.iteritems(): 
72  75 
self.bc[key] = value 
73  76  
77 
print '*** betweenness = %s' % self.bc 

74  78 
# Rescale the bc according to the original graph 
75 
factor = 2.0 / (self.num_vertices*self.num_vertices  3 * self.num_vertices + 2) 

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) 

76  81 
for key, value in self.bc.iteritems(): 
77  82 
self.bc[key] = value * factor 
78  83  
...  ...  
84  89  
85  90 
def __str__(self): 
86  91 
return str(self.bc) 
87 
# for bc_component in self.bc_components: 

88 
# print bc_component 

89  92  
90  93  
91  94 
class TrafficMatrix(): 
...  ...  
167  170  
168  171 
self.Dv_B = [dict() for i in range(self.num_components)] # link weight 
169  172 
self.generate_link_weight() 
173 
# self.compute_component_tree_weight() 

170  174  
171  175 
self.reverse_Dv_B = [dict() for i in range(self.num_components)] # reverse link weight 
172  176 
self.generate_reverse_link_weight() 
...  ...  
181  185 
return indices 
182  186  
183  187 
def get_link_weight(self, comp_index, point): 
184 
print "Dv_B = %s" % str(self.Dv_B) 

185  
186  188 
Dv_B_comp = self.Dv_B[comp_index] 
187  189  
188  190 
if point in Dv_B_comp: 
...  ...  
190  192 
else: 
191  193 
return 0 
192  194  
195 
def set_link_weight(self, comp_index, point, value): 

196 
self.Dv_B[comp_index][point] = value 

197  
193  198 
def get_reverse_link_weight(self, comp_index, point): 
194  199 
reverse_Dv_B_comp = self.reverse_Dv_B[comp_index] 
195  200  
...  ...  
207  212 
B_plus_v.append(comp.difference(points)) 
208  213 
B_cutpoints.append(points) 
209  214  
210 
print 'B_cutpoints %s' % str(B_cutpoints) 

211  215 
len_B_plus_v = [len(x) for x in B_plus_v] 
212  216 
len_B_cutpoints = [len(x) for x in B_cutpoints] 
213  217  
...  ...  
220  224 
point = list(cp)[0] # there is only 1 element 
221  225 
self.Dv_B[i][point] = len_B_plus_v[i] 
222  226  
223 
print 'B_cutpoints %s' % str(B_cutpoints)


227 
print "Link Weight  For all the leaves: %s" % self.Dv_B


224  228  
225  229 
# For other nodes in the blockcut tree 
226  230 
level += 1 
227  231 
while level <= max(len_B_cutpoints): 
232 
if level == 3: 

233 
debugger() 

228  234 
for (i, cp) in enumerate(B_cutpoints): 
229  235 
if len_B_cutpoints[i] == level: 
230  236  
231  237 
for point in cp: 
232 
print 'cutpoints = %s' % cp


238 
# 1st way


233  239 
shared_comp_indices = self._components_sharing_cutpoint(B_cutpoints, point) 
234  240 
shared_comp_indices.remove(i) 
235 
print 'shared indices %s' % shared_comp_indices 

236  241 
weight_shared_comp = list() 
237  242  
238  243 
for index in shared_comp_indices: 
239  244 
weight_shared_comp.append(self.get_link_weight(index, point)) 
240  245  
241 
print 'weight shared comp %s' % str(weight_shared_comp) 

242 
weight = num_vertices  1  sum(weight_shared_comp) 

246 
weight = self.num_vertices  1  sum(weight_shared_comp) 

243  247  
244  248 
self.Dv_B[i][point] = weight 
245  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  
246  257 
level += 1 
247  258  
248  259 
def generate_reverse_link_weight(self): 
...  ...  
250  261 
for key, value in Dv_B_i.iteritems(): 
251  262 
self.reverse_Dv_B[i][key] = self.num_vertices  1  self.get_link_weight(i, key) 
252  263  
253 
print 'reverse = %s' % self.reverse_Dv_B 

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 
print self.Dv_B 

275 
pair = Q.pop(0) 

276 
if pair['type'] == 'component_vertex_pair': 

277 
B_index = pair['value'][0] 

278 
v = pair['value'][1] 

279 
print' CV: %s %s' % (B_index, v) 

280 
size = len(self.bicomponents[B_index])  1; 

281 
all_cutpoints = self.bicomponents[B_index].intersection(self.cutpoints) 

282 
all_cutpoints.remove(v) 

283  
284 
for cp in all_cutpoints: 

285 
if self.get_link_weight(B_index, cp) != 1: 

286 
size += self.num_vertices  self.get_link_weight(B_index, cp) 

287  
288 
self.set_link_weight(B_index, v, size) 

289  
290 
# update Q 

291 
Q = self._find_unknown_weight_wrt_cutpoint(v, Q) 

292  
293 
if pair['type'] == 'vertex_component_pair': 

294 
size = 1 

295 
B_index = pair['value'][0] 

296 
v = pair['value'][1] 

297 
print' vc: %s %s' % (B_index, v) 

298 
shared_comp_indices = self._components_sharing_cutpoint(B_cutpoints, v) 

299 
shared_comp_indices.remove(B_index) 

300  
301  
302 
for i in shared_comp_indices: 

303 
if self.get_link_weight(i, v) !=  1: 

304 
size += self.get_link_weight(i, v) 

305  
306 
self.set_link_weight(B_index, v, self.num_vertices  1  size) 

307  
308 
# update Q 

309 
Q = self._find_unknown_weight_wrt_component(B_index, Q) 

310  
311 
def _inititalize_component_tree_weight(self): 

312 
Q = [] 

313 
for i, comp in enumerate(self.bicomponents): 

314 
current_cutpoints = self.cutpoints.intersection(comp) 

315 
if len(current_cutpoints) == 1: 

316 
Q.append({ 

317 
'type': 'component_vertex_pair', 

318 
'value': (i, list(current_cutpoints)[0]) # (B_i, cutpoint) = (ith component, the cutpoint name) 

319 
}) 

320 
for cp in current_cutpoints: 

321 
self.set_link_weight(i, cp, 1) 

322 
return Q 

323  
324 
def _find_unknown_weight_wrt_cutpoint(self, cutpoint, Q): 

325 
for i, Dv_B_comp in enumerate(self.Dv_B): 

326 
for cp, value in Dv_B_comp.iteritems(): 

327 
if value == 1: 

328 
pair = { 

329 
'type': 'vertex_component_pair', 

330 
'value': (i, cp) 

331 
} 

332 
Q.append(pair) 

333 
return Q 

334  
335 
def _find_unknown_weight_wrt_component(self, comp_index, Q): 

336 
Dv_B_comp = self.Dv_B[comp_index] 

337 
for cp, value in Dv_B_comp.iteritems(): 

338 
if value == 1: 

339 
pair = { 

340 
'type': 'component_vertex_pair', 

341 
'value': (comp_index, cp) 

342 
} 

343 
Q.append(pair) 

344 
return Q 

345  
254  346  
255  347 
def __str__(self): 
256  348 
return str(self.Dv_B) 
...  ...  
260  352 
print bicomponents 
261  353 
print [len(x) for x in bicomponents] 
262  354  
263 
if __name__ == '__main__': 

264 
filepath = MAIN_CODE_DIR + '/input/simple.edges' 

265 
file_suffix = 'edge_list' 

355 
def find_heuristic_bc(filepath): 

356 
pp = pprint.PrettyPrinter(indent=4) 

266  357  
267 
# Brandes betweenness centrality 

268 
utility.brandes_betweenness_centrality(filepath, file_suffix) 

269  
270 
# Heuristic betweenness centrality 

271  358 
graph = nx.read_weighted_edgelist(filepath) 
272  359  
273  360 
# Find biconnected components 
...  ...  
276  363 
subgraphs = list(nx.biconnected_component_subgraphs(graph)) 
277  364 
bicomponents = list(nx.biconnected_components(graph)) 
278  365 
component_edges = list(nx.biconnected_component_edges(graph)) 
279 
# cutpoints = list(nx.articulation_points(graph)) 

280  366 
cutpoints = set(nx.articulation_points(graph)) 
281  367  
282  368 
num_vertices = nx.number_of_nodes(graph) 
283  369  
284  370 
lw = LinkWeight(graph, bicomponents, cutpoints) 
285  371 
print 'link weight: ' 
286 
print lw 

372 
print(lw) 

373  
374 
# tm = TrafficMatrix(bicomponents, cutpoints, lw) 

375 
# print 'traffic matrix:' 

376 
# pp.pprint(tm.h) 

287  377  
288 
tm = TrafficMatrix(bicomponents, cutpoints, lw) 

289 
print tm 

378 
# bc = HeuristicBetweennessCentrality(subgraphs, bicomponents, cutpoints, num_vertices, lw, tm) 

379 
# bc.write(file_suffix) 

380 
# # print bc 

290  381  
382 
if __name__ == '__main__': 

383 
# filepath = MAIN_CODE_DIR + '/input/simple_house.edges' 

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

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

386 
# filepath = MAIN_CODE_DIR + '/input/ninux_30_1.edges' 

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

388 
filepath = MAIN_CODE_DIR + '/input/simple4.edges' 

389 
file_suffix = 'edge_list' 

390  
391 
# Weight betweenness centrality 

392 
utility.weight_betweenness_centrality(filepath, file_suffix) 

393  
394 
# Brandess betweenness centrality 

395 
utility.brandes_betweenness_centrality(filepath, file_suffix) 

291  396  
292 
bc = HeuristicBetweennessCentrality(subgraphs, bicomponents, cutpoints, num_vertices, lw, tm) 

293 
bc.write(file_suffix) 

294 
print bc 

397 
# Heuristic BC 

398 
find_heuristic_bc(filepath) 
Also available in: Unified diff