5
# Copyright (C) 2004,2005 by
5
# Copyright (C) 2004-2007 by
6
6
# Aric Hagberg <hagberg@lanl.gov>
7
7
# Dan Schult <dschult@colgate.edu>
8
8
# Pieter Swart <swart@lanl.gov>
9
9
# Distributed under the terms of the GNU Lesser General Public License
10
10
# http://www.gnu.org/copyleft/lesser.html
11
__author__ = """Aric Hagberg (hagberg@lanl.gov)\nPieter Swart (swart@lanl.gov)"""
12
__date__ = "$Date: 2005-07-06 08:02:28 -0600 (Wed, 06 Jul 2005) $"
14
__revision__ = "$Revision: 1064 $"
16
def betweenness_centrality(G,v=False,cutoff=False,normalized=True):
17
"""Betweenness centrality for nodes.
11
__author__ = """Aric Hagberg (hagberg@lanl.gov)\nPieter Swart (swart@lanl.gov)\nSasha Gutfraind (ag362@cornell.edu)"""
13
from networkx.path import dijkstra_predecessor_and_distance, predecessor
16
def brandes_betweenness_centrality(G,normalized=True,weighted_edges=False):
17
"""Compute the betweenness centrality for nodes in G:
18
the fraction of number of shortests paths that pass through each node.
20
The keyword normalized (default=True) specifies whether the
21
betweenness values are normalized by b=b/(n-1)(n-2) where
22
n is the number of nodes in G.
24
The keyword weighted_edges (default=False) specifies whether
25
to use edge weights (otherwise weights are all assumed equal).
29
A Faster Algorithm for Betweenness Centrality.
30
Journal of Mathematical Sociology 25(2):163-177, 2001.
31
http://www.inf.uni-konstanz.de/algo/publications/b-fabc-01.pdf
35
betweenness=dict.fromkeys(G,0.0) # b[v]=0 for v in G
41
sigma=dict.fromkeys(G,0) # sigma[v]=0 for v in G
44
if not weighted_edges: # use BFS
47
while Q: # use BFS to find shortest paths
50
for w in G.neighbors(v):
51
# for w in G.adj[v]: # speed hack, exposes internals
55
if D[w]==D[v]+1: # this is a shortest path, count paths
56
sigma[w]=sigma[w]+sigma[v]
57
P[w].append(v) # predecessors
58
else: # use Dijkstra's algorithm for shortest paths,
59
# modified from Eppstein
63
Q=[] # use Q as heap with (distance,node id) tuples
68
continue # already searched this node.
69
sigma[v]=sigma[v]+sigma[pred] # count paths
72
# for w in G.adj[v]: # speed hack, exposes internals
73
for w in G.neighbors(v):
74
vw_dist = D[v] + G.get_edge(v,w)
75
if w not in D and (w not in seen or vw_dist < seen[w]):
79
elif vw_dist==seen[w]: # handle equal paths
80
sigma[w]=sigma[w]+sigma[v]
84
delta=dict.fromkeys(G,0)
89
(float(sigma[v])/float(sigma[w]))*(1.0+delta[w])
91
betweenness[w]=betweenness[w]+delta[w]
95
order=len(betweenness)
97
return betweenness # no normalization b=0 for all nodes
98
scale=1.0/((order-1)*(order-2))
100
betweenness[v] *= scale
106
def newman_betweenness_centrality(G,v=None,cutoff=None,
108
weighted_edges=False):
110
"Load" centrality for nodes.
112
This actually computes 'load' and not betweenness.
113
See https://networkx.lanl.gov/ticket/103
18
115
The fraction of number of shortests paths that go
116
through each node counted according to the algorithm in
118
Scientific collaboration networks: II.
119
Shortest paths, weighted networks, and centrality,
120
M. E. J. Newman, Phys. Rev. E 64, 016132 (2001).
21
122
Returns a dictionary of betweenness values keyed by node.
22
123
The betweenness is normalized to be between [0,1].
23
The algorithm is described in [brandes-2003-faster]_.
25
125
If normalized=False the resulting betweenness is not normalized.
29
.. [brandes-2003-faster] Ulrik Brandes,
30
Faster Evaluation of Shortest-Path Based Centrality Indices, 2003,
31
available at http://citeseer.nj.nec.com/brandes00faster.html
127
If weighted_edges is True then use Dijkstra for finding shortest paths.
36
for source in G.nodes():
37
ubetween=_node_betweenness(G,source,cutoff=cutoff,normalized=normalized )
131
if v is not None: # only one node
134
ubetween=_node_betweenness(G,source,
136
normalized=normalized,
137
weighted_edges=weighted_edges)
38
138
betweenness+=ubetween[v]
39
139
return betweenness
41
betweenness={}.fromkeys(G.nodes(),0)
141
betweenness={}.fromkeys(G,0.0)
42
142
for source in betweenness:
43
ubetween=_node_betweenness(G,source,cutoff=cutoff,normalized=False)
143
ubetween=_node_betweenness(G,source,
146
weighted_edges=weighted_edges)
44
147
for vk in ubetween:
45
148
betweenness[vk]+=ubetween[vk]
47
150
order=len(betweenness)
152
return betweenness # no normalization b=0 for all nodes
48
153
scale=1.0/((order-1)*(order-2))
49
154
for v in betweenness:
50
155
betweenness[v] *= scale
51
156
return betweenness # all nodes
53
def _node_betweenness(G,source,cutoff=False,normalized=True):
54
"""See betweenness_centrality for what you probably want.
56
This is betweenness for a single node.
57
The fraction of number of shortests paths from source that go
60
To get the betweenness for a node you need to do all-pairs
158
def _node_betweenness(G,source,cutoff=False,normalized=True,weighted_edges=False):
159
"""Node betweenness helper:
160
see betweenness_centrality for what you probably want.
162
This actually computes "load" and not betweenness.
163
See https://networkx.lanl.gov/ticket/103
165
This calculates the load of each node for paths from a single source.
166
(The fraction of number of shortests paths from source that go
169
To get the load for a node you need to do all-pairs shortest paths.
171
If weighted_edges is True then use Dijkstra for finding shortest paths.
172
In this case a cutoff is not implemented and so is ignored.
64
176
# get the predecessor and path length data
65
(pred,length)=_fast_predecessor(G,source,cutoff)
178
(pred,length)=dijkstra_predecessor_and_distance(G,source)
180
(pred,length)=predecessor(G,source,cutoff=cutoff,return_seen=True)
67
182
# order the nodes by path length
68
183
onodes = [ (l,vert) for (vert,l) in length.items() ]
70
onodes[:] = [vert for (l,vert) in onodes]
185
onodes[:] = [vert for (l,vert) in onodes if l>0]
72
187
# intialize betweenness
73
188
between={}.fromkeys(length,1.0)
74
# work through all paths
79
193
num_paths=len(pred[v]) # Discount betweenness if more than
80
194
for x in pred[v]: # one shortest path.
81
if x==source: # stop if hit source because all remaining v
82
break # also have pred[v]==[source]
83
between[x]+=between[v]/num_paths
195
if x==source: # stop if hit source because all remaining v
196
break # also have pred[v]==[source]
197
between[x]+=between[v]/float(num_paths)
86
201
# rescale to be between 0 and 1
92
207
between[v] *= scale
95
def edge_betweenness(G,nodes=False,cutoff=False):
210
betweenness_centrality=brandes_betweenness_centrality
212
load_centrality=newman_betweenness_centrality
214
def betweenness_centrality_source(G,normalized=True,
215
weighted_edges=False,
218
Enchanced version of the method in centrality module that allows
219
specifying a list of sources (subgraph).
221
weighted_edges:: consider edge weights by running Dijkstra's algorithm (no effect on unweighted graphs).
223
sources:: list of nodes to consider as subgraph
227
A Faster Algorithm for Betweenness Centrality.
228
Journal of Mathematical Sociology 25(2):163-177, 2001.
229
http://www.inf.uni-konstanz.de/algo/publications/b-fabc-01.pdf
232
This algorithm does not count the endpoints, i.e.
233
a path from s to t does not contribute to the betweenness of s and t.
240
betweenness=dict.fromkeys(G,0.0)
242
S,P,D,sigma = _brandes_betweenness_helper(G,s,weighted_edges)
244
delta=dict.fromkeys(G,0) # unnormalized betweenness
248
delta[v] = delta[v] + \
249
(float(sigma[v])/float(sigma[w]))*(1.0+delta[w])
252
betweenness[w] = betweenness[w] + delta[w]
254
# normalize to size of entire graph
255
if normalized and G.number_of_edges() > 1:
256
order=len(betweenness)
257
scale=1.0/((order-1)*(order-2))
258
for v in betweenness:
259
betweenness[v] *= scale
264
def edge_betweenness(G,normalized=True,weighted_edges=False,sources=None):
266
Edge betweenness centrality.
268
weighted_edges:: consider edge weights by running Dijkstra's algorithm (no effect on unweighted graphs).
270
sources:: list of nodes to consider as subgraph
278
if not weighted_edges:
279
betweenness=dict.fromkeys(G.edges(),0.0)
281
betweenness=dict.fromkeys(map(lambda x:x[0:2], G.edges()), 0.0)
285
S, P, D, sigma =_brandes_betweenness_helper(G,s,weighted_edges)
286
delta=dict.fromkeys(G,0.0)
290
edgeFlow = (float(sigma[v])/float(sigma[w]))*(1.0+delta[w])
293
betweenness[edge] += edgeFlow
296
S, P, D, sigma =_brandes_betweenness_helper(G,s,weighted_edges)
297
delta=dict.fromkeys(G,0.0)
301
edgeFlow = (float(sigma[v])/float(sigma[w]))*(1.0+delta[w])
302
if betweenness.has_key((v,w)):
307
betweenness[edge] += edgeFlow
310
if normalized and G.number_of_edges() > 1:
311
# normalize to size of entire graph (beware of disconnected components)
312
order=len(betweenness)
313
scale=1.0/((order-1)*(order-2))
314
for edge in betweenness:
315
betweenness[edge] *= scale
320
def _brandes_betweenness_helper(G,root,weighted_edges):
322
Helper for betweenness centrality and edge betweenness centrality.
324
Runs single-source shortest path from root node.
326
weighted_edges:: consider edge weights
330
S=[] list of nodes reached during traversal
331
P={} predecessors, keyed by child node
333
sigma={} indexed by node, is the number of paths to root
334
going through the node
341
sigma=dict.fromkeys(G,0.0)
345
if not weighted_edges: # use BFS
348
while Q: # use BFS to find shortest paths
351
for w in G.neighbors(v): # for w in G.adj[v]: # speed hack, exposes internals
355
if D[w]==D[v]+1: # this is a shortest path, count paths
356
sigma[w]=sigma[w]+sigma[v]
357
P[w].append(v) # predecessors
358
else: # use Dijkstra's algorithm for shortest paths,
359
# modified from Eppstein
363
Q=[] # use Q as heap with (distance,node id) tuples
364
push(Q,(0,root,root))
368
continue # already searched this node.
369
sigma[v]=sigma[v]+sigma[pred] # count paths
372
# for w in G.adj[v]: # speed hack, exposes internals
373
for w in G.neighbors(v): # for w in G.adj[v]: # speed hack, exposes internals
374
vw_dist = D[v] + G.get_edge(v,w)
375
if w not in D and (w not in seen or vw_dist < seen[w]):
377
push(Q,(vw_dist,v,w))
379
elif vw_dist==seen[w]: # handle equal paths
380
sigma[w]=sigma[w]+sigma[v]
382
return S, P, D, sigma
387
def edge_load(G,nodes=False,cutoff=False):
added
removed
networkx/centrality.py
