Error in documentation of katz_centrality?

[erikkemperman]

Current Behavior

The docs for katz centrality state:

networkx/networkx/algorithms/centrality/katz.py

Lines 131 to 132 in f20ba5f

	When $\alpha = 1/\lambda_{\max}$ and $\beta=0$, Katz centrality is the same
	as eigenvector centrality.

The value for beta here was changed from 1 to 0 a long time ago, in this commit:
b33ebd4#diff-fd4d6088095ce7547e9e07adf7326d408cb55f6ef43d47aeba7f53d405b44b8dL259

Which I think may have been an incorrect response to issue #1247.

Expected Behavior

I believe that the previous note with beta=1 was actually correct. For what it's worth, here are the relevant parts of the implementation in current master:

networkx/networkx/algorithms/centrality/katz.py

Lines 153 to 166 in 6971d84

	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

If we assume that nstart is left to the default of None, we see that x starts out being all zeroes. But then, unless beta is non-zero for at least some of the nodes, it is impossible for any element of x to ever become non-zero:

networkx/networkx/algorithms/centrality/katz.py

Lines 168 to 177 in 6971d84

	# 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]

In other words, it looks to me like if nstart=None and beta=0 then Katz centrality will always produce an array of zeroes. And in particular, even if alpha is (ever so slightly less than) 1/lambda_max it will not resemble the eigenvector centrality.

Steps to Reproduce

(EDITED) Figured I should add an example, adapted from the example in the docs:

import math
G = nx.path_graph(4)
phi = (1 + math.sqrt(5)) / 2.0  # largest eigenvalue of adj matrix

print(f"For reference: eigenvector centrality")
eig_centrality = nx.eigenvector_centrality(G)
for n, c in sorted(eig_centrality.items()):
    print(f"{n} {c:.2f}")
# 0 0.37
# 1 0.60
# 2 0.60
# 3 0.37

print(f"Katz with beta=1.0")
katz_centrality_0 = nx.katz_centrality(G, alpha=(1 / phi - 0.01), beta=1.0)
for n, c in sorted(katz_centrality_0.items()):
    print(f"{n} {c:.2f}")
# 0 0.37
# 1 0.60
# 2 0.60
# 3 0.37

print(f"Katz with beta=0.0")
katz_centrality_1 = nx.katz_centrality(G, (1 / phi - 0.01), beta=0.0)
for n, c in sorted(katz_centrality_1.items()):
    print(f"{n} {c:.2f}")
# 0 0.00
# 1 0.00
# 2 0.00
# 3 0.00

Environment

Python version: 3.11
NetworkX version: 3.0rc

[BrunoBaldissera]

I guess you are right! It's nice that you even found the probable origin of this.

Since the beta parameter accounts for the weights in the neighborhood, an assignment of '0' should be expected to output zeroes as you reported.

[dschult]

Thanks for this! And for the detailed numerical analysis.
The theory requires alpha <= 1/lambda_max to avoid singular results. But in the limit alpha -> 1/lambda_max we can look at alphaA as a multiplication operator that shrinks all vectors except the eigenvector corresponding to lambda_max. And it keeps that vector the same length. Thus repeatedly multiplying by alphaA should turn any vector into its component in the direction of that eigenvector. Scaling the result to a unit vector reveals the same eigenvector for any starting guess that isn't orthogonal to the eigenvector. For Katz centrality we start with the vector beta. So certainly the current documentation is wrong. If beta=0, it is orthogonal to all eigenvectors. And we won't end up with the stated result of the eigenvector as the Katz centrality. It is also true that beta=1 does give the desired result. But Beta=2 also works... as does beta=0.2 or any beta>0. (So long as beta as a vector isn't orthogonal to the eigenvector).

So I see two possible fixes -- the suggest correction to the doc_string of \beta=1, or the correction \beta >= 0. We could also be more precise and say that this result holds in the limit as alpha -> 1/lambda_max. But I'm not sure that is causing any confusion. It is the incorrect value of beta=0 that is causing confusion.

Also, the sentence doesn't say this is the only case where Katz Centrality matches Eigenvector Centrality, so I'm fine with the suggested language here (and in the @BrunoBaldissera PR). Thanks for the excuse to take a romp down the lane of linear algebra and infinite series. :) Let's fix the doc_string!