Mercurial > repos > shellac > sam_consensus_v3
comparison env/lib/python3.9/site-packages/networkx/algorithms/centrality/katz.py @ 0:4f3585e2f14b draft default tip
"planemo upload commit 60cee0fc7c0cda8592644e1aad72851dec82c959"
author | shellac |
---|---|
date | Mon, 22 Mar 2021 18:12:50 +0000 |
parents | |
children |
comparison
equal
deleted
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 | |
49 correctly. More information is provided in [1]_. | |
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 | |
108 See Also | |
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 | |
225 correctly. More information is provided in [1]_. | |
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 | |
270 See Also | |
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 |