标题： 网络采样：从静态到流图 显示英文标题

标题： Network Sampling: From Static to Streaming Graphs

摘要： 网络采样对于分析社会网络、信息网络和生物网络至关重要。由于许多真实世界中的网络规模庞大，持续演化，和/或分布式的性质，网络结构通常被采样以促进研究。因此，更深入和全面地理解网络采样对于支持网络科学领域至关重要。本文中，我们通过强调不同的目标、感兴趣的总体和单位以及网络采样的方法类别，概述了网络采样的一个框架。此外，我们提出了网络采样方法的一系列计算模型，从基于静态域假设的传统研究模型到更适合流处理领域的更具挑战性的模型。我们设计了一组基于图归纳概念的采样方法，这些方法跨越了从静态到流处理的整个计算模型谱系，同时有效地保留了输入图的许多拓扑属性。此外，我们展示了如何针对三种主要的采样方法：节点采样、边采样和拓扑结构采样，修改传统的静态采样算法以适用于图流。我们的实验结果显示，我们提出的采样方法家族能够更准确地保留静态和流处理图的底层属性。最后，我们研究了网络采样算法对关系分类算法的参数估计和性能评估的影响。 显示英文摘要

摘要： Network sampling is integral to the analysis of social, information, and biological networks. Since many real-world networks are massive in size, continuously evolving, and/or distributed in nature, the network structure is often sampled in order to facilitate study. For these reasons, a more thorough and complete understanding of network sampling is critical to support the field of network science. In this paper, we outline a framework for the general problem of network sampling, by highlighting the different objectives, population and units of interest, and classes of network sampling methods. In addition, we propose a spectrum of computational models for network sampling methods, ranging from the traditionally studied model based on the assumption of a static domain to a more challenging model that is appropriate for streaming domains. We design a family of sampling methods based on the concept of graph induction that generalize across the full spectrum of computational models (from static to streaming) while efficiently preserving many of the topological properties of the input graphs. Furthermore, we demonstrate how traditional static sampling algorithms can be modified for graph streams for each of the three main classes of sampling methods: node, edge, and topology-based sampling. Our experimental results indicate that our proposed family of sampling methods more accurately preserves the underlying properties of the graph for both static and streaming graphs. Finally, we study the impact of network sampling algorithms on the parameter estimation and performance evaluation of relational classification algorithms.