Revision 82c7c698 fiddle/heuristic-betweenness-centrality/betweenness_centrality.py

View differences:

fiddle/heuristic-betweenness-centrality/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