Mercurial > repos > shellac > sam_consensus_v3
comparison env/lib/python3.9/site-packages/networkx/algorithms/centrality/reaching.py @ 0:4f3585e2f14b draft default tip
"planemo upload commit 60cee0fc7c0cda8592644e1aad72851dec82c959"
author | shellac |
---|---|
date | Mon, 22 Mar 2021 18:12:50 +0000 |
parents | |
children |
comparison
equal
deleted
inserted
replaced
-1:000000000000 | 0:4f3585e2f14b |
---|---|
1 """Functions for computing reaching centrality of a node or a graph.""" | |
2 | |
3 import networkx as nx | |
4 | |
5 from networkx.utils import pairwise | |
6 | |
7 __all__ = ["global_reaching_centrality", "local_reaching_centrality"] | |
8 | |
9 | |
10 def _average_weight(G, path, weight=None): | |
11 """Returns the average weight of an edge in a weighted path. | |
12 | |
13 Parameters | |
14 ---------- | |
15 G : graph | |
16 A networkx graph. | |
17 | |
18 path: list | |
19 A list of vertices that define the path. | |
20 | |
21 weight : None or string, optional (default=None) | |
22 If None, edge weights are ignored. Then the average weight of an edge | |
23 is assumed to be the multiplicative inverse of the length of the path. | |
24 Otherwise holds the name of the edge attribute used as weight. | |
25 """ | |
26 path_length = len(path) - 1 | |
27 if path_length <= 0: | |
28 return 0 | |
29 if weight is None: | |
30 return 1 / path_length | |
31 total_weight = sum(G.edges[i, j][weight] for i, j in pairwise(path)) | |
32 return total_weight / path_length | |
33 | |
34 | |
35 def 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 def local_reaching_centrality(G, v, paths=None, weight=None, normalized=True): | |
123 """Returns the local reaching centrality of a node in a directed | |
124 graph. | |
125 | |
126 The *local reaching centrality* of a node in a directed graph is the | |
127 proportion of other nodes reachable from that node [1]_. | |
128 | |
129 Parameters | |
130 ---------- | |
131 G : DiGraph | |
132 A NetworkX DiGraph. | |
133 | |
134 v : node | |
135 A node in the directed graph `G`. | |
136 | |
137 paths : dictionary (default=None) | |
138 If this is not `None` it must be a dictionary representation | |
139 of single-source shortest paths, as computed by, for example, | |
140 :func:`networkx.shortest_path` with source node `v`. Use this | |
141 keyword argument if you intend to invoke this function many | |
142 times but don't want the paths to be recomputed each time. | |
143 | |
144 weight : None or string, optional (default=None) | |
145 Attribute to use for edge weights. If `None`, each edge weight | |
146 is assumed to be one. A higher weight implies a stronger | |
147 connection between nodes and a *shorter* path length. | |
148 | |
149 normalized : bool, optional (default=True) | |
150 Whether to normalize the edge weights by the total sum of edge | |
151 weights. | |
152 | |
153 Returns | |
154 ------- | |
155 h : float | |
156 The local reaching centrality of the node ``v`` in the graph | |
157 ``G``. | |
158 | |
159 Examples | |
160 -------- | |
161 >>> G = nx.DiGraph() | |
162 >>> G.add_edges_from([(1, 2), (1, 3)]) | |
163 >>> nx.local_reaching_centrality(G, 3) | |
164 0.0 | |
165 >>> G.add_edge(3, 2) | |
166 >>> nx.local_reaching_centrality(G, 3) | |
167 0.5 | |
168 | |
169 See also | |
170 -------- | |
171 global_reaching_centrality | |
172 | |
173 References | |
174 ---------- | |
175 .. [1] Mones, Enys, Lilla Vicsek, and Tamás Vicsek. | |
176 "Hierarchy Measure for Complex Networks." | |
177 *PLoS ONE* 7.3 (2012): e33799. | |
178 https://doi.org/10.1371/journal.pone.0033799 | |
179 """ | |
180 if paths is None: | |
181 if nx.is_negatively_weighted(G, weight=weight): | |
182 raise nx.NetworkXError("edge weights must be positive") | |
183 total_weight = G.size(weight=weight) | |
184 if total_weight <= 0: | |
185 raise nx.NetworkXError("Size of G must be positive") | |
186 if weight is not None: | |
187 # Interpret weights as lengths. | |
188 def as_distance(u, v, d): | |
189 return total_weight / d.get(weight, 1) | |
190 | |
191 paths = nx.shortest_path(G, source=v, weight=as_distance) | |
192 else: | |
193 paths = nx.shortest_path(G, source=v) | |
194 # If the graph is unweighted, simply return the proportion of nodes | |
195 # reachable from the source node ``v``. | |
196 if weight is None and G.is_directed(): | |
197 return (len(paths) - 1) / (len(G) - 1) | |
198 if normalized and weight is not None: | |
199 norm = G.size(weight=weight) / G.size() | |
200 else: | |
201 norm = 1 | |
202 # TODO This can be trivially parallelized. | |
203 avgw = (_average_weight(G, path, weight=weight) for path in paths.values()) | |
204 sum_avg_weight = sum(avgw) / norm | |
205 return sum_avg_weight / (len(G) - 1) |