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"""Katz centrality."""
3import math
5import networkx as nx
6from networkx.utils import not_implemented_for
8__all__ = ["katz_centrality", "katz_centrality_numpy"]
11@not_implemented_for("multigraph")
12@nx._dispatchable(edge_attrs="weight")
13def katz_centrality(
14 G,
15 alpha=0.1,
16 beta=1.0,
17 max_iter=1000,
18 tol=1.0e-6,
19 nstart=None,
20 normalized=True,
21 weight=None,
22):
23 r"""Compute the Katz centrality for the nodes of the graph G.
25 Katz centrality computes the centrality for a node based on the centrality
26 of its neighbors. It is a generalization of the eigenvector centrality. The
27 Katz centrality for node $i$ is
29 .. math::
31 x_i = \alpha \sum_{j} A_{ij} x_j + \beta,
33 where $A$ is the adjacency matrix of graph G with eigenvalues $\lambda$.
35 The parameter $\beta$ controls the initial centrality and
37 .. math::
39 \alpha < \frac{1}{\lambda_{\max}}.
41 Katz centrality computes the relative influence of a node within a
42 network by measuring the number of the immediate neighbors (first
43 degree nodes) and also all other nodes in the network that connect
44 to the node under consideration through these immediate neighbors.
46 Extra weight can be provided to immediate neighbors through the
47 parameter $\beta$. Connections made with distant neighbors
48 are, however, penalized by an attenuation factor $\alpha$ which
49 should be strictly less than the inverse largest eigenvalue of the
50 adjacency matrix in order for the Katz centrality to be computed
51 correctly. More information is provided in [1]_.
53 Parameters
54 ----------
55 G : graph
56 A NetworkX graph.
58 alpha : float, optional (default=0.1)
59 Attenuation factor
61 beta : scalar or dictionary, optional (default=1.0)
62 Weight attributed to the immediate neighborhood. If not a scalar, the
63 dictionary must have a value for every node.
65 max_iter : integer, optional (default=1000)
66 Maximum number of iterations in power method.
68 tol : float, optional (default=1.0e-6)
69 Error tolerance used to check convergence in power method iteration.
71 nstart : dictionary, optional
72 Starting value of Katz iteration for each node.
74 normalized : bool, optional (default=True)
75 If True normalize the resulting values.
77 weight : None or string, optional (default=None)
78 If None, all edge weights are considered equal.
79 Otherwise holds the name of the edge attribute used as weight.
80 In this measure the weight is interpreted as the connection strength.
82 Returns
83 -------
84 nodes : dictionary
85 Dictionary of nodes with Katz centrality as the value.
87 Raises
88 ------
89 NetworkXError
90 If the parameter `beta` is not a scalar but lacks a value for at least
91 one node
93 PowerIterationFailedConvergence
94 If the algorithm fails to converge to the specified tolerance
95 within the specified number of iterations of the power iteration
96 method.
98 Examples
99 --------
100 >>> import math
101 >>> G = nx.path_graph(4)
102 >>> phi = (1 + math.sqrt(5)) / 2.0 # largest eigenvalue of adj matrix
103 >>> centrality = nx.katz_centrality(G, 1 / phi - 0.01)
104 >>> for n, c in sorted(centrality.items()):
105 ... print(f"{n} {c:.2f}")
106 0 0.37
107 1 0.60
108 2 0.60
109 3 0.37
111 See Also
112 --------
113 katz_centrality_numpy
114 eigenvector_centrality
115 eigenvector_centrality_numpy
116 :func:`~networkx.algorithms.link_analysis.pagerank_alg.pagerank`
117 :func:`~networkx.algorithms.link_analysis.hits_alg.hits`
119 Notes
120 -----
121 Katz centrality was introduced by [2]_.
123 This algorithm it uses the power method to find the eigenvector
124 corresponding to the largest eigenvalue of the adjacency matrix of ``G``.
125 The parameter ``alpha`` should be strictly less than the inverse of largest
126 eigenvalue of the adjacency matrix for the algorithm to converge.
127 You can use ``max(nx.adjacency_spectrum(G))`` to get $\lambda_{\max}$ the largest
128 eigenvalue of the adjacency matrix.
129 The iteration will stop after ``max_iter`` iterations or an error tolerance of
130 ``number_of_nodes(G) * tol`` has been reached.
132 For strongly connected graphs, as $\alpha \to 1/\lambda_{\max}$, and $\beta > 0$,
133 Katz centrality approaches the results for eigenvector centrality.
135 For directed graphs this finds "left" eigenvectors which corresponds
136 to the in-edges in the graph. For out-edges Katz centrality,
137 first reverse the graph with ``G.reverse()``.
139 References
140 ----------
141 .. [1] Mark E. J. Newman:
142 Networks: An Introduction.
143 Oxford University Press, USA, 2010, p. 720.
144 .. [2] Leo Katz:
145 A New Status Index Derived from Sociometric Index.
146 Psychometrika 18(1):39–43, 1953
147 https://link.springer.com/content/pdf/10.1007/BF02289026.pdf
148 """
149 if len(G) == 0:
150 return {}
152 nnodes = G.number_of_nodes()
154 if nstart is None:
155 # choose starting vector with entries of 0
156 x = {n: 0 for n in G}
157 else:
158 x = nstart
160 try:
161 b = dict.fromkeys(G, float(beta))
162 except (TypeError, ValueError, AttributeError) as err:
163 b = beta
164 if set(beta) != set(G):
165 raise nx.NetworkXError(
166 "beta dictionary must have a value for every node"
167 ) from err
169 # make up to max_iter iterations
170 for _ in range(max_iter):
171 xlast = x
172 x = dict.fromkeys(xlast, 0)
173 # do the multiplication y^T = Alpha * x^T A + Beta
174 for n in x:
175 for nbr in G[n]:
176 x[nbr] += xlast[n] * G[n][nbr].get(weight, 1)
177 for n in x:
178 x[n] = alpha * x[n] + b[n]
180 # check convergence
181 error = sum(abs(x[n] - xlast[n]) for n in x)
182 if error < nnodes * tol:
183 if normalized:
184 # normalize vector
185 try:
186 s = 1.0 / math.hypot(*x.values())
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._dispatchable(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 For strongly connected graphs, as $\alpha \to 1/\lambda_{\max}$, and $\beta > 0$,
293 Katz centrality approaches the results for 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, then tolist to make Python numbers
330 norm = np.sign(sum(centrality)) * np.linalg.norm(centrality) if normalized else 1
331 return dict(zip(nodelist, (centrality / norm).tolist()))