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$ and $t$.
33 If $s = t$, $\sigma(s, t) = 1$,
34 and if $v \in \{s, t\}$, $\sigma(s, t | v) = 0$ [2]_.
35 The denominator $\sigma(s, t)$ is a normalization factor that can be
36 turned off to get the raw path counts.
38 Parameters
39 ----------
40 G : graph
41 A NetworkX graph.
43 sources: list of nodes
44 Nodes to use as sources for shortest paths in betweenness.
46 targets: list of nodes
47 Nodes to use as targets for shortest paths in betweenness.
49 normalized : bool, optional (default=False)
50 If `True`, the betweenness values are rescaled by dividing by the number of
51 possible $(s, t)$-pairs in the graph.
53 weight : None or string, optional (default=None)
54 If `None`, all edge weights are 1.
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 : dict
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?
87 We are only counting the paths in one direction. They are
88 undirected paths but we are counting them in a directed way.
89 To count them as undirected paths, each should count as half a path.
91 References
92 ----------
93 .. [1] Ulrik Brandes, A Faster Algorithm for Betweenness Centrality.
94 Journal of Mathematical Sociology 25(2):163-177, 2001.
95 https://doi.org/10.1080/0022250X.2001.9990249
96 .. [2] Ulrik Brandes: On Variants of Shortest-Path Betweenness
97 Centrality and their Generic Computation.
98 Social Networks 30(2):136-145, 2008.
99 https://doi.org/10.1016/j.socnet.2007.11.001
100 """
101 b = dict.fromkeys(G, 0.0) # b[v]=0 for v in G
102 for s in sources:
103 # single source shortest paths
104 if weight is None: # use BFS
105 S, P, sigma, _ = shortest_path(G, s)
106 else: # use Dijkstra's algorithm
107 S, P, sigma, _ = dijkstra(G, s, weight)
108 b = _accumulate_subset(b, S, P, sigma, s, targets)
109 b = _rescale(
110 b, len(G), normalized=normalized, directed=G.is_directed(), endpoints=False
111 )
112 return b
115@nx._dispatchable(edge_attrs="weight")
116def edge_betweenness_centrality_subset(
117 G, sources, targets, normalized=False, weight=None
118):
119 r"""Compute betweenness centrality for edges for a subset of nodes.
121 .. math::
123 c_B(e) = \sum_{s \in S, t \in T} \frac{\sigma(s, t | e)}{\sigma(s, t)}
125 where $S$ is the set of sources, $T$ is the set of targets,
126 $\sigma(s, t)$ is the number of shortest $(s, t)$-paths,
127 and $\sigma(s, t | e)$ is the number of those paths
128 passing through edge $e$ [1]_.
129 The denominator $\sigma(s, t)$ is a normalization factor that can be
130 turned off to get the raw path counts.
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 (default=False)
144 If `True`, the betweenness values are rescaled by dividing by the number of
145 possible $(s, t)$-pairs in the graph.
147 weight : None or string, optional (default=None)
148 If `None`, all edge weights are 1.
149 Otherwise holds the name of the edge attribute used as weight.
150 Weights are used to calculate weighted shortest paths, so they are
151 interpreted as distances.
153 Returns
154 -------
155 edges : dict
156 Dictionary of edges with betweenness centrality as the value.
158 See Also
159 --------
160 betweenness_centrality
161 betweenness_centrality_subset
162 edge_betweenness_centrality
163 edge_load
165 Notes
166 -----
167 The basic algorithm is from [1]_.
169 For weighted graphs the edge weights must be greater than zero.
170 Zero edge weights can produce an infinite number of equal length
171 paths between pairs of nodes.
173 The normalization might seem a little strange but it is the same
174 as in edge_betweenness_centrality() and is designed to make
175 edge_betweenness_centrality(G) be the same as
176 edge_betweenness_centrality_subset(G,sources=G.nodes(),targets=G.nodes()).
178 References
179 ----------
180 .. [1] Ulrik Brandes: On Variants of Shortest-Path Betweenness
181 Centrality and their Generic Computation.
182 Social Networks 30(2):136-145, 2008.
183 https://doi.org/10.1016/j.socnet.2007.11.001
184 """
185 b = dict.fromkeys(G, 0.0) # b[v]=0 for v in G
186 b.update(dict.fromkeys(G.edges(), 0.0)) # b[e] for e in G.edges()
187 for s in sources:
188 # single source shortest paths
189 if weight is None: # use BFS
190 S, P, sigma, _ = shortest_path(G, s)
191 else: # use Dijkstra's algorithm
192 S, P, sigma, _ = dijkstra(G, s, weight)
193 b = _accumulate_edges_subset(b, S, P, sigma, s, targets)
194 for n in G: # remove nodes to only return edges
195 del b[n]
196 b = _rescale(b, len(G), normalized=normalized, directed=G.is_directed())
197 if G.is_multigraph():
198 b = _add_edge_keys(G, b, weight=weight)
199 return b
202def _accumulate_subset(betweenness, S, P, sigma, s, targets):
203 delta = dict.fromkeys(S, 0.0)
204 target_set = set(targets) - {s}
205 while S:
206 w = S.pop()
207 if w in target_set:
208 coeff = (delta[w] + 1.0) / sigma[w]
209 else:
210 coeff = delta[w] / sigma[w]
211 for v in P[w]:
212 delta[v] += sigma[v] * coeff
213 if w != s:
214 betweenness[w] += delta[w]
215 return betweenness
218def _accumulate_edges_subset(betweenness, S, P, sigma, s, targets):
219 """edge_betweenness_centrality_subset helper."""
220 delta = dict.fromkeys(S, 0)
221 target_set = set(targets)
222 while S:
223 w = S.pop()
224 for v in P[w]:
225 if w in target_set:
226 c = (sigma[v] / sigma[w]) * (1.0 + delta[w])
227 else:
228 c = delta[w] / len(P[w])
229 if (v, w) not in betweenness:
230 betweenness[(w, v)] += c
231 else:
232 betweenness[(v, w)] += c
233 delta[v] += c
234 if w != s:
235 betweenness[w] += delta[w]
236 return betweenness