ioftools / networkxMiCe / networkxmaster / networkx / algorithms / efficiency.py @ 5cef0f13
History  View  Annotate  Download (4.26 KB)
1 
# efficiency.py  functions for computing node, edge, and graph efficiency


2 
#

3 
# Copyright 2011, 2012, 2013, 2014, 2015 NetworkX developers

4 
#

5 
# This file is part of NetworkX.

6 
#

7 
# NetworkX is distributed under a BSD license; see LICENSE.txt for more

8 
# information.

9 
"""Provides functions for computing the efficiency of nodes and graphs."""

10 
from __future__ import division 
11  
12 
from itertools import permutations 
13  
14 
import networkx as nx 
15 
from networkx.exception import NetworkXNoPath 
16 
from ..utils import not_implemented_for 
17  
18 
__all__ = ['efficiency', 'local_efficiency', 'global_efficiency'] 
19  
20  
21 
@not_implemented_for('directed') 
22 
def efficiency(G, u, v): 
23 
"""Returns the efficiency of a pair of nodes in a graph.

24 

25 
The *efficiency* of a pair of nodes is the multiplicative inverse of the

26 
shortest path distance between the nodes [1]_. Returns 0 if no path

27 
between nodes.

28 

29 
Parameters

30 


31 
G : :class:`networkx.Graph`

32 
An undirected graph for which to compute the average local efficiency.

33 
u, v : node

34 
Nodes in the graph ``G``.

35 

36 
Returns

37 


38 
float

39 
Multiplicative inverse of the shortest path distance between the nodes.

40 

41 
Notes

42 


43 
Edge weights are ignored when computing the shortest path distances.

44 

45 
See also

46 


47 
local_efficiency

48 
global_efficiency

49 

50 
References

51 


52 
.. [1] Latora, Vito, and Massimo Marchiori.

53 
"Efficient behavior of smallworld networks."

54 
*Physical Review Letters* 87.19 (2001): 198701.

55 
<https://doi.org/10.1103/PhysRevLett.87.198701>

56 

57 
"""

58 
try:

59 
eff = 1 / nx.shortest_path_length(G, u, v)

60 
except NetworkXNoPath:

61 
eff = 0

62 
return eff

63  
64  
65 
@not_implemented_for('directed') 
66 
def global_efficiency(G): 
67 
"""Returns the average global efficiency of the graph.

68 

69 
The *efficiency* of a pair of nodes in a graph is the multiplicative

70 
inverse of the shortest path distance between the nodes. The *average

71 
global efficiency* of a graph is the average efficiency of all pairs of

72 
nodes [1]_.

73 

74 
Parameters

75 


76 
G : :class:`networkx.Graph`

77 
An undirected graph for which to compute the average global efficiency.

78 

79 
Returns

80 


81 
float

82 
The average global efficiency of the graph.

83 

84 
Notes

85 


86 
Edge weights are ignored when computing the shortest path distances.

87 

88 
See also

89 


90 
local_efficiency

91 

92 
References

93 


94 
.. [1] Latora, Vito, and Massimo Marchiori.

95 
"Efficient behavior of smallworld networks."

96 
*Physical Review Letters* 87.19 (2001): 198701.

97 
<https://doi.org/10.1103/PhysRevLett.87.198701>

98 

99 
"""

100 
n = len(G)

101 
denom = n * (n  1)

102 
if denom != 0: 
103 
g_eff = sum(efficiency(G, u, v) for u, v in permutations(G, 2)) / denom 
104 
else:

105 
g_eff = 0

106 
# TODO This can be made more efficient by computing all pairs shortest

107 
# path lengths in parallel.

108 
#

109 
# TODO This summation can be trivially parallelized.

110 
return g_eff

111  
112  
113 
@not_implemented_for('directed') 
114 
def local_efficiency(G): 
115 
"""Returns the average local efficiency of the graph.

116 

117 
The *efficiency* of a pair of nodes in a graph is the multiplicative

118 
inverse of the shortest path distance between the nodes. The *local

119 
efficiency* of a node in the graph is the average global efficiency of the

120 
subgraph induced by the neighbors of the node. The *average local

121 
efficiency* is the average of the local efficiencies of each node [1]_.

122 

123 
Parameters

124 


125 
G : :class:`networkx.Graph`

126 
An undirected graph for which to compute the average local efficiency.

127 

128 
Returns

129 


130 
float

131 
The average local efficiency of the graph.

132 

133 
Notes

134 


135 
Edge weights are ignored when computing the shortest path distances.

136 

137 
See also

138 


139 
global_efficiency

140 

141 
References

142 


143 
.. [1] Latora, Vito, and Massimo Marchiori.

144 
"Efficient behavior of smallworld networks."

145 
*Physical Review Letters* 87.19 (2001): 198701.

146 
<https://doi.org/10.1103/PhysRevLett.87.198701>

147 

148 
"""

149 
# TODO This summation can be trivially parallelized.

150 
efficiency_list = (global_efficiency(G.subgraph(G[v])) for v in G) 
151 
return sum(efficiency_list) / len(G) 