The LHN index is a normalized similarity index.

## From Katz Index to LHN Index

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}$1.

Not Every Random Graph

We require $\tilde{\mathcal G}$ to have the same set of node degrees as $\mathcal G$. Such a graph is a configuration model.

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 using1,

$$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 similarity2. 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}.$$

Planted: by ;

L Ma (2021). 'Graph Global Overlap Measure: Leicht-Holme-Newman Index', Datumorphism, 09 April. Available at: https://datumorphism.leima.is/cards/graph/graph-global-overlap-leicht-holme-newman-similarity/.