Sampling Connected Induced Subgraphs Uniformly at Random
Sampling Connected Induced Subgraphs Uniformly at Random
复制标题
DOI：
10.1007/978-3-642-31235-9_13
复制
发表时间：
2012-06
期刊：
影响因子：
--
通讯作者：
Xuesong Lu;S. Bressan
中科院分区：
文献类型：
--
作者：
Xuesong Lu;S. Bressan
现代应用程序的一个反复出现的挑战是处理大图形。生成较小大小的代表性样本的能力不仅有助于规避可伸缩性问题，而且本身也适用于统计分析和其他数据挖掘任务。为达到这一目的，必须设计出适当的抽样技术。在本文中，我们对图的连通子图的均匀随机抽样感兴趣。我们要求样本包含规定数量的顶点。利用拒绝抽样、随机游动和马尔可夫链蒙特卡罗三种不同的技术，设计、提出并讨论了几种算法。我们对这些算法的性能进行了实证评估和比较。我们证明了它们是有效和高效的，但存在一个权衡，这取决于图的密度和样本大小。我们提出了一种新的算法，称为邻库抽样(NRS)，它非常成功地实现了有效性和效率之间的权衡。
A recurrent challenge for modern applications is the processing of large graphs. The ability to generate representative samples of smaller size is useful not only to circumvent scalability issues but also, per se, for statistical analysis and other data mining tasks. For such purposes adequate sampling techniques must be devised. We are interested, in this paper, in the uniform random sampling of a connected subgraph from a graph. We require that the sample contains a prescribed number of vertices. The sampled graph is the corresponding induced graph.We devise, present and discuss several algorithms that leverage three different techniques: Rejection Sampling, Random Walk and Markov Chain Monte Carlo. We empirically evaluate and compare the performance of the algorithms. We show that they are effective and efficient but that there is a trade-off, which depends on the density of the graphs and the sample size. We propose one novel algorithm, which we call Neighbour Reservoir Sampling (NRS), that very successfully realizes the trade-off between effectiveness and efficiency.