Articulation Points Guided Redundancy Elimination for Betweenness Centrality

doi:10.1145/2851141.2851154

	Articulation Points Guided Redundancy Elimination for Betweenness Centrality
	Wang, Lei; Yang, Fan; Zhuang, Liangji; Cui, Huimin; Lv, Fang; Feng, Xiaobing
	2016-08-01
发表期刊	ACM SIGPLAN NOTICES
ISSN	0362-1340
卷号	51 期号:8 页码:73-86
摘要	Betweenness centrality (BC) is an important metrics in graph analysis which indicates critical vertices in large-scale networks based on shortest path enumeration. Typically, a BC algorithm constructs a shortest-path DAG for each vertex to calculate its BC score. However, for emerging real-world graphs, even the stateof- the-art BC algorithm will introduce a number of redundancies, as suggested by the existence of articulation points. Articulation points imply some common sub-DAGs in the DAGs for different vertices, but existing algorithms do not leverage such information and miss the optimization opportunity. We propose a redundancy elimination approach, which identifies the common sub-DAGs shared between the DAGs for different vertices. Our approach leverages the articulation points and reuses the results of the common sub-DAGs in calculating the BC scores, which eliminates redundant computations. We implemented the approach as an algorithm with two-level parallelism and evaluated it on a multicore platform. Compared to the state-of-theart implementation using shared memory, our approach achieves an average speedup of 4.6x across a variety of real-world graphs, with the traversal rates up to 45 similar to 2400 MTEPS (Millions of Traversed Edges per Second).
关键词	Algorithms Performance Partial Redundancy Elimination Parallelism Betweenness Centrality
DOI	10.1145/2851141.2851154
收录类别	SCI
语种	英语
资助项目	National High Technology Research and Development Program of China[2015AA011505] ; National Natural Science Foundation of China[61402445] ; National Natural Science Foundation of China[61303053] ; National Natural Science Foundation of China[61202055] ; National Natural Science Foundation of China[61221062] ; National Natural Science Foundation of China[61502452]
WOS研究方向	Computer Science
WOS类目	Computer Science, Software Engineering
WOS记录号	WOS:000393580200008
出版者	ASSOC COMPUTING MACHINERY
引用统计	被引频次：9[WOS] [WOS记录] [WOS相关记录]
文献类型	期刊论文
条目标识符	http://119.78.100.204/handle/2XEOYT63/7593
专题	中国科学院计算技术研究所期刊论文_英文
通讯作者	Wang, Lei
作者单位	Chinese Acad Sci, State Key Lab Comp Architecture, Inst Comp Technol, Beijing 100864, Peoples R China
推荐引用方式 GB/T 7714	Wang, Lei,Yang, Fan,Zhuang, Liangji,et al. Articulation Points Guided Redundancy Elimination for Betweenness Centrality[J]. ACM SIGPLAN NOTICES,2016,51(8):73-86.
APA	Wang, Lei,Yang, Fan,Zhuang, Liangji,Cui, Huimin,Lv, Fang,&Feng, Xiaobing.(2016).Articulation Points Guided Redundancy Elimination for Betweenness Centrality.ACM SIGPLAN NOTICES,51(8),73-86.
MLA	Wang, Lei,et al."Articulation Points Guided Redundancy Elimination for Betweenness Centrality".ACM SIGPLAN NOTICES 51.8(2016):73-86.