介绍
提出了一种根据图的度和聚类系数来指导图采样。现有的采样算法可以将原图缩小到 10%，但是，如果再进一步缩小就会对子图的结构造成破坏。
工作的主要特点
- 将样本量减少到1%以下，同时保留原始图的关键属性，如原图的度、聚类系数、路径长度和直径。以及，通过保留图的度混合模式（分类性）和模块性来保留图的整体结构。
- 将图采样分为两步。第一步，提取一个子图，其中包含所需数量的节点，但有额外的边。第二步，移除一些额外的边，让子图更接近原始图。
- 提出了一种去除边对图的聚类系数影响的近似方法，并运用这个方法去除掉额外的边。
- 只需要访问图的局部部分，而不需要访问整个图去进行均匀采样。
背景
Metropolis hastings random walk（MHRW）方法在捕捉图的度分布方面非常有效。
Hardiman 等人使用随机游走挖掘一部分节点去评估图的平均聚类系数，准确度很好。
指导采样
Guided Sampling (GS) 算法分为两个阶段。
第一个阶段
使用 modified depth first sampling（ModDFS）。在 ModDFS 中，为了可以从未采样的邻居节点中选取最高度的节点，调整了深度优先采样 （Depth First Sampling）。
第二个阶段
从子图中去除额外的边，以达到所需的度和聚类系数。不是随意删除某条边，而是计算边的权重（用来估计删除这条边时对图的平均聚类系数的影响）。然后，根据该权重指导对图的修剪，从而得到一个好的子图。
边的权重
聚类系数 clustering coefficient
局部聚类系数 \(CC_v\) ：表示节点 v 的邻居节点的连接性。
\[CC_v={\frac{2*l_v}{d_v*(d_v-1)}} \]其中 \(l_v\) 表示节点 \(v\) 的邻居节点之间存在的边数，\(d_v\) 表示节点 \(v\) 的邻居节点个数。
如果我去掉节点 \(v\) 邻居节点之间的一条边，那么 \(CC_v\) 就算降低，因为此时节点 \(v\) 的度没有改变，即 \(l_v\) 不变，而 \(d_v\) 减小。
节点对边的权重贡献
节点通过保持自身度恒定的简单直观为一对相邻节点之间的边赋予权重。在封闭的三元组 \(v、u、w\) 中，节点 \(v\)赋予边 \(e(u, w)\) 权重。
\[W_{e(u,w)}={\frac{2}{d_v*(d_v-1)}} \]边的权重
但是，计算对图的平均聚类系数的影响非常具有挑战性，因为删除一条边可能会干扰图中的许多三元组。
最后，边的权重是所有使用位于该边末端的节点构成紧密的三元组的权重之和。所以，边 \(e(u，w)\) 的权重计算公式：
\[W_{e(u,w)}=\sum_{i=1}^{k}{\frac{2}{d_i*(d_i-1)}} \]其中，节点 \(u\) 和节点 \(w\) 可以与节点集合 \({v_1，v_1，v_3,\ldots,v_k}\) 构成三元组，\(d_i\) 就是节点 \(v_i\) 的度。
权重高的边对图的平均聚类系数影响很大。原因如下：
- 移除权重高的边会降低许多节点的局部聚类系数（\(CC_v\) 中的 \(l_v\) 减小），从而图的平均聚类系数也会随之下降。
- 度低的节点对边的权重贡献更大（分母小），当我们移除高权重的边时，度比较低的节点的局部聚类系数会显著降低，导致图的平均聚类系数急剧下降。
举例
该图的平均聚类系数为 0.66。
节点 1 的度为 3，它赋予边 \(e(2，3)\) 和 \(e(3，4)\) 权重为 0.33。即 \({\frac{2}{3*2}}=0.33\)
节点 6 的度为 5，它赋予边 \(e(2，5)\)、 \(e(2，3)\)、 \(e(3，7)\) 和 \(e(7，9)\) 权重为 0.1。即 \({\frac{2}{5*4}}=0.1\)
因此可以得出边的总权重，例如 \(e(2，3)\) 的权重就是 \(0.33+0.1=0.43\)。
如果我们移除权重为 0.1 的 \(e(2，5)\)，图的平均聚类系数会下降到 0.63。而移除权重为 1.1 的 \(e(4，7)\)，图的平均聚类系数会下降到 0.51。因此，移除权重高的边，会使图的平均聚类系数下降更快。
GS 算法
输入
原图 G、原图的度和聚类系数的目标值 \(d_{org}\) 和 \(cc_{org}\) 、采样比例 \(\phi\)
输出
一个子图，子图中节点数 = 原始图中节点数 * \(\phi\)
初始化
子图节点数 \(V_s=0\)，子图边数 \(E_s=0\)
采样、诱导、边的权重
- 使用 ModDFS 算法得到 \(V_s\) 节点子集
- 通过给 \(V_s\) 子节点集添加边得到子图 \(G_s\)
- 计算 \(E_s\) 边子集中每条边的权重
- 将边子集中的边按照权重降序进行排列
- 计算 \(E_s\) 边子集中额外边的数量 \(e_{extra}=\mid{E_s}\mid-\frac{d_{org}*\mid{V_s}\mid}{2}\)
- 计算 \(G_s\) 的平均聚类系数 \(cc_{init}\)
移除额外的边
- 删除边的数量 \(e_{del}=0\)
- 边的比例 \(e_{ratio}=0\)
- 当前子图的聚类系数 \(cc_{curr}=cc_{init}\)
- 聚类系数比例 \(cc_{ratio}=\frac{cc_{org}}{cc_{curr}}\)
- 斜率 \(slope=\frac{\frac{cc_{curr}}{cc_{org}}-1}{e_{extra}}\)
- 期望的聚类系数 \(cc_{exp}=cc_{init}-(slope*e_{del}*cc_{org})\)
- 如果删除边的数量 \(e_{del}\) 小于额外边的数量 \(e_{extra}\)，就一直重复做 15 - 25 的步骤
- 取降序边集处于中间位置的下标， \(mid=\frac{\mid{E_s}\mid}{2}\)
- 如果当前聚类系数 \(cc_{curr}\) 大于期望聚类系数 \(cc_{exp}\)，并且也大于原始图聚类系数 \(cc_{org}\)，则执行 16
- 选择一条权重高的边 \(index=mid*cc_{ratio}*e_{ratio}\)，（当需要极速降低聚类系数时）
- 否则
- 选择一条权重低的边 \(index=mid+mid*e_{ratio}\)，（当需要微调来遵循假设的线，并最终达到目标值时）
- if 部分结束
- 从边子集 \(e_s\) 删除 \(index\) 这条边（注意：只有当这条边的两端节点的度大于一的时候，才删除边缘，这样才能确保没有孤立节点，保证子图是连通的）
- 删除边的数量 \(e_{del}\) 加一
- 删除 \(index\) 边之后重新计算此时子图 \(G_s\) 的聚类系数 \(cc_{curr}\)
- 更新聚类系数比例 \(cc_{ratio}=\frac{cc_{org}}{cc_{curr}}\)
- 更新边的比例 \(e_{ratio}=\frac{e_{extra}-e_{del}}{e_{extra}}\)
- 更新期望聚类系数 \(cc_{exp}=cc_{init}-(slope*e_{del}*cc_{org})\)
- 结束
时间复杂度
在估计原始图的度和聚类系数的时候，使用随机游走 Random Walk 和它的变体。随机游走访问 \(n_s\) 个节点的时间上界是 \(\frac{4}{27}n_s^3+O(n_s^3)\) 。所以估计原始图的度和聚类系数的时间复杂度为 \(2*O(n_s^3)\) 。
在 GS 第一阶段（用常数 C 表示第一阶段总体时间复杂度）：
- ModDFS 算法的时间复杂度为 \(O(n_s)\)
- 计算边的权重时间复杂度为 \(O(n_s^3)\)
- 对边进行排序的时间复杂度为 \(O(m_slog(m_s))\)
- 计算聚类系数的时间复杂度为 \(O(n_s^3)\)
在 GS 第二阶段的时间复杂度 \(O(n_s^2m_s)\) ，其中 \(m_s\) 是子图中边的数量：
- 最差情况，计算删除某条边之后图的聚类系数的时间复杂度为 \(O(n_s^2)\)
结论：GS 算法总的时间复杂度为 \(O(n_s^3)+O(n_s^2m_s)+C\)，其中 \(n_s\) 和 \(m_s\) 分别是子图中的节点数和边数，C 是常数。
评估准则
点统计 Point Statistics
点统计是一种单值统计信息。
将采样分数 \(\phi\) 从 0.001 变为 0.01，并将属性 \(\Theta\) 的缩放比定义为子图中该属性的值 \(\Theta_S\) 与原图中该属性的值 \(\Theta_A\)的比率：
\[Scaling\ Ratio=\frac{\Theta_S}{\Theta_A} \]分布 Distributions
分布是一种多值统计，表示了图中一个属性的分布。例如，度分布表示度大于或小于特定值的节点的比例。
我们绘制了在采样分数 \(\phi=0.001\) 下子图的度、聚类系数和路径长度的经验累积分布函数 empirical cumulative distribution function（ECDF）。
均方根误差 Root Mean Square Error
用来衡量子图 \(G_s\) 离原图 \(G\) 的差距。对于图的平均度等标量，通常使用均方根误差来衡量。
\[RMSE=\sqrt{\frac{1}{n}\sum_{1}^{n}{(\Theta_S-\Theta_A)^2}} \]JS 散度 Jensen–Shannon Distance
JSD 计算的是两个概率分布的相似性。
\[D_{JS}(P\mid{\mid}Q)=\frac{1}{2}D_{KL}(P\mid{\mid}M)+\frac{1}{2}D_{KL}(Q\mid{\mid}M) \]其中，\(D_JS\) 是 Jensen–Shannon 散度，\(D_KL\) 是 Kullback-Leibler 散度。\(P\) 和 \(Q\) 是两个概率分布函数，\(M=\frac{1}{2}(P+Q)\) 。
标签：系数,frac,权重,cc,Guided,large,graphs,聚类,节点 From： https://www.cnblogs.com/fireonfire/p/16704816.html