Graph Global Overlap Measure: Leicht-Holme-Newman Index

#Graph #Basics #Clustering

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


  1. Hamilton2020 Hamilton WL. Graph Representation Learning. Morgan & Claypool Publishers; 2020. pp. 1–159. doi:10.2200/S01045ED1V01Y202009AIM046  ↩︎

  2. Lue2010 Lu L, Zhou T. Link Prediction in Complex Networks: A Survey. arXiv [physics.soc-ph]. 2010. Available: http://arxiv.org/abs/1010.0725  ↩︎

Published: 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/.

Current Ref:

  • cards/graph/graph-global-overlap-leicht-holme-newman-similarity.md