ioftools / networkxMiCe / networkxmaster / networkx / algorithms / centrality / closeness.py @ 5cef0f13
History  View  Annotate  Download (4.56 KB)
1 
# Copyright (C) 20042019 by


2 
# Aric Hagberg <hagberg@lanl.gov>

3 
# Dan Schult <dschult@colgate.edu>

4 
# Pieter Swart <swart@lanl.gov>

5 
# All rights reserved.

6 
# BSD license.

7 
#

8 
# Authors: Aric Hagberg <aric.hagberg@gmail.com>

9 
# Pieter Swart <swart@lanl.gov>

10 
# Sasha Gutfraind <ag362@cornell.edu>

11 
# Dan Schult <dschult@colgate.edu>

12 
"""

13 
Closeness centrality measures.

14 
"""

15 
import functools 
16 
import networkx as nx 
17  
18 
__all__ = ['closeness_centrality']

19  
20  
21 
def closeness_centrality(G, u=None, distance=None, wf_improved=True): 
22 
r"""Compute closeness centrality for nodes.

23 

24 
Closeness centrality [1]_ of a node `u` is the reciprocal of the

25 
average shortest path distance to `u` over all `n1` reachable nodes.

26 

27 
.. math::

28 

29 
C(u) = \frac{n  1}{\sum_{v=1}^{n1} d(v, u)},

30 

31 
where `d(v, u)` is the shortestpath distance between `v` and `u`,

32 
and `n` is the number of nodes that can reach `u`. Notice that the

33 
closeness distance function computes the incoming distance to `u`

34 
for directed graphs. To use outward distance, act on `G.reverse()`.

35 

36 
Notice that higher values of closeness indicate higher centrality.

37 

38 
Wasserman and Faust propose an improved formula for graphs with

39 
more than one connected component. The result is "a ratio of the

40 
fraction of actors in the group who are reachable, to the average

41 
distance" from the reachable actors [2]_. You might think this

42 
scale factor is inverted but it is not. As is, nodes from small

43 
components receive a smaller closeness value. Letting `N` denote

44 
the number of nodes in the graph,

45 

46 
.. math::

47 

48 
C_{WF}(u) = \frac{n1}{N1} \frac{n  1}{\sum_{v=1}^{n1} d(v, u)},

49 

50 
Parameters

51 


52 
G : graph

53 
A NetworkX graph

54 

55 
u : node, optional

56 
Return only the value for node u

57 

58 
distance : edge attribute key, optional (default=None)

59 
Use the specified edge attribute as the edge distance in shortest

60 
path calculations

61 

62 
wf_improved : bool, optional (default=True)

63 
If True, scale by the fraction of nodes reachable. This gives the

64 
Wasserman and Faust improved formula. For single component graphs

65 
it is the same as the original formula.

66 

67 
Returns

68 


69 
nodes : dictionary

70 
Dictionary of nodes with closeness centrality as the value.

71 

72 
See Also

73 


74 
betweenness_centrality, load_centrality, eigenvector_centrality,

75 
degree_centrality

76 

77 
Notes

78 


79 
The closeness centrality is normalized to `(n1)/(G1)` where

80 
`n` is the number of nodes in the connected part of graph

81 
containing the node. If the graph is not completely connected,

82 
this algorithm computes the closeness centrality for each

83 
connected part separately scaled by that parts size.

84 

85 
If the 'distance' keyword is set to an edge attribute key then the

86 
shortestpath length will be computed using Dijkstra's algorithm with

87 
that edge attribute as the edge weight.

88 

89 
In NetworkX 2.2 and earlier a bug caused Dijkstra's algorithm to use the

90 
outward distance rather than the inward distance. If you use a 'distance'

91 
keyword and a DiGraph, your results will change between v2.2 and v2.3.

92 

93 
References

94 


95 
.. [1] Linton C. Freeman: Centrality in networks: I.

96 
Conceptual clarification. Social Networks 1:215239, 1979.

97 
http://leonidzhukov.ru/hse/2013/socialnetworks/papers/freeman79centrality.pdf

98 
.. [2] pg. 201 of Wasserman, S. and Faust, K.,

99 
Social Network Analysis: Methods and Applications, 1994,

100 
Cambridge University Press.

101 
"""

102 
if G.is_directed():

103 
G = G.reverse() # create a reversed graph view

104  
105 
if distance is not None: 
106 
# use Dijkstra's algorithm with specified attribute as edge weight

107 
path_length = functools.partial(nx.single_source_dijkstra_path_length, 
108 
weight=distance) 
109 
else:

110 
path_length = nx.single_source_shortest_path_length 
111  
112 
if u is None: 
113 
nodes = G.nodes 
114 
else:

115 
nodes = [u] 
116 
closeness_centrality = {} 
117 
for n in nodes: 
118 
sp = dict(path_length(G, n))

119 
totsp = sum(sp.values())

120 
if totsp > 0.0 and len(G) > 1: 
121 
closeness_centrality[n] = (len(sp)  1.0) / totsp 
122 
# normalize to number of nodes1 in connected part

123 
if wf_improved:

124 
s = (len(sp)  1.0) / (len(G)  1) 
125 
closeness_centrality[n] *= s 
126 
else:

127 
closeness_centrality[n] = 0.0

128 
if u is not None: 
129 
return closeness_centrality[u]

130 
else:

131 
return closeness_centrality
