root / fiddle / heuristic-betweenness-centrality / 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 Bi-connected 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 cut-point, another vertex is not a cut-point
|
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 cut-points
|
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 block-cut 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 block-cut 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) = (i-th 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 |
# Cut-point 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) |