Graph Global Overlap Measure: Katz Index

The Katz index is

$$ \mathbf S_{\text{Katz}}[u,v] = \sum_{i=1}^\infty \beta^i \mathbf A^i[u, v], $$

where $\mathbf A^i[u, v]$ is the matrix $\mathbf A$ to the $i$th power. Some for $\beta^i$. The Katz index describes the similarity between of node $u$ and node $v$.

Do not confuse power with contravariant indices

For readers familiar with tensor notations, it might be confusing. We some times use contravariant indices on the top right of the tensor notation.

But here ${}^{i}$ means to the $i$th power.

The index is proved to be the following

$$ \mathbf S_{\text{Katz}} = (\mathbf I - \beta \mathbf A)^{-1} - \mathbf I. $$

Parameter $\beta$

The parameter $\beta$ is the punishment for path length. If $\beta < 1$, each increase in power will make the whole term $\beta^i A^i$ smaller. If a path between $u$ and $v$ is longer, i.e., $i$ is larger, then the weight $\beta^i$ is smaller.

Graph Adjacency Matrix
A graph $\mathcal G$ can be represented with an adjacency matrix $\mathbf A$. There are some nice and clear examples on wikipedia1, for example, $$ \begin{pmatrix} 2 & 1 & 0 & 0 & 1 & 0\\ 1 & 0 & 1 & 0 & 1 & 0\\ 0 & 1 & 0 & 1 & 0 & 0\\ 0 & 0 & 1 & 0 & 1 & 1\\ 1 & 1 & 0 & 1 & 0 & 0\\ 0 & 0 & 0 & 1 & 0 & 0 \end{pmatrix} $$ for the graph Public Domain, Link

Planted: by ;

L Ma (2021). 'Graph Global Overlap Measure: Katz Index', Datumorphism, 09 April. Available at: https://datumorphism.leima.is/cards/graph/graph-global-overlap-katz-index/.