图元(Graphlet)是大图中连通的诱导子图,因其广泛的应用吸引着众多研究者的关注。图元的统计量,即图元的数目和比例可以揭示出大图的某些特征,是研究复杂网络的一个很好的切入点。然而现实世界中的网络含有的图元数目巨大,通过穷举的方式获得其准确数量代价巨大,为了能够以较小的代价获取图元估计量,近年来有很多研究者通过采样的方式获得图元数量和比例的估算值。估算图元数量和比例的算法主要分为两类,一类是通过在超图上进行采样的方式,超图中的每一个状态是一个目标图元。这种方式虽然可以拓展到点数比较多的图元上面,但是其运行速度慢,精度低且一般只能估算图元的比例而不能估算图元的数量。另外一种常见的图元估算方法是直接在原图上进行采样,使用这种方式的采样一般先在原图中生成某种特定类型的树,利用采样到的树诱导出的子图作为样本。这种方式的优点是运行速度较快,精度较高,其缺点是只能对含有节点数目较少的图元进行估算,而难以拓展到节点数目较多的图元。本文在分析了以前算法的优缺点的基础上,提出了一种新的图元采样算法SSRW(Scalable subgraph Sampling via Random Walk)。在保持当前最好精度的情况下,顺利地将图元采样算法扩展到了高阶图元上面。SSRW算法的核心是一个十分灵活的子图采样算法,在采样过程中直接在大图上进行采样而不需要其他的辅助算法。从一个已知概率的起始点开始进行图元采样,在采样过程中新的节点从多个已生成的节点的邻居中产生。这种灵活的采样方式使得我们可以采样到目标图元集合中的所有类型的图元。我们还对SSRW进行了扩展,使其可以方便地估算混合图元统计量。同时,我们还对其进行了并行化,使得在相同时间内得到了 50倍数量的样本从而提高效率。而且还进一步提出了提高图元采样算法精度的方法。当我们对在线社交网络进行图元统计量挖掘时,因其具有限制性访问的特点我们无法得到整个网络的拓扑结构,我们将SSRW与当前针对在线社交网络的最新算法相结合,顺利地得到了5节点以上的图元估计量。所测试的6图元比例的估算误差都小于8.5%,大部分所测试的7图元比例的估算误差都小于10%。