%0 Journal Article
%T Betweenness-based algorithm for a partition scale-free graph<br>
%A Zhang Bai-D
%A Wu Jun-Jie
%A Tang Yu-Hua
%A Zhou Jing
%A <br>
%J 中国物理 B
%D 2011
%I 
%X 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.
%K graph partitioning
%K betweenness-based partitioning algorithm
%K scale free network<br>
%U http://www.alljournals.cn/get_abstract_url.aspx?pcid=6E709DC38FA1D09A4B578DD0906875B5B44D4D294832BB8E&cid=47EA7CFDDEBB28E0&jid=CD8D6A6897B9334F09D8D1648C376FB4&aid=3D120F67FFBE1E37ABA3121ED00E56E6&yid=9377ED8094509821&vid=A04140E723CB732E&iid=708DD6B15D2464E8&sid=DD1A6DF9A4068ED7&journal_id=1009-1963&journal_name=中国物理&referenced_num=0&reference_num=33