我发现 PageRank 算法很大程度上依赖于边缘的存在，但边缘的权重影响很小。例如，即使权重之一是 0.0000001，三角形图（A -> B，B -> C，C -> A）上的 PageRank 始终为 (1/3, 1/3, 1/3)。是否有任何类似 PageRank 的方法在加权图上运行良好？
提前致谢！
加权图上是否有类似 PageRank 的方法？
数据挖掘
评估
2022-02-16 07:07:15
3个回答
Pagerank 的加权版本确实存在，并且很容易将边缘权重合并到 PageRank 算法中（只需将每个边缘的概率乘以其权重向量，然后归一化以使边缘概率相加为 1）
困难的问题是如何设置这些权重。Backstrom 和 Leskovec 在他们关于监督随机游走的 WSDM 论文中提出了一种算法来学习这些权重，他们建议将其用于链接预测和链接推荐。
正如您所提到的，PageRank 可以有效地识别连接图中的重要节点。
我认为你需要考虑添加什么样的重量，以及你把重量放在哪里。
我发现了一些在边缘添加权重的作品。
- 入站/出站链接加权 PageRank (Xing, Ghorbani 2004)
- AuthorRank 考虑共同作者链接之间的链接权重（Liu、Bollen、Nelson 和 Sompel 2005）
并且，其他一些作品在节点上添加了权重。
- 信用加权的 PageRank (Radicchi, Fortunato, Makines, Vespignani 2009)
- 具有引用次数、发表次数的加权 PageRank（Ding 2011）
在您提到的具体示例中，重量确实无关紧要。
在您的三角图示例（A->B, B->C, C->A）中，每个节点都有一个指向另一个节点的链接。
PageRank 算法通过边的数量（或总权重）对邻接矩阵进行归一化。从节点i到节点j的概率取决于边e_ij的权重除以从节点i出去的边的权重之和。
因此，如果一个节点只有一个出边，那么它的权重是多少并不重要。
（当然，可以想象一种变体，其中“阻尼因子”取决于节点边的总权重，因此当该总和较低时，结束游走的概率很高）。
其它你可能感兴趣的问题