Spectrum-preserving sparsification for visualization of big graphs
Spectrum-preserving sparsification for visualization of big graphs
复制标题
DOI：
10.1016/j.cag.2020.02.004
复制
发表时间：
2020-04-01
影响因子：
2.5
通讯作者：
Wang, Chaoli
中科院分区：
文献类型：
--
作者：
Imre, Martin;Tao, Jun;Wang, Chaoli
我们提出了一种新的频谱保持稀疏化算法可视化大图形数据。虽然谱方法有许多优点，但由于涉及拉普拉斯特征值问题而导致的高存储和计算成本会立即阻碍其在大图分析中的应用。在本文中，我们介绍了一种实用高效的，接近线性的时间谱稀疏化算法，用于处理真实世界的大图数据。除了频谱稀疏化，我们进一步提出了一个节点减少计划的基础上固有的频谱图属性，允许更积极的，详细的简化。为了使有效的视觉探索所产生的光谱稀疏图，我们实现谱聚类和边缘捆绑。我们的框架不依赖于特定的图形布局，可以集成到不同的图形绘制算法。我们用不同大小和特征的公开图形数据进行实验，以证明我们方法的效率和有效性。为了进一步验证我们的解决方案，我们定量比较我们的方法对不同的图形简化解决方案，使用代理质量度量和统计特性的图形。(C)2020爱思唯尔有限公司保留所有权利。
We present a novel spectrum-preserving sparsification algorithm for visualizing big graph data. Although spectral methods have many advantages, the high memory and computation costs due to the involved Laplacian eigenvalue problems could immediately hinder their applications in big graph analytics. In this paper, we introduce a practically efficient, nearly-linear time spectral sparsification algorithm for tackling real-world big graph data. Besides spectral sparsification, we further propose a node reduction scheme based on intrinsic spectral graph properties to allow more aggressive, level-of-detail simplification. To enable effective visual exploration of the resulting spectrally sparsified graphs, we implement spectral clustering and edge bundling. Our framework does not depend on a particular graph layout and can be integrated into different graph drawing algorithms. We experiment with publicly available graph data of different sizes and characteristics to demonstrate the efficiency and effectiveness of our approach. To further verify our solution, we quantitatively compare our method against different graph simplification solutions using a proxy quality metric and statistical properties of the graphs. (C) 2020 Elsevier Ltd. All rights reserved.