Catching the Head, Tail, and Everything in Between: A Streaming Algorithm for the Degree Distribution
Catching the Head, Tail, and Everything in Between: A Streaming Algorithm for the Degree Distribution
复制标题
抓住头、尾以及中间的一切：度分布的流算法
DOI：
10.1109/icdm.2015.47
复制
发表时间：
2015
期刊：
影响因子：
--
通讯作者：
A. Mcgregor
中科院分区：
文献类型：
--
作者：
O. Simpson;C. Seshadhri;A. Mcgregor
度分布是现实世界图最基本的性质之一。在许多领域中，人们已经广泛地观察到，图通常具有尾部或无标度的度分布。虽然平均阶数通常很小，但方差很高，并且在所有比例上都有度数的顶点。我们主要研究存储空间较小的大型流图的度分布逼近问题。我们设计了一个算法Headail，它的主要新奇之处是使用截断几何随机变量的新的不频繁度估计。并对其进行了数学分析，证明了它在实际应用中具有良好的性能。我们可以用不到1%的存储空间处理数百万条边的流，并获得度分布中所有尺度的极其精确的近似。我们还引入了拖尾直方图之间相对Hausdorff距离的新概念。现有的分布之间距离的概念是不适用的，因为它们忽略了尾部不常见的度数。相对Hausdorff距离衡量了所有尺度上的偏差，是比较程度分布的更合适的距离。通过跟踪这一新的衡量标准，我们能够为头部尾部的收敛提供强有力的经验证据。
The degree distribution is one of the most fundamental graph properties of interest for real-world graphs. It has been widely observed in numerous domains that graphs typically have a tailed or scale-free degree distribution. While the average degree is usually quite small, the variance is quite high and there are vertices with degrees at all scales. We focus on the problem of approximating the degree distribution of a large streaming graph, with small storage. We design an algorithm headtail, whose main novelty is a new estimator of infrequent degrees using truncated geometric random variables. We give a mathematical analysis of headtail and show that it has excellent behavior in practice. We can process streams will millions of edges with storage less than 1% and get extremely accurate approximations for all scales in the degree distribution. We also introduce a new notion of Relative Hausdorff distance between tailed histograms. Existing notions of distances between distributions are not suitable, since they ignore infrequent degrees in the tail. The Relative Hausdorff distance measures deviations at all scales, and is a more suitable distance for comparing degree distributions. By tracking this new measure, we are able to give strong empirical evidence of the convergence of headtail.