论文标题
通过边缘采样的本地访问稀疏连接的子图
Local Access to Sparse Connected Subgraphs Via Edge Sampling
论文作者
论文摘要
我们为局部计算密集图的稀疏连接子图的问题做出了一种方法。在这种情况下，给定一个连接图中的优势$ g =（v，e）$，算法本地决定其在稀疏连接子图$ g^* =（v，e^*）$中的会员资格，其中$ e^* \ subseteq e $ $ $ | e^* | = o（| e |）$。在处理大量图时，这种子图构造方法很有用，在图形的完整网络描述中读取不切实际。 虽然该领域的大多数先前结果都需要$ g $或$ | e'|的假设。 \ le（1+ε）| V | $对于某些$ε> 0 $，我们放松这些假设。给定一个常规图和参数$ t $，我们使用$ o（| v | t）$ edges使用$ \ wideTilde {o}（| e |/t）$ probes提供了$ o（| v | t）$边缘的会员查询。这是第一个在一般图上工作的算法，并允许其探针复杂性与所得子图中的边缘数量之间进行权衡。 我们通过以前在此问题中未使用的边缘稀疏技术动机来实现这一结果。我们认为，这些技术将激发该问题和相关问题的新算法。此外，我们描述了一种有效的方法，可以在$ g $的稀疏版本中访问任何节点的邻居设置，其中每个边缘都用一些I.I.D删除。可能性。
We contribute an approach to the problem of locally computing sparse connected subgraphs of dense graphs. In this setting, given an edge in a connected graph $G = (V, E)$, an algorithm locally decides its membership in a sparse connected subgraph $G^* = (V, E^*)$, where $E^* \subseteq E$ and $|E^*| = o(|E|)$. Such an approach to subgraph construction is useful when dealing with massive graphs, where reading in the graph's full network description is impractical. While most prior results in this area require assumptions on $G$ or that $|E'| \le (1+ε)|V|$ for some $ε> 0$, we relax these assumptions. Given a general graph and a parameter $T$, we provide membership queries to a subgraph with $O(|V|T)$ edges using $\widetilde{O}(|E|/T)$ probes. This is the first algorithm to work on general graphs and allow for a tradeoff between its probe complexity and the number of edges in the resulting subgraph. We achieve this result with ideas motivated from edge sparsification techniques that were previously unused in this problem. We believe these techniques will motivate new algorithms for this problem and related ones. Additionally, we describe an efficient method to access any node's neighbor set in a sparsified version of $G$ where each edge is deleted with some i.i.d. probability.
