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