Shortcuts on this page
r m x toggle line displays
j k next/prev highlighted chunk
0 (zero) top of page
1 (one) first highlighted chunk
1"""Betweenness centrality measures for subsets of nodes."""
3import networkx as nx
4from networkx.algorithms.centrality.betweenness import (
5 _add_edge_keys,
6 _rescale,
7)
8from networkx.algorithms.centrality.betweenness import (
9 _single_source_dijkstra_path_basic as dijkstra,
10)
11from networkx.algorithms.centrality.betweenness import (
12 _single_source_shortest_path_basic as shortest_path,
13)
15__all__ = [
16 "betweenness_centrality_subset",
17 "edge_betweenness_centrality_subset",
18]
21@nx._dispatchable(edge_attrs="weight")
22def betweenness_centrality_subset(G, sources, targets, normalized=False, weight=None):
23 r"""Compute betweenness centrality for a subset of nodes.
25 .. math::
27 c_B(v) =\sum_{s\in S, t \in T} \frac{\sigma(s, t|v)}{\sigma(s, t)}
29 where $S$ is the set of sources, $T$ is the set of targets,
30 $\sigma(s, t)$ is the number of shortest $(s, t)$-paths,
31 and $\sigma(s, t|v)$ is the number of those paths
32 passing through some node $v$ other than $s, t$.
33 If $s = t$, $\sigma(s, t) = 1$,
34 and if $v \in {s, t}$, $\sigma(s, t|v) = 0$ [2]_.
37 Parameters
38 ----------
39 G : graph
40 A NetworkX graph.
42 sources: list of nodes
43 Nodes to use as sources for shortest paths in betweenness
45 targets: list of nodes
46 Nodes to use as targets for shortest paths in betweenness
48 normalized : bool, optional
49 If True the betweenness values are normalized by $2/((n-1)(n-2))$
50 for graphs, and $1/((n-1)(n-2))$ for directed graphs where $n$
51 is the number of nodes in G.
53 weight : None or string, optional (default=None)
54 If None, all edge weights are considered equal.
55 Otherwise holds the name of the edge attribute used as weight.
56 Weights are used to calculate weighted shortest paths, so they are
57 interpreted as distances.
59 Returns
60 -------
61 nodes : dictionary
62 Dictionary of nodes with betweenness centrality as the value.
64 See Also
65 --------
66 betweenness_centrality
67 edge_betweenness_centrality
68 edge_betweenness_centrality_subset
69 load_centrality
71 Notes
72 -----
73 The basic algorithm is from [1]_.
75 For weighted graphs the edge weights must be greater than zero.
76 Zero edge weights can produce an infinite number of equal length
77 paths between pairs of nodes.
79 The normalization might seem a little strange but it is
80 designed to make betweenness_centrality(G) be the same as
81 betweenness_centrality_subset(G,sources=G.nodes(),targets=G.nodes()).
83 The total number of paths between source and target is counted
84 differently for directed and undirected graphs. Directed paths
85 are easy to count. Undirected paths are tricky: should a path
86 from "u" to "v" count as 1 undirected path or as 2 directed paths?
88 For betweenness_centrality we report the number of undirected
89 paths when G is undirected.
91 For betweenness_centrality_subset the reporting is different.
92 If the source and target subsets are the same, then we want
93 to count undirected paths. But if the source and target subsets
94 differ -- for example, if sources is {0} and targets is {1},
95 then we are only counting the paths in one direction. They are
96 undirected paths but we are counting them in a directed way.
97 To count them as undirected paths, each should count as half a path.
99 References
100 ----------
101 .. [1] Ulrik Brandes, A Faster Algorithm for Betweenness Centrality.
102 Journal of Mathematical Sociology 25(2):163-177, 2001.
103 https://doi.org/10.1080/0022250X.2001.9990249
104 .. [2] Ulrik Brandes: On Variants of Shortest-Path Betweenness
105 Centrality and their Generic Computation.
106 Social Networks 30(2):136-145, 2008.
107 https://doi.org/10.1016/j.socnet.2007.11.001
108 """
109 b = dict.fromkeys(G, 0.0) # b[v]=0 for v in G
110 for s in sources:
111 # single source shortest paths
112 if weight is None: # use BFS
113 S, P, sigma, _ = shortest_path(G, s)
114 else: # use Dijkstra's algorithm
115 S, P, sigma, _ = dijkstra(G, s, weight)
116 b = _accumulate_subset(b, S, P, sigma, s, targets)
117 b = _rescale(
118 b, len(G), normalized=normalized, directed=G.is_directed(), endpoints=False
119 )
120 return b
123@nx._dispatchable(edge_attrs="weight")
124def edge_betweenness_centrality_subset(
125 G, sources, targets, normalized=False, weight=None
126):
127 r"""Compute betweenness centrality for edges for a subset of nodes.
129 .. math::
131 c_B(v) =\sum_{s\in S,t \in T} \frac{\sigma(s, t|e)}{\sigma(s, t)}
133 where $S$ is the set of sources, $T$ is the set of targets,
134 $\sigma(s, t)$ is the number of shortest $(s, t)$-paths,
135 and $\sigma(s, t|e)$ is the number of those paths
136 passing through edge $e$ [2]_.
138 Parameters
139 ----------
140 G : graph
141 A networkx graph.
143 sources: list of nodes
144 Nodes to use as sources for shortest paths in betweenness
146 targets: list of nodes
147 Nodes to use as targets for shortest paths in betweenness
149 normalized : bool, optional
150 If True the betweenness values are normalized by `2/(n(n-1))`
151 for graphs, and `1/(n(n-1))` for directed graphs where `n`
152 is the number of nodes in G.
154 weight : None or string, optional (default=None)
155 If None, all edge weights are considered equal.
156 Otherwise holds the name of the edge attribute used as weight.
157 Weights are used to calculate weighted shortest paths, so they are
158 interpreted as distances.
160 Returns
161 -------
162 edges : dictionary
163 Dictionary of edges with Betweenness centrality as the value.
165 See Also
166 --------
167 betweenness_centrality
168 betweenness_centrality_subset
169 edge_betweenness_centrality
170 edge_load
172 Notes
173 -----
174 The basic algorithm is from [1]_.
176 For weighted graphs the edge weights must be greater than zero.
177 Zero edge weights can produce an infinite number of equal length
178 paths between pairs of nodes.
180 The normalization might seem a little strange but it is the same
181 as in edge_betweenness_centrality() and is designed to make
182 edge_betweenness_centrality(G) be the same as
183 edge_betweenness_centrality_subset(G,sources=G.nodes(),targets=G.nodes()).
185 References
186 ----------
187 .. [1] Ulrik Brandes: On Variants of Shortest-Path Betweenness
188 Centrality and their Generic Computation.
189 Social Networks 30(2):136-145, 2008.
190 https://doi.org/10.1016/j.socnet.2007.11.001
191 """
192 b = dict.fromkeys(G, 0.0) # b[v]=0 for v in G
193 b.update(dict.fromkeys(G.edges(), 0.0)) # b[e] for e in G.edges()
194 for s in sources:
195 # single source shortest paths
196 if weight is None: # use BFS
197 S, P, sigma, _ = shortest_path(G, s)
198 else: # use Dijkstra's algorithm
199 S, P, sigma, _ = dijkstra(G, s, weight)
200 b = _accumulate_edges_subset(b, S, P, sigma, s, targets)
201 for n in G: # remove nodes to only return edges
202 del b[n]
203 b = _rescale(b, len(G), normalized=normalized, directed=G.is_directed())
204 if G.is_multigraph():
205 b = _add_edge_keys(G, b, weight=weight)
206 return b
209def _accumulate_subset(betweenness, S, P, sigma, s, targets):
210 delta = dict.fromkeys(S, 0.0)
211 target_set = set(targets) - {s}
212 while S:
213 w = S.pop()
214 if w in target_set:
215 coeff = (delta[w] + 1.0) / sigma[w]
216 else:
217 coeff = delta[w] / sigma[w]
218 for v in P[w]:
219 delta[v] += sigma[v] * coeff
220 if w != s:
221 betweenness[w] += delta[w]
222 return betweenness
225def _accumulate_edges_subset(betweenness, S, P, sigma, s, targets):
226 """edge_betweenness_centrality_subset helper."""
227 delta = dict.fromkeys(S, 0)
228 target_set = set(targets)
229 while S:
230 w = S.pop()
231 for v in P[w]:
232 if w in target_set:
233 c = (sigma[v] / sigma[w]) * (1.0 + delta[w])
234 else:
235 c = delta[w] / len(P[w])
236 if (v, w) not in betweenness:
237 betweenness[(w, v)] += c
238 else:
239 betweenness[(v, w)] += c
240 delta[v] += c
241 if w != s:
242 betweenness[w] += delta[w]
243 return betweenness