图稀疏算法研究进展

作为加速大规模图分析的技术,图稀疏算法在尽可能保留原始图性质的基础上实现图的稀疏化存储,从而加速大规模图的分析和处理。图稀疏算法是一种顶点全保存边稀疏的采样方法,可概括为四种边度量下的图稀疏采样方法:基于距离相似性的生成图稀疏算法、基于边连通的割稀疏和谱稀疏算法、基于社会网络的聚类稀疏和影响力传播的稀疏算法。本文归纳了这些算法的优缺点和适应性,最后展望了大规模图稀疏化尚未探索的有意义的研究课题。