algorithm - 评估路由图中的节点连通性

我有一个有向的加权路由图（大约 10^5 条边，每个节点 4 条边，很多圈）。

每条边都有与之相关的成本。如何评价每个节点的“连通性”？它应该衡量从这个节点到达其他节点的成本。

如果每个节点都有一个可靠性因子（包含该节点的所选路径将失败并且必须找到新路径的概率），一切将如何变化？

谢谢你的帮助

标签： algorithmroutinggraph-algorithm

我相信您提出的问题在很多方面都与PageRank算法的用例相匹配。

我不会讨论该算法的一般工作原理，因为网上有很多博客/视频已经非常详细地解释了它。我个人最喜欢的短视频之一就是这个。

现在让我们看看该算法如何适合您的用例。让我们将connectedness节点x定义为C(x)。我们可以将您给定的陈述“从该节点到达其他节点有多便宜”改写为“我们在整个图中随机游走最终到达给定节点的可能性有多大，这样我们就倾向于采用成本为少”。

这种说法在很大程度上与 PageRank 算法背后的思想有关。我们只需要考虑如何包括我们工作的边缘成本。

原始的 PageRank 算法将给定节点的页面排名统一划分到它的所有相邻节点（在公式中表示为 PR(y)/OUT(y)）。另一方面，我们需要更加偏向于成本较低的边缘，我建议将公式修改为，

(SUM-EDGES-COST(y) - EDGE-COST(x, y)) * (C(y) / SUM-EDGES-COST(y))

而不是传统的C(x) / OUT(x)。我们取差值(SUM-EDGES-COST(y) - EDGE-COST(x, y))因为在我们的场景中，较低的边缘成本意味着更多connectedness。另一种可能性是将softmax函数应用于每个节点的边缘成本作为标准化策略。

为了回答关于具有节点x的R(x)给出的可靠性因子的部分，我们可以将其直接乘以公式中的C(x)。

收拾东西，

应该符合您给定的场景。

我在这里介绍的只是一种可能性，我可以从脑海中想到它，而且很可能它可能不会成功。我只能希望它以某种或其他方式帮助您。干杯! :)