链接预测任务的两种类型：随机缺失边；随时间演化边。

第一种假设可以以蛋白质之间的交互作用举例，缺失的是研究者还没有发现的交互作用。
第二种假设可以以社交网络举例，随着时间流转，人们认识更多朋友。

基于相似性进行链接预测：计算两点间的相似性得分（如用共同邻居衡量相似性），然后将点对进行排序，得分最高的n组点对就是预测结果，与真实值作比

提出了两种方式计算共同邻居数：

1.Jaccard系数（Jaccard similarity coefficient）是一种用于比较两个有限样本集之间相似性的度量方法。它定义为两个集合交集的大小与并集的大小的比值。Jaccard系数的计算公式为：

𝐽(𝐴,𝐵)=∣𝐴∩𝐵∣∣𝐴∪𝐵∣J(A,B)=∣A∪B∣∣A∩B∣​

其中，𝐴A 和 𝐵B 分别代表两个集合，∣𝐴∩𝐵∣∣A∩B∣ 表示集合 𝐴A 与 𝐵B 的交集元素的数量，而 ∣𝐴∪𝐵∣∣A∪B∣ 表示集合 𝐴A 与 𝐵B 的并集元素的数量。Jaccard系数的值域在 [0, 1] 之间，值越大表示两个集合的相似度越高。

白话：分子是两个集合的交集，分母是两个集合的并集，所得到的值越大则说明相关性越高，反之越低。

2.Adamic-Adar Index（AAI）是一种用于衡量网络中两个节点相似度的局部相似性度量方法。它特别关注两个节点共有的邻居节点，并给予那些在网络中不太常见的共有邻居更高的权重，而对于那些更常见的共有邻居则给予较低的权重。具体来说，AAI的计算公式如下图。其中，Γ(𝑢)Γ(u) 表示节点 𝑢u 的邻居节点集合，Γ(𝑣)Γ(v) 表示节点 𝑣v 的邻居节点集合，Γ(𝑢)∩Γ(𝑣)Γ(u)∩Γ(v) 表示 𝑢u 和 𝑣v 的共有邻居节点集合。

举例：在社交网络上表现好的原因：有一堆度数低的共同好友比有一堆名人共同好友的得分更高。

白话：这个算法主要用在预测潜在链接。

        同时我们可以发现对于方法1而言有一个缺陷，因为如上图A和E之间只有两个单位距离但是用公式1算出来的话，结果为0。但是这两个点未来仍有可能被连接起来。

Katz index：计算点对之间所有长度路径的条数
计算方式：邻接矩阵求幂

1. 邻接矩阵的k次幂结果，每个元素就是对应点对之间长度为k的路径的条数
2. 证明：
3. 

4. 计算 u和v 之间长度为2的路径数量，就是计算每个u的邻居 Aui与u有1条长度为1的路径与 v之间长度为1的路径数量。同理可得更高次幂。

通过上面的 Katz指数，原来计算A，E之间的关联度为0，现在的关联度会随着距离的增加而减少。而不会因为没有共同邻居而直接为0。