本文是一篇软件工程硕士论文，本文研究者们提出启发式算法来求解影响最大化问题，启发式算法虽然时间复杂度低，但由于网络中普遍存在着“富俱乐部”现象，很多启发式算法不能有效地避免此现象的产生，所以造成种子节点传播范围的重叠，这不利于信息在网络中广泛传播。如何在较短的时间内在大规模的网络中求解影响最大化问题是一个非常具有挑战性的问题。
1 绪论
1.1 研究背景与意义
1.1.1 研究背景
社交网络是由个人或组织组成的社会结构，它们由一种或多种特定类型的相互依存关系所捆绑，例如基于 Facebook 所展示的友谊关系网络、DBLP 计算机科学书目的合著者网络等[1]。过去的几十年见证了在线社交网络的蓬勃发展，成千上万人相互交流并产生前所未有的海量数据[2]。2021 年 2 月 3 日，中国互联网信息中心(CNNIC)发布《第 47 次中国互联网络发展状况统计报告》[3]，截至 2020年 12 月，我国网民规模达 9.89 亿，互联网普及率达 70.4%，使用手机上网的比例达 99.7%。因为网络的存在，人们可以忽略时间和空间的问题便捷地获取和传递信息，人们可以做到“足不出户便知天下事”，这极大的降低了人们的社交成本。这种社交方式在信息传播中起着至关重要的作用，也为信息传播的方式带来了巨大变革[4]。以前，人们了解信息的途径只能通过电视、报纸、杂志等少数媒体，这些媒体掌握着信息传播的话语权和主动权，用户们只是信息的被动接受者，即用户了解到的信息是怎样的完全取决于媒体[5]。如今，社交网络将人们带入了自媒体时代，每个用户既是信息的接受者也是信息的传播者和创造者，每个用户都可以通过社交网络影响其他用户。
近年来涌现出了大量的社交平台，它们规模宏大、发展势头迅猛，例如微信、微博、贴吧等社交网络服务平台已成为信息的独立源头，传播的信息数量呈指数级增长[6]。2020 年 5 月 16 日发布的《2019-2020 年微信就业影响力报告》指出，截至 2020 年第一季度，微信及 WeC hat 的合并月活跃用户数达 12.025 亿。由此可见，社交平台在人们的日常生活中扮演着不可替代的角色，有些商家甚至会用微博“粉丝”的数量来衡量一个明星的“影响力”，来决定是否选择某位明星来代言产品。“影响力”看似抽象，实则无处不在，生活的各个角落都能找到影响力的影子，比如我们会买自己偶像代言的手机，会观看朋友或者身边同事推荐的电影，出去旅游的时候会去网红景点打卡等，像这种通过口碑进行扩散的行为就是影响力进行传播后的结果。在这样的背景之下，网络营销横空出世，以一种全新的销售模式改变大众对传统消费方式的认知，进而使大众慢慢适应这样的营销手段。同样，用户影响力研究在科技的发展中也占有一席之地，这吸引了众多研究学者的目光，众多学者将研究的角度聚集在影响力和影响力的传播上。
1.2 国内外研究现状
目前常用的求解影响最大化问题的算法(以下简称“算法”)可以分为基于贪心框架的算法、基于智能优化的算法和基于网络特征的算法，其中基于网络特征的算法又可细分为基于节点路径和基于节点邻域两个类别，它基于直观属性或生活经验，并考虑了网络或中心的静态拓扑结构。
1.2.1 基于贪心框架的算法
Domingos[16]等人在研究市场营销问题时第一次将影响力最大化问题视作算法类问题。之后的研究者们提出了许多基于传播过程的影响力最大化算法。Kempe[17]等人证明了此类问题是 NP-hard 的，并提出了一种基于传播的贪心算法，该方法近似保证了影响效果在最优的影响效果的以内。基于传播的方法在准确性方面优于其他算法，但由于此类方法依赖于计算机在每一轮评估影响，所以是比较耗时的，通常在几千个顶点的图中需要运行几个小时。为了克服基于传播的方法耗时长的缺点，Leskovec[13]等人提出了名为 CELF 的优化算法，该算法主要是在种子选择上进行了优化，它使用影响最大化目标的子模性[18]来大大减少对节点影响扩散的评估次数。他们的实验结果表明，CELF 优化可以在选择种子时实现多达 700 倍的加速，这是一个非常令人震撼的结果。但是，CELF 仍然需要几个小时来完成一个包含数万个节点的图形，对大规模网络来说仍然没有效率。Goyal 等人[19]提出了 CELF++算法来优化运行时间，但在大规模网络中仍然存在这个问题。随着人们在网络上的交互越来越频繁，网络的规模也在不断地扩大，该类基于贪心框架的方法面临着巨大的运算压力，在实际应用中难以满足实际需求
1.2.2 基于智能优化的算法
影响最大化算法本质上属于一种 NP-hard 的离散优化问题[20]，常规的方法很难找到合适的解，并且容易陷入局部最优解。智能优化类算法如演化算法、Memetic 算法等借鉴自然演化过程，模拟生物进化过程或者生物群体的生存之道，在解空间中能找到较好的解，甚至是全局最优解。Jiang 等人[21]针对影响最大化问题提出了一种基于模拟退火(SA, Simulated Annealing)的方法。这是解决该问题的第一个基于 SA 的算法。 此外，作者提出了两种启发式方法来加速 SA 的收敛过程，并提出了一种计算影响力的新方法来加快所提出算法的速度。结果表明所提出的算法比最先进的贪婪算法运行速度快 2-3 个数量级，同时能够提高贪心算法的准确性。Bucur 等人在文献[22]中通过遗传算法来求解影响最大化问题，作者证明通过使用简单的遗传算子，可以在可行的运行时间中找到影响最大化的解决方案，这些解决方案与许多已知的启发式方法找到的解决方案具有可比性，有时甚至更好。遗传算法的优势表明，它们不需要对网络底层的图进行任何假设，并且与当前的启发式算法相比，它们可以获得更多套可行的解决方案。
2 相关理论知识
2.1 社交网络
社交网络(Social Network)是由各种各样的关系组成的网络，该名词是 1954年由 J.A.Barnes[43]首次使用，一个社交网络的大小最大约为 150 人左右，平均大小约为 124 人左右。社交网络源于网络社交，所谓网络，指的是计算机之间的联网，人们通过网络进行交往，称之为网络社交。最早的网络社交平台是电子邮件，人们通过远程的邮件传输进行联系，并且这一应用还一直延续到现在。随着网络社交不断的演变，人们在网络中的交流日益多样化，各种应用服务也更加齐全，于是就形成了社交网络[44]。
随着社交网络的种类变得越来越多，为了更清楚地展示社交网络的基本特征，人们开始以“图”的形式来表示社交网络，即网络的可视化[45]。
图(Graph)是一种比线性表和树更为复杂的数据结构。在线性表中，数据元素之间仅有线性关系每个数据元素只有一个直接前驱和一个直接后继；在树形结构中，数据元素之间有着明显的层次关系，并且每一层的数据元素可能和下一层中的多个元素(即孩子节点)相关，但只能和上一层中一个元素(即其双亲节点)相关；而在图结构中，节点之间的关系可以是任意的，图中任意两个数据元素之间都可能相关。数学中图论是通过节点(Vertex)和边(Edge)构成一张图，在社交网络的图形式描述中，节点(Vertex)可以代表社交网络中的某一成员，边(Edge)则表示为成员之间存在的某种联系。因此，社交网络可以抽象为一个二元组的图𝐺(𝑉, 𝐸)来表示，其中𝑉代表该社交网络中所有成员组成的集合，𝐸代表所有成员之间相互联系的集合，这已经是当前所有研究人员达成的共识[46]。
如图 2-1 所示为美国空手道俱乐部中成员关系的社交网络模型[47]，每一个节点代表一位成员，当节点所代表的两个人在空手道课程、体育锻炼和俱乐部会议之外的环境中持续互动时，在两点之间画一条线，这条线则被称为边，表示两人在日常生活中还保持有联系。
2.2 影响最大化问题
2.2.1 基本研究路径
目前研究影响最大化问题的算法大多从两个方面出发：一方面，是对贪心算法的改进，贪心算法虽然能取得较好的最终影响范围，但因其依赖于蒙特卡洛模拟在每一轮计算各个节点的边际收益，所需的时间代价巨大，所以此类算法主要是对贪心算法的时间效率进行改进；另一方面，是研究者们提出的各种基于网络特征的算法，此类算法的提出多数基于直观经验或基于网络节点的中心性度量，此类算法虽然最终影响范围略低于贪心算法，但因其速度快、时间代价低等优点被人们广泛研究。本文提出的算法是基于网络特征的算法，所以对此类算法的基本研究路径进行说明，如图 2-2 所示。
如图 2-2 所示，当一种算法被设计出来，需对算法的效果进行验证，因此需对其进行模拟实验。模拟实验的具体过程如下：首先应确定和哪些算法作对比，再从网上找到一组公开的社交网络数据集，对不同规模的数据集，种子集𝑘的大小应有所区别，再将设计出的算法和对比算法选择出的种子集，在指定的信息传播模型上进行影响传播模拟，最终得到影响传播范围，并对其进行分析。
3 基于动态筛选的影响最大化算法 ............................ 25
3.1 研究动机 ............................... 25
3.2 基本框架 ............................... 25
3.3 关键技术 .............................. 27
4 实证分析 ...
