Estimating and sampling graphs with multidimensional random walks
Estimating and sampling graphs with multidimensional random walks
复制标题
DOI：
10.1145/1879141.1879192
复制
发表时间：
2010-02
期刊：
影响因子：
--
通讯作者：
Bruno Ribeiro;D. Towsley
中科院分区：
文献类型：
--
作者：
Bruno Ribeiro;D. Towsley
通过采样估计大型图的特征是复杂网络研究的重要组成部分。目前的采样方法，如（独立）随机顶点和随机游动是有用的，但有缺点。随机顶点采样可能需要太多的资源（时间、带宽或金钱）。随机游走，通常需要较少的资源，每个样本，可能会遭受大的估计误差，在断开连接或松散连接的图形。在这项工作中，我们提出了一个新的m维随机游走，使用m个依赖的随机游走。我们表明，所提出的采样方法，我们称之为前沿采样，具有良好的采样性能的一个定期的随机游走。同时，我们在大的真实的世界图上的模拟表明，在存在断开或松散连接的组件，前沿采样表现出较低的估计误差比定期随机游动。我们还表明，前沿采样比随机顶点采样更适合于对图的度分布的尾部进行采样。
Estimating characteristics of large graphs via sampling is a vital part of the study of complex networks. Current sampling methods such as (independent) random vertex and random walks are useful but have drawbacks. Random vertex sampling may require too many resources (time, bandwidth, or money). Random walks, which normally require fewer resources per sample, can suffer from large estimation errors in the presence of disconnected or loosely connected graphs. In this work we propose a new m-dimensional random walk that uses m dependent random walkers. We show that the proposed sampling method, which we call Frontier sampling, exhibits all of the nice sampling properties of a regular random walk. At the same time, our simulations over large real world graphs show that, in the presence of disconnected or loosely connected components, Frontier sampling exhibits lower estimation errors than regular random walks. We also show that Frontier sampling is more suitable than random vertex sampling to sample the tail of the degree distribution of the graph.