root / fiddle / heuristicbetweennesscentrality / centrality_biconnected.py @ 3673c3e8
History  View  Annotate  Download (12.1 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, subgraphs, bicomponents, cutpoints, num_vertices, link_weight, traffic_matrix): 
17 
self.subgraphs = subgraphs

18 
self.bicomponents = bicomponents

19 
self.cutpoints = cutpoints

20 
self.num_vertices = num_vertices

21 
self.link_weight = link_weight

22 
self.traffic_matrix = traffic_matrix

23  
24 
self.bc_components = list() 
25 
self.calculate_bc_non_cutpoint()

26 
self.calculate_bc_cutpoint()

27  
28 
self.bc = dict() 
29 
self.finalize()

30  
31 
def calculate_bc_non_cutpoint(self): 
32 
"""BC for non cutpoint

33 
"""

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

36 
results = centrality.weight_betweenness_centrality(subgraphs, traffic_matrix) 
37 
self.bc_components.append(results)

38  
39 
def calculate_bc_cutpoint(self): 
40 
self.bc_cutpoints = dict() 
41  
42 
bc_inter = dict()

43 
for v in self.cutpoints: 
44 
inter = 0

45 
for i, comp in enumerate(self.bicomponents): 
46 
if v in comp: 
47 
inter += self.link_weight.get_link_weight(i, v

48 
) * self.link_weight.get_reverse_link_weight(i, v)

49 
bc_inter[v] = inter 
50  
51 
print 'XXXX bc_components = %s' % self.bc_components 
52 
print 'XXXX inter = %s' % bc_inter 
53  
54 
for v in self.cutpoints: 
55 
bc_locally = 0

56 
for i, comp in enumerate(self.bicomponents): 
57 
if v in comp: 
58 
bc_locally += self.bc_components[i][v]

59 
# self.bc_cutpoints[v] = bc_locally  bc_inter[v]

60 
# TODO: do not minus the bc_inter

61 
self.bc_cutpoints[v] = bc_locally

62  
63 
def finalize(self): 
64 
# Add the bc for non cutpoint vertices

65 
for bc_component in self.bc_components: 
66 
for key, value in bc_component.iteritems(): 
67 
if key not in self.bc: 
68 
self.bc[key] = value

69  
70 
# Add the bc for cutpoint vertices

71 
for key, value in self.bc_cutpoints.iteritems(): 
72 
self.bc[key] = value

73  
74 
print '*** betweenness = %s' % self.bc 
75 
# Rescale the bc according to the original graph

76 
factor = 1.0 / ((self.num_vertices  1) * (self.num_vertices  2)) 
77 
# TODO: check the scaling factor, how much should it be?

78 
# factor = 2.0 / (self.num_vertices*self.num_vertices  3 * self.num_vertices + 2)

79 
for key, value in self.bc.iteritems(): 
80 
self.bc[key] = value * factor

81  
82 
def write(self, file_suffix=''): 
83 
filepath = '/output/heuristic_%s.csv' % file_suffix

84 
with open(MAIN_CODE_DIR + filepath, 'w') as output: 
85 
for node, centrality in self.bc.iteritems(): 
86 
output.write('%s, %s\n' % (node, centrality))

87  
88 
def __str__(self): 
89 
return str(self.bc) 
90  
91  
92 
class TrafficMatrix(): 
93 
def __init__(self, bicomponents, cutpoints, link_weight): 
94 
self.bicomponents = bicomponents

95 
self.cutpoints = cutpoints

96 
self.num_components = len(bicomponents) 
97 
self.link_weight = link_weight

98  
99 
self.h = list() 
100 
self.generate_empty_traffic_matrix()

101 
self.generate_traffic_matrix()

102  
103 
def generate_empty_traffic_matrix(self): 
104 
for i in range(self.num_components): 
105 
l = len(self.bicomponents[i]) 
106 
matrix = [[1 for x in range(l)] for y in range(l)] 
107 
# update the main diagonal

108 
for x in range(l): 
109 
matrix[x][x] = 0

110  
111 
self.h.append(matrix)

112  
113 
def generate_traffic_matrix(self): 
114 
# Update the value when one vertex is a cutpoint, another vertex is not a cutpoint

115 
for i, components in enumerate(self.bicomponents): 
116 
normal_points = components.difference(self.cutpoints)

117 
cutpoints = self.cutpoints.intersection(components)

