1 """
2 Centrality measures.
3
4 """
5
6
7
8
9
10
11 __author__ = """Aric Hagberg (hagberg@lanl.gov)\nPieter Swart (swart@lanl.gov)\nSasha Gutfraind (ag362@cornell.edu)"""
12
13 from networkx.path import dijkstra_predecessor_and_distance, predecessor
14
15
17 """Compute the betweenness centrality for nodes in G:
18 the fraction of number of shortests paths that pass through each node.
19
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.
23
24 The keyword weighted_edges (default=False) specifies whether
25 to use edge weights (otherwise weights are all assumed equal).
26
27 The algorithm is from
28 Ulrik Brandes,
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
32
33 """
34 import heapq
35 betweenness=dict.fromkeys(G,0.0)
36 for s in G:
37 S=[]
38 P={}
39 for v in G:
40 P[v]=[]
41 sigma=dict.fromkeys(G,0)
42 D={}
43 sigma[s]=1
44 if not weighted_edges:
45 D[s]=0
46 Q=[s]
47 while Q:
48 v=Q.pop(0)
49 S.append(v)
50 for w in G.neighbors(v):
51
52 if w not in D:
53 Q.append(w)
54 D[w]=D[v]+1
55 if D[w]==D[v]+1:
56 sigma[w]=sigma[w]+sigma[v]
57 P[w].append(v)
58 else:
59
60 push=heapq.heappush
61 pop=heapq.heappop
62 seen = {s:0}
63 Q=[]
64 push(Q,(0,s,s))
65 while Q:
66 (dist,pred,v)=pop(Q)
67 if v in D:
68 continue
69 sigma[v]=sigma[v]+sigma[pred]
70 S.append(v)
71 D[v] = seen[v]
72
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]):
76 seen[w] = vw_dist
77 push(Q,(vw_dist,v,w))
78 P[w]=[v]
79 elif vw_dist==seen[w]:
80 sigma[w]=sigma[w]+sigma[v]
81 P[w].append(v)
82
83
84 delta=dict.fromkeys(G,0)
85 while S:
86 w=S.pop()
87 for v in P[w]:
88 delta[v]=delta[v]+\
89 (float(sigma[v])/float(sigma[w]))*(1.0+delta[w])
90 if w != s:
91 betweenness[w]=betweenness[w]+delta[w]
92
93
94 if normalized:
95 order=len(betweenness)
96 if order <=2:
97 return betweenness
98 scale=1.0/((order-1)*(order-2))
99 for v in betweenness:
100 betweenness[v] *= scale
101
102 return betweenness
103
104
105
109 """
110 "Load" centrality for nodes.
111
112 This actually computes 'load' and not betweenness.
113 See https://networkx.lanl.gov/ticket/103
114
115 The fraction of number of shortests paths that go
116 through each node counted according to the algorithm in
117
118 Scientific collaboration networks: II.
119 Shortest paths, weighted networks, and centrality,
120 M. E. J. Newman, Phys. Rev. E 64, 016132 (2001).
121
122 Returns a dictionary of betweenness values keyed by node.
123 The betweenness is normalized to be between [0,1].
124
125 If normalized=False the resulting betweenness is not normalized.
126
127 If weighted_edges is True then use Dijkstra for finding shortest paths.
128
129
130 """
131 if v is not None:
132 betweenness=0.0
133 for source in G:
134 ubetween=_node_betweenness(G,source,
135 cutoff=cutoff,
136 normalized=normalized,
137 weighted_edges=weighted_edges)
138 betweenness+=ubetween[v]
139 return betweenness
140 else:
141 betweenness={}.fromkeys(G,0.0)
142 for source in betweenness:
143 ubetween=_node_betweenness(G,source,
144 cutoff=cutoff,
145 normalized=False,
146 weighted_edges=weighted_edges)
147 for vk in ubetween:
148 betweenness[vk]+=ubetween[vk]
149 if normalized:
150 order=len(betweenness)
151 if order <=2:
152 return betweenness
153 scale=1.0/((order-1)*(order-2))
154 for v in betweenness:
155 betweenness[v] *= scale
156 return betweenness
157
159 """Node betweenness helper:
160 see betweenness_centrality for what you probably want.
161
162 This actually computes "load" and not betweenness.
163 See https://networkx.lanl.gov/ticket/103
164
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
167 through each node.)
168
169 To get the load for a node you need to do all-pairs shortest paths.
170
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.
173
174 """
175
176
177 if weighted_edges:
178 (pred,length)=dijkstra_predecessor_and_distance(G,source)
179 else:
180 (pred,length)=predecessor(G,source,cutoff=cutoff,return_seen=True)
181
182
183 onodes = [ (l,vert) for (vert,l) in length.items() ]
184 onodes.sort()
185 onodes[:] = [vert for (l,vert) in onodes if l>0]
186
187
188 between={}.fromkeys(length,1.0)
189
190 while onodes:
191 v=onodes.pop()
192 if v in pred:
193 num_paths=len(pred[v])
194 for x in pred[v]:
195 if x==source:
196 break
197 between[x]+=between[v]/float(num_paths)
198
199 for v in between:
200 between[v]-=1
201
202 if normalized:
203 l=len(between)
204 if l > 2:
205 scale=1.0/float((l-1)*(l-2))
206 for v in between:
207 between[v] *= scale
208 return between
209
210 betweenness_centrality=brandes_betweenness_centrality
211
212 load_centrality=newman_betweenness_centrality
213
217 """
218 Enchanced version of the method in centrality module that allows
219 specifying a list of sources (subgraph).
220
221 weighted_edges:: consider edge weights by running Dijkstra's algorithm (no effect on unweighted graphs).
222
223 sources:: list of nodes to consider as subgraph
224
225 See Sec. 4 in
226 Ulrik Brandes,
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
230
231
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.
234 """
235 import heapq
236
237 if sources == None:
238 sources = G.nodes()
239
240 betweenness=dict.fromkeys(G,0.0)
241 for s in sources:
242 S,P,D,sigma = _brandes_betweenness_helper(G,s,weighted_edges)
243
244 delta=dict.fromkeys(G,0)
245 while S:
246 w=S.pop()
247 for v in P[w]:
248 delta[v] = delta[v] + \
249 (float(sigma[v])/float(sigma[w]))*(1.0+delta[w])
250 if w == s:
251 continue
252 betweenness[w] = betweenness[w] + delta[w]
253
254
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
260
261 return betweenness
262
263
265 """
266 Edge betweenness centrality.
267
268 weighted_edges:: consider edge weights by running Dijkstra's algorithm (no effect on unweighted graphs).
269
270 sources:: list of nodes to consider as subgraph
271
272 """
273 import heapq
274
275 if sources == None:
276 sources = G.nodes()
277
278 if not weighted_edges:
279 betweenness=dict.fromkeys(G.edges(),0.0)
280 else:
281 betweenness=dict.fromkeys(map(lambda x:x[0:2], G.edges()), 0.0)
282
283 if G.is_directed():
284 for s in sources:
285 S, P, D, sigma =_brandes_betweenness_helper(G,s,weighted_edges)
286 delta=dict.fromkeys(G,0.0)
287 while S:
288 w=S.pop()
289 for v in P[w]:
290 edgeFlow = (float(sigma[v])/float(sigma[w]))*(1.0+delta[w])
291 edge = (v,w)
292 delta[v] += edgeFlow
293 betweenness[edge] += edgeFlow
294 else:
295 for s in sources:
296 S, P, D, sigma =_brandes_betweenness_helper(G,s,weighted_edges)
297 delta=dict.fromkeys(G,0.0)
298 while S:
299 w=S.pop()
300 for v in P[w]:
301 edgeFlow = (float(sigma[v])/float(sigma[w]))*(1.0+delta[w])
302 if betweenness.has_key((v,w)):
303 edge = (v,w)
304 else:
305 edge = (w,v)
306 delta[v] += edgeFlow
307 betweenness[edge] += edgeFlow
308
309
310 if normalized and G.number_of_edges() > 1:
311
312 order=len(betweenness)
313 scale=1.0/((order-1)*(order-2))
314 for edge in betweenness:
315 betweenness[edge] *= scale
316
317 return betweenness
318
319
321 """
322 Helper for betweenness centrality and edge betweenness centrality.
323
324 Runs single-source shortest path from root node.
325
326 weighted_edges:: consider edge weights
327
328 Finds::
329
330 S=[] list of nodes reached during traversal
331 P={} predecessors, keyed by child node
332 D={} distances
333 sigma={} indexed by node, is the number of paths to root
334 going through the node
335 """
336 import heapq
337 S=[]
338 P={}
339 for v in G:
340 P[v]=[]
341 sigma=dict.fromkeys(G,0.0)
342 D={}
343 sigma[root]=1
344
345 if not weighted_edges:
346 D[root]=0
347 Q=[root]
348 while Q:
349 v=Q.pop(0)
350 S.append(v)
351 for w in G.neighbors(v):
352 if w not in D:
353 Q.append(w)
354 D[w]=D[v]+1
355 if D[w]==D[v]+1:
356 sigma[w]=sigma[w]+sigma[v]
357 P[w].append(v)
358 else:
359
360 push=heapq.heappush
361 pop=heapq.heappop
362 seen = {root:0}
363 Q=[]
364 push(Q,(0,root,root))
365 while Q:
366 (dist,pred,v)=pop(Q)
367 if v in D:
368 continue
369 sigma[v]=sigma[v]+sigma[pred]
370 S.append(v)
371 D[v] = seen[v]
372
373 for w in G.neighbors(v):
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]):
376 seen[w] = vw_dist
377 push(Q,(vw_dist,v,w))
378 P[w]=[v]
379 elif vw_dist==seen[w]:
380 sigma[w]=sigma[w]+sigma[v]
381 P[w].append(v)
382 return S, P, D, sigma
383
384
385
386
388 """
389 Edge Betweenness
390
391 WARNING:
392
393 This module is for demonstration and testing purposes.
394
395 """
396 betweenness={}
397 if not nodes:
398 nodes=G.nodes()
399 for source in nodes:
400 ubetween=_edge_betweenness(G,source,nodes,cutoff=cutoff)
401 for v in ubetween.keys():
402 b=betweenness.setdefault(v,0)
403 betweenness[v]=ubetween[v]+b
404 return betweenness
405
407 """
408 Edge betweenness helper.
409 """
410 between={}
411
412
413 from networkx.path import predecessor
414 (pred,length)=predecessor(G,source,cutoff=cutoff,return_seen=True)
415
416 onodes = map(lambda k: (length[k], k), length.keys())
417 onodes.sort()
418 onodes[:] = [val for (key, val) in onodes]
419
420 for e in G.edges(nodes):
421 u,v=e[0],e[1]
422 between[(u,v)]=1.0
423 between[(v,u)]=1.0
424
425 while onodes:
426 v=onodes.pop()
427 if (pred.has_key(v)):
428 num_paths=len(pred[v])
429 for w in pred[v]:
430 if (pred.has_key(w)):
431 num_paths=len(pred[w])
432 for x in pred[w]:
433 between[(w,x)]+=between[(v,w)]/num_paths
434 between[(x,w)]+=between[(w,v)]/num_paths
435 return between
436
438 """
439 Degree centrality for nodes (fraction of nodes connected to).
440
441 Returns a dictionary of degree centrality values keyed by node.
442
443 The degree centrality is normalized to the maximum possible degree
444 in the graph G.
445
446 """
447 degree_centrality={}
448 deg=G.degree(with_labels=True)
449 s=1.0/(G.order()-1.0)
450 for vk in deg:
451 degree_centrality[vk]=deg[vk]*s
452
453 if v is None:
454 return degree_centrality
455 else:
456 return degree_centrality[v]
457
485
486
488 import doctest
489 suite = doctest.DocFileSuite('tests/centrality.txt',package='networkx')
490 return suite
491
492
493
494
495 if __name__ == "__main__":
496 import os
497 import sys
498 import unittest
499
500 if sys.version_info[:2] < (2, 4):
501 print "Python version 2.4 or later required for tests (%d.%d detected)." % sys.version_info[:2]
502 sys.exit(-1)
503
504 nxbase=sys.path[0]+os.sep+os.pardir
505 sys.path.insert(0,nxbase)
506 unittest.TextTestRunner().run(_test_suite())
507