Betweenness-based algorithm for a partition scale-free graph

doi:10.1088/1674-1056/20/11/118903

中国物理B ›› 2011, Vol. 20 ›› Issue (11): 118903-118903.doi: 10.1088/1674-1056/20/11/118903

Betweenness-based algorithm for a partition scale-free graph

唐玉华¹, 张百达², 吴俊杰², 周静²

(1)Department of Computer Science and Technology, School of Computers, National University of Defense Technology, Changsha 410073, China; (2)National Laboratory for Parallel and Distributed Processing, School of Computers, National University of Defense Technology, Changsha 410073, China

收稿日期:2011-03-30 修回日期:2011-08-17 出版日期:2011-11-15 发布日期:2011-11-15
基金资助:
Project supported by the National Science Foundation for Distinguished Young Scholars of China (Grant Nos. 61003082 and 60903059), the National Natural Science Foundation of China (Grant No. 60873014) and the Foundation for Innovative Research Groups of the National Natural Science Foundation of China (Grant No. 60921062).

Betweenness-based algorithm for a partition scale-free graph

Zhang Bai-Da(张百达)^a)^†, Wu Jun-Jie(吴俊杰)^a), Tang Yu-Hua(唐玉华)^b), and Zhou Jing(周静)^a)

^a National Laboratory for Parallel and Distributed Processing, School of Computers, National University of Defense Technology, Changsha 410073, China; ^b Department of Computer Science and Technology, School of Computers, National University of Defense Technology, Changsha 410073, China

Received:2011-03-30 Revised:2011-08-17 Online:2011-11-15 Published:2011-11-15
Supported by:
Project supported by the National Science Foundation for Distinguished Young Scholars of China (Grant Nos. 61003082 and 60903059), the National Natural Science Foundation of China (Grant No. 60873014) and the Foundation for Innovative Research Groups of the National Natural Science Foundation of China (Grant No. 60921062).

摘要/Abstract

摘要： Many real-world networks are found to be scale-free. However, graph partition technology, as a technology capable of parallel computing, performs poorly when scale-free graphs are provided. The reason for this is that traditional partitioning algorithms are designed for random networks and regular networks, rather than for scale-free networks. Multilevel graph-partitioning algorithms are currently considered to be the state of the art and are used extensively. In this paper, we analyse the reasons why traditional multilevel graph-partitioning algorithms perform poorly and present a new multilevel graph-partitioning paradigm, top down partitioning, which derives its name from the comparison with the traditional bottom-up partitioning. A new multilevel partitioning algorithm, named betweenness-based partitioning algorithm, is also presented as an implementation of top-down partitioning paradigm. An experimental evaluation of seven different real-world scale-free networks shows that the betweenness-based partitioning algorithm significantly outperforms the existing state-of-the-art approaches.

关键词: graph partitioning, betweenness-based partitioning algorithm, scale free network

Abstract: Many real-world networks are found to be scale-free. However, graph partition technology, as a technology capable of parallel computing, performs poorly when scale-free graphs are provided. The reason for this is that traditional partitioning algorithms are designed for random networks and regular networks, rather than for scale-free networks. Multilevel graph-partitioning algorithms are currently considered to be the state of the art and are used extensively. In this paper, we analyse the reasons why traditional multilevel graph-partitioning algorithms perform poorly and present a new multilevel graph-partitioning paradigm, top down partitioning, which derives its name from the comparison with the traditional bottom-up partitioning. A new multilevel partitioning algorithm, named betweenness-based partitioning algorithm, is also presented as an implementation of top-down partitioning paradigm. An experimental evaluation of seven different real-world scale-free networks shows that the betweenness-based partitioning algorithm significantly outperforms the existing state-of-the-art approaches.

Key words: graph partitioning, betweenness-based partitioning algorithm, scale free network

中图分类号: (Networks and genealogical trees)

89.75.Hc

87.23.Ge (Dynamics of social systems) 89.20.Hh (World Wide Web, Internet) 89.75.-k (Complex systems)

张百达, 吴俊杰, 唐玉华, 周静. Betweenness-based algorithm for a partition scale-free graph[J]. 中国物理B, 2011, 20(11): 118903-118903.

