Graph Global Overlap Measure: Leicht-Holme-Newman Index

The LHN index is a normalized similarity index.

From Katz Index to LHN Index

[[Katz Index]] 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 … has a knob to tune the punishment towards longer paths. The Leicht-Holme-Newman Similarity, aka, LHN Similarity, has a better normalization factor.

The LHN similarity of a graph $\mathcal G$ normalizes the path calculation by the expected number of path in a random graph $\tilde{\mathcal G}$¹.

The expected number of path different path length is not analytically feasible in general. We have for lower power

$$ \begin{align} \mathbb E [ A[u,v] ] &= \frac{d_u d_v}{2\lvert \mathcal E\rvert} \\ \mathbb E [ A^2[u,v] ] &= \frac{d_u d_v}{2\lvert \mathcal E\rvert} \sum_{u\in \mathcal V} (d_m-1) d_u. \end{align} $$

However, a iterative method shows us an approximation and we can approximate the LHN similarity using¹,

$$ S_{\text{LHN}} = 2\alpha m \lambda_1 \mathbf D^{-1} \left( \mathbf I - \frac{\beta}{\lambda_1} \mathbf A \right)^{-1} \mathbf D^{-1}, $$

where $\mathbf D$ is the matrix $\mathrm{diag} ({d_1, d_2, \cdots})$, and $\lambda_1$ is the largest eigenvalue of the adjacency matrix $\mathbf A$.

Indications of LHN Index

Lue & Zhou wrote an intuitive review of LHN similarity². The idea of LHN implements the idea that two nodes $u$ and $v$ are similar if their neighbors $\mathcal N(u)$ and $\mathcal N(v)$ are similar,

$$ \mathbf S_{\text{LHN}} = \beta \mathbf A \mathbf S_{\text{LHN}} + \alpha \mathbf I, $$

where $\alpha$ and $\beta$ are free parameters that controls the punishment of different lengths.

Moving the matrices around, we get

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