Betweenness-based algorithm for a partition scale-free graph  

作　　者：张百达 吴俊杰 唐玉华 周静 

机构地区：[1]National Laboratory for Parallel and Distributed Processing,School of Computers,National University of Defense Technology [2]Department of Computer Science and Technology,School of Computers,National University of Defense Technology

出　　处：《Chinese Physics B》2011年第11期556-564,共9页中国物理B（英文版）

基　　金：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);the Foundation for Innovative Research Groups of the National Natural Science Foundation of China(Grant No.60921062)

摘　　要：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.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 

分 类 号：O157.5[理学—数学]