BC tree-based spectral sampling for big complex network visualization
BC tree-based spectral sampling for big complex network visualization
复制标题
DOI：
10.1007/s41109-021-00405-3
复制
发表时间：
2021-08-21
影响因子：
2.2
通讯作者：
Ma, Kwan-Liu
中科院分区：
文献类型：
--
作者：
Hu, Jingming;Chu, Tuan Tran;Ma, Kwan-Liu
图采样方法已被用来降低大型复杂网络的规模和复杂性，用于图挖掘和可视化。然而，现有的图采样方法往往不能保持原始图的连通性和重要结构。本文介绍了一种新的基于图连通性的谱图采样分治方法，称为BC树(即将连通图分解成双连通分量)和谱稀疏。具体地，我们提出了两种方法，即通过计算每个连通分量的顶点和边的有效阻值来进行谱顶点抽样BC_SV和谱边缘抽样BC_SS。在此基础上，提出了基于图连通性的分布式谱稀疏算法DBC_SS和基于图连通性的分布式图绘制算法DBC_GD，旨在将基于连通性的图分解和分布式计算相结合，进一步提高谱稀疏和图绘制的运行效率。实验结果表明，BC_SV和BC_SS在保持相同采样质量的情况下，明显快于以往的谱图采样方法。与顺序方法相比，DBC_SS和DBC_GD获得了进一步显著的运行时间改进，并且DBC_GD进一步在质量度量方面比顺序图形绘制布局获得了显著改进。
Graph sampling methods have been used to reduce the size and complexity of big complex networks for graph mining and visualization. However, existing graph sampling methods often fail to preserve the connectivity and important structures of the original graph. This paper introduces a new divide and conquer approach to spectral graph sampling based on graph connectivity, called the BC Tree (i.e., decomposition of a connected graph into biconnected components) and spectral sparsification. Specifically, we present two methods, spectral vertex sampling BC_SV and spectral edge sampling BC_SS by computing effective resistance values of vertices and edges for each connected component. Furthermore, we present DBC_SS and DBC_GD, graph connectivity-based distributed algorithms for spectral sparsification and graph drawing respectively, aiming to further improve the runtime efficiency of spectral sparsification and graph drawing by integrating connectivity-based graph decomposition and distributed computing. Experimental results demonstrate that BC_SV and BC_SS are significantly faster than previous spectral graph sampling methods while preserving the same sampling quality. DBC_SS and DBC_GD obtain further significant runtime improvement over sequential approaches, and DBC_GD further achieves significant improvements in quality metrics over sequential graph drawing layouts.