面向复杂网络的图稀疏算法综述

大规模数据下复杂网络的算法分析面临复杂度高的挑战,为此引入图稀疏的思想,在保持原始图性质的情况下以一定的精度在稀疏图上实现了高效的算法分析。图稀疏算法是一种保留顶点、对边稀疏采样的方法。按照相应算法分析所需要的原始图性质,提出图稀疏的边度量方式。文中系统回顾了4种边度量下的图稀疏采样方法:生成图稀疏、边连通图稀疏、聚类图稀疏、边传播性图稀疏,归纳了不同边度量方式下图稀疏的优缺点和适应性,并进一步讨论了动态图流稀疏化的最新研究进展。最后,总结了图稀疏领域有待解决的问题并展望了未来的研究方向。

Survey of Graph Sparsification Algorithms for Complex Networks

With the increasing of data scale,traditional graph algorithms confront the challenge of excessive complexity.The idea of graph sparse was introduced into algorithm,and analytical algorithm was realized efficiently on the sparse graph while preserving the original property with certain accuracy precision.Graph sparsity algorithm is a sampling method which preserves the original vertexes and sparses the edges.In this paper,the latest progresses of graph sparse algorithm were reviewed from four aspects,such as sparse spanning algorithm,edge connectivity sparse,clustering sparse and influence propagation sparse.The advantages and disadvantages of the graph sparse algorithms and the adaptability were summarized in different edge metrics.In addition,dynamic graph streaming sparse methods were analyzed.Finally,several important problems were outlined and future research directions in the field of sparse complex network were prospected.