Graphlets(图元)是指大规模网络中那些节点数目较少的连通诱导子图,在社交网络和生物信息学等领域有着广泛的应用。随着graphlets节点数目的增多,graphlets的种类数增长迅速且结构变化复杂,快速估计大规模社交网络中所有graphlets的频率是一项挑战。由于精确计数的计算成本较高,目前大多用基于随机游走的采样算法来近似估计graphlets的频率,而这些算法大多只能估计不超过5个节点的graphlets,很难扩展到高阶graphlets。因此,设计一个估计精度高且能扩展到估计高阶graphlets频率的采样算法具有重要的研究意义。本文中,我们提出了一种基于最大公共子结构感知的社交网络graphlets采样算法 CSRW(Common Substructure based graphlets sampling via Random Walk)。给定graphlets的节点数k,CSRW首先感知并游走一个所有k-graphlets都共享的最大公共子结构2-path((?)),再从多个节点的邻居中随机生成下一跳节点,直至得到k-graphlets样本,从而以统一的方式估计所有类型k-graphlets的频率。此外,当graphlets节点数目k增加时,k-graphlets呈现出更复杂的拓扑结构。那些结构更稠密的graphlets在真实社交网络中很少出现,采样相对困难。为此,本文提出了一种基于两种子结构感知调和的社交网络graphlets采样算法CSRW2,以提升那些较少出现、结构更稠密的graphlets的估计精确度。给定阶数k(k=4,5),CSRW2首先分别采样子结构(k-1)-path和3-star((?)),再扩展得到两种样本,然后用比例放大法调和两种样本,从而可以适应graphlets结构的复杂变化并高效估计graphlets的频率。综合性实验表明,CSRW能统一地估计所有k-graphlets类型,其算法精确性优于当前代表性算法SRW2CSS和WRW;6,7-graphlets的估计结果也证明了CSRW的可扩展性。CSRW2也以统一的框架估计所有k-graphlets的频率(k=4,5),且相对CSRW来说,CSRW2更有利于估计那些出现较少、结构较稠密的graphlets。