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"""Load centrality."""
3from operator import itemgetter
5import networkx as nx
7__all__ = ["load_centrality", "edge_load_centrality"]
10@nx._dispatchable(edge_attrs="weight")
11def newman_betweenness_centrality(G, v=None, cutoff=None, normalized=True, weight=None):
12 """Compute load centrality for nodes.
14 The load centrality of a node is the fraction of all shortest
15 paths that pass through that node.
17 Parameters
18 ----------
19 G : graph
20 A networkx graph.
22 normalized : bool, optional (default=True)
23 If True the betweenness values are normalized by b=b/(n-1)(n-2) where
24 n is the number of nodes in G.
26 weight : None or string, optional (default=None)
27 If None, edge weights are ignored.
28 Otherwise holds the name of the edge attribute used as weight.
29 The weight of an edge is treated as the length or distance between the two sides.
31 cutoff : bool, optional (default=None)
32 If specified, only consider paths of length <= cutoff.
34 Returns
35 -------
36 nodes : dictionary
37 Dictionary of nodes with centrality as the value.
39 See Also
40 --------
41 betweenness_centrality
43 Notes
44 -----
45 Load centrality is slightly different than betweenness. It was originally
46 introduced by [2]_. For this load algorithm see [1]_.
48 References
49 ----------
50 .. [1] Mark E. J. Newman:
51 Scientific collaboration networks. II.
52 Shortest paths, weighted networks, and centrality.
53 Physical Review E 64, 016132, 2001.
54 http://journals.aps.org/pre/abstract/10.1103/PhysRevE.64.016132
55 .. [2] Kwang-Il Goh, Byungnam Kahng and Doochul Kim
56 Universal behavior of Load Distribution in Scale-Free Networks.
57 Physical Review Letters 87(27):1–4, 2001.
58 https://doi.org/10.1103/PhysRevLett.87.278701
59 """
60 if v is not None: # only one node
61 betweenness = 0.0
62 for source in G:
63 ubetween = _node_betweenness(G, source, cutoff, False, weight)
64 betweenness += ubetween[v] if v in ubetween else 0
65 if normalized:
66 order = G.order()
67 if order <= 2:
68 return betweenness # no normalization b=0 for all nodes
69 betweenness *= 1.0 / ((order - 1) * (order - 2))
70 else:
71 betweenness = {}.fromkeys(G, 0.0)
72 for source in betweenness:
73 ubetween = _node_betweenness(G, source, cutoff, False, weight)
74 for vk in ubetween:
75 betweenness[vk] += ubetween[vk]
76 if normalized:
77 order = G.order()
78 if order <= 2:
79 return betweenness # no normalization b=0 for all nodes
80 scale = 1.0 / ((order - 1) * (order - 2))
81 for v in betweenness:
82 betweenness[v] *= scale
83 return betweenness # all nodes
86def _node_betweenness(G, source, cutoff=False, normalized=True, weight=None):
87 """Node betweenness_centrality helper:
89 See betweenness_centrality for what you probably want.
90 This actually computes "load" and not betweenness.
91 See https://networkx.lanl.gov/ticket/103
93 This calculates the load of each node for paths from a single source.
94 (The fraction of number of shortests paths from source that go
95 through each node.)
97 To get the load for a node you need to do all-pairs shortest paths.
99 If weight is not None then use Dijkstra for finding shortest paths.
100 """
101 # get the predecessor and path length data
102 if weight is None:
103 (pred, length) = nx.predecessor(G, source, cutoff=cutoff, return_seen=True)
104 else:
105 (pred, length) = nx.dijkstra_predecessor_and_distance(G, source, cutoff, weight)
107 # order the nodes by path length
108 onodes = [(l, vert) for (vert, l) in length.items()]
109 onodes.sort()
110 onodes[:] = [vert for (l, vert) in onodes if l > 0]
112 # initialize betweenness
113 between = {}.fromkeys(length, 1.0)
115 while onodes:
116 v = onodes.pop()
117 if v in pred:
118 num_paths = len(pred[v]) # Discount betweenness if more than
119 for x in pred[v]: # one shortest path.
120 if x == source: # stop if hit source because all remaining v
121 break # also have pred[v]==[source]
122 between[x] += between[v] / num_paths
123 # remove source
124 for v in between:
125 between[v] -= 1
126 # rescale to be between 0 and 1
127 if normalized:
128 l = len(between)
129 if l > 2:
130 # scale by 1/the number of possible paths
131 scale = 1 / ((l - 1) * (l - 2))
132 for v in between:
133 between[v] *= scale
134 return between
137load_centrality = newman_betweenness_centrality
140@nx._dispatchable
141def edge_load_centrality(G, cutoff=False):
142 """Compute edge load.
144 WARNING: This concept of edge load has not been analysed
145 or discussed outside of NetworkX that we know of.
146 It is based loosely on load_centrality in the sense that
147 it counts the number of shortest paths which cross each edge.
148 This function is for demonstration and testing purposes.
150 Parameters
151 ----------
152 G : graph
153 A networkx graph
155 cutoff : bool, optional (default=False)
156 If specified, only consider paths of length <= cutoff.
158 Returns
159 -------
160 A dict keyed by edge 2-tuple to the number of shortest paths
161 which use that edge. Where more than one path is shortest
162 the count is divided equally among paths.
163 """
164 betweenness = {}
165 for u, v in G.edges():
166 betweenness[(u, v)] = 0.0
167 betweenness[(v, u)] = 0.0
169 for source in G:
170 ubetween = _edge_betweenness(G, source, cutoff=cutoff)
171 for e, ubetweenv in ubetween.items():
172 betweenness[e] += ubetweenv # cumulative total
173 return betweenness
176def _edge_betweenness(G, source, nodes=None, cutoff=False):
177 """Edge betweenness helper."""
178 # get the predecessor data
179 (pred, length) = nx.predecessor(G, source, cutoff=cutoff, return_seen=True)
180 # order the nodes by path length
181 onodes = [n for n, d in sorted(length.items(), key=itemgetter(1))]
182 # initialize betweenness, doesn't account for any edge weights
183 between = {}
184 for u, v in G.edges(nodes):
185 between[(u, v)] = 1.0
186 between[(v, u)] = 1.0
188 while onodes: # work through all paths
189 v = onodes.pop()
190 if v in pred:
191 # Discount betweenness if more than one shortest path.
192 num_paths = len(pred[v])
193 for w in pred[v]:
194 if w in pred:
195 # Discount betweenness, mult path
196 num_paths = len(pred[w])
197 for x in pred[w]:
198 between[(w, x)] += between[(v, w)] / num_paths
199 between[(x, w)] += between[(w, v)] / num_paths
200 return between