社会网络影响模体挖掘

论文摘要

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

论文目录

• 摘要
• Abstract
• 1 绪论
•   1.1 研究背景与意义
•   1.2 国内外研究综述
•     1.2.1 子图识别研究综述
•     1.2.2 模体度量研究综述
•   1.3 研究内容
•   1.4 主要贡献
•   1.5 论文结构安排
• 2 模体挖掘基础术语
•   2.1 研究对象
•   2.2 基础概念
•   2.3 网络模体
•   2.4 经典子图识别算法
•     2.4.1 ESU算法
•     2.4.2 Rand-ESU算法
•     2.4.3 G-tries算法
•     2.4.4 G-tries-S算法
•     2.4.5 Acc-Motifs算法
•   2.5 本章小结
• 3 精确模体挖掘算法
•   3.1 整体思路
•     3.1.1 待解决问题
•     3.1.2 解决方案
•   3.2 模体挖掘过程
•     3.2.1 子图识别
•     3.2.2 模体度量
•   3.3 实验
•     3.3.1 实验环境及数据集
•     3.3.2 评价指标
•     3.3.3 子图频次分析
•     3.3.4 子图显著性分析
•   3.4 本章小结
• 4 近似模体挖掘算法
•   4.1 整体思路
•     4.1.1 待解决问题
•     4.1.2 解决方案
•   4.2 近似模体挖掘过程
•     4.2.1 MCMC基础概念
•     4.2.2 MCMC采样公共子结构算法
•     4.2.3 模体度量
•   4.3 实验
•     4.3.1 实验环境及数据集
•     4.3.2 评价指标
•     4.3.3 子图频次分析
•     4.3.4 子图显著性分析
•   4.4 本章小结
• 5 总结与展望
•   5.1 总结
•   5.2 展望
• 致谢
• 参考文献
• 附录

文章来源

类型: 硕士论文

作者: 王雅姣

导师: 冯健

关键词: 子图识别,模体度量,子图同构,邻域等价类,采样

来源: 西安科技大学

年度: 2019

分类: 基础科学

专业: 数学

单位: 西安科技大学

分类号: O157.5

总页数: 57

文件大小: 5257K

下载量: 62