图数据库的 PageRank 算法

拼搏现实的明天。 2024-03-27 07:36 48阅读 0赞

## 图数据库的 PageRank 算法 ##

*本文译自：[PageRank Algorithm for Graph Databases][]*

![在这里插入图片描述][675c6487229c4e0488d626a7755c8e4f.png_pic_center]

PageRank 最有趣和最著名的应用程序肯定是真正激发其创建的应用程序。谷歌创始人拉里佩奇和谢尔盖布林需要[一种算法来对页面进行排名][Link 1]并为用户提供最佳搜索结果。

使用 PageRank 算法，每个页面都会根据链接到它的其他页面的数量和重要性获得排名。页面排名较高的页面比排名较低的页面增加了它们链接到的页面的排名。

在图数据库术语中，PageRank 算法用于根据传入关系的数量和相关源节点的排名来衡量每个节点的重要性。PageRank 算法实际输出的是一个概率分布，表示通过随机遍历图形访问任何特定节点的可能性。

所以，这基本上是一个节点人气竞赛。

![在这里插入图片描述][aabd4873e77247dfaa99a9b8df899879.png_pic_center]

一种广泛使用的 PageRank 类型是个性化 PageRank，它在推荐系统中非常有用。使用个性化 PageRank，您可以通过允许它仅从给定集合中的一个节点开始并仅跳转到给定集合中的一个节点来限制随机游走。这种类型的 PageRank 从那组特定节点的角度带出中心节点。例如，[Twitter 使用个性化 PageRank][Twitter _ PageRank] 来推荐在线关注的人。

下面的动画显示了 PageRank 在简单网络上的结果。一部广受欢迎的电影的续集将自动比一个随机的新片名更受欢迎，因为它已经拥有固定的粉丝群。在图形术语中，指向相邻节点的最大节点使其更重要。

![在这里插入图片描述][347888f91cb94c4f868dc37dbaa9708d.gif_pic_center]

PageRank 可用作衡量影响力的指标，可用于各种应用程序，而不仅仅是网站和电影排名。

### PageRank 用例 ###

如果社交网络或搜索引擎不是您正在开发的产品，请查看如何在其他各种用例或知识图谱中利用 PageRank 来推断这些利基市场中的知识。

#### 推荐引擎 ####

在推荐引擎中，PageRank 算法可用于[推荐][Link 2]符合目标用户偏好或当前在所有其他用户中流行的产品。该算法考虑购买次数和购买或评论产品的用户的可靠性。

可靠的用户具有有效的使用历史和评论，而不可靠的用户是虚假客户，其目的是人为地夸大某些产品的指标，使它们看起来更受欢迎。

#### 数据沿袭 ####

了解文档在数据沿袭图中的重要性有两个重要的应用：影响分析和系统可靠性。

在添加新的数据属性、迁移或重大更新的情况下，例如在获取后合并数据源，影响分析可以帮助评估此类更改的上下游影响。

PageRank 还可以帮助识别需要保持高度可靠的高影响节点，因为它们在整个组织的许多其他地方使用。

#### 欺诈识别 ####

在[欺诈检测][Link 3]中，PageRank 可用作机器学习算法的附加特征（输入），以改进分类并减少误报。

[使用共享卡][Link 4]参与欺诈交易的用户更有可能成为欺诈者。因此，这些特定交易中涉及的节点等级可能是一条有价值的信息，可用于机器学习模型，以预测和检测与网络中已知欺诈者有联系的个人之间的欺诈行为。

还可以根据流经每个节点的资金量对节点进行排名，以标记比特定用户的平均资金流动量多得多的交易。

#### 身份和访问管理 ####

在管理权限时，限制对敏感资产的访问非常重要，因为利用这些资产可能会给公司造成代价高昂的损失。在很多系统中，由于缺乏时间和资源，往往会把高权限给实际上并不需要的人。

PageRank 可以帮助识别许多用户可以访问哪些敏感资产，以确定实际上谁需要访问并删除其余用户的权限。

![在这里插入图片描述][567f767836094b38beb83ed519c0bb75.png_pic_center]

#### 网络优化 ####

关键基础设施是可以表示为高度相互依赖的节点和关系网络的系统。由于它们的性质，一个节点中的故障可能会导致其他节点中的一连串故障。PageRank 可以帮助识别可能发生故障的节点以及它们是否会级联到网络中的其他节点。

![在这里插入图片描述][9b222d047cb7413a9d0ba036bc18cb43.png_pic_center]

由于能源基础设施也是一个网络，因此使用 PageRank 来识别拓扑中的漏洞是非常宝贵的，可以为公司和用户节省时间、金钱和挫败感。

#### 网络安全 ####

因为绝对消除系统中的所有威胁是不可行的。PageRank 可以帮助计算某些恶性事件导致严重攻击的概率。正如 PageRank 的最初目的是确定哪些站点由于所有其他站点都指向它而更有可能被随机点击，在安全系统中，它可以用来指出更可能执行哪种攻击，以及攻击的后果哪些攻击会更严重。

