论文标题
边缘流中的大型非常密集的子图
Large Very Dense Subgraphs in a Stream of Edges
论文作者
论文摘要
我们研究了一个具有$ n $ nodes和$ m $边缘的社交图中的大型非常密集的子图的检测和重建，当图表遵循功率法律分布时，当$ m = o（n。\ log n）$时，该图表遵循功率法律分布。如果子图$ s $具有$ω（| s |^2）$边缘，则非常密集。我们用大小$ k = o（\ sqrt {n}。\ log n）$的储层均匀采样边缘。我们的检测算法检查储层是否具有巨大组件。我们表明，如果该图包含一个非常密集的子图$ω（\ sqrt {n}）$，那么检测算法几乎肯定是正确的。另一方面，遵循功率法律分布的随机图几乎肯定没有很大的非常密集的子图，并且检测算法几乎肯定是正确的。我们定义了一个随机图的新模型，该模型遵循功率法分布并具有大量密集的子图。然后，我们表明，在这类随机图上，我们可以以很高的概率重建非常密集的子图的良好近似值。我们将这些结果推广到通过在边缘流中滑动窗口定义的动态图。
We study the detection and the reconstruction of a large very dense subgraph in a social graph with $n$ nodes and $m$ edges given as a stream of edges, when the graph follows a power law degree distribution, in the regime when $m=O(n. \log n)$. A subgraph $S$ is very dense if it has $Ω(|S|^2)$ edges. We uniformly sample the edges with a Reservoir of size $k=O(\sqrt{n}.\log n)$. Our detection algorithm checks whether the Reservoir has a giant component. We show that if the graph contains a very dense subgraph of size $Ω(\sqrt{n})$, then the detection algorithm is almost surely correct. On the other hand, a random graph that follows a power law degree distribution almost surely has no large very dense subgraph, and the detection algorithm is almost surely correct. We define a new model of random graphs which follow a power law degree distribution and have large very dense subgraphs. We then show that on this class of random graphs we can reconstruct a good approximation of the very dense subgraph with high probability. We generalize these results to dynamic graphs defined by sliding windows in a stream of edges.
