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

摘要：

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

关键词： 社交网络 介数中心度 算法改进 最短路径

作者: Yang Jianxiang 杨建祥 Wang Chaokun 王朝坤 Bat Yiyuan 白易元 Hao Jingchao 郝竞超 Wang Hao 汪浩

作者单位: School of Software, Tsinghua University, Beijing 100084 清华大学软件学院 北京 100084 Tsinghua National Laboratory for Information Science and Technology, Beijing 100084 清华信息科学与技术国家实验室(筹) 北京 100084 Key Laboratory for Information System Security(Tsinghua University), Ministry of Education, Beijing 信息系统安全教育部重点实验室(清华大学) 北京 100084

会议类型: 国内会议

会议名称: 第29届中国数据库学术会议

会议地点: 合肥

会议语种:中文

页码: 243-249

在线出版日期: 2012-10-01（万方平台首次上网日期，不代表论文的发表时间）