链路预测之基于局部信息的相似性指标

参考文献为Link Prediction in Complex Networks: A Survey

链接预测方法最简单的框架是基于相似度的算法，其中为每对节点$x$和$y$分配一个分数$S_{xy}$，该分数直接定义为$x$和$y$之间的相似度(或邻近度)。所有未观察到的链接均根据其得分进行排名，并且连接更多相似节点的链接被认为具有较高的存在可能性。节点相似性可以通过使用节点的基本属性来定义：如果两个节点具有许多共同特征，则认为它们是相似的。

本文主要介绍10个基于局部信息的相似性指标。

1 局部相似性指标

（1）$CommonNeighbours(CN)$。对于一个节点$x$，让$\Gamma （x）$表示$x$的邻域集合。一般来说，两个节点，$x$和$y$，如果有许多共同的邻居，则更有可能有一条链接。此邻域重叠的最简单度量是有向计数，即$$s_{xy}^{CN}=|\Gamma (x)\cap \Gamma (y)|.$$
显然，$S_{xy}=(A^2{)}_{xy}$，$A$为邻接矩阵。若$x$和$y$直接相连，则$A_{xy}=1$，否则$A_{xy}=0$。$(A^2{)}_{xy}$是连接$x$和$y$的长度为2的不同路径的数目。

（2）$SaltonIndex$(称余弦相似性)。
$$s_{xy}^{Salton}=\frac{|\Gamma (x)\cap \Gamma (y)|}{\sqrt{k_x\times k_y}}.$$
其中$k_x$为节点$x$的度数。

（3） $JaccardIndex$
$$S_{xy}^{Jaccard}=\frac{|\Gamma (x)\cap \Gamma (y)|}{|\Gamma (x)\cup \Gamma (y)}$$

（4）$SorensenIndex$。该指标主要用于生态群落数据，定义为
$$S_{xy}^{sorensen}=\frac{2|\Gamma (x)\cap \Gamma (y)|}{k_x+k_y}$$

（5）$HubPromotedIndex(HPI)$。该指标是为了量化代谢网络中底物对的拓扑重叠而提出的，其定义为：
$$S_{xy}^{HPI}=\frac{|\Gamma (x)\cap \Gamma (y)|}{min\{k_x,k_y\}}$$
在这一衡量标准下，由于分母仅由较小的度数决定，因此与中心节点相邻的链路可能会被分配高分。因为离中心节点越近，分母越小，$HPI$数值就越大。

（6）$HubDepressedIndex(HDI)$
$$S_{xy}^{HDI}=\frac{|\Gamma (x)\cap \Gamma (y)|}{max\{k_x,k_y\}}$$

（7）$Leicht-Holme-NewmanIndex(LHN1)$。该指标为具有许多公共邻居的节点对分配高相似度，不是与可能的最大值相比，而是与此类邻居的预期数量相比。它被定义为
$$S_{xy}^{LHN1}=\frac{|\Gamma (x)\cap \Gamma (y)|}{k_x\times k_y}$$
其中分母$k_x\times k_y$与配置模型中节点x和y的公共邻居的预期数量成比例

（8）$PreferentialAttachmentIndex(PA)$。优先连接机制可用于生成演化的无标度网络，其中新链路连接到节点$x$的概率与$k_x$成正比。在每一个时间戳，一个旧的链路被移除，一个新的链路被生成。这种新的链路连接$x$和$y$的概率与$k_x\times k_y$成正比，在这种机制的激励下，相应的相似性指数可以定义为
$$S_{xy}^{PA}=k_x\times k_y$$
它被广泛用于量化受各种网络动力学影响的链路的功能重要性，如渗滤、同步和运输。该指标不需要每个节点的邻域信息，因此，它的计算复杂性最小。

（9）$Adamic-AdarIndex(AA)$。该指标通过赋予较少连接的邻域更多的权重来细化公共邻域的简单计数，定义为
$$S_{xy}^{AA}=\sum _{z\in \Gamma (x)\cap \Gamma (y)}\frac{1}{log{k}_z}$$

（10）$ResourceAllocationIndex(RA)$。这个指数是由复杂网络上的资源分配动态引起的。考虑一对节点$x$和$y$，它们不是直接连接的。节点$x$可以向$y$发送一些资源，它们的公共邻居扮演发送器的角色。在最简单的情况下，我们假设每个发送器都有一个资源单元，并将其平均分配给它的所有邻居。$x$和$y$之间的相似性可以定义为从$x$接收到的资源$y$的数量，即
$$S_{xy}^{RA}=\sum _{z\in \Gamma (x)\cap \Gamma (y)}\frac{1}{k_z}$$