Key nodes discovery in network graph based on Graphlab

Zhuang-liang GAO; Yan-fei LYU; Hong ZHANG

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

您当前的位置：

首页 >

文章列表页 >

Key nodes discovery in network graph based on Graphlab

Academic paper | 更新时间：2024-06-05

- Key nodes discovery in network graph based on Graphlab
- Journal on Communications Vol. 37, Issue 3, Pages: 182-189(2016)
- 作者机构：
  
  1. 北京航空航天大学计算机学院，北京100191
  2. 国家计算机网络应急技术处理协调中心，北京100029
- 作者简介：
- 基金信息：
  
  The National Basic Research Program of China (973 Program)(2011CB302605)
- DOI：10.11959/j.issn.1000-436x.2016066
  CLC： TP316.4
- Online First：2016-03，
  
  Published：25 March 2016
- 稿件说明：
移动端阅览
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：

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 .

Views

1476

下载量

CSCD

Alert me when the article has been cited

提交

Tools

Publicity Resources

Efficient distributed traffic offloading algorithm based on SDN architecture

Distributed maximum weight matching algorithm based on belief propagation

Planar t-spanner for wireless ad hoc network

Distributed aggregate algorithm for average query based on WSN

Distributed algorithms for cooperative routing and power allocation in wireless sensor networks

Related Author

Wen-jie QIAN

Zhu REN

Wei-wei CHENG

Wen-tao LYU

Wei-qiang XU

Yuan ZHANG

PENG Wei

LU Xi-cheng

Related Institution

School of Information Science and Technology, Zhejiang Sci-Tech University

National Mobile Communications Research Laboratory, Southeast University

School of Computer,National University of Defense Technology

国防科技大学计算机学院

School of Computer and Communication,Hunan University

AI问答

⁰