节点相似性度量指标汇总

本文主要介绍复杂网络中顶点相似性度量指标。

基于局部信息的节点相似度指标

共同邻居

$s_{xy}=|\Gamma(x)\cap\Gamma(y)|$

Salton指标

$s_{xy}=\frac{|\Gamma(x)\cap\Gamma(y)|}{\sqrt{k(x)×k(y)}}$

Jaccard指标

$s_{xy}=\frac{|\Gamma(x)\cap\Gamma(y)|}{|\Gamma(x)\cup\Gamma(y)|}$

Sorenson指标

$s_{xy}=\frac{2|\Gamma(x)\cap\Gamma(y)|}{k(x)+k(y)}$

大度节点有利指标（HPI）

$s_{xy}=\frac{|\Gamma(x)\cap\Gamma(y)|}{min\{k(x),k(y)\}}$

大度节点不利指标（HDI）

$s_{xy}=\frac{|\Gamma(x)\cap\Gamma(y)|}{max\{k(x),k(y)\}}$

优先链接指标

$s_{xy}=\frac{|\Gamma(x)\cap\Gamma(y)|}{k(x)×k(y)}$

Adamic-Adar指标（AA）

$s_{xy}=\sum_{z\in \Gamma(x)\cap\Gamma(y)}\frac{1}{logk(z)}$

资源分配指标（RA）

$s_{xy}=\sum_{z\in \Gamma(x)\cap\Gamma(y)}\frac{1}{k(z)}$

基于全局信息的节点相似度指标

局部路径指标

$S=A^2+\alpha A^3$

其中 $(A^n)_{xy}$ 给出了节点x和y之间长度为n的路径数。

Katz指标

$s_{xy}=\sum_{i=1}^\infty\beta^l(A^l)_{xy}$

其中 $\beta$ 为权重衰减因子。对应的相似矩阵如下：

$S=\beta A+\beta^2A^2+\cdots=(I-\beta A)^{-1}-I$

LHN-II指标

太复杂。。。不写

基于随机游走的相似度指标

SimRank（SimR）指标

基本假设是如果两节点所连接的节点相似，那么这两个节点就相似，其定义如下：

$s_{xy}^{SimR}=C\frac{\sum_{z\in \Gamma(x)}\sum_{z^{,}\in \Gamma(y)}}{k_xk_y}$

其中假定 $s_{xx}=1,C\in[0,1]$ 为相似性传递时的衰减参数。SimR指标可以用来描述两个分别从节点x和y出发的粒子多久会相遇。