图计算的框架简单介绍完后, 上手最典型的例子就是 PageRank (网页排名) 的算法运用, 这篇还会介绍它的衍生算法, 包括带权版, 个性化 PageRank, Article Rank等.
0x00. 前言 在接触 PageRank (后简称PR)本身之前, 需要知道学习大部分图算法都需要从两个方面了解:
一是这个算法是什么意思, 有什么作用
另一个是这个算法对应在图论 中的数学定义 / 公式
为了方便理解, 我这记录一般侧重 前者, 对数学定义/抽象给出参考 链接, 感兴趣的同学可以细究. (图论可从 wiki 里简单了解一下), 然后
1. 历史背景 之所以要单独说一下 PR 的历史, 是因为它对 Google/互联网的影响的确太大了, 可以说是 90 年代里程碑式的论文, 虽然许多人包括我在内(之前)并没有读过 PR 原 paper, 但也早已听闻过它的大名. 它和 2003 年左右 Google 丢出的分布式三马车有类似的影响力, 所以不妨简单了解一下~
大家都对 Google 是做搜索引擎出身, 成为了世界上最大的搜索引擎厂商耳熟能详, 但是可能对搜索引擎的发展史了解甚少:
最早的时候,
The Anatomy of a Large-Scale Hypertextual Web Search Engine , 这是原论文 的全名, PageRank 是论文中提到的具体计算方式, 其中 Page 是由作者 Larry Page 的名字提取得来, 正好也可有网页/页面的含义, 所以它可称作佩奇排名 / 网页排名算法.
文章由 Google 的两位创始人联手发表, 主要的目的是为了分析海量的网页 并应用在搜索引擎的排名上的问题. PageRank 就是论文提出的一个利用网络的拓扑结构 来计算排名的方式, 论文里大部分内容提到了具体搜索引擎系统的设计实现, 并不是本文重点, 就不细提了
要注意的是实际实现的 PR 算法, 大多数是在原文基础上做了改变和改进 (XxxRank) 的, 多少都有些出入 (应用场景同样)
那么言归正传, PageRank 到底是如何快速对所有网页进行排名打分的呢, 它有两大 实现方式: 简单版 VS 完整版 , 然后还有许多变形版就暂且不提, 总之理解它的核心原理即可, 具体实现差异不大.
graph TD
subgraph Example 1
b-->a
c-->a
d-->a
end
subgraph Example 2
a2(a)-->b2(b)-->c2(c)-->d2(d)-->a2
end
subgraph Example 3
b1(b)--> a1(a)
b1(b)--> c1(c)
c1(c)--> a1(a)
d1(d)-->a1
d1(d)-->b1
d1(d)-->c1
end
结合上面给的 3 个图例, 先看一下简单版 做法: (参考 Wikipedia)
把所有网页/网站当做一个顶点 , 外链/指向其他网站的当成边 , 那么就天然构成了一个图 .
每个点(网页)都有一个给定且相同的初始 PR 权重 (一般 0~1
之间), 假设初始为 0.25, 下面看几个图例 :
Eg1: 假设有 4 个网页 a, b, c, d, 如果 b, c, d 有且只有一个边(外链)指向 a, 那么 a 的最终权重为 PR(a) = PR(b) + PR(c) + PR(d) = 0.75
, 其他三个点无人指向则为 0.
Eg2: 假设 4 个网页是单环指向, 那么每个点的 PR 值都相同为 0.25
Eg3: 再看复杂一点的情况, 此时 b, c, d 三点都指向了多个外链, 那么它计算权重的时候就需要除以外链数, 相当于稀释了投票权重, 那么PR(a) = PR(b)/2 + PR(c)/1 + PR(d)/3 = 0.25/2 + 0.25 + 0.25/3
, 其他点同理, d 没有入边为0
那么通过这几个例子可以很简单的推出一个递推公式: PR(a) = PR(n1)/D(n1) + PR(n2)/D(n2) + …PR(n)/D(n)
, 这里 D(n)
就是每个点的出边 数, 那么当一个点的出边为 0 时, 它的 PR 值算作是 0 , 就会引出大问题
怎么算呢? 由此引入了一个修正/阻尼系数 d(damping)
也就是说图中每个点的 PR 值, 是由它所有的入边 的权重和来组成, 要注意这里结果要乘以一个修正系数 d (它后面再说), 并且为了
那么简单版的问题是什么呢, 容易出现特殊情况, 比如如果一个站点的外链也是自己, 出现了自指向 的边, 按照原本的模型就是自己给自己打分了,
完整版 的代表就是引入了一个随机访问者 (random surfer) 的概念, 不再给每个点初始以相同的权重, 而是模拟一个人在浏览器随机的进行网页访问, 具体如下:
那么上述这种引入一个所谓 random surfer 的做法, 其实就是一种典型的随机游走 模型, 炼金里的新名词概念挺多, 本质倒是并不复杂, 理解含义就好.
Dangling : 它是 “悬空/悬挂” 的意思, 它是英文单词 dangle 的 ing 形式 (并不是拼音 ~), dangling website 代表没有外链的页面, 也就是图中出度为 0 的点
3. 优缺点 PR 的优点很明显, 实现和理解都很简单, 缺点主要在于新页面 的权值通常比旧站点低的多 (参考自 wiki)
PR 是中心性算法里最出名的一个,
PS: Neo4j
有出一本图算法介绍的书, 觉得对入门图计算还是有很大帮助的, 网上不少资料也是从这摘取的, 可直接阅读官方 PDF
单机实现已经在 hugegraph server 了, 先来看看单机版的实现思路 (注: 这里面没有最小收敛精度)
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 public Map<Id, Double> personalRank (Id source, String label, WithLabel withLabel) { Map<Id, Double> ranks = newMap(); ranks.put(source, 1.0 ); Id labelId = this .graph().edgeLabel(label).id(); Directions dir = this .getStartDirection(source, label); Set<Id> outSeeds = newIdSet(); Set<Id> inSeeds = newIdSet(); if (dir == Directions.OUT) { outSeeds.add(source); } else { inSeeds.add(source); } Set<Id> rootAdjacencies = newIdSet(); for (long i = 0 ; i < this .maxDepth; i++) { Map<Id, Double> newRanks = this .calcNewRanks(outSeeds, inSeeds, labelId, ranks); ranks = this .compensateRoot(source, newRanks); if (i == 0 ) { rootAdjacencies.addAll(ranks.keySet()); } } removeAll(ranks, rootAdjacencies); if (withLabel == WithLabel.SAME_LABEL) { removeAll(ranks, dir == Directions.OUT ? inSeeds : outSeeds); } else if (withLabel == WithLabel.OTHER_LABEL) { removeAll(ranks, dir == Directions.OUT ? outSeeds : inSeeds); } return ranks; } private Map<Id, Double> calcNewRanks (Set<Id> outSeeds, Set<Id> inSeeds, Id label, Map<Id, Double> ranks) { Map<Id, Double> newRanks = newMap(); BiFunction<Set<Id>, Directions, Set<Id>> neighborIncrRanks; neighborIncrRanks = (seeds, dir) -> { Set<Id> tmpSeeds = newIdSet(); for (Id seed : seeds) { Double oldRank = ranks.get(seed); Iterator<Id> iter = this .adjacentVertices(seed, dir, label, this .degree); List<Id> neighbors = IteratorUtils.list(iter); long degree = neighbors.size(); if (degree == 0L ) { newRanks.put(seed, oldRank); continue ; } double incrRank = oldRank * this .alpha / degree; for (Id neighbor : neighbors) { tmpSeeds.add(neighbor); double rank = newRanks.getOrDefault(neighbor, 0.0 ); newRanks.put(neighbor, rank + incrRank); } } return tmpSeeds; }; Set<Id> tmpInSeeds = neighborIncrRanks.apply(outSeeds, Directions.OUT); Set<Id> tmpOutSeeds = neighborIncrRanks.apply(inSeeds, Directions.IN); outSeeds.addAll(tmpOutSeeds); inSeeds.addAll(tmpInSeeds); return newRanks; } private Map<Id, Double> compensateRoot (Id root, Map<Id, Double> newRanks) { double rank = newRanks.getOrDefault(root, 0.0 ); rank += (1 - this .alpha); newRanks.put(root, rank); return newRanks; } private Directions getStartDirection (Id source, String label) { HugeVertex vertex = (HugeVertex) graph().vertices(source).next(); VertexLabel vertexLabel = vertex.schemaLabel(); EdgeLabel edgeLabel = this .graph().edgeLabel(label); Id sourceLabel = edgeLabel.sourceLabel(); Id targetLabel = edgeLabel.targetLabel(); E.checkArgument(edgeLabel.linkWithLabel(vertexLabel.id()), "The vertex '%s' doesn't link with edge label '%s'" , source, label); E.checkArgument(!sourceLabel.equals(targetLabel), "The edge label for personal rank must " + "link different vertex labels" ); if (sourceLabel.equals(vertexLabel.id())) { return Directions.OUT; } else { assert targetLabel.equals(vertexLabel.id()); return Directions.IN; } } private static void removeAll (Map<Id, Double> map, Set<Id> keys) { for (Id key : keys) { map.remove(key); } }
0x0n. 其他 随着现在炼金的兴起, 可能不少同学接触到 PR 是从类似“马尔可夫”, “无监督学习”, “随机游走”等术语/概念里衍生听到的, 这里给一些参考, 但是暂不详细介绍了
参考资料:
PageRank - Wikipedia
The Anatomy of a Large-Scale Hypertextual Web Search Engine (PR paper) - Google
Graph Algorithm - Chapter5.5 PageRank - Neo4j - ORelly
neo4j /graph-data-science-pr
Massively Parallel Algorithms for Personalized PageRank - pvldb 14