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

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