118  
119 
for cutpoint in cutpoints: 
120 
for normal_point in normal_points: 
121 
communication_intensity = self.link_weight.get_reverse_link_weight(i, cutpoint) + 1 
122 
self.update(i, cutpoint, normal_point, communication_intensity)

123  
124 
# Update the value when both vertices are cutpoints

125 
for i, components in enumerate(self.bicomponents): 
126 
cutpoints = list(self.cutpoints.intersection(components)) 
127 
len_cutpoints = len(cutpoints)

128 
if len_cutpoints > 1: 
129 
for k in range(len_cutpoints  1): 
130 
for l in range(1, len_cutpoints): 
131 
if k == l:

132 
continue

133 
communication_intensity = ( 
134 
self.link_weight.get_reverse_link_weight(i, cutpoints[k]) + 1) * ( 
135 
self.link_weight.get_reverse_link_weight(i, cutpoints[l]) + 1 
136 
) 
137 
self.update(i, cutpoints[k], cutpoints[l], communication_intensity)

138  
139 
def simple_update(self, comp_index, x_pos, y_pos, value): 
140 
self.h[comp_index][x_pos][y_pos] = value

141 
# to keep the symmetric property of Traffic Matrix

142 
self.h[comp_index][y_pos][x_pos] = value

143  
144 
def update(self, comp_index, x, y, value): 
145 
comp = sorted(self.bicomponents[comp_index]) 
146 
try:

147 
x_pos = list(comp).index(x)

148 
y_pos = list(comp).index(y)

149 
except:

150 
debugger() 
151 
a = 2

152  
153 
self.simple_update(comp_index, x_pos, y_pos, value)

154  
155 
def __str__(self): 
156 
return str(self.h) 
157  
158 
def __getitem__(self, key): 
159 
return self.h[key] 
160  
161  
162 
class LinkWeight(): 
163 
def __init__(self, graph, bicomponents, cutpoints): 
164 
self.num_vertices = nx.number_of_nodes(graph)

165 
self.bicomponents = bicomponents

166 
self.num_components = len(bicomponents) 
167 
self.cutpoints = cutpoints

168  
169 
self.Dv_B = [dict() for i in range(self.num_components)] # link weight 
170 
self.compute_component_tree_weight()

171  
172 
self.reverse_Dv_B = [dict() for i in range(self.num_components)] # reverse link weight 
173 
self.generate_reverse_link_weight()

174  
175 
def _components_sharing_cutpoint(self, B_cutpoints, point): 
176 
indices = list()

177 
for i, cp in enumerate(B_cutpoints): 
178 
if point in cp: 
179 
indices.append(i) 
180  
181 
return indices

182  
183 
def get_link_weight(self, comp_index, point): 
184 
Dv_B_comp = self.Dv_B[comp_index]

185  
186 
if point in Dv_B_comp: 
187 
return Dv_B_comp[point]

188 
else:

189 
return 0 
190  
191 
def set_link_weight(self, comp_index, point, value): 
192 
self.Dv_B[comp_index][point] = value

193  
194 
def get_reverse_link_weight(self, comp_index, point): 
195 
reverse_Dv_B_comp = self.reverse_Dv_B[comp_index]

196  
197 
if point in reverse_Dv_B_comp: 
198 
return reverse_Dv_B_comp[point]

199 
else:

200 
return 0 
201  
202 
def generate_reverse_link_weight(self): 
203 
for i, Dv_B_i in enumerate(self.Dv_B): 
204 
for key, value in Dv_B_i.iteritems(): 
205 
self.reverse_Dv_B[i][key] = self.num_vertices  1  self.get_link_weight(i, key) 
206  
207 
def compute_component_tree_weight(self): 
208 
"""Follows exactly the Algorithm 1 [Puzis 2012]

209 
"""

210 
B_cutpoints = list() # number of cutpoints in component B 
211 
for comp in self.bicomponents: 
212 
points = comp.intersection(self.cutpoints)

213 
B_cutpoints.append(points) 
214  
215 
Q = self._inititalize_component_tree_weight()

216 
print "finish initialization\n" 
217 
while Q:

218 
pair = Q.pop(0)

