Eigenvector centrality as a limiting case of Katz centrality

Question

In Networks by Newman (2nd ed.), eigenvector centrality (sometimes called Bonacich centrality) is defined as the vector $x$ that solves $$ A x = \kappa x, $$ where $\kappa$ is the principal (largest, most positive) eigenvalue of the adjacency matrix $A$. Katz centrality is defined as the vector $y$ that solves $$ y = \alpha A y + \bf 1, $$ where $0 \leq \alpha < \kappa^{-1}$ and $\bf 1$ is a conforming vector of ones. That is, $y = ({\bf I} - \alpha A)^{-1} {\bf 1}$.

Question: In the book (p.164), it states that in the limit as $\alpha \nearrow \kappa^{-1}$, Katz centrality converges to eigenvector centrality. How can I prove this?

Thoughts so far:

• I understand that, when it exists, $y = ({\bf I} - \alpha A)^{-1} {\bf 1} = {\bf 1} + \alpha A {\bf 1} + \alpha^2 A^2 {\bf 1} + ...$. This sum diverges when $\alpha = \kappa$. At that point, $\det({\bf I} - \alpha A) = 0$. This means that $\det(\alpha^{-1}{\bf I} - A) = 0$, which is the characteristic equation whose roots $\alpha^{-1}$ are the eigenvalues of $A$. This means that $({\bf I} - \alpha A)^{-1} {\bf 1}$ is well-defined for $\alpha \in [0, \kappa^{-1})$. I'm not sure how to incorporate this into the final proof.
• The book mentions that centrality of a node is only meaningful relative to the centrality of other nodes. So perhaps I should assume that eigenvector centrality, for example, should be defined as $\mathcal C^{e} = \frac{x}{\|x\|}$ and Katz centrality as $\mathcal C^{k} = \frac{y}{\|y\|}$.

Edit:

I have posted my attempt at a solution below. I would still like to verify some aspects of it.

Answer 1

Consider the definition of Eigenvector centrality given above where $\mathcal C^e = \frac{x}{\|x\|}$ and the definition of Katz centrality, where $\mathcal C^k(\alpha) = \frac{({\bf I} - \alpha A)^{-1} {\bf 1}}{\|({\bf I} - \alpha A)^{-1} {\bf 1}\|}$. When $\alpha < \kappa^{-1}$, recall that we can write $y = ({\bf I} - \alpha A)^{-1} {\bf 1} = {\bf 1} + \alpha A {\bf 1} + \alpha^2 A^2 {\bf 1} + ...$.

Define $a_n(\alpha) = {\bf 1} + \alpha A {\bf 1} + \alpha^2 A {\bf 1}\, + ... + \, \alpha^n A^n {\bf 1}$, let $a_0 = {\bf 1}$. Define $b_n(\alpha) = \|a_n(\alpha)\|$.

Given these definitions, we would like to calculate the limit $$ \lim_{\alpha \nearrow \kappa^{-1}} \mathcal C^k(\alpha) = \lim_{\alpha \nearrow \kappa^{-1}} \lim_{n\rightarrow\infty} \frac{a_n(\alpha)}{b_n (\alpha)}, $$ where $\kappa$ is the principal eigenvalue of $A$.

Note that $\lim_{n \rightarrow \infty} a_n/b_n$ is defined for all values $\alpha \in [0, \kappa^{-1})$. Also, $a_n$ and $b_n$ are finite for $n < \infty$. We can thus switch the order of the limits so that $$ \lim_{\alpha \nearrow \kappa^{-1}} \mathcal C^k(\alpha) = \lim_{n\rightarrow\infty} \lim_{\alpha \nearrow \kappa^{-1}} \frac{a_n(\alpha)}{b_n(\alpha)} = \lim_{n\rightarrow\infty} \frac{a_n(\kappa^{-1})}{b_n(\kappa^{-1})} $$

