Coverage for /pythoncovmergedfiles/medio/medio/usr/local/lib/python3.9/dist-packages/networkx/algorithms/centrality/betweenness_subset.py: 16%
83 statements
« prev ^ index » next coverage.py v7.3.2, created at 2023-10-20 07:00 +0000
1"""Betweenness centrality measures for subsets of nodes."""
2import networkx as nx
3from networkx.algorithms.centrality.betweenness import (
4 _add_edge_keys,
5)
6from networkx.algorithms.centrality.betweenness import (
7 _single_source_dijkstra_path_basic as dijkstra,
8)
9from networkx.algorithms.centrality.betweenness import (
10 _single_source_shortest_path_basic as shortest_path,
11)
13__all__ = [
14 "betweenness_centrality_subset",
15 "edge_betweenness_centrality_subset",
16]
19@nx._dispatch(edge_attrs="weight")
20def betweenness_centrality_subset(G, sources, targets, normalized=False, weight=None):
21 r"""Compute betweenness centrality for a subset of nodes.
23 .. math::
25 c_B(v) =\sum_{s\in S, t \in T} \frac{\sigma(s, t|v)}{\sigma(s, t)}
27 where $S$ is the set of sources, $T$ is the set of targets,
28 $\sigma(s, t)$ is the number of shortest $(s, t)$-paths,
29 and $\sigma(s, t|v)$ is the number of those paths
30 passing through some node $v$ other than $s, t$.
31 If $s = t$, $\sigma(s, t) = 1$,
32 and if $v \in {s, t}$, $\sigma(s, t|v) = 0$ [2]_.
35 Parameters
36 ----------
37 G : graph
38 A NetworkX graph.
40 sources: list of nodes
41 Nodes to use as sources for shortest paths in betweenness
43 targets: list of nodes
44 Nodes to use as targets for shortest paths in betweenness
46 normalized : bool, optional
47 If True the betweenness values are normalized by $2/((n-1)(n-2))$
48 for graphs, and $1/((n-1)(n-2))$ for directed graphs where $n$
49 is the number of nodes in G.
51 weight : None or string, optional (default=None)
52 If None, all edge weights are considered equal.
53 Otherwise holds the name of the edge attribute used as weight.
54 Weights are used to calculate weighted shortest paths, so they are
55 interpreted as distances.
57 Returns
58 -------
59 nodes : dictionary
60 Dictionary of nodes with betweenness centrality as the value.
62 See Also
63 --------
64 edge_betweenness_centrality
65 load_centrality
67 Notes
68 -----
69 The basic algorithm is from [1]_.
71 For weighted graphs the edge weights must be greater than zero.
72 Zero edge weights can produce an infinite number of equal length
73 paths between pairs of nodes.
75 The normalization might seem a little strange but it is
76 designed to make betweenness_centrality(G) be the same as
77 betweenness_centrality_subset(G,sources=G.nodes(),targets=G.nodes()).
79 The total number of paths between source and target is counted
80 differently for directed and undirected graphs. Directed paths
81 are easy to count. Undirected paths are tricky: should a path
82 from "u" to "v" count as 1 undirected path or as 2 directed paths?
84 For betweenness_centrality we report the number of undirected
85 paths when G is undirected.
87 For betweenness_centrality_subset the reporting is different.
88 If the source and target subsets are the same, then we want
89 to count undirected paths. But if the source and target subsets
90 differ -- for example, if sources is {0} and targets is {1},
91 then we are only counting the paths in one direction. They are
92 undirected paths but we are counting them in a directed way.
93 To count them as undirected paths, each should count as half a path.
95 References
96 ----------
97 .. [1] Ulrik Brandes, A Faster Algorithm for Betweenness Centrality.
98 Journal of Mathematical Sociology 25(2):163-177, 2001.
99 https://doi.org/10.1080/0022250X.2001.9990249
100 .. [2] Ulrik Brandes: On Variants of Shortest-Path Betweenness
101 Centrality and their Generic Computation.
102 Social Networks 30(2):136-145, 2008.
103 https://doi.org/10.1016/j.socnet.2007.11.001
104 """
105 b = dict.fromkeys(G, 0.0) # b[v]=0 for v in G
106 for s in sources:
107 # single source shortest paths
108 if weight is None: # use BFS
109 S, P, sigma, _ = shortest_path(G, s)
110 else: # use Dijkstra's algorithm
111 S, P, sigma, _ = dijkstra(G, s, weight)
112 b = _accumulate_subset(b, S, P, sigma, s, targets)
113 b = _rescale(b, len(G), normalized=normalized, directed=G.is_directed())
114 return b
117@nx._dispatch(edge_attrs="weight")
118def edge_betweenness_centrality_subset(
119 G, sources, targets, normalized=False, weight=None
120):
121 r"""Compute betweenness centrality for edges for a subset of nodes.
123 .. math::
125 c_B(v) =\sum_{s\in S,t \in T} \frac{\sigma(s, t|e)}{\sigma(s, t)}
127 where $S$ is the set of sources, $T$ is the set of targets,
128 $\sigma(s, t)$ is the number of shortest $(s, t)$-paths,
129 and $\sigma(s, t|e)$ is the number of those paths
130 passing through edge $e$ [2]_.
132 Parameters
133 ----------
134 G : graph
135 A networkx graph.
137 sources: list of nodes
138 Nodes to use as sources for shortest paths in betweenness
140 targets: list of nodes
141 Nodes to use as targets for shortest paths in betweenness
143 normalized : bool, optional
144 If True the betweenness values are normalized by `2/(n(n-1))`
145 for graphs, and `1/(n(n-1))` for directed graphs where `n`
146 is the number of nodes in G.
148 weight : None or string, optional (default=None)
149 If None, all edge weights are considered equal.
150 Otherwise holds the name of the edge attribute used as weight.
151 Weights are used to calculate weighted shortest paths, so they are
152 interpreted as distances.
154 Returns
155 -------
156 edges : dictionary
157 Dictionary of edges with Betweenness centrality as the value.
159 See Also
160 --------
161 betweenness_centrality
162 edge_load
164 Notes
165 -----
166 The basic algorithm is from [1]_.
168 For weighted graphs the edge weights must be greater than zero.
169 Zero edge weights can produce an infinite number of equal length
170 paths between pairs of nodes.
172 The normalization might seem a little strange but it is the same
173 as in edge_betweenness_centrality() and is designed to make
174 edge_betweenness_centrality(G) be the same as
175 edge_betweenness_centrality_subset(G,sources=G.nodes(),targets=G.nodes()).
177 References
178 ----------
179 .. [1] Ulrik Brandes, A Faster Algorithm for Betweenness Centrality.
180 Journal of Mathematical Sociology 25(2):163-177, 2001.
181 https://doi.org/10.1080/0022250X.2001.9990249
182 .. [2] Ulrik Brandes: On Variants of Shortest-Path Betweenness
183 Centrality and their Generic Computation.
184 Social Networks 30(2):136-145, 2008.
185 https://doi.org/10.1016/j.socnet.2007.11.001
186 """
187 b = dict.fromkeys(G, 0.0) # b[v]=0 for v in G
188 b.update(dict.fromkeys(G.edges(), 0.0)) # b[e] for e in G.edges()
189 for s in sources:
190 # single source shortest paths
191 if weight is None: # use BFS
192 S, P, sigma, _ = shortest_path(G, s)
193 else: # use Dijkstra's algorithm
194 S, P, sigma, _ = dijkstra(G, s, weight)
195 b = _accumulate_edges_subset(b, S, P, sigma, s, targets)
196 for n in G: # remove nodes to only return edges
197 del b[n]
198 b = _rescale_e(b, len(G), normalized=normalized, directed=G.is_directed())
199 if G.is_multigraph():
200 b = _add_edge_keys(G, b, weight=weight)
201 return b
204def _accumulate_subset(betweenness, S, P, sigma, s, targets):
205 delta = dict.fromkeys(S, 0.0)
206 target_set = set(targets) - {s}
207 while S:
208 w = S.pop()
209 if w in target_set:
210 coeff = (delta[w] + 1.0) / sigma[w]
211 else:
212 coeff = delta[w] / sigma[w]
213 for v in P[w]:
214 delta[v] += sigma[v] * coeff
215 if w != s:
216 betweenness[w] += delta[w]
217 return betweenness
220def _accumulate_edges_subset(betweenness, S, P, sigma, s, targets):
221 """edge_betweenness_centrality_subset helper."""
222 delta = dict.fromkeys(S, 0)
223 target_set = set(targets)
224 while S:
225 w = S.pop()
226 for v in P[w]:
227 if w in target_set:
228 c = (sigma[v] / sigma[w]) * (1.0 + delta[w])
229 else:
230 c = delta[w] / len(P[w])
231 if (v, w) not in betweenness:
232 betweenness[(w, v)] += c
233 else:
234 betweenness[(v, w)] += c
235 delta[v] += c
236 if w != s:
237 betweenness[w] += delta[w]
238 return betweenness
241def _rescale(betweenness, n, normalized, directed=False):
242 """betweenness_centrality_subset helper."""
243 if normalized:
244 if n <= 2:
245 scale = None # no normalization b=0 for all nodes
246 else:
247 scale = 1.0 / ((n - 1) * (n - 2))
248 else: # rescale by 2 for undirected graphs
249 if not directed:
250 scale = 0.5
251 else:
252 scale = None
253 if scale is not None:
254 for v in betweenness:
255 betweenness[v] *= scale
256 return betweenness
259def _rescale_e(betweenness, n, normalized, directed=False):
260 """edge_betweenness_centrality_subset helper."""
261 if normalized:
262 if n <= 1:
263 scale = None # no normalization b=0 for all nodes
264 else:
265 scale = 1.0 / (n * (n - 1))
266 else: # rescale by 2 for undirected graphs
267 if not directed:
268 scale = 0.5
269 else:
270 scale = None
271 if scale is not None:
272 for v in betweenness:
273 betweenness[v] *= scale
274 return betweenness