基于PageRank的网络布局算法

A PageRank-based Network Layout Algorithm

摘要:

基于力导向模型的网络布局算法由于其布局结果直观并且便于分析所以在网络可视化中占有举足轻重的地位。但是当前的网络布局算法在面对大规模网络数据的时候通常不容易在较短时间内获取一个高质量的布局结果。本文提出了一个基于PageRank的力导向模型的算法。该算法引入了PageRank来完善节点的重力和斥力计算以改善布局质量；并且引入节点中心性来预估初始布局中节点的位置；同时,又提出了基于PageRank的自适应步长用来平衡布局的效率和质量。最后为了有效的减少布局算法在面对大规模网络数据时的计算时间,本文设计了一个基于CUDA的灵活的CPU+GPU异构并行计算框架。通过对不同类型和不同规模的网络数据集的实验,该算法能够产出一个符合美学标准的高质量布局,并且在同样的硬件条件下,本文所提出的优化方案相比于原始算法速度最大提高了58倍。

Abstract:

With the layout results intuitive and easy to analyze, the network layout algorithm plays a critical role in network visualization based on the Force-Directed model. However, a high-quality layout result is not obtained easily by current network layout algorithms in a brief period when confronted with large-scale network data. An algorithm based on PageRank"s Force-Directed model is proposed in this paper, which can produce a better layout with aesthetic metrics such as Crosslessness , Minimum angle metric and so on. Moreover, to enhance the layout quality, the algorithm introduces PageRank to perfect the gravity and repulsion force calculation of nodes. Simultaneously, this paper proposes an adaptive step length based on PageRank to balance the efficiency and quality of the layout. Finally, a flexible CPU+GPU heterogeneous parallel computing framework was designed based on CUDA to effectively reduce the calculation time of the layout algorithm in the face of large-scale network data. The algorithm can produce a high quality layout via experiments with different types and sizes of network datasets. And under the same hardware conditions, the optimization scheme proposed in this paper is up to 58 times faster than the original algorithm.