一种高效的顶点偏心率计算方法

• 作者: 刘冬 杜明 王志军 周军峰
• 来源期刊: 新一代信息技术
• 关键词: 偏心率 偏心率范围 顶点合并 参考顶点池
• 年，卷（期）: 2021,（2）
• 所属期刊栏目: 科技论文
• 页码范围: 1-10
• 页数: 10页
• 分类号: TP319
• 语种: 中文
• DOI: 10.3969/j.issn.2096-6091.2021.02.001

摘要

目的 偏心率可以用来描述图中顶点的重要程度,一个顶点偏心率指的是从该顶点出发的最长最短路径的长度,得知顶点的偏心率有助于分析图的其他特征,比如图的中心性、半径和直径等.方法 针对现有方法存在的索引构建代价高、计算效率低的问题展开研究,提出一种基于子图划分思想的偏心率求解算法ECC-DIS,该算法提出了子图划分策略、顶点合并策略和相应的偏心率求解算法,在计算时得出顶点对每个子图的局部偏心率,并基于索引进行剪枝,可在较小范围内计算偏心率,局部偏心率的最大值为该顶点的偏心率.结果 通过子图划分和顶点合并,降低了索引规模和顶点计算规模,改进了偏心率计算的效率.结论 在多个真实数据集上进行实验,实验结果从多个方面验证了本文提出算法的高效性.