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

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

Abstract

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

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.

Figures/Tables 11

References 15

[16]	[EB/OL]. 2011.
[17]	UGANDER J , KARRER B , BACKSTROM L , et al. The anatomy o the facebook social graph[J]. arXiv preprint arXiv:1111.4503. 2011.
[18]	[EB/OL]. 2014.
[19]	JURE L , ANDREJ K . SNAP Datasets:large network dataset collection[EB/OL]. .
[1]	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, c2007:124-137.
[2]	ANTHONISSE J . The rush in a directed graph[M]. Amsterdam: Stichting Mathematisch Contrum, 1971:1-10.
[3]	FREEMAN L . A set of measure of centrality based on betweenness[J]. Sociomtry, 1977,40(1): 35-41.
[4]	CARPENTER T , KARAKOSTAS G , SHALLCROSS D . Practical issues and algorithms for analyzing terrorist networks[C]// International Workshop on Mobile Commerce. San Antonio, c2012.
[5]	BRANDS U . A faster algorithm for betweenness centralit Journal of Mathematical Sociology, 2001,25(2): 163-177.
[6]	BRANDS U . On variants of shortest-path betweenness centrality and their generic computation[J]. Social Networks, 2008,30(2): 136-145.
[7]	LEE M , LEE J , PARK J Y , et al. QUBE:a quick algorithm for updating betweenness centrality[C]//WWW. Lyon,France, c2012:351-360.
[8]	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.
[9]	TAN G , TU D , SUN N . A parallel algorithm for computing betweenness centrality[C]// Washington ICPP. c2009:340-347.
[10]	JEREY D , SANJAY G . MapReduce:simplied data processing on large clusters[C]// 6th USENIX Symp on Operating Syst Design nd Impl. c2004:137-150.
[11]	GRZEGORZ M , MATTHEW H . Austern pregel:a system for large-scale graph processing[C]// The ACM SIGMOD Conference(SIGMOD). Indianapolis,Indiana, c2010:135-146.
[12]	LOW Y , GONZALEZ J , KYROLA A , et al. GraphLab:a new parallel framework for machine learning[C]// Uncertainty in Artificial Intelligence. c2010:340-349.
[13]	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.
[14]	GONZALEZ J E , LOW Y , GU H , et al. PowerGraph:distributed graphparallel computation on natural graphs[C]// USENIX Conf Operating Systems Design and Implementation. c2012:17-30.
[15]	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). c2013:2-16.

Metrics

Recommended 0

No Suggested Reading articles found!

符号	含义
V_p	在分区P中的所有顶点集合
V^maP	在分区P中的master顶点
V^miP	在分区P中的mirror顶点
N^outP (u)	在分区P中顶点u的所有出边邻居
Nⁱⁿ_P (u)	在分区P中顶点u的所有入边邻居
u_{d is t}(v)	顶点v到顶点u的距离，初始值-1
u_s(v)	顶点v到顶点u的最短路径的数量，初始值0
u_done	到顶点u的已计算过的顶点集合

数据集	顶点数	边数	边数1	边数2
数据集1	1 000	—	4 186	10 006
	2 000	—	7 986	18 676
	3 000	—	21 231	25 679
	4 000	—	26 048	33 884
数据集2	1 500	97 140	—	—
数据集2	SNAP10 835	159 388	—	—

Key nodes discovery in network graph based on Graphlab

RichHTML

PDF

Knowledge

Abstract

Cite this article

share this article

Figures/Tables 11

References 15

Related Articles 10

Metrics

Recommended 0

[1]	Qiuyang GU, Bao WU, Zhaoyang SUN, Renyong CHI. Key node identification algorithm for complex network based on improved grey wolf optimization [J]. Journal on Communications, 2021, 42(6): 72-83.
[2]	Wen-jie QIAN,Zhu REN,Wei-wei CHENG,Wen-tao LYU,Wei-qiang XU. Efficient distributed traffic offloading algorithm based on SDN architecture [J]. Journal on Communications, 2017, 38(6): 167-176.
[3]	Bin LIU,Ya-jing SUN,Hao-ran LIU,Rong-rong YIN. Key node decision algorithm based on local information and energy factor in wireless sensor network [J]. Journal on Communications, 2015, 36(10): 9-16.
[4]	Jian-xun ZHANG,Zhi-min GU,Xiao-han HU,Min CAI. Multi-core helper thread prefetching for irregular data intensive applications [J]. Journal on Communications, 2014, 35(8): 137-146.
[5]	. Multi-core helper thread prefetching for irregular data intensive applications [J]. Journal on Communications, 2014, 35(8): 17-146.
[6]	Yuan ZHANG. Distributed maximum weight matching algorithm based on belief propagation [J]. Journal on Communications, 2012, 33(10): 132-137.
[7]	Dao-yuan YAO,Hai-lin WANG,Bao-xian ZHANG,Hai-tao LIU. QoS-based sensing scheduling protocol for wireless sensor networks [J]. Journal on Communications, 2010, 31(5): 128-134.
[8]	Cai-ping LIU,Ren-fa LI,Xi-ping LIU. Distributed aggregate algorithm for average query based on WSN [J]. Journal on Communications, 2008, 29(11): 24-30.
[9]	Jiang-bo SI,Zan LI,Lan-jun DANG,Zeng-ji LIU. Distributed algorithms for cooperative routing and power allocation in wireless sensor networks [J]. Journal on Communications, 2008, 29(11): 67-76.
[10]	Ming LI,Xi-cheng LU,Wei PENG. Planar t-spanner for wireless ad hoc network [J]. Journal on Communications, 2005, 26(6): 62-69.