中国物理B ›› 2011, Vol. 20 ›› Issue (11): 118903-118903.doi: 10.1088/1674-1056/20/11/118903
唐玉华1, 张百达2, 吴俊杰2, 周静2
Zhang Bai-Da(张百达)a)†, Wu Jun-Jie(吴俊杰)a), Tang Yu-Hua(唐玉华)b), and Zhou Jing(周静)a)
摘要: 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.
中图分类号: (Networks and genealogical trees)