Coverage for /pythoncovmergedfiles/medio/medio/usr/local/lib/python3.9/dist-packages/networkx/algorithms/centrality/katz.py: 16%
61 statements
« prev ^ index » next coverage.py v7.3.2, created at 2023-10-20 07:00 +0000
1"""Katz centrality."""
2import math
4import networkx as nx
5from networkx.utils import not_implemented_for
7__all__ = ["katz_centrality", "katz_centrality_numpy"]
10@not_implemented_for("multigraph")
11@nx._dispatch(edge_attrs="weight")
12def katz_centrality(
13 G,
14 alpha=0.1,
15 beta=1.0,
16 max_iter=1000,
17 tol=1.0e-6,
18 nstart=None,
19 normalized=True,
20 weight=None,
21):
22 r"""Compute the Katz centrality for the nodes of the graph G.
24 Katz centrality computes the centrality for a node based on the centrality
25 of its neighbors. It is a generalization of the eigenvector centrality. The
26 Katz centrality for node $i$ is
28 .. math::
30 x_i = \alpha \sum_{j} A_{ij} x_j + \beta,
32 where $A$ is the adjacency matrix of graph G with eigenvalues $\lambda$.
34 The parameter $\beta$ controls the initial centrality and
36 .. math::
38 \alpha < \frac{1}{\lambda_{\max}}.
40 Katz centrality computes the relative influence of a node within a
41 network by measuring the number of the immediate neighbors (first
42 degree nodes) and also all other nodes in the network that connect
43 to the node under consideration through these immediate neighbors.
45 Extra weight can be provided to immediate neighbors through the
46 parameter $\beta$. Connections made with distant neighbors
47 are, however, penalized by an attenuation factor $\alpha$ which
48 should be strictly less than the inverse largest eigenvalue of the
49 adjacency matrix in order for the Katz centrality to be computed
50 correctly. More information is provided in [1]_.
52 Parameters
53 ----------
54 G : graph
55 A NetworkX graph.
57 alpha : float, optional (default=0.1)
58 Attenuation factor
60 beta : scalar or dictionary, optional (default=1.0)
61 Weight attributed to the immediate neighborhood. If not a scalar, the
62 dictionary must have an value for every node.
64 max_iter : integer, optional (default=1000)
65 Maximum number of iterations in power method.
67 tol : float, optional (default=1.0e-6)
68 Error tolerance used to check convergence in power method iteration.
70 nstart : dictionary, optional
71 Starting value of Katz iteration for each node.
73 normalized : bool, optional (default=True)
74 If True normalize the resulting values.
76 weight : None or string, optional (default=None)
77 If None, all edge weights are considered equal.
78 Otherwise holds the name of the edge attribute used as weight.
79 In this measure the weight is interpreted as the connection strength.
81 Returns
82 -------
83 nodes : dictionary
84 Dictionary of nodes with Katz centrality as the value.
86 Raises
87 ------
88 NetworkXError
89 If the parameter `beta` is not a scalar but lacks a value for at least
90 one node
92 PowerIterationFailedConvergence
93 If the algorithm fails to converge to the specified tolerance
94 within the specified number of iterations of the power iteration
95 method.
97 Examples
98 --------
99 >>> import math
100 >>> G = nx.path_graph(4)
101 >>> phi = (1 + math.sqrt(5)) / 2.0 # largest eigenvalue of adj matrix
102 >>> centrality = nx.katz_centrality(G, 1 / phi - 0.01)
103 >>> for n, c in sorted(centrality.items()):
104 ... print(f"{n} {c:.2f}")
105 0 0.37
106 1 0.60
107 2 0.60
108 3 0.37
110 See Also
111 --------
112 katz_centrality_numpy
113 eigenvector_centrality
114 eigenvector_centrality_numpy
115 :func:`~networkx.algorithms.link_analysis.pagerank_alg.pagerank`
116 :func:`~networkx.algorithms.link_analysis.hits_alg.hits`
118 Notes
119 -----
120 Katz centrality was introduced by [2]_.
122 This algorithm it uses the power method to find the eigenvector
123 corresponding to the largest eigenvalue of the adjacency matrix of ``G``.
124 The parameter ``alpha`` should be strictly less than the inverse of largest
125 eigenvalue of the adjacency matrix for the algorithm to converge.
126 You can use ``max(nx.adjacency_spectrum(G))`` to get $\lambda_{\max}$ the largest
127 eigenvalue of the adjacency matrix.
128 The iteration will stop after ``max_iter`` iterations or an error tolerance of
129 ``number_of_nodes(G) * tol`` has been reached.
131 When $\alpha = 1/\lambda_{\max}$ and $\beta=0$, Katz centrality is the same
132 as eigenvector centrality.
134 For directed graphs this finds "left" eigenvectors which corresponds
135 to the in-edges in the graph. For out-edges Katz centrality
136 first reverse the graph with ``G.reverse()``.
138 References
139 ----------
140 .. [1] Mark E. J. Newman:
141 Networks: An Introduction.
142 Oxford University Press, USA, 2010, p. 720.
143 .. [2] Leo Katz:
144 A New Status Index Derived from Sociometric Index.
145 Psychometrika 18(1):39–43, 1953
146 https://link.springer.com/content/pdf/10.1007/BF02289026.pdf
147 """
148 if len(G) == 0:
149 return {}
151 nnodes = G.number_of_nodes()
153 if nstart is None:
154 # choose starting vector with entries of 0
155 x = {n: 0 for n in G}
156 else:
157 x = nstart
159 try:
160 b = dict.fromkeys(G, float(beta))
161 except (TypeError, ValueError, AttributeError) as err:
162 b = beta
163 if set(beta) != set(G):
164 raise nx.NetworkXError(
165 "beta dictionary " "must have a value for every node"
166 ) from err
168 # make up to max_iter iterations
169 for _ in range(max_iter):
170 xlast = x
171 x = dict.fromkeys(xlast, 0)
172 # do the multiplication y^T = Alpha * x^T A + Beta
173 for n in x:
174 for nbr in G[n]:
175 x[nbr] += xlast[n] * G[n][nbr].get(weight, 1)
176 for n in x:
177 x[n] = alpha * x[n] + b[n]
179 # check convergence
180 error = sum(abs(x[n] - xlast[n]) for n in x)
181 if error < nnodes * tol:
182 if normalized:
183 # normalize vector
184 try:
185 s = 1.0 / math.hypot(*x.values())
186 # this should never be zero?
187 except ZeroDivisionError:
188 s = 1.0
189 else:
190 s = 1
191 for n in x:
192 x[n] *= s
193 return x
194 raise nx.PowerIterationFailedConvergence(max_iter)
197@not_implemented_for("multigraph")
198@nx._dispatch(edge_attrs="weight")
199def katz_centrality_numpy(G, alpha=0.1, beta=1.0, normalized=True, weight=None):
200 r"""Compute the Katz centrality for the graph G.
202 Katz centrality computes the centrality for a node based on the centrality
203 of its neighbors. It is a generalization of the eigenvector centrality. The
204 Katz centrality for node $i$ is
206 .. math::
208 x_i = \alpha \sum_{j} A_{ij} x_j + \beta,
210 where $A$ is the adjacency matrix of graph G with eigenvalues $\lambda$.
212 The parameter $\beta$ controls the initial centrality and
214 .. math::
216 \alpha < \frac{1}{\lambda_{\max}}.
218 Katz centrality computes the relative influence of a node within a
219 network by measuring the number of the immediate neighbors (first
220 degree nodes) and also all other nodes in the network that connect
221 to the node under consideration through these immediate neighbors.
223 Extra weight can be provided to immediate neighbors through the
224 parameter $\beta$. Connections made with distant neighbors
225 are, however, penalized by an attenuation factor $\alpha$ which
226 should be strictly less than the inverse largest eigenvalue of the
227 adjacency matrix in order for the Katz centrality to be computed
228 correctly. More information is provided in [1]_.
230 Parameters
231 ----------
232 G : graph
233 A NetworkX graph
235 alpha : float
236 Attenuation factor
238 beta : scalar or dictionary, optional (default=1.0)
239 Weight attributed to the immediate neighborhood. If not a scalar the
240 dictionary must have an value for every node.
242 normalized : bool
243 If True normalize the resulting values.
245 weight : None or string, optional
246 If None, all edge weights are considered equal.
247 Otherwise holds the name of the edge attribute used as weight.
248 In this measure the weight is interpreted as the connection strength.
250 Returns
251 -------
252 nodes : dictionary
253 Dictionary of nodes with Katz centrality as the value.
255 Raises
256 ------
257 NetworkXError
258 If the parameter `beta` is not a scalar but lacks a value for at least
259 one node
261 Examples
262 --------
263 >>> import math
264 >>> G = nx.path_graph(4)
265 >>> phi = (1 + math.sqrt(5)) / 2.0 # largest eigenvalue of adj matrix
266 >>> centrality = nx.katz_centrality_numpy(G, 1 / phi)
267 >>> for n, c in sorted(centrality.items()):
268 ... print(f"{n} {c:.2f}")
269 0 0.37
270 1 0.60
271 2 0.60
272 3 0.37
274 See Also
275 --------
276 katz_centrality
277 eigenvector_centrality_numpy
278 eigenvector_centrality
279 :func:`~networkx.algorithms.link_analysis.pagerank_alg.pagerank`
280 :func:`~networkx.algorithms.link_analysis.hits_alg.hits`
282 Notes
283 -----
284 Katz centrality was introduced by [2]_.
286 This algorithm uses a direct linear solver to solve the above equation.
287 The parameter ``alpha`` should be strictly less than the inverse of largest
288 eigenvalue of the adjacency matrix for there to be a solution.
289 You can use ``max(nx.adjacency_spectrum(G))`` to get $\lambda_{\max}$ the largest
290 eigenvalue of the adjacency matrix.
292 When $\alpha = 1/\lambda_{\max}$ and $\beta=0$, Katz centrality is the same
293 as eigenvector centrality.
295 For directed graphs this finds "left" eigenvectors which corresponds
296 to the in-edges in the graph. For out-edges Katz centrality
297 first reverse the graph with ``G.reverse()``.
299 References
300 ----------
301 .. [1] Mark E. J. Newman:
302 Networks: An Introduction.
303 Oxford University Press, USA, 2010, p. 173.
304 .. [2] Leo Katz:
305 A New Status Index Derived from Sociometric Index.
306 Psychometrika 18(1):39–43, 1953
307 https://link.springer.com/content/pdf/10.1007/BF02289026.pdf
308 """
309 import numpy as np
311 if len(G) == 0:
312 return {}
313 try:
314 nodelist = beta.keys()
315 if set(nodelist) != set(G):
316 raise nx.NetworkXError("beta dictionary must have a value for every node")
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)) * beta
322 except (TypeError, ValueError, AttributeError) as err:
323 raise nx.NetworkXError("beta must be a number") from err
325 A = nx.adjacency_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).squeeze()
329 # Normalize: rely on truediv to cast to float
330 norm = np.sign(sum(centrality)) * np.linalg.norm(centrality) if normalized else 1
331 return dict(zip(nodelist, centrality / norm))