Coverage for /pythoncovmergedfiles/medio/medio/usr/local/lib/python3.9/dist-packages/networkx/algorithms/centrality/reaching.py: 17%

1"""Functions for computing reaching centrality of a node or a graph.""" 

2 

3import networkx as nx 

4from networkx.utils import pairwise 

5 

6__all__ = ["global_reaching_centrality", "local_reaching_centrality"] 

7 

8 

9def _average_weight(G, path, weight=None): 

10 """Returns the average weight of an edge in a weighted path. 

11 

12 Parameters 

13 ---------- 

14 G : graph 

15 A networkx graph. 

16 

17 path: list 

18 A list of vertices that define the path. 

19 

20 weight : None or string, optional (default=None) 

21 If None, edge weights are ignored. Then the average weight of an edge 

22 is assumed to be the multiplicative inverse of the length of the path. 

23 Otherwise holds the name of the edge attribute used as weight. 

24 """ 

25 path_length = len(path) - 1 

26 if path_length <= 0: 

27 return 0 

28 if weight is None: 

29 return 1 / path_length 

30 total_weight = sum(G.edges[i, j][weight] for i, j in pairwise(path)) 

31 return total_weight / path_length 

32 

33 

34@nx._dispatch(edge_attrs="weight") 

35def global_reaching_centrality(G, weight=None, normalized=True): 

36 """Returns the global reaching centrality of a directed graph. 

37 

38 The *global reaching centrality* of a weighted directed graph is the 

39 average over all nodes of the difference between the local reaching 

40 centrality of the node and the greatest local reaching centrality of 

41 any node in the graph [1]_. For more information on the local 

42 reaching centrality, see :func:`local_reaching_centrality`. 

43 Informally, the local reaching centrality is the proportion of the 

44 graph that is reachable from the neighbors of the node. 

45 

46 Parameters 

47 ---------- 

48 G : DiGraph 

49 A networkx DiGraph. 

50 

51 weight : None or string, optional (default=None) 

52 Attribute to use for edge weights. If ``None``, each edge weight 

53 is assumed to be one. A higher weight implies a stronger 

54 connection between nodes and a *shorter* path length. 

55 

56 normalized : bool, optional (default=True) 

57 Whether to normalize the edge weights by the total sum of edge 

58 weights. 

59 

60 Returns 

61 ------- 

62 h : float 

63 The global reaching centrality of the graph. 

64 

65 Examples 

66 -------- 

67 >>> G = nx.DiGraph() 

68 >>> G.add_edge(1, 2) 

69 >>> G.add_edge(1, 3) 

70 >>> nx.global_reaching_centrality(G) 

71 1.0 

72 >>> G.add_edge(3, 2) 

73 >>> nx.global_reaching_centrality(G) 

74 0.75 

75 

76 See also 

77 -------- 

78 local_reaching_centrality 

79 

80 References 

81 ---------- 

82 .. [1] Mones, Enys, Lilla Vicsek, and Tamás Vicsek. 

83 "Hierarchy Measure for Complex Networks." 

84 *PLoS ONE* 7.3 (2012): e33799. 

85 https://doi.org/10.1371/journal.pone.0033799 

86 """ 

87 if nx.is_negatively_weighted(G, weight=weight): 

88 raise nx.NetworkXError("edge weights must be positive") 

89 total_weight = G.size(weight=weight) 

90 if total_weight <= 0: 

91 raise nx.NetworkXError("Size of G must be positive") 

92 

93 # If provided, weights must be interpreted as connection strength 

94 # (so higher weights are more likely to be chosen). However, the 

95 # shortest path algorithms in NetworkX assume the provided "weight" 

96 # is actually a distance (so edges with higher weight are less 

97 # likely to be chosen). Therefore we need to invert the weights when 

98 # computing shortest paths. 

99 # 

100 # If weight is None, we leave it as-is so that the shortest path 

101 # algorithm can use a faster, unweighted algorithm. 

102 if weight is not None: 

103 

