链接预测是图数据挖掘中的一个重要问题。链接预测旨在预测图中丢失的边, 或者未来可能会出现的边。这些算法主要用于判断相邻的两个节点之间的亲密程度。通常亲密度越大的节点之间的亲密分值越高。
The Adamic Adar algorithm (algo.linkprediction.adamicAdar)
Adamic Adar是一种基于节点之间共同邻居的亲密度测算方法。2003年由 Lada Adamic 和 Eytan Adar t在 predict links in a social network中提出的，计算亲密度的公式如下：
formula
其中
N(u)是与节点u相邻的节点集合。A(x,y)为0表明节点x和y不接近，该值越高表明两个节点间的亲密度越大。Neo4j-algo包提供了该算法的具体实现，下面我们可以看一个例子。创建节点和边：
MERGE (zhen:Person {name: "Zhen"})
MERGE (praveena:Person {name: "Praveena"})
MERGE (michael:Person {name: "Michael"})
MERGE (arya:Person {name: "Arya"})
MERGE (karin:Person {name: "Karin"})
MERGE (zhen)-[:FRIENDS]-(arya)
MERGE (zhen)-[:FRIENDS]-(praveena)
MERGE (praveena)-[:WORKS_WITH]-(karin)
MERGE (praveena)-[:FRIENDS]-(michael)
MERGE (michael)-[:WORKS_WITH]-(karin)
MERGE (arya)-[:FRIENDS]-(karin)
创建完成之后的图结构如下：
graph
计算两个指定节点之间的亲密度：
MATCH (p1:Person {name: 'Michael'})
MATCH (p2:Person {name: 'Karin'})
RETURN algo.linkprediction.adamicAdar(p1, p2) AS score
计算结果如下所示：
score
另外，我们还可以基于特定的关系类型和关系指向，计算一对节点之间的亲密度。
MATCH (p1:Person {name: 'Michael'})
MATCH (p2:Person {name: 'Karin'})
RETURN algo.linkprediction.adamicAdar(p1, p2, {relationshipQuery: "FRIENDS",
direction: "BOTH"}) AS score
计算结果如下：
score
Common Neighbors (algo.linkprediction.commonNeighbors)
相同邻居，顾名思义，指的是两个节点同时关联的节点、数量。
计算公式如下：
formula
其中
N(x)是与节点x相邻的节点集合，N(y)是与节点y相邻的节点集合，相同邻居指的是两个集合的交集。该值越高表明两个节点之间亲密度越高。当节点x和节点y不相邻时，该值为0。还使用上面的数据集合，则计算两个节点的相同邻居的代码如下：
MATCH (p1:Person {name: 'Michael'})
MATCH (p2:Person {name: 'Karin'})
RETURN algo.linkprediction.commonNeighbors(p1, p2) AS score
结果如下：
image.png
同样的，该度量方法也可以指定关系的类型和关系的方向，这里不再赘述。
Preferential Attachment (algo.linkprediction.preferentialAttachment)
优先连接依赖于两个节点的连接数，如果两个节点的连接数都很大，标签该节点对被连接的概率越大。计算公式如下：
image.png
其中
N(u)是与节点u相邻的节点集合。该值为0表明节点x和y不接近，该值越高表明两个节点间的亲密度越大。示例如下：
MATCH (p1:Person {name: 'Michael'})
MATCH (p2:Person {name: 'Karin'})
RETURN algo.linkprediction.preferentialAttachment(p1, p2) AS score
Resource Allocation (algo.linkprediction.resourceAllocation)
资源分配算法公式如下：
image.png
其中
N(u)是与节点u相邻的节点集合。该值为0表明节点x和y不接近，该值越高表明两个节点间的亲密度越大。示例如下：
MATCH (p1:Person {name: 'Michael'})
MATCH (p2:Person {name: 'Karin'})
RETURN algo.linkprediction.resourceAllocation(p1, p2) AS score
Total Neighbors (algo.linkprediction.totalNeighbors)
总邻居数指的是两个相邻节点之间的总邻居数，计算公式如下：
image.png
其中
N(u)是与节点u相邻的节点集合。该值为0表明节点x和y不接近，该值越高表明两个节点间的亲密度越大。示例如下：
MATCH (p1:Person {name: 'Michael'})
MATCH (p2:Person {name: 'Karin'})
RETURN algo.linkprediction.totalNeighbors(p1, p2) AS score
参考：
