Betweenness-based algorithm for a partition scale-free graph

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

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.

Keywords: graph partitioning betweenness-based partitioning algorithm scale free network

Received: 30 March 2011
Revised: 17 August 2011
Accepted manuscript online:

PACS:	89.75.Hc	(Networks and genealogical trees)
	87.23.Ge	(Dynamics of social systems)
	89.20.Hh	(World Wide Web, Internet)
	89.75.-k	(Complex systems)

Fund: 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).

Cite this article:

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

[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

[1]	An estimation formula for the average path length of scale-free networks Li Ying(李旲), Cao Hong-Duo(曹宏铎), Shan Xiu-Ming(山秀明), and Ren Yong(任勇) . Chin. Phys. B, 2008, 17(7): 2327-2332.

No Suggested Reading articles found!

Viewed

Full text

Abstract

Cited

Metrics
Related Articles

Betweenness-based algorithm for a partition scale-free graph

Cite this article:

Online attention