Zhang Bai-Da(张百达), Wu Jun-Jie(吴俊杰), Tang Yu-Hua(唐玉华), and Zhou Jing(周静) . Betweenness-based algorithm for a partition scale-free graph[J]. Chin. Phys. B, 2011, 20(11): 118903-118903.

参考文献 33

[1]	Albert R and Barabási A 2002 Rev. Modern Phys. 74 47
[2]	Newman M 2003 SIAM Rev. 45 167
[3]	Goodman D and Brette R 2008 Frontiers in Neuroinformatics 2 134
[4]	Hendrickson B and Kolda T 2000 Parallel Computing 26 1519
[5]	Garey M and Johnson L 1976 Theoretical Computer Science 1 237
[6]	Karypis G and Kumar V 1995 The University of Minnesota 2 11
[7]	Hendrickson B and Leland R 1994 The Chaco User's Guide-Version 2.0 (Technical report) (Sandia National Laboratories)
[8]	Pellegrini F and Roman J 1996 Proceedings of HPCN'96, Brussels, April 1996 p. 493
[9]	Walshaw C and Cross M 2007 Mesh Partitioning Techniques and Domain Decomposition Techniques 21 27
[10]	Barabási A and Albert R 1999 Science 286 509
[11]	Abou-Rjeili A and Karypis G 2006 Parallel and Distributed Processing Symposium Newyork, April 2006 10
[12]	Fortunato S 2010 Phys. Reports 486 75
[13]	Duch J and Arenas A 2005 Phys. Rev. E 72 027104
[14]	Zou S R, Peng Y J, Liu A F, Xu X L and He D R 2011 Chin. Phys. B 20 018902
[15]	Zhang L M, Deng X H, Yu J P and Wu X S 2011 Chin. Phys. B 20 048902
[16]	Tian L, Di Z R and Yao H 2011 Acta Phys. Sin. 60 02120
[17]	Newman M 2002 Phys. Rev. Lett. 89 208701
[18]	Yang R, Wang W X, Lai Y C and Chen G R 2009 Phys. Rev. E 79 026112
[19]	Yang R, Zhou T, Xie Y B, Lai Y C and Wang B H 2008 Phys. Rev. E 78 066109
[20]	Newman M and Girvan M 2004 Phys. Rev. E 69 26113
[21]	Shen Y 2011 Chin. Phys. B 20 040511
[22]	Cui A X, Fu Y S, Shang M S, Chen D B and Zhou T 2011 Acta Phys. Sin. 60 803 (in Chinese)
[23]	Schloegel K, Karypis G and Kumar V 2003 Sourcebook of Parallel Computing (Morgan Kaufmann Publishers Inc.) p. 491
[24]	Karypis G and Kumar V 1995 Proceedings of the International Conference on Parallel Processing New York, p. 135
[25]	Barnard S and Simon H 1994 Concurrency: Practice and Experience 6 101
[26]	Karypis G and Kumar V 1999 SIAM Journal on Scientific Computing 20 359
[27]	Hendrickson B and Leland R 1995 SIAM Journal on Scientific Computing 16 452
[28]	Hendrickson B and Leland R (US Patent) 5587922
	[1996]
[29]	Kernighan B and Lin S 1970 Bell System Technical Journal 49 291
[30]	Mattheyses C and Fiduccia C 1982 Proceedings of the 19th Design Automation Conference New York, p. 175
[31]	Hendrickson B and Leland R 1995 Proceedings of the 1995 ACM/IEEE Conference on Supercomputing p. 28
[32]	Karypis G and Kumar V 1995 Proceedings of the 1995 ACM/IEEE Conference on Supercomputing p. 29
[33]	Hou B N and Yao Y P 2010 2010 IEEE/ACM 14th International Symposium on Distributed Simulation and Real Time Applications p. 7

Betweenness-based algorithm for a partition scale-free graph

Betweenness-based algorithm for a partition scale-free graph

PDF (PC)

赞

可视化

摘要/Abstract

引用本文

使用本文

参考文献 33

相关文章 1

Metrics

本文评价

推荐阅读 0