commit 82c7c698645c5f140850f115615f25d9cda38018
Author: Quynh PX Nguyen
Date: Wed Dec 30 04:33:43 2015 +0700
[f] WBBC = HBC :)
diff --git a/fiddle/heuristic-betweenness-centrality/betweenness_centrality.py b/fiddle/heuristic-betweenness-centrality/betweenness_centrality.py
index 7347111..532221b 100644
--- a/fiddle/heuristic-betweenness-centrality/betweenness_centrality.py
+++ b/fiddle/heuristic-betweenness-centrality/betweenness_centrality.py
@@ -113,29 +113,20 @@ def weight_betweenness_centrality(G, traffic_matrix=None, k=None, normalized=Tru
else:
random.seed(seed)
nodes = random.sample(G.nodes(), k)
- vertices = G.nodes()
+ vertices = sorted(G.nodes())
- # print 'nodes = %s' % nodes
- # print 'vertices = %s' % vertices
for s in nodes:
- # single source shortest paths
- # print '\nxxx _single_source_shortest_path'
if weight is None: # use BFS
S, P, sigma = _single_source_shortest_path_basic(G, s)
else: # use Dijkstra's algorithm
S, P, sigma = _single_source_dijkstra_path_basic(G, s, weight)
- # print s
- # print S
- # print P
- # print sigma
# accumulation
if traffic_matrix:
betweenness = _accumulate_weight(betweenness, S, P, sigma, s, traffic_matrix, vertices)
else:
betweenness = _accumulate_weight_basic(betweenness, S, P, sigma, s)
- print '@@@ betweenness = %s' % betweenness
if rescale:
betweenness = _rescale(betweenness, len(G),
normalized=normalized,
@@ -185,7 +176,6 @@ def _single_source_dijkstra_path_basic(G, s, weight='weight'):
sigma = dict.fromkeys(G, 0.0) # sigma[v]=0 for v in G
D = {}
sigma[s] = 1.0
- print sigma
push = heappush
pop = heappop
seen = {s: 0}
@@ -225,21 +215,12 @@ def _accumulate_basic(betweenness, S, P, sigma, s, traffic_matrix, nodes):
delta = dict.fromkeys(S, 0)
while S:
w = S.pop()
- print 'w = %s' % w
coeff = (1.0 + delta[w]) / sigma[w]
- # coeff = (delta[w]) / sigma[w]
for v in P[w]:
- print '\tv = %s' % v
h = _get_value_from_traffic_matrix(nodes, traffic_matrix, s, v)
- print '\t h = %s' % h
delta[v] += sigma[v] * coeff + h
- print 'delta = %s' % delta
if w != s:
- # print h
- # betweenness[w] += delta[w] * h
betweenness[w] += delta[w]
- print 'betweenness = %s' % betweenness
- return betweenness
def _accumulate_weight_basic(betweenness, S, P, sigma, s):
@@ -254,7 +235,6 @@ def _accumulate_weight_basic(betweenness, S, P, sigma, s):
.. [1] Rami Puzis
Optimization of NIDS Placement for Protection of Intercommunicating Critical Infrastructures
"""
- # betweenness[s] += len(S) - 1
delta = dict.fromkeys(S, 0)
while S:
w = S.pop()
@@ -265,7 +245,6 @@ def _accumulate_weight_basic(betweenness, S, P, sigma, s):
delta[v] += sigma[v] * coeff
if w != s:
betweenness[w] += delta[w]
- # print 'out betweenness = %s' % betweenness
return betweenness
def _accumulate_weight(betweenness, S, P, sigma, s, traffic_matrix, nodes):
@@ -276,23 +255,17 @@ def _accumulate_weight(betweenness, S, P, sigma, s, traffic_matrix, nodes):
.. [1] Rami Puzis
Optimization of NIDS Placement for Protection of Intercommunicating Critical Infrastructures
"""
- # betweenness[s] += len(S) - 1
delta = dict.fromkeys(S, 0)
while S:
- # print 'in betweenness = %s' % betweenness
w = S.pop()
h = _get_value_from_traffic_matrix(nodes, traffic_matrix, s, w)
delta[w] += h
coeff = delta[w] / sigma[w]
- # print " coeff = %s" % coeff
+
for v in P[w]:
- # print " v = %s" % v
- # print " h = %s" % h
delta[v] += sigma[v] * coeff
- # print ' delta = %s' % delta
if w != s:
betweenness[w] += delta[w]
- # print 'betweenness = %s' % betweenness
return betweenness