219 
if pair['type'] == 'component_vertex_pair': 
220 
B_index = pair['value'][0] 
221 
v = pair['value'][1] 
222 
size = len(self.bicomponents[B_index])  1; 
223 
all_cutpoints = self.bicomponents[B_index].intersection(self.cutpoints) 
224 
all_cutpoints.remove(v) 
225  
226 
for cp in all_cutpoints: 
227 
if self.get_link_weight(B_index, cp) != 1: 
228 
size += self.num_vertices  self.get_link_weight(B_index, cp)  1 
229  
230 
link_weight = size 
231 
self._verify_link_weight(B_index, v, link_weight)

232 
self.set_link_weight(B_index, v, link_weight)

233  
234 
# update Q

235 
Q = self._find_unknown_weight_wrt_cutpoint(v, Q)

236  
237 
if pair['type'] == 'vertex_component_pair': 
238 
size = 0

239 
B_index = pair['value'][0] 
240 
v = pair['value'][1] 
241 
shared_comp_indices = self._components_sharing_cutpoint(B_cutpoints, v)

242 
shared_comp_indices.remove(B_index) 
243  
244  
245 
for i in shared_comp_indices: 
246 
if self.get_link_weight(i, v) !=  1: 
247 
size += self.get_link_weight(i, v)

248  
249 
link_weight = self.num_vertices  1  size 
250 
self._verify_link_weight(B_index, v, link_weight)

251 
self.set_link_weight(B_index, v, link_weight)

252  
253 
# update Q

254 
Q = self._find_unknown_weight_wrt_component(B_index, Q)

255  
256 
def _verify_link_weight(self, B_index, v, value): 
257 
""" If the old_value exist in self.Dv_B, then it must be equal to new value

258 

259 
Otherwise, do nothing

260 
"""

261 
old_value = self.get_link_weight(B_index, v)

262  
263 
if old_value != 1: # 1 is unknown 
264 
if old_value != value:

265 
print "BUGS FOUND in _verify_link_weight()" 
266 
sys.exit() 
267  
268  
269 
def _inititalize_component_tree_weight(self): 
270 
Q = [] 
271 
for i, comp in enumerate(self.bicomponents): 
272 
current_cutpoints = self.cutpoints.intersection(comp)

273 
if len(current_cutpoints) == 1: 
274 
Q.append({ 
275 
'type': 'component_vertex_pair', 
276 
'value': (i, list(current_cutpoints)[0]) # (B_i, cutpoint) = (ith component, the cutpoint name) 
277 
}) 
278 
print "added component_vertex_pair(%s, %s)" % (i, list(current_cutpoints)[0]) 
279 
for cp in current_cutpoints: 
280 
self.set_link_weight(i, cp, 1) 
281 
return Q

282  
283 
def _find_unknown_weight_wrt_cutpoint(self, cutpoint, Q): 
284 
print "_find_unknown_weight_wrt_cutpoint %s" % cutpoint 
285  
286 
# Cutpoint v such that the weights of all but one of its links in T are already computed.

287 
num_of_uncomputed_weight = 0

288 
uncomputed_component_index = [] 
289  
290 
for i, Dv_B_comp in enumerate(self.Dv_B): 
291 
if cutpoint in Dv_B_comp: 
292 
if Dv_B_comp[cutpoint] == 1: 
293 
num_of_uncomputed_weight += 1

294 
print " %i" % i 
295 
uncomputed_component_index.append(i) 
296 
if num_of_uncomputed_weight > 1: 
297 
break

298  
299 
if num_of_uncomputed_weight == 1: 
300 
pair = { 
301 
'type': 'vertex_component_pair', 
302 
'value': (uncomputed_component_index.pop(), cutpoint)

303 
} 
304 
print " Added vertex_component_pair (%s, %s)" % pair['value']; 
305 
Q.append(pair) 
306 
return Q

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

310 
Dv_B_comp = self.Dv_B[comp_index]

311 
values = Dv_B_comp.values() 
312  
313 
# Check if 1 value appear only 1 time

314 
flag = False

315 
minus_one_value = [x for x in values if x == 1] 
316 
if len(minus_one_value) == 1: 
317 
for cp, value in Dv_B_comp.iteritems(): 
318 
if value == 1: 
319 
pair = { 
320 
'type': 'component_vertex_pair', 
321 
'value': (comp_index, cp)

322 
} 
323 
print "Added component_vertex_pair (%s, %s)" % pair['value']; 
324 
Q.append(pair) 
325 
return Q

326  
327 
def __str__(self): 
328 
return str(self.Dv_B) 
329 