Back to Search
Start Over
Betweenness-based algorithm for a partition scale-free graph
- Source :
- Chinese Physics B. 20:118903
- Publication Year :
- 2011
- Publisher :
- IOP Publishing, 2011.
-
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.
Details
- ISSN :
- 16741056
- Volume :
- 20
- Database :
- OpenAIRE
- Journal :
- Chinese Physics B
- Accession number :
- edsair.doi...........a4c584bcf8365a4f6093763b7ab787c5