大数据 | 大数据基础--算法之亚线性时间算法：计算图的平均度算法二

网页版：http://burningcloud.cn/article/120/index.html 亲爱的读者朋友大家晚上好，上次我们分析了计算平均度的第一个估计算法，简而言之就是先分桶，然后估计桶的大小。然而该算法在特定的情境下表现非常不好。这次，我们从一个反例开始。

反例

举反例之前先来简单回顾一下上个算法的内容。

从$V$取出样本集合$S$$S_i\leftarrow S\cap B_i$${\rho }_i\leftarrow \frac{S_i}{S}$返回$\hat{\bar{d}}={\sum }_{i=0}^{t-1}{\rho }_i(1+\beta {)}^i$

这样的算法，对于较小的$|B_i|$的估计会很差，比如一个完全二分图$K_{3,n-3}$，有$3$个节点度为$n-3$，$n-3$个节点度为$3$，按照上面的算法，应当存在$a$和$b$，使得$(1+\beta {)}^{a-1}<3\le (1+\beta {)}^a\&(1+\beta {)}^{b-1}<n-3\le (1+\beta {)}^b$。我们记这两个桶分别为$B_a,B_b$，于是$|B_a|=n-3,|B_b|=3$。当$n$特别大而抽样的数量特别小的时候，很有可能没有抽样到$B_b$中的元素，而这个桶中的元素的度都很大，所以对结果的影响也会很大，最坏的情况下，这个桶中的元素一个也没有抽到，结果大约为$3$，而真实情况下平均度大约为$6$，这样一来误差就太大了。道理就是这么个道理，而且这里举出的例子还不是最坏的情况。

接下来提出的改进算法并不能完全解决这个问题，但是可以将原算法改造成一个$(ϵ,\delta )$算法，并且将近似比控制在$2$。

改进算法

对于较小的桶的${\rho }_i$的，并且假定一个$\bar{d}$的一个下届$\alpha$。

从$V$中抽取样本$S$$S_i\leftarrow S\cap B_i$$\mathbf{f}\mathbf{o}\mathbf{r}i\in \{0,\dots ,t-1\}\mathbf{d}\mathbf{o}$ $\mathbf{i}\mathbf{f}|S_i|\ge {\theta }_{\rho }\mathbf{t}\mathbf{h}\mathbf{e}\mathbf{n}$${\rho }_i\leftarrow \frac{|S_i|}{|S|}$$\mathbf{e}\mathbf{l}\mathbf{s}\mathbf{e}$ ${\rho }_i\leftarrow 0$ $\mathbf{r}\mathbf{e}\mathbf{t}\mathbf{u}\mathbf{r}\mathbf{n}\hat{\bar{d}}={\sum }_{i=0}^{t-1}{\rho }_i(1+\beta {)}^i$

我们将算法的结果调整为以$2/3$的概率有$(0.5-ϵ)\bar{d}<\hat{\bar{d}}<(1+ϵ)\bar{d}$。

这里给出一组参数，使得能够满足上述结果：

$\beta =\frac{ϵ}{4}$$|S|=\Theta (\sqrt{\frac{n}{\alpha }}\cdot poly(logn,1/ϵ))$$t=\lceil lo{g}_{(1+\beta )}n\rceil +1$${\theta }_{\rho }=\frac{1}{t}\sqrt{\frac{3}{8}\cdot \frac{ϵ\alpha }{n}}|S|$

评价

这个算法并不能彻底解决上述问题，但是基于此算法的改进却能够做到这一点，这些改进的方法将会在接下里的文章中介绍，敬请期待。