article20201011

Posted on 2021-06-13 Edited on 2021-06-14

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

亲爱的读者朋友大家晚上好，上次我们分析了计算平均度的第二个估计算法，简而言之就是在算法一的基础上为小桶定一个下届。我们继续对算法二进行优化，这次我们期望获得一个近似比为$1+\epsilon$的算法。

算法改进的思想

我们将算法出现的误差归结到边上，让我们来看看究竟是哪些边导致了这样的错误。将节点分为$U,V/U$两部分，其中$U$是度数较小的节点，$V/U$是度数较大的节点，$E(U,V/U)$表示连接两个集合的边的集合。于是，我们断言出现误差就是因为$E(U,V/U)$中的边我们只计算了一次，关于这一点我们回忆一下之前举的例子就很好理解了。于是我们只要找到每次抽样的时候这部分的边的比例就可以了。

优化分析

定义：$rnq(v)$表示从$v$的邻居节点中随机选取一个节点，$E_i$表示桶$B_i$中的度数总和。

问题1：对于每个桶$B_i$中的边，求出其中属于$E(U,V/U)$中的边的比例$\Delta_i$。

解问题1：重复如下操作$m$次，随机选择$u \in B_i$，令$u' \gets rnq(u)$。如果$(u,u') \in E(V/U,V/U),\delta_j = 0$；否则也就是$(u,u') \in E(V/U,U),\delta_j = 1$。最后$\Delta_i \gets \frac{\sum{\delta_j} }{m}$。

问题2：$T_i$为真实情况下，$B_i$中属于$E(U,V/U)$的边的数量，估计$T_i$的上下界。

解问题2：对于桶$B_i $，我们有公式：$ E[_i] $，对此公式进行转换，得到第二个公式：${|B_i|(1 + )^{i-1} }E[_i] T_i |B_i|(1 + )^{i}E[_i]$

改进算法

以上，解决前面两个问题之后，利用$E[\Delta_i]$的$1+\epsilon$估计，可以得到$\Delta_i\rho_i(1+\beta)^i$是$\frac{T_i}{n}$的$(1+\epsilon)(1+\beta)$估计。于是乎，经过改造的算法如下所示：

从$V$中抽取样本$S$，$|S| = \tilde{O}(\frac{L}{\rho\epsilon^2}),L=poly(\frac{log\ n}{\epsilon}),\rho = \frac{1}{t}\sqrt{\frac{\epsilon}{4}\cdot \frac{\alpha}{n} }$
$S_i \gets S \cap B_i$
$\boldsymbol{for}\ i \in \{0,\dots,t-1\}\ \boldsymbol{do}$
1. $\boldsymbol{if}\ |S_i| \geq \theta_\rho\ \boldsymbol{then}$
  1. $\rho_i \gets \frac{|S_i|}{|S|}$
  2. $estimate\ \Delta_i$
2. $\boldsymbol{else}$
  1. $\rho_i\gets 0$
$\boldsymbol{return}\ \hat{\bar{d} } = \sum_{i=0}^{t-1}(1+\Delta_i)\rho_i(1+\beta)^{i}$

评价

弥补了一部分误差，近似比为$1+$。