### annotate env/lib/python3.9/site-packages/networkx/algorithms/centrality/katz.py @ 0:4f3585e2f14bdraftdefaulttip

author shellac Mon, 22 Mar 2021 18:12:50 +0000
Ignore whitespace changes - Everywhere: Within whitespace: At end of lines:
rev   line source
0
shellac
parents:
diff changeset
1 """Katz centrality."""
shellac
parents:
diff changeset
2 from math import sqrt
shellac
parents:
diff changeset
3
shellac
parents:
diff changeset
4 import networkx as nx
shellac
parents:
diff changeset
5 from networkx.utils import not_implemented_for
shellac
parents:
diff changeset
6
shellac
parents:
diff changeset
7 __all__ = ["katz_centrality", "katz_centrality_numpy"]
shellac
parents:
diff changeset
8
shellac
parents:
diff changeset
9
shellac
parents:
diff changeset
10 @not_implemented_for("multigraph")
shellac
parents:
diff changeset
11 def katz_centrality(
shellac
parents:
diff changeset
12 G,
shellac
parents:
diff changeset
13 alpha=0.1,
shellac
parents:
diff changeset
14 beta=1.0,
shellac
parents:
diff changeset
15 max_iter=1000,
shellac
parents:
diff changeset
16 tol=1.0e-6,
shellac
parents:
diff changeset
17 nstart=None,
shellac
parents:
diff changeset
18 normalized=True,
shellac
parents:
diff changeset
19 weight=None,
shellac
parents:
diff changeset
20 ):
shellac
parents:
diff changeset
21 r"""Compute the Katz centrality for the nodes of the graph G.
shellac
parents:
diff changeset
22
shellac
parents:
diff changeset
23 Katz centrality computes the centrality for a node based on the centrality
shellac
parents:
diff changeset
24 of its neighbors. It is a generalization of the eigenvector centrality. The
shellac
parents:
diff changeset
25 Katz centrality for node $i$ is
shellac
parents:
diff changeset
26
shellac
parents:
diff changeset
27 .. math::
shellac
parents:
diff changeset
28
shellac
parents:
diff changeset
29 x_i = \alpha \sum_{j} A_{ij} x_j + \beta,
shellac
parents:
diff changeset
30
shellac
parents:
diff changeset
31 where $A$ is the adjacency matrix of graph G with eigenvalues $\lambda$.
shellac
parents:
diff changeset
32
shellac
parents:
diff changeset
33 The parameter $\beta$ controls the initial centrality and
shellac
parents:
diff changeset
34
shellac
parents:
diff changeset
35 .. math::
shellac
parents:
diff changeset
36
shellac
parents:
diff changeset
37 \alpha < \frac{1}{\lambda_{\max}}.
shellac
parents:
diff changeset
38
shellac
parents:
diff changeset
39 Katz centrality computes the relative influence of a node within a
shellac
parents:
diff changeset
40 network by measuring the number of the immediate neighbors (first
shellac
parents:
diff changeset
41 degree nodes) and also all other nodes in the network that connect
shellac
parents:
diff changeset
42 to the node under consideration through these immediate neighbors.
shellac
parents:
diff changeset
43
shellac
parents:
diff changeset
44 Extra weight can be provided to immediate neighbors through the
shellac
parents:
diff changeset
45 parameter $\beta$. Connections made with distant neighbors
shellac
parents:
diff changeset
46 are, however, penalized by an attenuation factor $\alpha$ which
shellac
parents:
diff changeset
47 should be strictly less than the inverse largest eigenvalue of the
shellac
parents:
diff changeset
48 adjacency matrix in order for the Katz centrality to be computed
shellac
parents:
diff changeset
49 correctly. More information is provided in [1]_.
shellac
parents:
diff changeset
50
shellac
parents:
diff changeset
51 Parameters
shellac
parents:
diff changeset
52 ----------
shellac
parents:
diff changeset
53 G : graph
shellac
parents:
diff changeset
54 A NetworkX graph.
shellac
parents:
diff changeset
55
shellac
parents:
diff changeset
56 alpha : float
shellac
parents:
diff changeset
57 Attenuation factor
shellac
parents:
diff changeset
58
shellac
parents:
diff changeset
59 beta : scalar or dictionary, optional (default=1.0)
shellac
parents:
diff changeset
60 Weight attributed to the immediate neighborhood. If not a scalar, the
shellac
parents:
diff changeset
61 dictionary must have an value for every node.
shellac
parents:
diff changeset
62
shellac
parents:
diff changeset
63 max_iter : integer, optional (default=1000)
shellac
parents:
diff changeset
64 Maximum number of iterations in power method.
shellac
parents:
diff changeset
65
shellac
parents:
diff changeset
66 tol : float, optional (default=1.0e-6)
shellac
parents:
diff changeset
67 Error tolerance used to check convergence in power method iteration.
shellac
parents:
diff changeset
68
shellac
parents:
diff changeset
69 nstart : dictionary, optional
shellac
parents:
diff changeset
70 Starting value of Katz iteration for each node.
shellac
parents:
diff changeset
71
shellac
parents:
diff changeset
72 normalized : bool, optional (default=True)
shellac
parents:
diff changeset
73 If True normalize the resulting values.
shellac
parents:
diff changeset
74
shellac
parents:
diff changeset
75 weight : None or string, optional (default=None)
shellac
parents:
diff changeset
76 If None, all edge weights are considered equal.
shellac
parents:
diff changeset
77 Otherwise holds the name of the edge attribute used as weight.
shellac
parents:
diff changeset
78
shellac
parents:
diff changeset
79 Returns
shellac
parents:
diff changeset
80 -------
shellac
parents:
diff changeset
81 nodes : dictionary
shellac
parents:
diff changeset
82 Dictionary of nodes with Katz centrality as the value.
shellac
parents:
diff changeset
83
shellac
parents:
diff changeset
84 Raises
shellac
parents:
diff changeset
85 ------
shellac
parents:
diff changeset
86 NetworkXError
shellac
parents:
diff changeset
87 If the parameter beta is not a scalar but lacks a value for at least
shellac
parents:
diff changeset
88 one node
shellac
parents:
diff changeset
89
shellac
parents:
diff changeset
90 PowerIterationFailedConvergence
shellac
parents:
diff changeset
91 If the algorithm fails to converge to the specified tolerance
shellac
parents:
diff changeset
92 within the specified number of iterations of the power iteration
shellac
parents:
diff changeset
93 method.
shellac
parents:
diff changeset
94
shellac
parents:
diff changeset
95 Examples
shellac
parents:
diff changeset
96 --------
shellac
parents:
diff changeset
97 >>> import math
shellac
parents:
diff changeset
98 >>> G = nx.path_graph(4)
shellac
parents:
diff changeset
99 >>> phi = (1 + math.sqrt(5)) / 2.0 # largest eigenvalue of adj matrix
shellac
parents:
diff changeset
100 >>> centrality = nx.katz_centrality(G, 1 / phi - 0.01)
shellac
parents:
diff changeset
101 >>> for n, c in sorted(centrality.items()):
shellac
parents:
diff changeset
102 ... print(f"{n} {c:.2f}")
shellac
parents:
diff changeset
103 0 0.37
shellac
parents:
diff changeset
104 1 0.60
shellac
parents:
diff changeset
105 2 0.60
shellac
parents:
diff changeset
106 3 0.37
shellac
parents:
diff changeset
107
shellac
parents:
diff changeset
shellac
parents:
diff changeset
109 --------
shellac
parents:
diff changeset
110 katz_centrality_numpy
shellac
parents:
diff changeset
111 eigenvector_centrality
shellac
parents:
diff changeset
112 eigenvector_centrality_numpy
shellac
parents:
diff changeset
113 pagerank
shellac
parents:
diff changeset
114 hits
shellac
parents:
diff changeset
115
shellac
parents:
diff changeset
116 Notes
shellac
parents:
diff changeset
117 -----
shellac
parents:
diff changeset
118 Katz centrality was introduced by [2]_.
shellac
parents:
diff changeset
119
shellac
parents:
diff changeset
120 This algorithm it uses the power method to find the eigenvector
shellac
parents:
diff changeset
121 corresponding to the largest eigenvalue of the adjacency matrix of G.
shellac
parents:
diff changeset
122 The parameter alpha should be strictly less than the inverse of largest
shellac
parents:
diff changeset
123 eigenvalue of the adjacency matrix for the algorithm to converge.
shellac
parents:
diff changeset
124 You can use max(nx.adjacency_spectrum(G)) to get $\lambda_{\max}$ the largest
shellac
parents:
diff changeset
125 eigenvalue of the adjacency matrix.
shellac
parents:
diff changeset
126 The iteration will stop after max_iter iterations or an error tolerance of
shellac
parents:
diff changeset
127 number_of_nodes(G) * tol has been reached.
shellac
parents:
diff changeset
128
shellac
parents:
diff changeset
129 When $\alpha = 1/\lambda_{\max}$ and $\beta=0$, Katz centrality is the same
shellac
parents:
diff changeset
130 as eigenvector centrality.
shellac
parents:
diff changeset
131
shellac
parents:
diff changeset
132 For directed graphs this finds "left" eigenvectors which corresponds
shellac
parents:
diff changeset
133 to the in-edges in the graph. For out-edges Katz centrality
shellac
parents:
diff changeset
134 first reverse the graph with G.reverse().
shellac
parents:
diff changeset
135
shellac
parents:
diff changeset
136 References
shellac
parents:
diff changeset
137 ----------
shellac
parents:
diff changeset
138 .. [1] Mark E. J. Newman:
shellac
parents:
diff changeset
139 Networks: An Introduction.
shellac
parents:
diff changeset
140 Oxford University Press, USA, 2010, p. 720.
shellac
parents:
diff changeset
141 .. [2] Leo Katz:
shellac
parents:
diff changeset
142 A New Status Index Derived from Sociometric Index.
shellac
parents:
diff changeset
143 Psychometrika 18(1):39–43, 1953
shellac
parents:
diff changeset
144 http://phya.snu.ac.kr/~dkim/PRL87278701.pdf
shellac
parents:
diff changeset
145 """
shellac
parents:
diff changeset
146 if len(G) == 0:
shellac
parents:
diff changeset
147 return {}
shellac
parents:
diff changeset
148
shellac
parents:
diff changeset
149 nnodes = G.number_of_nodes()
shellac
parents:
diff changeset
150
shellac
parents:
diff changeset
151 if nstart is None:
shellac
parents:
diff changeset
152 # choose starting vector with entries of 0
shellac
parents:
diff changeset
153 x = {n: 0 for n in G}
shellac
parents:
diff changeset
154 else:
shellac
parents:
diff changeset
155 x = nstart
shellac
parents:
diff changeset
156
shellac
parents:
diff changeset
157 try:
shellac
parents:
diff changeset
158 b = dict.fromkeys(G, float(beta))
shellac
parents:
diff changeset
159 except (TypeError, ValueError, AttributeError) as e:
shellac
parents:
diff changeset
160 b = beta
shellac
parents:
diff changeset
161 if set(beta) != set(G):
shellac
parents:
diff changeset
162 raise nx.NetworkXError(
shellac
parents:
diff changeset
163 "beta dictionary " "must have a value for every node"
shellac
parents:
diff changeset
164 ) from e
shellac
parents:
diff changeset
165
shellac
parents:
diff changeset
166 # make up to max_iter iterations
shellac
parents:
diff changeset
167 for i in range(max_iter):
shellac
parents:
diff changeset
168 xlast = x
shellac
parents:
diff changeset
169 x = dict.fromkeys(xlast, 0)
shellac
parents:
diff changeset
170 # do the multiplication y^T = Alpha * x^T A - Beta
shellac
parents:
diff changeset
171 for n in x:
shellac
parents:
diff changeset
172 for nbr in G[n]:
shellac
parents:
diff changeset
173 x[nbr] += xlast[n] * G[n][nbr].get(weight, 1)
shellac
parents:
diff changeset
174 for n in x:
shellac
parents:
diff changeset
175 x[n] = alpha * x[n] + b[n]
shellac
parents:
diff changeset
176
shellac
parents:
diff changeset
177 # check convergence
shellac
parents:
diff changeset
178 err = sum([abs(x[n] - xlast[n]) for n in x])
shellac
parents:
diff changeset
179 if err < nnodes * tol:
shellac
parents:
diff changeset
180 if normalized:
shellac
parents:
diff changeset
181 # normalize vector
shellac
parents:
diff changeset
182 try:
shellac
parents:
diff changeset
183 s = 1.0 / sqrt(sum(v ** 2 for v in x.values()))
shellac
parents:
diff changeset
184 # this should never be zero?
shellac
parents:
diff changeset
185 except ZeroDivisionError:
shellac
parents:
diff changeset
186 s = 1.0
shellac
parents:
diff changeset
187 else:
shellac
parents:
diff changeset
188 s = 1
shellac
parents:
diff changeset
189 for n in x:
shellac
parents:
diff changeset
190 x[n] *= s
shellac
parents:
diff changeset
191 return x
shellac
parents:
diff changeset
192 raise nx.PowerIterationFailedConvergence(max_iter)
shellac
parents:
diff changeset
193
shellac
parents:
diff changeset
194
shellac
parents:
diff changeset
195 @not_implemented_for("multigraph")
shellac
parents:
diff changeset
196 def katz_centrality_numpy(G, alpha=0.1, beta=1.0, normalized=True, weight=None):
shellac
parents:
diff changeset
197 r"""Compute the Katz centrality for the graph G.
shellac
parents:
diff changeset
198
shellac
parents:
diff changeset
199 Katz centrality computes the centrality for a node based on the centrality
shellac
parents:
diff changeset
200 of its neighbors. It is a generalization of the eigenvector centrality. The
shellac
parents:
diff changeset
201 Katz centrality for node $i$ is
shellac
parents:
diff changeset
202
shellac
parents:
diff changeset
203 .. math::
shellac
parents:
diff changeset
204
shellac
parents:
diff changeset
205 x_i = \alpha \sum_{j} A_{ij} x_j + \beta,
shellac
parents:
diff changeset
206
shellac
parents:
diff changeset
207 where $A$ is the adjacency matrix of graph G with eigenvalues $\lambda$.
shellac
parents:
diff changeset
208
shellac
parents:
diff changeset
209 The parameter $\beta$ controls the initial centrality and
shellac
parents:
diff changeset
210
shellac
parents:
diff changeset
211 .. math::
shellac
parents:
diff changeset
212
shellac
parents:
diff changeset
213 \alpha < \frac{1}{\lambda_{\max}}.
shellac
parents:
diff changeset
214
shellac
parents:
diff changeset
215 Katz centrality computes the relative influence of a node within a
shellac
parents:
diff changeset
216 network by measuring the number of the immediate neighbors (first
shellac
parents:
diff changeset
217 degree nodes) and also all other nodes in the network that connect
shellac
parents:
diff changeset
218 to the node under consideration through these immediate neighbors.
shellac
parents:
diff changeset
219
shellac
parents:
diff changeset
220 Extra weight can be provided to immediate neighbors through the
shellac
parents:
diff changeset
221 parameter $\beta$. Connections made with distant neighbors
shellac
parents:
diff changeset
222 are, however, penalized by an attenuation factor $\alpha$ which
shellac
parents:
diff changeset
223 should be strictly less than the inverse largest eigenvalue of the
shellac
parents:
diff changeset
224 adjacency matrix in order for the Katz centrality to be computed
shellac
parents:
diff changeset
225 correctly. More information is provided in [1]_.
shellac
parents:
diff changeset
226
shellac
parents:
diff changeset
227 Parameters
shellac
parents:
diff changeset
228 ----------
shellac
parents:
diff changeset
229 G : graph
shellac
parents:
diff changeset
230 A NetworkX graph
shellac
parents:
diff changeset
231
shellac
parents:
diff changeset
232 alpha : float
shellac
parents:
diff changeset
233 Attenuation factor
shellac
parents:
diff changeset
234
shellac
parents:
diff changeset
235 beta : scalar or dictionary, optional (default=1.0)
shellac
parents:
diff changeset
236 Weight attributed to the immediate neighborhood. If not a scalar the
shellac
parents:
diff changeset
237 dictionary must have an value for every node.
shellac
parents:
diff changeset
238
shellac
parents:
diff changeset
239 normalized : bool
shellac
parents:
diff changeset
240 If True normalize the resulting values.
shellac
parents:
diff changeset
241
shellac
parents:
diff changeset
242 weight : None or string, optional
shellac
parents:
diff changeset
243 If None, all edge weights are considered equal.
shellac
parents:
diff changeset
244 Otherwise holds the name of the edge attribute used as weight.
shellac
parents:
diff changeset
245
shellac
parents:
diff changeset
246 Returns
shellac
parents:
diff changeset
247 -------
shellac
parents:
diff changeset
248 nodes : dictionary
shellac
parents:
diff changeset
249 Dictionary of nodes with Katz centrality as the value.
shellac
parents:
diff changeset
250
shellac
parents:
diff changeset
251 Raises
shellac
parents:
diff changeset
252 ------
shellac
parents:
diff changeset
253 NetworkXError
shellac
parents:
diff changeset
254 If the parameter beta is not a scalar but lacks a value for at least
shellac
parents:
diff changeset
255 one node
shellac
parents:
diff changeset
256
shellac
parents:
diff changeset
257 Examples
shellac
parents:
diff changeset
258 --------
shellac
parents:
diff changeset
259 >>> import math
shellac
parents:
diff changeset
260 >>> G = nx.path_graph(4)
shellac
parents:
diff changeset
261 >>> phi = (1 + math.sqrt(5)) / 2.0 # largest eigenvalue of adj matrix
shellac
parents:
diff changeset
262 >>> centrality = nx.katz_centrality_numpy(G, 1 / phi)
shellac
parents:
diff changeset
263 >>> for n, c in sorted(centrality.items()):
shellac
parents:
diff changeset
264 ... print(f"{n} {c:.2f}")
shellac
parents:
diff changeset
265 0 0.37
shellac
parents:
diff changeset
266 1 0.60
shellac
parents:
diff changeset
267 2 0.60
shellac
parents:
diff changeset
268 3 0.37
shellac
parents:
diff changeset
269
shellac
parents:
diff changeset
shellac
parents:
diff changeset
271 --------
shellac
parents:
diff changeset
272 katz_centrality
shellac
parents:
diff changeset
273 eigenvector_centrality_numpy
shellac
parents:
diff changeset
274 eigenvector_centrality
shellac
parents:
diff changeset
275 pagerank
shellac
parents:
diff changeset
276 hits
shellac
parents:
diff changeset
277
shellac
parents:
diff changeset
278 Notes
shellac
parents:
diff changeset
279 -----
shellac
parents:
diff changeset
280 Katz centrality was introduced by [2]_.
shellac
parents:
diff changeset
281
shellac
parents:
diff changeset
282 This algorithm uses a direct linear solver to solve the above equation.
shellac
parents:
diff changeset
283 The parameter alpha should be strictly less than the inverse of largest
shellac
parents:
diff changeset
284 eigenvalue of the adjacency matrix for there to be a solution.
shellac
parents:
diff changeset
285 You can use max(nx.adjacency_spectrum(G)) to get $\lambda_{\max}$ the largest
shellac
parents:
diff changeset
286 eigenvalue of the adjacency matrix.
shellac
parents:
diff changeset
287
shellac
parents:
diff changeset
288 When $\alpha = 1/\lambda_{\max}$ and $\beta=0$, Katz centrality is the same
shellac
parents:
diff changeset
289 as eigenvector centrality.
shellac
parents:
diff changeset
290
shellac
parents:
diff changeset
291 For directed graphs this finds "left" eigenvectors which corresponds
shellac
parents:
diff changeset
292 to the in-edges in the graph. For out-edges Katz centrality
shellac
parents:
diff changeset
293 first reverse the graph with G.reverse().
shellac
parents:
diff changeset
294
shellac
parents:
diff changeset
295 References
shellac
parents:
diff changeset
296 ----------
shellac
parents:
diff changeset
297 .. [1] Mark E. J. Newman:
shellac
parents:
diff changeset
298 Networks: An Introduction.
shellac
parents:
diff changeset
299 Oxford University Press, USA, 2010, p. 720.
shellac
parents:
diff changeset
300 .. [2] Leo Katz:
shellac
parents:
diff changeset
301 A New Status Index Derived from Sociometric Index.
shellac
parents:
diff changeset
302 Psychometrika 18(1):39–43, 1953
shellac
parents:
diff changeset
303 http://phya.snu.ac.kr/~dkim/PRL87278701.pdf
shellac
parents:
diff changeset
304 """
shellac
parents:
diff changeset
305 try:
shellac
parents:
diff changeset
306 import numpy as np
shellac
parents:
diff changeset
307 except ImportError as e:
shellac
parents:
diff changeset
308 raise ImportError("Requires NumPy: http://numpy.org/") from e
shellac
parents:
diff changeset
309 if len(G) == 0:
shellac
parents:
diff changeset
310 return {}
shellac
parents:
diff changeset
311 try:
shellac
parents:
diff changeset
312 nodelist = beta.keys()
shellac
parents:
diff changeset
313 if set(nodelist) != set(G):
shellac
parents:
diff changeset
314 raise nx.NetworkXError(
shellac
parents:
diff changeset
315 "beta dictionary " "must have a value for every node"
shellac
parents:
diff changeset
316 )
shellac
parents:
diff changeset
317 b = np.array(list(beta.values()), dtype=float)
shellac
parents:
diff changeset
318 except AttributeError:
shellac
parents:
diff changeset
319 nodelist = list(G)
shellac
parents:
diff changeset
320 try:
shellac
parents:
diff changeset
321 b = np.ones((len(nodelist), 1)) * float(beta)
shellac
parents:
diff changeset
322 except (TypeError, ValueError, AttributeError) as e:
shellac
parents:
diff changeset
323 raise nx.NetworkXError("beta must be a number") from e
shellac
parents:
diff changeset
324
shellac
parents:
diff changeset
325 A = nx.adj_matrix(G, nodelist=nodelist, weight=weight).todense().T
shellac
parents:
diff changeset
326 n = A.shape[0]
shellac
parents:
diff changeset
327 centrality = np.linalg.solve(np.eye(n, n) - (alpha * A), b)
shellac
parents:
diff changeset
328 if normalized:
shellac
parents:
diff changeset
329 norm = np.sign(sum(centrality)) * np.linalg.norm(centrality)
shellac
parents:
diff changeset
330 else:
shellac
parents:
diff changeset
331 norm = 1.0