动态大规模社交网络上的社区发现研究

发布时间：2024-05-20 22:48

　　现实生活中的很多真实系统都可以看作是复杂网络的一种拓扑抽象,如科学家合作网、电力网、城市交通运输网等。研究表明,社区结构是复杂网络最重要的特征属性之一,即属于同一个社区的节点之间连接较为紧密,而不同社区间的节点连接相对稀疏。社区结构的发现就是将网络节点按照其内在的拓扑结构连接的紧密程度划分成若干个子图的过程。分析并发现社交网络中的社区结构对用户行为分析,情感分析,个体影响力分析等都具有重要作用。对于大规模的复杂网络,节点数量较多,关系错综复杂,传统的社区发现算法存在运行效率低,可扩展性不足,难以处理大规模网络等问题。基于增量的动态社区发现算法由于在聚类时参照了前一时刻的信息,避免了对整个网络重新进行聚类,因此能有效降低算法的时间复杂度。同时,基于并行的大数据计算框架也大大提高了程序的运行效率。本文在分析传统社区发现算法的基础上,深入研究动态大规模社交网络上的社区发现问题,主要研究成果如下:(1)提出一种将社区结构稳定度和增量相关节点相结合进行社区发现的方法。算法以前一个时刻得到的社区结构为基础,通过基于Jaccard系数的社区归属判定条件来调整增量相关节点的社区归属,同时考虑每个社区的...

【文章页数】：62 页

【学位级别】：硕士

【文章目录】：
中文摘要
Abstract
第一章 引言
    1.1 研究背景及意义
    1.2 国内外研究现状
        1.2.1 静态社区划分
        1.2.2 动态社区划分
    1.3 本文主要工作
    1.4 本文组织结构
第二章 社区发现相关概念与方法
    2.1 复杂网络和社区结构相关概念
        2.1.1 复杂网络
        2.1.2 社区结构
    2.2 社区划分质量评价标准
        2.2.1 标准化互信息
        2.2.2 模块度
        2.2.3 ARI指数
    2.3 静态复杂网络社区发现算法
        2.3.1 基于图划分的方法
        2.3.2 基于模块度优化的方法
        2.3.3 基于标签传播的方法
        2.3.4 基于动力学的方法
        2.3.5 基于仿生计算的方法
        2.3.6 基于派系过滤的方法
        2.3.7 基于边划分的方法
        2.3.8 基于局部扩展的方法
    2.4 动态复杂网络社区发现算法
        2.4.1 基于时间独立评价的方法
        2.4.2 基于时间集成的方法
        2.4.3 基于统一评价的方法
        2.4.4 基于增量式的方法
    2.5 本章小节
第三章 考虑社区结构稳定度的增量标签传播算法
    3.1 基本概念
    3.2 算法设计思想
    3.3 算法实现
    3.4 算法复杂度分析
    3.5 实验结果与分析
        3.5.1 实验准备
        3.5.2 人工数据集实验
        3.5.3 真实数据集实验
    3.6 本章小结
第四章 基于边密度聚类的增量社区发现算法
    4.1 基本概念
    4.2 基于边密度聚类的静态社区发现
        4.2.1 算法设计思想
        4.2.2 算法实现
        4.2.3 算法时间复杂度分析
    4.3 基于边密度聚类的增量社区发现
        4.3.1 算法设计思想
        4.3.2 算法实现
        4.3.3 算法时间复杂度分析
    4.4 实验与结果分析
        4.4.1 实验准备
        4.4.2 人工数据集实验
        4.4.3 真实数据集实验
    4.5 本章小结
总结与展望
    本文总结
    未来工作展望
参考文献
致谢
个人简历
在学期间的研究成果及发表的学术论文



本文编号：3979235