欢迎您！东篱公司
退出
-
申报数据库
-
立项数据库
-
成果数据库
-
项目获奖数据库
中文摘要：
<正>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.
同期刊论文项目
同项目期刊论文
Fine-grained Parallel RNAalifold Algorithm for RNA Secondary Structure Prediction on FPGA, Proceedin
Fine-grained parallel RNA secondary structure prediction using SCFGs on FPGA, Journal of Parallel Co
期刊信息
位置：