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) = \frac{1}{P} \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$ and $t$.
33 If $s = t$, $\sigma(s, t) = 1$,
34 and if $v \in \{s, t\}$, $\sigma(s, t | v) = 0$ [2]_.
35 $P$ is a normalization factor representing the number of pairs of nodes
36 that have counted shortest paths. Its value depends on the values of `normalized`
37 and `endpoints`, and on whether the graph is directed (see Notes). It can
38 be set to ``1`` with ``normalized=False``.
40 Parameters
41 ----------
42 G : graph
43 A NetworkX graph.
45 sources: list of nodes
46 Nodes to use as sources for shortest paths in betweenness.
48 targets: list of nodes
49 Nodes to use as targets for shortest paths in betweenness.
51 normalized : bool, optional (default=False)
52 If `True`, the betweenness values are rescaled by dividing by the number of
53 possible $(s, t)$-pairs in the graph.
55 weight : None or string, optional (default=None)
56 If `None`, all edge weights are 1.
57 Otherwise holds the name of the edge attribute used as weight.
58 Weights are used to calculate weighted shortest paths, so they are
59 interpreted as distances.
61 Returns
62 -------
63 nodes : dict
64 Dictionary of nodes with betweenness centrality as the value.
66 See Also
67 --------
68 betweenness_centrality
69 edge_betweenness_centrality
70 edge_betweenness_centrality_subset
71 load_centrality
73 Notes
74 -----
75 The basic algorithm is from [1]_.
77 For weighted graphs the edge weights must be greater than zero.
78 Zero edge weights can produce an infinite number of equal length
79 paths between pairs of nodes.
81 The normalization might seem a little strange but it is
82 designed to make betweenness_centrality(G) be the same as
83 betweenness_centrality_subset(G, sources=G, targets=G, normalized=True).
85 The total number of paths between source and target is counted
86 differently for directed and undirected graphs. Directed paths
87 are easy to count. Undirected paths are tricky: should a path
88 from ``u`` to ``v`` count as 1 undirected path or as 2 directed paths?
89 We are only counting the paths in one direction. They are
90 undirected paths but we are counting them in a directed way.
91 To count them as undirected paths, each should count as half a path.
93 References
94 ----------
95 .. [1] Ulrik Brandes, A Faster Algorithm for Betweenness Centrality.
96 Journal of Mathematical Sociology 25(2):163-177, 2001.
97 https://doi.org/10.1080/0022250X.2001.9990249
98 .. [2] Ulrik Brandes: On Variants of Shortest-Path Betweenness
99 Centrality and their Generic Computation.
100 Social Networks 30(2):136-145, 2008.
101 https://doi.org/10.1016/j.socnet.2007.11.001
102 """
103 b = dict.fromkeys(G, 0.0) # b[v]=0 for v in G
104 for s in sources:
105 # single source shortest paths
106 if weight is None: # use BFS
107 S, P, sigma, _ = shortest_path(G, s)
108 else: # use Dijkstra's algorithm
109 S, P, sigma, _ = dijkstra(G, s, weight)
110 b = _accumulate_subset(b, S, P, sigma, s, targets)
111 b = _rescale(
112 b, len(G), normalized=normalized, directed=G.is_directed(), endpoints=False
113 )
114 return b
117@nx._dispatchable(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(e) = \frac{1}{P} \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$ [1]_.
131 $P$ is a normalization factor representing the number of pairs of nodes
132 that have counted shortest paths. Its value depends on the values of `normalized`
133 and `endpoints`, and on whether the graph is directed (see Notes). It can
134 be set to ``1`` with ``normalized=False``.
136 Parameters
137 ----------
138 G : graph
139 A networkx graph.
141 sources: list of nodes
142 Nodes to use as sources for shortest paths in betweenness.
144 targets: list of nodes
145 Nodes to use as targets for shortest paths in betweenness.
147 normalized : bool, optional (default=False)
148 If `True`, the betweenness values are rescaled by dividing by the number of
149 possible $(s, t)$-pairs in the graph.
151 weight : None or string, optional (default=None)
152 If `None`, all edge weights are 1.
153 Otherwise holds the name of the edge attribute used as weight.
154 Weights are used to calculate weighted shortest paths, so they are
155 interpreted as distances.
157 Returns
158 -------
159 edges : dict
160 Dictionary of edges with betweenness centrality as the value.
162 See Also
163 --------
164 betweenness_centrality
165 betweenness_centrality_subset
166 edge_betweenness_centrality
167 edge_load
169 Notes
170 -----
171 The basic algorithm is from [1]_.
173 For weighted graphs the edge weights must be greater than zero.
174 Zero edge weights can produce an infinite number of equal length
175 paths between pairs of nodes.
177 The normalization might seem a little strange but it is the same
178 as in edge_betweenness_centrality() and is designed to make
179 edge_betweenness_centrality(G) be the same as
180 edge_betweenness_centrality_subset(G, sources=G, targets=G, normalized=True).
182 References
183 ----------
184 .. [1] Ulrik Brandes: On Variants of Shortest-Path Betweenness
185 Centrality and their Generic Computation.
186 Social Networks 30(2):136-145, 2008.
187 https://doi.org/10.1016/j.socnet.2007.11.001
188 """
189 b = dict.fromkeys(G, 0.0) # b[v]=0 for v in G
190 b.update(dict.fromkeys(G.edges(), 0.0)) # b[e] for e in G.edges()
191 for s in sources:
192 # single source shortest paths
193 if weight is None: # use BFS
194 S, P, sigma, _ = shortest_path(G, s)
195 else: # use Dijkstra's algorithm
196 S, P, sigma, _ = dijkstra(G, s, weight)
197 b = _accumulate_edges_subset(b, S, P, sigma, s, targets)
198 for n in G: # remove nodes to only return edges
199 del b[n]
200 b = _rescale(b, len(G), normalized=normalized, directed=G.is_directed())
201 if G.is_multigraph():
202 b = _add_edge_keys(G, b, weight=weight)
203 return b
206def _accumulate_subset(betweenness, S, P, sigma, s, targets):
207 delta = dict.fromkeys(S, 0.0)
208 target_set = set(targets) - {s}
209 while S:
210 w = S.pop()
211 if w in target_set:
212 coeff = (delta[w] + 1.0) / sigma[w]
213 else:
214 coeff = delta[w] / sigma[w]
215 for v in P[w]:
216 delta[v] += sigma[v] * coeff
217 if w != s:
218 betweenness[w] += delta[w]
219 return betweenness
222def _accumulate_edges_subset(betweenness, S, P, sigma, s, targets):
223 """edge_betweenness_centrality_subset helper."""
224 delta = dict.fromkeys(S, 0)
225 target_set = set(targets)
226 while S:
227 w = S.pop()
228 for v in P[w]:
229 if w in target_set:
230 c = (sigma[v] / sigma[w]) * (1.0 + delta[w])
231 else:
232 c = delta[w] / len(P[w])
233 if (v, w) not in betweenness:
234 betweenness[(w, v)] += c
235 else:
236 betweenness[(v, w)] += c
237 delta[v] += c
238 if w != s:
239 betweenness[w] += delta[w]
240 return betweenness