Revision 82c7c698 fiddle/heuristicbetweennesscentrality/betweenness_centrality.py
fiddle/heuristicbetweennesscentrality/betweenness_centrality.py  

113  113 
else: 
114  114 
random.seed(seed) 
115  115 
nodes = random.sample(G.nodes(), k) 
116 
vertices = G.nodes()


116 
vertices = sorted(G.nodes())


117  117  
118 
# print 'nodes = %s' % nodes 

119 
# print 'vertices = %s' % vertices 

120  118 
for s in nodes: 
121 
# single source shortest paths 

122 
# print '\nxxx _single_source_shortest_path' 

123  119 
if weight is None: # use BFS 
124  120 
S, P, sigma = _single_source_shortest_path_basic(G, s) 
125  121 
else: # use Dijkstra's algorithm 
126  122 
S, P, sigma = _single_source_dijkstra_path_basic(G, s, weight) 
127  123  
128 
# print s 

129 
# print S 

130 
# print P 

131 
# print sigma 

132  124 
# accumulation 
133  125 
if traffic_matrix: 
134  126 
betweenness = _accumulate_weight(betweenness, S, P, sigma, s, traffic_matrix, vertices) 
135  127 
else: 
136  128 
betweenness = _accumulate_weight_basic(betweenness, S, P, sigma, s) 
137  129  
138 
print '@@@ betweenness = %s' % betweenness 

139  130 
if rescale: 
140  131 
betweenness = _rescale(betweenness, len(G), 
141  132 
normalized=normalized, 
...  ...  
185  176 
sigma = dict.fromkeys(G, 0.0) # sigma[v]=0 for v in G 
186  177 
D = {} 
187  178 
sigma[s] = 1.0 
188 
print sigma 

189  179 
push = heappush 
190  180 
pop = heappop 
191  181 
seen = {s: 0} 
...  ...  
225  215 
delta = dict.fromkeys(S, 0) 
226  216 
while S: 
227  217 
w = S.pop() 
228 
print 'w = %s' % w 

229  218 
coeff = (1.0 + delta[w]) / sigma[w] 
230 
# coeff = (delta[w]) / sigma[w] 

231  219 
for v in P[w]: 
232 
print '\tv = %s' % v 

233  220 
h = _get_value_from_traffic_matrix(nodes, traffic_matrix, s, v) 
234 
print '\t h = %s' % h 

235  221 
delta[v] += sigma[v] * coeff + h 
236 
print 'delta = %s' % delta 

237  222 
if w != s: 
238 
# print h 

239 
# betweenness[w] += delta[w] * h 

240  223 
betweenness[w] += delta[w] 
241 
print 'betweenness = %s' % betweenness 

242 
return betweenness 

243  224  
244  225  
245  226 
def _accumulate_weight_basic(betweenness, S, P, sigma, s): 
...  ...  
254  235 
.. [1] Rami Puzis 
255  236 
Optimization of NIDS Placement for Protection of Intercommunicating Critical Infrastructures 
256  237 
""" 
257 
# betweenness[s] += len(S)  1 

258  238 
delta = dict.fromkeys(S, 0) 
259  239 
while S: 
260  240 
w = S.pop() 
...  ...  
265  245 
delta[v] += sigma[v] * coeff 
266  246 
if w != s: 
267  247 
betweenness[w] += delta[w] 
268 
# print 'out betweenness = %s' % betweenness 

269  248 
return betweenness 
270  249  
271  250 
def _accumulate_weight(betweenness, S, P, sigma, s, traffic_matrix, nodes): 
...  ...  
276  255 
.. [1] Rami Puzis 
277  256 
Optimization of NIDS Placement for Protection of Intercommunicating Critical Infrastructures 
278  257 
""" 
279 
# betweenness[s] += len(S)  1 

280  258 
delta = dict.fromkeys(S, 0) 
281  259 
while S: 
282 
# print 'in betweenness = %s' % betweenness 

283  260 
w = S.pop() 
284  261 
h = _get_value_from_traffic_matrix(nodes, traffic_matrix, s, w) 
285  262 
delta[w] += h 
286  263 
coeff = delta[w] / sigma[w] 
287 
# print " coeff = %s" % coeff 

264  
288  265 
for v in P[w]: 
289 
# print " v = %s" % v 

290 
# print " h = %s" % h 

291  266 
delta[v] += sigma[v] * coeff 
292 
# print ' delta = %s' % delta 

293  267 
if w != s: 
294  268 
betweenness[w] += delta[w] 
295 
# print 'betweenness = %s' % betweenness 

296  269 
return betweenness 
297  270  
298  271 
Also available in: Unified diff