论文标题
DRGRAPH：通过降低维度的有效图形布局算法，用于大规模图
DRGraph: An Efficient Graph Layout Algorithm for Large-scale Graphs by Dimensionality Reduction
论文作者
论文摘要
大规模图的有效布局仍然是一个具有挑战性的问题：基于力量和基于尺寸降低的方法的图形距离和梯度计算的高间接费用受到高高的限制。在本文中，我们提出了一种称为DRGRAPH的新图布局算法，该算法通过三个方案来增强非线性维度降低过程：通过稀疏距离矩阵近似图形距离近似图距离，通过使用负采样技术来估算梯度，并通过多层布局来加速优化过程。 Drgraph实现了用于计算和内存消耗的线性复杂性，并扩展到具有数百万个节点的大规模图。实验结果和与最先进的图形布局方法的比较表明，Drgraph可以生成具有更快的运行时间和较低内存需求的视觉比较布局。
Efficient layout of large-scale graphs remains a challenging problem: the force-directed and dimensionality reduction-based methods suffer from high overhead for graph distance and gradient computation. In this paper, we present a new graph layout algorithm, called DRGraph, that enhances the nonlinear dimensionality reduction process with three schemes: approximating graph distances by means of a sparse distance matrix, estimating the gradient by using the negative sampling technique, and accelerating the optimization process through a multi-level layout scheme. DRGraph achieves a linear complexity for the computation and memory consumption, and scales up to large-scale graphs with millions of nodes. Experimental results and comparisons with state-of-the-art graph layout methods demonstrate that DRGraph can generate visually comparable layouts with a faster running time and a lower memory requirement.
