## 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