随着互联网的快速发展，数据分析系统需要处理的图规模呈爆炸式增长，使得系统的计算能力和存储能力面临严峻挑战。高效低误差的抽样技术能有效缩减待处理数据集的规模，同时保留原有数据集的主要特征，可用于可视化、查询、分析和社交网络影响力估测等，因而成为解决该挑战的重要途径。面向图的抽样技术分为两类：一类是通过产生边集样本来估测图特征的抽样技术，称为面向图边集的抽样技术；另一类是通过产生顶点集样本估测图特征的抽样技术，称为面向图顶点集的抽样技术。然而，现有的图抽样技术估测目标单一，且存在估测误差和开销大的问题，不能满足实际应用需求。针对这些问题，本文开展了以下创新性研究工作。
　　提出了基于双采样机制的蓄水池抽样技术T-Sample(Triangle-based Reservoir Sampling)。该技术旨在解决现有面向图边集的抽样技术不能同时准确估测图中三角形总量和顶点度特征的问题。T-Sample中的双采样机制是指联合统一和非统一的蓄水池抽样技术共同产生边集样本。其中统一蓄水池抽样算法在时空开销小的前提下能准确估测三角形总量这一重要的图结构特征，而非统一蓄水池抽样算法用于维持原图中重要的链接关系，进而能准确估测顶点的度这一重要的图结构特征。实验证明，相比现有面向图边集的抽样技术，T-Sample在估测图中三角形总量时，准确率可提高50%，估测方差可降低56%，并且可获取图中占比99%以上的顶点度种类。
　　提出了基于顶点团的随机游走抽样技术NCRW(Node Clique Random Walk)。该技术旨在解决现有面向图顶点集的抽样技术不能准确反映原图中顶点的多样性，同时估测图特征时误差大，而无法有效支撑图查询类应用的问题。现有随机游走抽样技术的核心步骤是从上一个样本点的邻居顶点获取下一个样本点，会频繁返回已抽样过的顶点，从而产生大量重复样本；又由于两个相邻样本互为邻居顶点，导致大量的相似样本。与现有随机游走抽样技术不同的是：NCRW采用从一个顶点团(顶点的最大完全子图)随机游走到另一个顶点团的方式遍历图。在遍历过程中，采用不返回策略避免产生重复样本，并通过扩大下一样本的选择空间来减少相似样本。因此，NCRW能获取没有重复且相似性少的样本，并且样本的实际分布与其期望分布相近。实验证明：在相同样本个数的情况下，相比现有的随机游走抽样技术， NCRW几乎不会产生重复样本且产生相似样本的比例下降10%以上，同时估测图的顶点度分布和聚集系数分布的平均误差分别降低10%和6.8%。
　　提出了基于两阶邻居域的抽样技术2-Hopper。该技术旨在解决现有随机游走抽样技术由于不能同时准确估测图中顶点的个体属性和社会属性，而无法有效支持图分析类应用的问题。2-Hopper重新规划顶点到两阶邻居之间的路径，以减少图中顶点间大量的冗余路径，从而避免产生大量的重复样本，同时又有利于获取和分析顶点的社会属性；另外，提出一种递归算法用于在抽样过程中估测顶点的社会属性。实验证明：2-Hopper不仅能准确估测个体属性和社会属性，并且至少有89.9%的样本可用于分析这两类属性，用于分析图特征的样本比例相比现有随机游走抽样技术可提高25%。
　　提出了双重随机游走抽样技术DRaWS(Dual Random Walk based Sampling)。该技术旨在解决现有随机游走技术的收敛时间长，且不能同时准确估测图中顶点和团的特征，而无法有效支撑社交网络影响力估测类应用的问题。图中有大量的由全链接关系的顶点构成的团，使得随机游走抽样技术在遍历时，很可能会陷入团中，从而增加抽样开销。另外，现有的抽样技术并不能区分顶点和团的抽样概率，导致不能准确估测这两类实体的特征。DRaWS利用图中顶点和团设计具有双重状态的步数机，进而反映顶点和团的不同抽样概率，同时利用图中的团构造超级结构缩短和减少抽样路径，以降低抽样开销。最后通过不同的抽样概率设计不同的估测算法以准确估测图中的这两类实体的结构特征。实验证明：DRaWS能减少抽样开销并提高估测准确度，相比现有的抽样技术，DRaWS估测的度和图中团特征的平均误差可分别降低26%和50%以上。