论文标题
在均匀时间内均匀地对边缘采样
Sampling an Edge Uniformly in Sublinear Time
论文作者
论文摘要
Sublrinear算法的区域最近引起了很多关注。在这种情况下，必须为输入选择特定的访问模型，因为该算法没有时间预处理，甚至没有时间查看整个输入。一个基本问题仍然是关于图形的两个通用模型之间关系的开放 - 如果有或不访问“随机边缘”查询 - 即是否可以在模型中随机均匀地采样边缘，而无需访问随机边缘查询。 在本文中，我们积极回答这个问题。具体来说，我们给出了一种算法解决此问题，该问题在预期的时间$ o（\ frac {n} {\ sqrt {m}}} \ log n）$中运行。这只是一个比对数因子慢，比[5]中给出的下限慢。我们的算法使用[7]中的算法，我们以更仔细的方式分析了算法，从而在总体图中提高了更好的界限。我们还展示了在预期的时间$ o（\ frac {n} {\ sqrt {m}} \ log \ frac {1}ε）$中的预期时间$ o（\ frac {n} {\ frac {n} {\ frac {n} {\ frac {1}ε）$中的样品均匀的方法，以改进以前已知的算法。 我们还注意到，来自足够接近统一的分布的采样边缘足以模拟使用随机边缘查询的sublinear算法，同时仅将算法的成功概率仅减少$ o（1）$。这允许使用可用于模拟随机边缘查询的简单算法。
The area of sublinear algorithms have recently received a lot of attention. In this setting, one has to choose specific access model for the input, as the algorithm does not have time to pre-process or even to see the whole input. A fundamental question remained open on the relationship between the two common models for graphs -- with and without access to the "random edge" query -- namely whether it is possible to sample an edge uniformly at random in the model without access to the random edge queries. In this paper, we answer this question positively. Specifically, we give an algorithm solving this problem that runs in expected time $O(\frac{n}{\sqrt{m}} \log n)$. This is only a logarithmic factor slower than the lower bound given in [5]. Our algorithm uses the algorithm from [7] which we analyze in a more careful way, leading to better bounds in general graphs. We also show a way to sample edges $ε$-close to uniform in expected time $O(\frac{n}{\sqrt{m}} \log \frac{1}ε)$, improving upon the best previously known algorithm. We also note that sampling edges from a distribution sufficiently close to uniform is sufficient to be able to simulate sublinear algorithms that use the random edge queries while decreasing the success probability of the algorithm only by $o(1)$. This allows for a much simpler algorithm that can be used to emulate random edge queries.