### 在 Memgraph 中的实现 ###

[Memgraph 使用 C++ 实现了 PageRank][Memgraph _ C_ _ PageRank]，这使得它非常适合性能非常重要的用例。该图需要定向，并且该算法不考虑关系的权重。

默认参数与 NetworkX PageRank 实现中的相同，因此[如果您是 NetworkX 用户][NetworkX]，它将一帆风顺：

*  `max_iterations`: 整数（默认值 = 100） ➡ PageRank 算法中的最大迭代次数。
 *  `damping_factor`: double (default = 0.85) ➡ PageRanks 阻尼系数。这是从图中的随机节点继续随机游走的概率。
 *  `stop_epsilon`: double (default = 1e-5) ➡ 用于终止 PageRank 迭代的值。如果从一次迭代到另一次迭代的变化小于`stop_epsilon`，则停止执行。

要在 Memgraph 中调用 PageRank，请使用以下查询：

CALL pagerank.get()YIELD node, rankRETURN node, rank;

[您可以在欧洲天然气管道][Link 5]数据集沙盒中的 Playground 上进行试用。使用以下查询检查具有最高值的节点（如果失败可能会导致问题）：

CALL pagerank.get()YIELD node, rankRETURN node, rankORDER BY node DESC;

![在这里插入图片描述][09ac13e0841a4fd69b4499277d8d9e53.png_pic_center]

与 MAGE 开源库中的所有其他算法一样，您只能在具有[`project()`函数][project]的特定节点组上运行 PageRank 。将子图保存在一个变量中，然后将其作为算法的第一个参数提供：

MATCH p=(n:SpecificLabel)WITH project(p) AS subgraphCALL pagerank.get(subgraph)YIELD node, rankRETURN node, rank;

如果您的应用程序对时间高度敏感并且节点和关系会在短时间内到达，请使用允许保留先前处理状态的[动态 PageRank 。][PageRank]当实体更新或新实体到达图中时，不是在整个图中重新启动算法，而是在恒定时间仅处理到达实体的邻域对象。

### 结论 ###

PageRank 是一种成熟的图形算法，尚未失去其相关性。更重要的是，随着图形数据库使用的增加，它肯定会在许多管理系统中找到自己的位置。有关使用 PageRank 的更多示例，请查看[Memgraph 关于同一主题的博客文章][Memgraph]，或探索更多[图形算法][Link 6]。

如果您对是否正确使用 PageRank 有任何疑问，或者您需要帮助将其实施到您的用例中，[Memgraph 的 Discord 服务器][Memgraph _ Discord]上的一个热情的社区将非常乐意帮助您将图形和算法集成到您的系统中。

[PageRank Algorithm for Graph Databases]: https://memgraph.com/blog/pagerank-algorithm-for-graph-databases
[675c6487229c4e0488d626a7755c8e4f.png_pic_center]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/27/57985e8002624786adca0829730221fe.png
[Link 1]: http://infolab.stanford.edu/~backrub/google.html
[aabd4873e77247dfaa99a9b8df899879.png_pic_center]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/27/dc5a9b1694574df0a9d51a3d44e65652.png
[Twitter _ PageRank]: https://dl.acm.org/doi/10.1145/2488388.2488433
[347888f91cb94c4f868dc37dbaa9708d.gif_pic_center]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/27/cb32eef2f9ee4d3caeac948abc01deee.png
[Link 2]: https://memgraph.com/blog/five-recommendation-algorithms-no-recommendation-engine-is-whole-without
[Link 3]: https://memgraph-staging.webflow.io/fraud-detection-insurance
[Link 4]: https://memgraph.com/fraud-detection-card
[567f767836094b38beb83ed519c0bb75.png_pic_center]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/27/265f54e62f934af1a6eb392bded4b696.png
[9b222d047cb7413a9d0ba036bc18cb43.png_pic_center]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/27/3cc9ee34163f437bb6eddeb06fab0602.png
[Memgraph _ C_ _ PageRank]: https://memgraph.com/docs/mage/query-modules/cpp/pagerank
[NetworkX]: https://memgraph.com/memgraph-for-networkx
[Link 5]: https://playground.memgraph.com/sandbox/europe-gas-pipelines-scigrid
[09ac13e0841a4fd69b4499277d8d9e53.png_pic_center]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/27/0e581df6861b481da86a60c2aa0cb413.png
[project]: https://memgraph.com/docs/mage/how-to-guides/run-a-subgraph-module
[PageRank]: https://memgraph.com/docs/mage/algorithms/dynamic-graph-analytics/pagerank-online-algorithm
[Memgraph]: https://memgraph.com/blog?topics=PageRank
[Link 6]: https://memgraph.com/blog?topics=Graph+Algorithms
[Memgraph _ Discord]: https://discord.com/invite/memgraph