路由图中节点连通性的速率

Question

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

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

如果每个节点都有一个可靠性因子(包含该节点的所选路径将失败并必须找到新路径的概率)，那么一切会发生什么变化？

谢谢你的帮忙

Answer 1

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

我不会讨论算法是如何工作的，因为网上有很多博客/视频，已经详细解释了它。我个人最喜欢的短视频之一是this。

现在让我们看看算法是如何适合你的用例的。让我们将节点x的connectedness定义为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)。我们取差值(和-边-成本(Y)-边-成本(x，y))，因为在我们的场景中，较低的边成本意味着更多的connectedness。另一种可能性是将softmax函数应用于每个节点的边缘成本作为归一化策略。

关于有一个可靠性因子的部分，由R(x)给出，对于节点x，我们可以直接将它乘以公式中的C(x)。

总而言之，

​

​

应该与您给定的场景相匹配。

我在这里提出的只是一种可能性，我可以从我的脑海中思考，它很可能不会成功。我所能希望的就是它能以某种方式帮助你。干杯！:)