2
$\begingroup$

In Mark Newman's Networks book, 2010 edition, page 173, he explains some mathematical details behind the Katz Centrality measure:

In matrix terms, Eq. (7.8) can be written x = αAx + β1, (7.9) where 1 is the vector (1, 1, 1 . . .). Rearranging for x, we find that x = β(I − αA)^{−1} · 1. As we have said, we normally don’t care about the absolute magnitude of the centrality, only about which vertices have high or low centrality values, so the overall multiplier β is unimportant. For convenience we usually set β = 1, giving x = (I − αA)^{−1} · 1. (7.10) This centrality measure was first proposed by Katz in 1953 [169] and we will refer to it as the Katz centrality. The Katz centrality differs from ordinary eigenvector centrality in the important respect of having a free parameter α, which governs the balance between the eigenvector term and the constant term in Eq. (7.8). If we wish to make use of the Katz centrality we must first choose a value for this constant. In doing so it is important to understand that α cannot be arbitrarily large. If we let α → 0, then only the constant term survives in Eq. (7.8) and all vertices have the same centrality β (which we have set to 1). As we increase α from zero the centralities increase and eventually there comes a point at which they diverge. This happens at the point where (I − αA)^{−1} diverges in Eq. (7.10), i.e., when det(I − αA) passes through zero. Rewriting this condition as det(A − α^{−1}I) = 0, (7.11) we see that it is simply the characteristic equation whose roots α^{−1} are equal to the eigenvalues of the adjacency matrix. As α increases, the determinant first crosses zero when α^{-1} = κ1, the largest eigenvalue of A, or alternatively when α = 1/κ1. Thus, we should choose a value of α less than this if we wish the expression for the centrality to converge

Now, what does it mean for centralities to diverge when the characteristic equation of the adjacency matrix is bigger than zero? I do not understand why we should pick a value of α < 1/κ1 when in a footnote to the above paragraph we read:

Formally one recovers finite values again when one moves past 1/κ1 to higher α, but in practice these values are meaningless. The method returns good results only for α < 1/κ1.

$\endgroup$

2 Answers 2

1
$\begingroup$

By diverging, Newman really means that if $\alpha$ is equal to the inverse of any eigenvalues of $A$, then some or all values of the vector $x$ may tend to infinity, i.e. diverge. You can see this as, in this case, when doing $\frac{1}{(I-\alpha A)}$ you are "dividing by zero" somewhere.

One should pick a value $\alpha<\kappa_1^{-1}$ because in this case, as $|\alpha A|<1$, we can express $(I-\alpha A)^{-1}$ as the Neumann series of $\alpha A$: $$ (I-\alpha A)^{-1}=I + \alpha A + \alpha^2 A^2 + \alpha^3 A^3 + ... $$ Hence $$ x = \left(\sum_{\ell=0}^\infty\alpha^\ell A^\ell\right)\vec{1}. $$ This gives a nice interpretation of the Katz centrality of a node $i$ as the weighted sum of all walks emanating from $i$, with the count for walks of length $\ell$ (given by $A^\ell$) weighted by a factor $\alpha^\ell$. This also shows you that all values of the Katz centrality will be positive (this is not guaranteed when $\alpha > \kappa_1^{-1}$).

$\endgroup$
0
$\begingroup$

I don't know if you ever found an answer to this. I came across your question when I was looking for one.

By diverges here, I think Newman just means doesn't make sense/ has infinitely many answers. So the equation $x= (I- \alpha A)^{-1} 1$ "diverges" when $(I- \alpha A)^{-1}$ doesn't make sense/ has infinitely many answers, since the vector $1$ makes sense always. This happens when we can solve for the inverse, i.e. when $det( I- \alpha A)=0$.

As for the footnote. I believe he is just referring to a point he made a few pages back. Recall, he spoke about the Perron-Frobenius theorem which told us that only the largest eigenvalue would give us a result which made sense, since it was the only one that allow us that have all non-negative centrality scores. So if you choose bigger than $\frac{1}{\kappa_1}$ then you are heading towards the other eigenvalues and so your centralities will be negative and thus "these values are meaningless".

I stand to be corrected on any of this, but this is what I've been able to make sense of so far.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.