104 def as_distance(u, v, d): 

105 return total_weight / d.get(weight, 1) 

106 

107 shortest_paths = nx.shortest_path(G, weight=as_distance) 

108 else: 

109 shortest_paths = nx.shortest_path(G) 

110 

111 centrality = local_reaching_centrality 

112 # TODO This can be trivially parallelized. 

113 lrc = [ 

114 centrality(G, node, paths=paths, weight=weight, normalized=normalized) 

115 for node, paths in shortest_paths.items() 

116 ] 

117 

118 max_lrc = max(lrc) 

119 return sum(max_lrc - c for c in lrc) / (len(G) - 1) 

120 

121 

122@nx._dispatch(edge_attrs="weight") 

123def local_reaching_centrality(G, v, paths=None, weight=None, normalized=True): 

124 """Returns the local reaching centrality of a node in a directed 

125 graph. 

126 

127 The *local reaching centrality* of a node in a directed graph is the 

128 proportion of other nodes reachable from that node [1]_. 

129 

130 Parameters 

131 ---------- 

132 G : DiGraph 

133 A NetworkX DiGraph. 

134 

135 v : node 

136 A node in the directed graph `G`. 

137 

138 paths : dictionary (default=None) 

139 If this is not `None` it must be a dictionary representation 

140 of single-source shortest paths, as computed by, for example, 

141 :func:`networkx.shortest_path` with source node `v`. Use this 

142 keyword argument if you intend to invoke this function many 

143 times but don't want the paths to be recomputed each time. 

144 

145 weight : None or string, optional (default=None) 

146 Attribute to use for edge weights. If `None`, each edge weight 

147 is assumed to be one. A higher weight implies a stronger 

148 connection between nodes and a *shorter* path length. 

149 

150 normalized : bool, optional (default=True) 

151 Whether to normalize the edge weights by the total sum of edge 

152 weights. 

153 

154 Returns 

155 ------- 

156 h : float 

157 The local reaching centrality of the node ``v`` in the graph 

158 ``G``. 

159 

160 Examples 

161 -------- 

162 >>> G = nx.DiGraph() 

163 >>> G.add_edges_from([(1, 2), (1, 3)]) 

164 >>> nx.local_reaching_centrality(G, 3) 

165 0.0 

166 >>> G.add_edge(3, 2) 

167 >>> nx.local_reaching_centrality(G, 3) 

168 0.5 

169 

170 See also 

171 -------- 

172 global_reaching_centrality 

173 

174 References 

175 ---------- 

176 .. [1] Mones, Enys, Lilla Vicsek, and Tamás Vicsek. 

177 "Hierarchy Measure for Complex Networks." 

178 *PLoS ONE* 7.3 (2012): e33799. 

179 https://doi.org/10.1371/journal.pone.0033799 

180 """ 

181 if paths is None: 

182 if nx.is_negatively_weighted(G, weight=weight): 

183 raise nx.NetworkXError("edge weights must be positive") 

184 total_weight = G.size(weight=weight) 

185 if total_weight <= 0: 

186 raise nx.NetworkXError("Size of G must be positive") 

187 if weight is not None: 

188 # Interpret weights as lengths. 

189 def as_distance(u, v, d): 

190 return total_weight / d.get(weight, 1) 

191 

192 paths = nx.shortest_path(G, source=v, weight=as_distance) 

193 else: 

194 paths = nx.shortest_path(G, source=v) 

195 # If the graph is unweighted, simply return the proportion of nodes 

196 # reachable from the source node ``v``. 

197 if weight is None and G.is_directed(): 

198 return (len(paths) - 1) / (len(G) - 1) 

199 if normalized and weight is not None: 

200 norm = G.size(weight=weight) / G.size() 

201 else: 

202 norm = 1 

203 # TODO This can be trivially parallelized. 

204 avgw = (_average_weight(G, path, weight=weight) for path in paths.values()) 

205 sum_avg_weight = sum(avgw) / norm 

206 return sum_avg_weight / (len(G) - 1)