基于子结构感知的社交网络Graphlets采样算法研究

发布时间：2021-05-26 09:56

　　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样本,从而以统一的方式估计所有... 

【文章来源】：中国科学技术大学安徽省 211工程院校 985工程院校

【文章页数】：72 页

【学位级别】：硕士

【文章目录】：
摘要
ABSTRACT
第1章 绪论
    1.1 在线社交网络及其应用
    1.2 在线社交网络的数据挖掘
        1.2.1 网络数据挖掘及其应用
        1.2.2 社交网络的常用挖掘指标:Graphlets
        1.2.3 社交网络的常用挖掘手段:采样方法
    1.3 社交网络中Graphlets挖掘的研究状况与发展趋势
    1.4 本文的研究内容和主要贡献
    1.5 本文组织结构
第2章 社交网络中Graphlets采样算法的相关研究
    2.1 社交网络中Graphlets采样的背景知识
        2.1.1 社交网络图模型
        2.1.2 Graphlets
        2.1.3 随机游走
        2.1.4 图上的随机游走采样
    2.2 社交网络中Graphlets采样的相关研究
    2.3 本文的研究意义
    2.4 本章小结
第3章 基于最大公共子结构感知的Graphlets采样算法CSRW
    3.1 引例
        3.1.1 基于SRW的Graphlets采样算法示例及其不足
        3.1.2 Graphlets统一采样思路的形成
    3.2 CSRW的算法思想
    3.3 CSRW的偏差校正
        3.3.1 CSRW的重复系数计算
        3.3.2 CSRW的无偏估计
    3.4 CSRW估计Graphlets频率值的算法框架
    3.5 实验分析
        3.5.1 算法精确度分析
        3.5.2 算法扩展性验证
        3.5.3 时间性能分析
    3.6 本章小结
第4章 基于两种子结构感知调和的Graphlets采样算法CSRW2
    4.1 改进思路的形成
    4.2 CSRW2的算法思想
    4.3 CSRW2的偏差校正
        4.3.1 CSRW2的重复系数计算
        4.3.2 CSRW2的比例放大调和法
        4.3.3 CSRW2的无偏估计
    4.4 CSRW2估计Graphlets频率值的算法框架
    4.5 实验分析
        4.5.1 算法精确度分析
        4.5.2 时间性能分析
    4.6 本章小结
第5章 总结与展望
    5.1 总结
    5.2 展望
参考文献
致谢
在读期间发表的学术论文与取得的研究成果



本文编号：3206180