Take the 2-minute tour ×

I am teaching a course using M.E.J. Newman's Networks. It covers several measures of vertex centrality. One of them is the Katz centrality.

Let $G$ be a graph and let $A$ be its adjacency matrix. Let $\mathbf{1}$ denote the vector $(1, \ldots, 1)$ and let $I$ denote the identity matrix. Then the Katz centrality of $G$ is given by the vector $$\mathbf{v} = (I - \alpha A)^{-1}\mathbf{1}, \tag*{(1)}$$ where $\alpha > 0$ is a free parameter.

My question concerns the value of $\alpha$. It is clear that $\alpha$ cannot take any value $\lambda^{-1}$, where $\lambda$ is an eigenvalue of $A$: if $\alpha$ took such a value, the right-hand side of $(1)$ would not exist.

So, letting $\lambda_1$ denote the largest eigenvalue of $A$, Newman writes that in order to determine the Katz centrality of a graph, one should let $\alpha$ be less than $1/\lambda_1$. In a footnote (p. 317, footnote 6), he writes, "Formally one uncovers finite values again when one moves past $1/\lambda_1$ to higher $\alpha$, but in practice these values are meaningless. The method returns good results only for $\alpha < 1/\lambda_1$."

What does that statement mean? Why don't larger values of $\alpha$ work?

share|improve this question

1 Answer 1

up vote 6 down vote accepted

Short answer: the factor $(I-\alpha A)^{-1}$ is derived from the infinite sum $\displaystyle\sum_{k=0}^\infty (\alpha A)^k$, which models the average long-term behaviour of random walks along the edges of the graph (with $\alpha$ as an attenuation factor). If $\alpha$ is too large then the infinite sum doesn't converge. Even though the other expression is defined, it isn't connected in an obvious way to the underlying sum.

It's quite analogous to the old chestnut $$ 1 + 2 + 4 + 8 + 16 + \cdots = -1.$$ There are certainly ways to interpret the above so that it can be justified, but the result doesn't carry quite the same concreteness of meaning.

EDIT: I was thinking of regular graphs when referring to random walks. In general it would be more apt to describe the sum as a weighted count of the number of neighbours at distance $k$ (with repetition allowed, so that each vertex $v$ is a neighbour of itself at distance $2$, with multiplicity $d(v)$).

share|improve this answer

Your Answer


