通信学报 ›› 2016, Vol. 37 ›› Issue (3): 182-189.doi: 10.11959/j.issn.1000-436x.2016066

• 学术论文 • 上一篇    下一篇

基于Graphlab的网络图关键节点发现算法研究

高壮良1,吕雁飞2,张鸿2   

  1. 1 北京航空航天大学计算机学院,北京100191
    2 国家计算机网络应急技术处理协调中心,北京100029
  • 出版日期:2016-03-25 发布日期:2017-08-04
  • 基金资助:
    国家重点基础研究发展计划(“973”计划)基金资助项目

Key nodes discovery in network graph based on Graphlab

Zhuang-liang GAO1,Yan-fei LYU2,Hong ZHANG2   

  1. 1 School of Computer Science and Engineering,Beihang Un versity,Beijing 100191,China
    2 National Computer Network Emergency Response Technical Team/Coordination Center of China,Beijing 100029,China
  • Online:2016-03-25 Published:2017-08-04
  • Supported by:
    The National Basic Research Program of China(973 Program)

摘要:

针对桥接中心度的计算特点设计了一种分布式的网络图关键节点发现算法(DABC),并基于 Graphlab进行了实现。算法具有良好的扩展性,由于能够利用集群的内存资源,算法能处理的图规模与集群的大小成正比,并且该算法利用并行处理大幅度提升了计算速度。实验表明,与传统的基于单机实现的关键节点发现算法相比,算法可以获得高达4倍的性能提升。

关键词: 关键节点, 桥接中心度, 分布式算法, Graphlab

Abstract:

A distributed key nodes discovery algorithm was proposed(DABC) which was implemented on Graphlab.Due to the good scalability,the scale of graph supported by algorithm was enlarged significantly.The parallel processing also enhances the speed of calculation.Experiment results show that proposed algorithm can achieve up to 4 times per-formance improvement compared with the traditional centralized key node discovery algorithm.

Key words: key node, betweenness centrality, distributed algorithm, Graphlab

No Suggested Reading articles found!