社交网络介数中心度快速更新算法

摘要

近年来,社交网络的高速发展,社交成员的重要性度量受到了越来越多的关注.其中,介数中心度(betweenness centrality)被广泛地应用于节点重要性的度量中.针对图结构频繁变化的场合中介数中心度效率较低这一问题,通过在第1次计算介数中心度时改进Brandes算法,并在之后的更新操作时缩小需要计算的最短路径点对范围,提高寻找最短路径效率的方法,大大提高了有向无权图中加边操作时的介数中心度更新效率,该算法在不同真实数据上的实验,尤其是在稀疏图或具有较多独立区域的有向图中表现出很好的更新加速性能.