加权PageRank
- 提出者
- Xing, W. & Ghorbani, A.
- 年份
- 2004
- 类型
- Centrality measure / ranking algorithm
- 类别
- Network science
本文为机器翻译,尚未经过审校。 阅读英文原文
它有什么作用?
加权PageRank将经典的PageRank算法扩展到边具有不同强度或频率的网络中,它根据入边和出边的权重比例分配重要性,而不是同等对待所有链接。在任何连接强度很重要的网络中,这都比二值PageRank信息量大得多。
方法背后的直觉
经典的PageRank算法将每个超链接或连接视为等同:一个节点从一个微弱的连接获得的声望与从一个强大的连接获得的声望是相同的。加权PageRank通过将每个投票乘以边的相对权重来纠正这一点。一个节点如果从许多重要的节点那里获得权重很高的入边,它在排名中会攀升得最高,而一个节点如果拥有许多但连接很弱的边,它的排名则保持在中等水平。这反映了在大多数现实世界网络中,影响力是如何实际积累的,其中交互频率或交易量信号了真正的价值。
历史学
PageRank由Brin和Page于1998年提出,作为Google搜索的基础,将所有超链接视为平等的投票。加权PageRank由Xing和Ghorbani于2004年正式提出,将该算法扩展为根据边权重比例分配排名,借鉴了入权重和出权重分数。此后,它被应用于引用分析、生物信息学、社交网络分析和推荐系统等领域,只要链接强度是影响力的有意义代理。
何时使用
当你的网络具有有意义的边权重,并且你需要对节点进行全局、面向流的重要性排序时,使用加权PageRank。它非常适用于具有共同引用计数的引用网络、具有流量的网页图、具有表达水平的生物相互作用网络、具有交互频率的社交网络以及金融交易网络。当忽略边强度会错误地表示影响力流时,优先选择加权PageRank而非二值PageRank。当边权重不可靠或任意分配时,当网络非常稀疏且权重大多为二值时(标准PageRank足够),或者当你需要加权度这样的纯局部中心性度量时,避免使用它。它不适用于概念上流向方向无意义的无向网络。
局限与注意事项
- 需要边权重有意义且可靠测量;嘈杂或任意的权重会降低排名质量。
- 阻尼因子(d)是一个自由参数;传统的0.85可能不适用于非网络图。
- 对所选的权重归一化方案敏感;如果入权重和出权重组合不同,结果可能会有所不同。
- 不区分不同类型的边;单一权重模型可能会抹杀重要的结构区别。
- 在没有高效稀疏矩阵实现的情况下,对于非常大、稠密的网络,收敛可能很慢。
来源中的条件不能替代独立的科学审查或分析引擎的验证。
优势
- 直接将边强度纳入重要性传播,在加权网络中给出比二值PageRank更真实的排名。
- 捕捉全局、网络范围的声望,而不仅仅是局部连通性。
- 保留了PageRank的随机跳转机制,通过修正后可以抵抗悬挂节点和断开连接的组件。
- 通过高效的迭代计算扩展到大型网络;稀疏矩阵运算使内存可控。
- 易于解释:高分意味着一个节点接收到来自其他高分节点的大量、加权认可。
应用
- 在加权的引用和合著网络中识别有影响力的论文或作者。
- 在具有超链接流量或点击率的网页或文档排名中。
- 在加权的生物相互作用网络中检测关键蛋白质或基因。
- 通过交易量流在金融交易网络中对节点进行排序。
- 在加权的社交媒体交互图中对用户或内容进行排名。
- 构建以项目共现频率作为边权重的推荐系统。
使用方式
使用方式
将网络表示为一个图,其中每条边都带有一个数值权重,反映了连接强度——例如交互频率、交易量、合著计数或相似度得分。该算法要求这些权重为非负数;负权重必须在分析前进行转换。
对于从节点v到节点u的每条有向边,计算两个权重因子:一个入权重因子,将边权重按u的总入权重进行归一化;一个出权重因子,将边权重按v的总出权重进行归一化。这些分数决定了v通过这条特定边传递给u的排名比例。
公式
W_{in}(v,u) = \frac{w(v,u)}{\sum_{k \in In(u)} w(k,u)}, \quad W_{out}(v,u) = \frac{w(v,u)}{\sum_{k \in Out(v)} w(v,k)}迭代应用加权PageRank公式:每个节点的排名等于一个基础的随机跳转项(1减去阻尼因子d,通常为0.85)加上d乘以所有入邻节点其排名乘以两个权重因子之和。这使得排名按边强度比例分配,而不是均匀分配。
公式
WPR(u) = (1-d) + d \sum_{v \in In(u)} WPR(v) \cdot W_{in}(v,u) \cdot W_{out}(v,u)重复排名更新,直到每个节点的得分变化低于一个小容差(通常为1e-6)。对于强连通图,收敛是有保证的;对于具有悬挂节点或孤立组件的图,在迭代之前应用标准的悬挂节点修正。
一旦得分收敛,就按加权PageRank得分降序对所有节点进行排序。这些排名反映了每个节点在考虑网络拓扑和边强度后的全局结构重要性。
常见陷阱
- 使用原始的、未归一化的边权重而不检查其尺度——将数量级差异很大的值混合在一起会扭曲排名传播。
- 忘记处理悬挂节点(没有出边的节点),如果未修正,它们会从整个网络中耗尽排名。
- 假设默认的阻尼因子0.85普遍适用;在引用或生物网络中,不同的值可能更能反映领域。
- 将加权PageRank得分解释为绝对概率而非相对排名——只有它们的顺序在不同运行中是稳定的。
- 在没有归一化的情况下比较不同大小的网络中的加权PageRank得分。
常见问题
加权PageRank与标准PageRank有何不同?
标准PageRank无论边强度如何,都将节点的排名平均分配给所有出邻居。加权PageRank通过每条边的相对入权重和出权重来缩放此分配,因此更强的连接携带的排名比例更高。
应该使用什么阻尼因子?
传统值是0.85,源于关于随机冲浪的网页图假设。对于社交、生物或引用网络,文献中探讨了0.5到0.9之间的值。建议对一系列阻尼值进行敏感性分析。
加权PageRank可以应用于无向网络吗?
可以,通过将每条无向边表示为一对具有相同权重的有向边。然后,该算法产生对称的入权重和出权重因子,这简化为一个仍然尊重边强度的公式。
如何处理零权重边?
零权重边对排名传播没有贡献,因此可以在分析前删除。如果零权重在结构上具有意义(缺失而非数据缺失),请在删除前清楚地说明区别。
加权PageRank是否优于加权度中心性?
这取决于研究问题。加权度中心性仅捕获直接连接,而加权PageRank捕获通过整个网络传播的全局声望。使用加权度来衡量局部影响,使用加权PageRank来衡量网络范围的重要性。