use*_*879 6 algorithm graph graph-algorithm
我正在阅读基于Brandes算法的中间性中心性.我对算法有一些疑问
该算法是否给出了精确的中介中心性或近似值？当我在Sage上运行BC时,它基于Brandes算法,它没有给出确切的值.比如14,我得到13.9956 ......
有人可以用更简单的术语解释"对依赖的累积"部分吗？
当"我们需要存储每个顶点的依赖项和前辈列表"时,该怎么做.是否在执行Dijkstra算法时完成此操作？
加权图表需要做什么？
Brandes算法给出了每个顶点的精确中心性.我不知道Sage中使用了哪种算法实现,但可能是精确度问题.
算法的积累部分可能是最棘手的.当你到达那个部分时,你有sigma 从当前顶点到其余顶点的最短路径的数量.此外,在Pred中,每个顶点都有通过最短路径到达它们的顶点列表.依赖增量将是中介的所述量小号将有助于顶点(范围从0到的其余部分Ñ -2),即,多少取决于小号上每个顶点.
顶点w从S弹出直到空,从s中最远的一个开始并以s本身结束(请记住,当在算法的最短路径计数部分到达时,顶点被添加到S).对于w(Pred [ w ])的前辈列表中的每个v,计算依赖关系的新值,并且(对我来说)是棘手的部分.
表达式表示delta [ v ] = delta [ v ] +(sigma [ v ]/sigma [ w ])*(1 + delta [ w ]),或换句话说,v的新依赖关系是已经有的依赖加(sigma [ v ]/sigma [ w ])*(1 + delta [ w ]).好吧,首先请注意,当从S弹出一个顶点w时,它的整个依赖关系delta [ w ]已被计算出来,因为将来没有比w更远的节点,所以它不能处于任何其他最短的中间路径.然后,应当清楚的是(西格玛 [ v ]/西格玛 [ 瓦特 ])是对依赖性(小号,瓦特)的v,即,多少取决于顶点小号和瓦特的v保持连接(因为它是从s到w经过v)的最短路径的比例.但是(这是不太明显的部分,我认为),顶点v不仅在s和w之间的最短路径中,它也在涉及w的所有最短路径中!因此,如果存在从s到通过w的某个顶点x的最短路径,那么必须存在从s到x经过v的路径.简单来说,如果它依赖于w,s将更多地依赖于v.所以,系数(1个+ 增量 [ 瓦特 ])进行说明如下:1,对于依赖v的对(小号,瓦特),和增量 [ 瓦特 ]为的依赖性v每对(小号,<超出w >的任何顶点.
最后,delta [ w ]被添加到其完全中介Cb [ w ](除非w == s,因为s不被认为是依赖于它自身).
正如我所说,乍一看这并不是一个简单易懂的算法.花点时间,如果你还有疑问,请发表评论.
我不完全确定你在这里提到的是什么.如果你问如何从Dijkstra算法的输出中获得前辈列表,那么,你不能,至少直接.如果您想使用预先存在的Dijkstra算法实现此算法,除非算法在执行期间允许某种类型的访问者,否则您将无法实现此功能,例如Boost Graph库Dijkstra实现.顺便说一句,这个库已经实现了这个算法(见这里),甚至是分布式/并行版本(这里和这里),如果你对此感兴趣的话.
有(至少)两种方法可以在中介计算中考虑权重(我假设你的意思是边权重):作为"长度",因此它对最短路径计算有影响,并且作为"重要性"或"多重性"(例如,关系出现的次数).布兰德斯本人在他的论文"最短路径中介性变量"及其通用计算,算法10("长度")和11("多重性")的论文中为这些和其他案例提供了几种变体.请注意,本文算法11中存在错误,Brandes的出版物页面中对此进行了解释(在列表中查找论文的名称).