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

高壮良; 吕雁飞; 张鸿

doi:10.11959/j.issn.1000-436x.2016066

您当前的位置：

首页 >

文章列表页 >

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

学术论文 | 更新时间：2024-06-05

- 基于Graphlab的网络图关键节点发现算法研究
- Key nodes discovery in network graph based on Graphlab
- 通信学报 2016年37卷第3期页码：182-189
- 作者机构：
  
  1. 北京航空航天大学计算机学院，北京100191
  2. 国家计算机网络应急技术处理协调中心，北京100029
- 作者简介：
  
  [ "高壮良（1990-），男，山东菏泽人，北京航空航天大学硕士生，主要研究方向为分布式图计算。" ]
  [ "吕雁飞（1984-），男，辽宁朝阳人，博士，国家计算机网络应急技术处理协调中心工程师，主要研究方向为大数据技术。" ]
  [ "张鸿（1976-），男，陕西西安人，博士，国家计算机网络应急技术处理协调中心高级工程师，主要研究方向为云计算、大数据、网络安全。" ]
- 基金信息：
  
  国家重点基础研究发菜计划（“973”计划）基金资助项目(2011CB302605)
- DOI：10.11959/j.issn.1000-436x.2016066
  中图分类号： TP316.4
- 网络出版日期：2016-03，
  
  纸质出版日期：2016-03-25
- 稿件说明：
移动端阅览
高壮良, 吕雁飞, 张鸿. 基于Graphlab的网络图关键节点发现算法研究[J]. 通信学报, 2016,37(3):182-189.

Zhuang-liang GAO, Yan-fei LYU, Hong ZHANG. Key nodes discovery in network graph based on Graphlab[J]. Journal on communications, 2016, 37(3): 182-189.
高壮良, 吕雁飞, 张鸿. 基于Graphlab的网络图关键节点发现算法研究[J]. 通信学报, 2016,37(3):182-189. DOI： 10.11959/j.issn.1000-436x.2016066.

Zhuang-liang GAO, Yan-fei LYU, Hong ZHANG. Key nodes discovery in network graph based on Graphlab[J]. Journal on communications, 2016, 37(3): 182-189. DOI： 10.11959/j.issn.1000-436x.2016066.

摘要

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

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.

关键词

Keywords

references

BADER D A , KINTALI S , MADDURI K , et al . Approximating betweenness centrality [C ] // Workshop on Algorithms and Models for the Web-Graph . San Diego,CA , c 2007 : 124 - 137 .

ANTHONISSE J . The rush in a directed graph [M ] . Amsterdam : Stichting Mathematisch Contrum , 1971 : 1 - 10 .

FREEMAN L . A set of measure of centrality based on betweenness [J ] . Sociomtry , 1977 , 40 ( 1 ): 35 - 41 .

CARPENTER T , KARAKOSTAS G , SHALLCROSS D . Practical issues and algorithms for analyzing terrorist networks [C ] // International Workshop on Mobile Commerce . San Antonio , c 2012 .

BRANDS U . A faster algorithm for betweenness centralit Journal of Mathematical Sociology , 2001 , 25 ( 2 ): 163 - 177 .

BRANDS U . On variants of shortest-path betweenness centrality and their generic computation [J ] . Social Networks , 2008 , 30 ( 2 ): 136 - 145 .

LEE M , LEE J , PARK J Y , et al . QUBE:a quick algorithm for updating betweenness centrality [C ] //WWW. Lyon,France , c 2012 : 351 - 360 .

YANG J X , WANG C K , BAI Y Y . A fast algorithm for updating betweenness centrality in social networks [J ] . Journal f Computer Research and Development , 2012 , 49 ( 1 ): 243 - 249 .

TAN G , TU D , SUN N . A parallel algorithm for computing betweenness centrality [C ] // Washington ICPP . c 2009 : 340 - 347 .

JEREY D , SANJAY G . MapReduce:simplied data processing on large clusters [C ] // 6th USENIX Symp on Operating Syst Design nd Impl . c 2004 : 137 - 150 .

GRZEGORZ M , MATTHEW H . Austern pregel:a system for large-scale graph processing [C ] // The ACM SIGMOD Conference (SIGMOD). Indianapolis,Indiana , c 2010 : 135 - 146 .

LOW Y , GONZALEZ J , KYROLA A , et al . GraphLab:a new parallel framework for machine learning [C ] // Uncertainty in Artificial Intelligence . c 2010 : 340 - 349 .

LOW Y , BICKSON D , GONZALEZ J , et al . Distributed GraphLab:a framework for machine learning and data mining in the loud [J ] . Proceedings of the VLDB Endowment , 2012 , 5 ( 8 ): 716 - 727 .

GONZALEZ J E , LOW Y , GU H , et al . PowerGraph:distributed graphparallel computation on natural graphs [C ] // USENIX Conf Operating Systems Design and Implementation . c 2012 : 17 - 30 .

XIN R S , GONZALEZ J E , FRANKLIN M J , et al . GraphX:a resilient distributed graph system on Spark [C ] // First International Workshop on Graph Data Management Experiences and Systems (GRADES 2013). c 2013 : 2 - 16 .

https://giraph.apache.org https://giraph.apache.org [EB/OL ] . 2011 .

UGANDER J , KARRER B , BACKSTROM L , et al . The anatomy o the facebook social graph [J ] . arXiv preprint arXiv:1111.4503 . 2011 .

http://graphlab.org/projects/source.html http://graphlab.org/projects/source.html [EB/OL ] . 2014 .

JURE L , ANDREJ K . SNAP Datasets:large network dataset collection [EB/OL ] . http://snap.stanford.edu/data/2014 http://snap.stanford.edu/data/2014 .

浏览量

716

下载量

CSCD

文章被引用时，请邮件提醒。

提交

工具集

关联资源

基于SDN架构的高效分布式流量分载算法

基于信念传播的分布式最大权匹配算法

面向无线ad hoc网络的一种平面t-支撑图

无线传感器网络分布式均值查询聚集算法研究

无线传感器网络中的分布式协作路由和功率分配算法研究