图计算之Adamic-Adar算法

Jin's Blog

2021-08-24 (Updated: 2021-10-15)

图

上一篇介绍了图计算中经典的聚类算法 —— 聚类系数和三角计数算法, 它们可以表示图中任一点/子图的紧密程度, 今天则来看看表示两点间紧密程度的代表算法之一 —— [Adamic/Adar 算法](Adamic/Adar 算法)

0x00. 定义

Adamic/Adar 指数的命名是来自 2003 年Adamic & Adar两个人发表的一篇 paper, 有时候没了解清楚的时候, 会以为它就叫 Adar 指数, 或者以为 Adamic Adar (Neo4j中称呼)是一个人名, 其实严谨的称呼的确应如 Wikipedia 中的定义, 用 / 或 &表示. 确认清算法的简单由来也是对原作者的一份敬意. (后文可能会简称为 AA 算法)

简单说, 它其实就是一个典型的社交网络中判断两点的紧密度的算法, 用来求两点间共同邻居多少的一个系数表示 (< 0.0)

AA 算法基于共同邻居 (Common Neighbors) 作为前置条件. 看过聚类系数那篇文章的话, 应该很快能联想到二者的相似性: 共同邻居和三角计数只返回一个数目, 而为了更直观简单的比较不同点之间的紧密度, 可使用一个系数 (通常 0≤a≤1) 来更为直观得到小数值表示.

1. 数学定义

在看 AA 的计算公式前, 先看看两点共同邻居的定义, 简单说, 假设点 X 的邻居集合为 Neighbor(x), 点 Y 的邻居集合为 Neighbor(y), 则二者的共同邻居是二者的交集: N~~(x)~~ ∩ N~~(y)~~

那么, 已知两点的共同邻居后, AA 算法的定义比较简单, 它是 X, Y 两点每个共同邻居的出度的对数倒数累加 (文字表示有点绕), 对应的公式如下其实就简单许多, 简而言之, 如果已知两点的共同邻居个每个邻居的出度, 就是一个遍历累加的过程了.

2. 举例说明

这里引用海外文章的手稿原图, 举了个简单的例子, 如下图所示, 计算 “A 和 C” / “A 和 E” 点的 AA 系数的计算方式:

那这里有个关键点是理解为何要加一个 logeD 这样的取对数呢? 不妨想一下这个当某个点是超级顶点(有巨大出度)的情况下, 取对数倒数后就是一个极小的权值, 也就代表着略过超级顶点, 因为这样的点出现过于普遍, 而当某个点只有最少出度 (2) 时, 代表这个共同邻居的珍稀度最高, 给它高权值

0x01. 具体实现

1. TP版本

AA算法搞清楚逻辑后, 给一个实现的核心参考版本, 计算逻辑也就两行:

public double adamicAdar(Id source, Id target, Directions dir,
                         String label, long degree, long limit) {
    Set<Id> neighbors = checkAndGetCommonNeighbors(source, target, dir,
                                                   label, degree, limit);
    EdgeStep step = new EdgeStep(graph(), dir, ImmutableList.of(label));

    return neighbors.stream()
                    .mapToDouble(vid -> 1.0 / Math.log(this.vertexDegree(vid, step)))
                    .sum();
}

然后他的邻居 ResourceAllocation 几乎一样:

public double resourceAllocation(Id source, Id target, Directions dir,
                                 String label, long degree, long limit) {
    Set<Id> neighbors = checkAndGetCommonNeighbors(source, target, dir,
                                                   label, degree, limit);
    EdgeStep step = new EdgeStep(graph(), dir, ImmutableList.of(label));

    return neighbors.stream()
                    .mapToDouble(vid -> 1.0 / this.vertexDegree(vid, step))
                    .sum();
}

关键就在于求这个点的 degree 个数, 其他就是一个单纯的数学公式累加了, 要注意提醒的是, 由于美国点的 degree 数是可能变动的, 所以这里使用流的时候请勿使用并行流 (parallelStream)

2. AP版本

如果要计算全图的AA系数, 其实也是一样的, 因为这里基本没有涉及任何的消息传递, 有了出边数后就是一个单独的计算, 所以在 pregel 的模型中, 在step0 就能完成, 也就是写一下 computer0()的逻辑就行, 没有太多变化, 就不再重贴了

0x02. 优化改进

原本的 AA 算法本身计算倒是比较简单易懂, 这里我们会在获取 degree 这做计算下推, 利用类 rocksdb 的原生集合器, 可以很大提升速度优化性能 (也无需返回整个点/边迭代器再做累加, 只需要返回数值即可)

0x03. 其他

AA 算法是以对数的倒数为核心进行权值累加, 有一个类似的兄弟 RA (ResourceAllocation) 算法, 直接取倒数累加, 在 Neo4j 的文档里也有说明, 这里就不单独描述了, 包括类似的一些 Link Prediction 的算法, 后续可以看看整体的关系 (可参考引用资料的最后一个链接)

参考资料: