大图采样方法综述

A Survey of Large Graph Sampling Techniques

大图采样是常用的网络图简化方法,可显著降低大图数据的规模.文中从随机图采样、特征驱动的大图采样方法、大图采样的评估指标和大图采样方法的应用4个角度进行综述.首先介绍随机点、随机边和随机游走的随机图采样方法;然后论述拓扑结构、社区结构、动态网络关联和语义关联特征驱动的大图采样方法;再介绍拓扑结构、视觉感知和特征驱动的大图采样指标;最后介绍了大图采样方法在社交网络、地理交通、生物医学和深度学习等领域的应用,并展望了该方法的发展前景.

As a common method for simplifying network graphs,large graph sampling can reduce the size of large graph data significantly.In this paper,related works are summarized from the following perspectives:random graph sampling techniques,feature-driven large graph sampling techniques,evaluation metrics of large graph sampling and applications of large graph sampling technique.Firstly,random graph sampling is categorized into three types,including random node,random edge,and random walk graph sampling.Secondly,the feature-driven large graph sampling techniques are discussed,including topology-preserving,community structure-preserving,dynamic network association and semantic association feature-driven large graph sampling.Thirdly,the evaluation metrics of large graph sampling techniques are introduced,including topological metrics,visual perception metrics and feature-driven metrics.Finally,the applications of large graph sampling technique in social networks,geographic traffic,biomedical and deep learning are summarized,and the development of large graph sampling method is prospected.