第一章 绪 论
1.1 研究背景与意义
在过去的近二十年的时间里，社交媒体已经逐渐取代了传统媒体，成为了人们生活的一部分。截止 2021 年 2 月，全球社交媒体用户数量高达 42 亿，占全球总人口数量的53%。而且，仅在过去的一年时间内，社交媒体用户数量就增长了 4.9 亿。这些社交媒体提供的社交服务涵盖了新闻、影视、购物、学习和通讯等多方面的服务，解决了人们的大部分需求。因此，人们愿意每天在社交媒体上花费大量的时间。庞大的用户群体加上大量的在线时间，社交媒体不仅产生了海量的数据，而且源源不断地为社交网络分析研究注入活力。值得注意的是，社交数据与其他数据不同，社交数据包含人与事物、人与人、人与社区以及社区与社区之间复杂的关系。这些复杂的关系激发了研究者们对社交媒体中信息传播研究的兴趣，并且他们的研究成果被广泛地应用在医疗、商业、交通等多个领域。例如，许多学者就采用信息传播相关技术模拟新冠肺炎病毒传播过程，预测病毒的传播范围，为防疫工作做出了贡献。影响最大化问题作为社交媒体中信息传播的重要问题，同时也是本文的重要研究问题。
影响最大化问题旨在从网络中选取少量的节点作为种子节点，信息从这些种子节点开始传播，使得信息的传播范围最广。影响最大化问题作为信息传播问题中的一个重要问题，它蕴含着巨大的商业价值，如个性营销[79,80,85]、链路预测[78,82]和谣言控制[81,86]等。该问题的研究兴起于十多年前，经过这些年的发展，涌现出了不少优秀的研究成果。但是影响最大化问题的研究仍然面临着一些挑战。首先，影响最大化问题是 NP-hard 问题，要想解决 NP-hard 问题自然先想到贪心式算法，但这类算法却难以应对规模越来越大的网络。启发式算法虽然可以在较短的时间内处理影响最大化问题，但精度较低，且现有的启发式算法没有深入挖掘网络特征，将节点特征与网络结构特征结合起来分析网络。其次，由于信息传播的时效性，经算法挖掘得到的种子节点的影响传播范围往往无法达到预期效果，如何进一步提升种子节点的影响力也成了亟待解决的问题。因此，为了弥补这些不足，本文提出了综合节点特征和网络结构特征的种子挖掘算法 CVIM (Cut-vertex-based Influence Maximization)、动静态网络混合加边框架 DSNHE 和 LN (Latent Node)加边策略。
........................
1.2 国内外研究现状
影响最大化问题最早进入学术界是在 2001 年，Domingos 和 Richardson[1]提出用马尔科夫随机场来模拟信息传播过程，并给出了一个启发式的解决方案，给学者们打开了一道新的大门。紧接着，在 2003 年，Kempe[2]等人将影响最大化问题定义为一种 topk的离散最优化问题，即找出影响传播范围最大的k 个种子节点。此外，他们还提出了两种基本的传播模型，线性阈值模型(Linear Threshold, LT)和独立级联模型(Independent Cascade, IC)，并证明了在这两种传播模型下，影响最大化问题是一个 NP-hard 问题。他们提出了一个近似比为(11/e)的 Greedy 算法，可以得到影响最大化问题最优解 63%的近似解。他们提出的这些方法和结论给影响最大化问题的研究奠定了基础。学者们在此基础上刻苦钻研，使得影响最大化问题研究领域硕果累累。如图 1.1 所示，本文主要从模型、算法和优化三个方面的国内外研究现状进行归纳总结。
图 1.1 国内外研究现状的主要类别 1.2.1 信息传播模型
信息传播模型模拟了网络中的交互过程，是研究影响最大化问题的基础。如今，社会学、医学以及经济学等领域出现了多种多样的信息传播模型。常见的信息传播模型有：线性阈值模型、独立级联模型、传染病模型等。本节将现有的模型主要分为阈值模型、级联模型和其他模型三类，并按照这三种类型介绍相关模型。
..........................
第二章 相关理论概述
2.1经典传播模型
传染病模型早期被用于模拟传染病的传播过程，后面逐渐被应用到网络分析领域。传染病模型其实是以疾病传染的过程提取构建出来的模型的总称，根据不同的场景，它被划分为很多种模型，例如：SI 模型、SIS 模型、SIR 模型和 SIRS 模型，其中 SIR 模型被广泛应用于模拟信息传播过程。因此，在网络分析领域中，传染病模型默认为 SIR模型。本文所涉及的传染病模型即为 SIR 模型，在第三章和第四章中，SIR 模型作为种子节点的影响传播模型，确定了参数 α 的取值，并验证了 CVIM 算法、IMM++算法和LN 加边策略的有效性。在上述四种传染病模型中，涉及到节点的三种状态：易感态(Susceptible)、感染态(Infected)、恢复态(Recovered)。
图 2.2 四种传染病模型中节点状态转移方式 .............................
2.2相关概念及形式化描述
在现实生活中，往往存在着一些关键角色，虽然他们可能不是主角，但他们是整个拼图中必不可少的一块（如中介、经纪人、交通枢纽等）。把这些关键角色映射到网络图上，他们就是网络图中的割点。在给出割点的定义之前，必须先提一下连通图和连通分量的基本概念。因为割点是图中的一种特殊的点，它与图的连通性有关。本文通过图例介绍了连通性的相关概念，详细情况见图 3.1。
图 3.1 图的连通性示例 在图 3.1 中，G 是一个无向图，同时也是非连通图。而 G1 是一个连通图，因为在G1 中，任意两个不同的节点之间都存在可达路径。此外，G1 是 G 的子图，并且如果往G1 中加上(8, 9)这条边，G1 就不是连通图。基于这些前提，则可以推断 G1 是 G 的极大连通子图，同时也可以称 G1 是 G 的连通分量。因为连通图的极大连通子图就是它本身，所以 G1 也是 G1 的极大连通子图，即 G1 是 G1 的连通分量，并且是唯一连通分量。G2是将 G1 中的节点 2 以及与节点 2 相关联的边删除后得到的无向图。从图中可以看出，G2 有 3 个连通分量，G1 只有 1 个连通分量，去除节点 2 以及与节点 2 相关联的边使得图的连通分量增加了，满足这个条件的节点被称为割点，即节点 2 是 G1 的割点。
...........................
第三章 基于割点的影响最大化算法 ....................................... 20
3.1 引言 ............................................ 20
3.2 相关概念及形式化描述 ..................................... 20
第四章 通过优化网络结构实现影响最大化 ................................. 32
4.1 引言 ........................................... 32
4.2 加边问题 ..................................... 33
第五章 总结与展望 ................................... 50
5.1 总结 ......................................... 50
5.2 展望 .............................. 51
第四章 通过优化网络结构实现影响最大化
4.1 引言
对于影响最大化的研究，学者们大部分专注于种子挖掘算法的研究，他们认为只要找到最优种子节点，就能得到最大的收益。而在现实生活中往往存在投入的种子无法达到预期效果的情况，这时我们就可以通过优化网络结构来加速信息的传播。如何优化网络结构是一个值得研究的问题，如重连边[87]、加边[88, 89]等。图 4.1 是一个网络结构优化示例图。
图 4.1 重连边与加边的对比 在图 4.1 中，其中节点 4 是信息源，子图(a)是重连边示例图，子图(b)是加边示例图。子图(a)中，左侧是源网络，中间是重连边后的网络，右侧是节点 4 传播信息到其他节点的概率表，表中 p1 是源网络中节点 4 传播信息到其他节点的概率，p2 是重连边后的网络中节点 4 传播信息到其他节点的概率。从表中数据可以看出大部分节点的传播概率明显上升，有效地提高了信息源扩散的范围（假设激活概率=0.2，则源网络中，节点 4将激活 3 个节点，重连边后的网络中，节点 4 将激活 5 个节点）。同理，子图(b)中，所有的节点在添加边之后，节点 4 传播信息到它们的概率都提高了，在与前面同等条件下，添加边后的网络中，节点 4 将激活 6 个节点。
..............................
第五章 总结与展望
5.1 总结
身处信息时代，社交媒体发展迅速，信息传播的平台和方式变得多样化，如Facebook、Twitter、抖音、微博和微信等。We Are Social 和 Hootsuite 两家公司联合在《2020 全球数字报告》中指出，普通网民平均每天要花费大约 7 个小时的时间在社交网络上，社交媒体用户数更是突破 38 亿。光微信这一个社交平台，全球每月就有 11.5 亿用户使用它进行交互，产生了大量的信息。这些信息传播的速度之快、范围之广，使得社交网络上信息传播问题越来越受到学者们的关注。本文对社交网络影响力计算做了如下工作：
(1) 基于割点的社交网络影响最大化算法
由于割点在图论中扮演者不可或缺的角色，本文基于图论中的割点理论，提出基于割点的影响最大化算法 CVIM。它将连通分量纳入到评估节点影响力的指标中，并结合度的优势，筛选出有效的种子集，从而找出影响最大化问题的解。实验结果表明，CVIM与部分具有代表性的算法相比，在运行时间、影响传播范围和种子富集性指标上具有一定的优势，并且能有稳定的表现。
(2) 通过优化网络结构实现影响最大化
本文提出一个新的研究问题 动态网络加边问题，该问题对传统的影响最大化问题和加边问题起到了重要的补充作用。在动态加边问题中，不仅需要从第一个网络快照中选择最佳种子集，还得在后续快照中动态更新节点的度量值。因此，处理动态网络加边问题比影响最大化问题和加边问题更加困难。为了解决这个问题，本文提出 DSNHE框架作为动态网络加边问题的解决方案。在 DSNHE 框架中，本文在 IMM 算法的基础上改进设计了 IMM++算法来挖掘种子。为了快速捕捉网络的动态变化，从而构造影响集用来更新节点的评估值。另外，本文设计了一种新颖的加边策略来完成加边操作。本文已经在不同的真实开源的数据集上进行了广泛的实验，实验结果表明了本文所提的IMM++在影响传播范围指标上具有一定的优势，同时也肯定了加边操作的意义，且验证了 LN 加边策略无论在静态网络还是动态网络上都具有较高的效率。这项工作探索了通过在动态网络中加边来加快信息传播的可能性。这将使研究人员能够更加关注影响最大化问题和加边问题，并探索更多的可能性。
参考文献（略）
这是一篇优质的软件工程论文范文，如果想查看更多优质的软件工程论文范文，可以查阅本站的软件工程栏目，还可以直接收藏本站，本站每天更新优质的各类论文范文。
相关文章：
人力资源管理论文：以思源电气为例分析其股权激励计划的04-26
经济类专业毕业论文选题04-26
计算机论文开题报告研究方法有哪些？04-26
护理论文：足底热敷结合麻油对骨折患者便秘的康复护理效04-26
管理论文：S公司生产效率管理案例探讨04-26