## root / globecomm / heuristic_bc / centrality_biconnected.py @ bd3d6dca

History | View | Annotate | Download (12 KB)

1 | bd3d6dca | Quynh PX Nguyen | ```
# Implement the section IV in Puzis 2012 paper
``` |
---|---|---|---|

2 | ```
# straight_lineent the section IV in Puzis 2012 paper
``` |
||

3 | ```
# Heuristic Betweenness Centrality - Partitioning to Bi-connected 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 cut-point, another vertex is not a cut-point
``` |
||

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 cut-points
``` |
||

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) = (i-th 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) |