基于介度指标和社团结构的影响力最大化算法研究

发布时间：2025-02-09 19:28

　　在社会中存在各种各样的网络,例如:人际关系网,社交网络,互联网,交通网络等。随着科技的进步与发展这些网络也变得日益复杂,尤其在互联网较为发达的今天,这些网络中的关系越来越明显,网络拓扑结构的演变也越来越剧烈,对这些网络的研究也成为了学术界的焦点,尤其在信息的传播和广告的投放等方面愈加热门。因此,对社会中这些网络的基本特征、网络中传播动力学的规律和网络拓扑结构演变过程进行深入的学习和研究具有重要的意义。影响力最大化算法的研究,目的在于寻找一种高效低廉的策略选择一组满足给定大小的集合作为种子节点集,在一定的传播模型下,可以使得种子集合影响力传播的覆盖范围达到最广。影响力最大化问题的研究不仅对复杂网络理论研究有着重大的意义,而且在产品推广、信息传播、舆论控制等方面有着广泛的应用前景。近年来对影响力最大化算法研究也相当广泛,其中较为热门的算法,一类是基于贪心策略的算法,另一类是基于启发式的算法。基于贪心策略的算法有着较高的准确率,但其时间复杂度非常高,不适于大型网络的计算;基于启发式的算法有着优异的运算效率,但其鲁棒性不强,准确率较低。为此,本文以社会网络为研究对象,分析对比了基于中心性算法对求...

【文章页数】：67 页

【学位级别】：硕士

【文章目录】：
中文摘要
Abstract
第一章 绪论
    1.1 研究背景
    1.2 国内外研究现状
    1.3 本文的贡献
    1.4 本文的组织结构
第二章 相关的理论知识
    2.1 图的相关理论
    2.2 复杂网络的相关理论
    2.3 影响力最大化相关知识
    2.4 影响力最大化问题中的传播模型
        2.4.1 独立级联模型
        2.4.2 线性阈值模型
        2.4.3 权重级联模型
        2.4.4 其他的传播模型
    2.5 经典的影响力最大化算法
        2.5.1 贪心算法
        2.5.2 CELF算法
        2.5.3 基于度中心性的算法
        2.5.4 SCG算法
        2.5.5 PageRank算法
        2.5.6 SingleDiscount算法
        2.5.7 度折扣算法
    2.6 本章小结
第三章 基于介度指标评价的算法
    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.4 实验结果及其分析
        3.4.1 调节系数α的选择
        3.4.2 实验结果及其分析
    3.5 本章小结
第四章 基于社团结构的介度指标评价算法
    4.1 社团结构
    4.2 基于派系的社团划分算法
        4.2.1 k-派系定义
        4.2.2 k-派系发现算法
    4.3 基于社团结构的介度指标评价算法
        4.3.1 介度指标与社团结构结合
        4.3.2 基于社团结构的介度指标评价算法的改进
        4.3.3 算法的复杂度分析
    4.4 实验设置及其结果分析
        4.4.1 实验参数设置
        4.4.2 影响力传播范围对比
        4.4.3 算法的时间效率对比
    4.5 本章小结
第五章 总结与展望
    5.1 本文总结
    5.2 未来工作的展望
参考文献
致谢



本文编号：4032750