伴随着社会网络平台的蓬勃发展,大量的用户交互信息能够研究用户之间的相互影响以及信息的传播模式。分析用户之间的影响力有助于分析用户角色和评估传播模型,而网络模体被认为是复杂网络的基本构造块,可以更好地从微观结构理解宏观结构的演化规律,所以模体挖掘是研究社会网络结构特性的重要手段。模体挖掘分为子图识别和模体度量两个步骤,论文针对这两方面进行如下研究。针对传统模体挖掘过程中的精确子图识别中存在的计算效率低的问题,本文基于公共子图的树形遍历G-tries算法提出邻域等价类的精确子图识别算法Ex-Motifs来减少子图同构的匹配过程。基本思想如下:在对目标顶点参与的子图进行识别时,在特定的子图同构过程中利用邻域等价公式对子图频次进行计数,以提高传统子图同构的计算效率。实验结果表明,相比经典的精确识别子图算法,Ex-Motifs的计算效率相对较高。由于精确子图识别算法Ex-Motifs的计算效率低,本文在此基础上提出一种基于公共子结构的马尔科夫链蒙特卡罗采样策略的近似挖掘算法InEx-Motifs。具体步骤如下:首先对原始网络中的顶点进行采样,然后利用MCMC随机游走采样策略对该顶点参与的子图进行识别,最后对该顶点的邻居多次采样以达到采样均衡。实验结果表明,在相对误差这一度量指标上,InEx-Motifs算法的平均相对误差最小;在运行时间这—度量指标上,InEx-Motifs的计算效率相对较高。因传统的模体度量方式是生成与原始网络相同度序列的多个随机网络对比各子图频次,对时间和空间上的消耗较大。所以本文不与随机网络对比子图频次来获取模体,而是提出一种基于公共子结构的模体度量指标,直接在原始网络上对子图频次判断其显著性。实验结果表明,本文的度量方法能够找到与传统模体度量方法相似的模体。