Katz centrality

Take an arbitrary network, preferably a directed one, and ask yourself; what is the most important node in this network? The question appears in all sorts of contexts; data networks (what is the critical hub?), social networks (who is the influential person?), epidemic networks (who is spreading the virus?) and so on. The answer to this depends on various factors and the type of network you consider but one of the more common approaches is the so-called Katz centrality. For your information, ‘centrality’ the study of what an important node is in a network and how it can be computed.

Take a node and assign to the adjacent node a weight $latex \alpha$, to the next level of children/siblings assign $latex \alpha^2$ and so on. In other words

$latex \text{Katz}(i)=\sum _{k=1}^{\infty } \sum _{j=1}^n \alpha ^k A^k_{ji}$

and note that the link pointing towards a node are looked at. Using the other direction would not change the maths but would semantically make a difference. In general, the more linking the more weight a node has in this formulation. The definition is equivalent to the matrix equation

$latex Katz = (1-\alpha A^T)^{-1} – 1$

There is a subtlety regarding the parameter defining the decreasing weight. From the double series above it’s apparent that the convergence is determined by $latex \alpha$ and from the matrix equation it shows through the inverse. Both views amount to the same question: what should be the parameter so the centrality is not infinite? Easy enough, the matrix equation blows up if

$latex det( A^T – \alpha^{-1}) = 0$

Assuming $latex \kappa$ is the largest eigenvalue of A we deduce that the first singularity occurs when

$latex \alpha \kappa = 1$

In practice people take a value which either makes sense in the context of the data or something close to the largest eigenvalue.

An example using Mathematica is straightforward;

mA = Partition[RandomChoice[{0, 0, 0, 0, 1}, 200*200], {200}];

centrality1 = Inverse[IdentityMatrix[Length[mA]] - 0.01*Transpose@mA].ConstantArray[1, Length[mA]];
centrality2 = LinearSolve[IdentityMatrix[Length[mA]] - 0.01*Transpose@mA, ConstantArray[1, Length[mA]]];

found = Position[centrality1, Max[centrality1]][[1]]
centrality1[[found]]


Of course, Mathematica has its internal implementation, the “KatzCentrality” method, but we wanted to give here a raw calculation.

Tags: