在线社交网络中基于标签传播社区发现算法的研究

发布时间：2021-08-06 22:25

　　随着互联网技术和Web2.0应用的飞速发展,大量形态各异的在线社交网络风靡世界,成为人们分享和传递信息的重要平台,也帮助人们在网络中维系着自己的社会关系。因此,研究社交网络中的社区结构有着非常现实的意义,也成为近些年的研究热点。研究人员曾提出过很多社区发现算法,然而很多算法都有时间复杂度较高的问题。基于标签传播的社区发现算法具有接近线性的时间复杂度,它对图中每个顶点分配一个代表其所在社区的标签,按照随机顺序对每个顶点进行标签更新。一个顶点若具有多个满足条件的候选标签,则随机选择标签。然而该算法的结果包含很多小而碎的社区,且结果很不稳定。因此我们提出了基于标签影响值的社区发现算法（LIB）。LIB算法选取一个种子集,为其中的顶点分配标签并按顶点度排序进行传播,在传播过程中为每一种标签计算标签影响值来选择标签。我们在不同类型的数据集上进行了对比实验,实验结果表明LIB算法在复杂度相近的情况下明显提高了所发现社区的质量,并有很好的稳定性。为了能更多的考虑社交网络中的动态行为,并且更多的从社会学意义上提高社区发现的质量,我们提出了基于标签影响向量的社区发现算法（LIVB）。LIVB算法将在线社... 

【文章来源】：复旦大学上海市 211工程院校 985工程院校 教育部直属院校

【文章页数】：53 页

【学位级别】：硕士

【文章目录】：
摘要
Abstract
第一章 引言
    1.1 背景介绍
    1.2 相关概念
        1.2.1 社交网络中的社区
        1.2.2 社交网络的数学表达
        1.2.3 社区发现算法
    1.3 本文组织架构
第二章 相关工作与背景知识
    2.1 社区发现相关算法
    2.2 基于标签传播的社区发现算法
    2.3 社区质量评价指标
第三章 基于标签影响值的社区发现算法
    3.1 算法思想
    3.2 LIB社区发现算法
        3.2.1 种子集合的选取
        3.2.2 标签传播过程
        3.2.3 社区生成算法LIB
    3.3 LIB算法时间复杂度
第四章 LIB算法实验验证
    4.1 实验数据
        4.1.1 基准数据集
        4.1.2 抓取数据集
    4.2 实验环境
    4.3 实验评估方法
    4.4 实验结果与分析
        4.4.1 实验一 基于基准数据集的实验
        4.4.2 实验二 基于抓取数据集的实验
第五章 基于标签影响向量的社区发现算法
    5.1 算法提出背景
    5.2 Label-Influence-Vector-Based社区发现算法
        5.2.1 算法思想
        5.2.2 标签影响向量的计算
        5.2.3 标签影响向量的比较方式
        5.2.4 社区生成算法LIVB
    5.3 LIVB算法时间复杂度
    5.4 标签影响向量比较公式的传递性证明
        5.4.1 问题定义
        5.4.2 问题分析
        5.4.3 分类详细证明
第六章 LIVB算法实验验证
    6.1 实验数据
    6.2 实验环境
    6.3 实验评估方法
    6.4 实验结果与分析
        6.4.1 实验三 LIVB算法和LPA算法对比实验
        6.4.2 实验四 LPA算法在不同类型图上的对比实验
第七章 总结与展望
    7.1 论文总结
    7.2 未来工作展望
参考文献
附录一 硕士期间所发表的论文
致谢



本文编号：3326589