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

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

反例

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

1. 从\(V\)取出样本集合\(S\)
2. \(S_i \gets S \cap B_i\)
3. \(\rho_i \gets \frac{S_i}{S}\)
4. 返回\(\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 \leq (1+\beta)^{a}\And (1+\beta)^{b-1} < n-3 \leq (1+\beta)^{b}\)。我们记这两个桶分别为\(B_a,B_b\)，于是\(|B_a| = n-3,|B_b| = 3\)。当\(n\)特别大而抽样的数量特别小的时候，很有可能没有抽样到\(B_b\)中的元素，而这个桶中的元素的度都很大，所以对结果的影响也会很大，最坏的情况下，这个桶中的元素一个也没有抽到，结果大约为\(3\)，而真实情况下平均度大约为\(6\)，这样一来误差就太大了。道理就是这么个道理，而且这里举出的例子还不是最坏的情况。

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

改进算法

对于较小的桶的\(\rho_i\)的，并且假定一个\(\bar{d}\)的一个下届\(\alpha\)。

1. 从\(V\)中抽取样本\(S\)
2. \(S_i \gets S \cap B_i\)
3. \(\boldsymbol{for}\ i \in \{0,\dots,t-1\}\ \boldsymbol{do}\)
   1. \(\boldsymbol{if}\ |S_i| \geq \theta_\rho\ \boldsymbol{then}\)
   2. \(\rho_i \gets \frac{|S_i|}{|S|}\)
   3. \(\boldsymbol{else}\)
      1. \(\rho_i\gets 0\)
4. \(\boldsymbol{return}\ \hat{\bar{d} } = \sum_{i=0}^{t-1}\rho_i(1+\beta)^{i}\)

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

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

1. \(\beta = \frac{\epsilon}{4}\)
2. \(|S| = \Theta(\sqrt{\frac{n}{\alpha} }\cdot poly(log\ n,1/\epsilon))\)
3. \(t = \left \lceil log_{(1+\beta)}n \right \rceil + 1\)
4. \(\theta_{\rho} = \frac{1}{t}\sqrt{\frac{3}{8}\cdot\frac{\epsilon\alpha}{n} }|S|\)

评价

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