Define $$ x_{n+1} = \frac{A^{n+1} x_0}{\|A^{n+1} x_0\|}, $$ with $x_0 = {\bf 1}$. Assuming the needed conditions for the power iteration algorithm, $x_{n+1} \rightarrow x$, where $x$ is an eigenvector associated with principal eigenvalue of $A$.

Since $\det \left({\bf I} - \frac{1}{\kappa} A\right) = 0$, we know that $a_n$ and $b_n$ diverge when $\alpha = \kappa^{-1}$. Assume that $A$ is nonnegative (network edge weights are nonnegative). Then $b_n$ is also strictly monotonic. This allows us to use the Stolz–Cesàro theorem: $$ \lim_{n\rightarrow\infty} \frac{a_n}{b_n} = \lim_{n\rightarrow\infty} \frac{a_{n+1}-a_n}{b_{n+1}-b_n}. $$ Calculating, $$ \frac{a_{n+1}-a_n}{b_{n+1}-b_n} = \frac{\alpha^{n+1} A^{n+1} {\bf 1}}{\|a_{n+1}\| - \|a_n\|} = \frac{\kappa^{-n-1} \|A^{n+1} {\bf 1}\| \, x_{n+1} }{\|a_{n+1}\| - \|a_n\|} \geq \frac{\kappa^{-n-1} \|A^{n+1} {\bf 1}\| \, x_{n+1} }{\|\kappa^{-n-1} A^{n+1} {\bf 1}\|} = x_{n+1}, $$ where the inequality follows from the reverse triangle inequality. Since $\|a_n(\kappa^{-1})\|$ diverges and is monotonically increasing, the inequality holds with equality in the limit. Thus, $$ \lim_{\alpha \nearrow \kappa^{-1}} \mathcal C^k(\alpha) = \lim_{n\rightarrow\infty} \frac{a_n(\kappa^{-1})}{b_n(\kappa^{-1})} = \lim_{n\rightarrow\infty} x_n = x = \mathcal C^e. $$

Notes:

• I should probably be a little more careful about switching the order of the limits.
• I should clarify the conditions needed for power iteration. (See Perron-Frobenius.)

Answer 2

Let's assume that the network is undirected, so symmetric, and further that the graph is irreducible (equivalent to connected) so the strict form of the Perron-Frobenius Theorem holds. Write out $A$ in the spectral decomposition so that $$A=\sum_{i=1}^n \lambda_i v_iv_i^T,$$where the $v_i$ are the eigenvectors (and form an orthonormal basis) and $\kappa_1=\lambda_1>\lambda_2\geq \ldots\geq \lambda_n>-\kappa$ are the eigenvalues. By the Perron-Frobenius Theorem, $v_1>0$ componentwise. This is $x$ in your notation. It follows from the von Neumann bound you used that for $\alpha<\kappa^{-1}$, $$ (I-\alpha A)^{-1}=\frac{1}{1-\alpha\kappa}xx^T +\sum_{i=2}^n \frac{1}{1-\alpha \lambda_i}v_iv_i^{T}. $$

We now compute \begin{align} (I-\alpha A)^{-1}\mathbf{1}=\frac{1}{1-\alpha\kappa}x(x^T\mathbf{1}) +\sum_{i=2}^n \frac{1}{1-\alpha \lambda_i}v_i(v_i^{T}\mathbf{1}). \end{align}

The eigenvector centrality ranking cares only about the relative values of the components, so we may safely multiply by the scalar $1-\alpha \kappa$. This gives

$$(1-\alpha \kappa)(I-\alpha A)^{-1}\mathbf{1}=x(x^T\mathbf{1})+ \sum_{i=2}^n \frac{1-\alpha \kappa}{1-\alpha \lambda_i}v_i(v_i^{T}\mathbf{1}).$$ As $\alpha\to \kappa^{-1}$, the terms in the sum vanish as the denominators are bounded away from $0$ by the strict inequality in Perron-Frobenius, and this converges to $x(x^T\mathbf{1})$. $x^T\mathbf{1}$ is just some positive scalar from the Perron-Frobenius Theorem, so the limiting vector is $x$ up to a scalar factor.