4.1 实验环境与数据集描述 ......................................... 35
4.2 实验设置 ....................................... 36
5 总结与展望 ...................................... 63
5.1 总结 ........................................... 63
5.2 展望 ................................... 64
4 实证分析
4.1 实验环境与数据集描述
本文实验主要采用 Java 编程，在带有 JDK1.8 版本的 Eclipse 平台上进行实验。实验中使用的计算机配置为：Windows 10 企业版(64 位)操作系统，Intel(R) Core(TM) i7-7700HQ CPU@ 2.80GHz RAM 16G 的处理器。
为验证本文算法的有效性，本文将其应用于 14 个大小不同的现实网络，它们的基本统计特征如表 4.1 所示，其中𝑛为网络中的节点数，𝑚为网络中的边数，< 𝑘 >为网络的平均度数，𝑘𝑚𝑎𝑥为网络中的最大度数，𝑐为网络的平均聚集系数[70]，𝐻为节点度分布的异质性系数[71]且𝐻 =< 𝑘2>/< 𝑘 >2。在本文中，这些图都视为无向图和无权图。
表 4.1 展示了本文所用数据集的基本统计特征，其中包括：(1) CE-GT 是秀丽隐杆线虫的遗传物质相互作用网络[72]；(2)Enron 是从邮件系统 Enron.com 中抽取的邮件联系网络[73]；(3)Oz 网络[74]包含居住在澳大利亚国立大学校园内学生宿舍中的 217 位居民之间的友情等级；(4) Physicians 数据集[75]是医师之间的创新成果网络；(5) TC 数据集[76]由美国 FAA(联邦航空管理局)国家飞行数据中心(NFDC)，首选航线数据库构建而成；(6) Grid-Plant 数据集[77]是一个生物医学交互存储库，表示蛋白质相互作用网络；(7) EPA 数据集[78]是通过将 200 页的响应集扩展到搜索引擎查询而构建的； (8)NS 数据集[79]是网络科学领域的合著者网络；(9) Routeviews 数据集[80]是相互连接的 Internet 自治系统的无向网络；(10) Deter0数据集[81]是随机线性规划问题的确定性等价网络；(11) Ia-reality数据集[82]由麻省理工学院(MIT)的一小群核心用户之间的人工手机呼叫事件组成；(12) Ca-GrQc 数据集是[83]Arxiv 广义相对论领域的合作网络；(13) PGP 数据集[84]是PrettyGoodPrivacy 加密程序上的用户交互网络；(14) SC 数据集[85]是由 WikiData提取的通过“姐妹城市”或“双子城市”关系连接的世界无定向网络。以上数据集均来自 http://konect.cc/networks/或 http://networkrepository.com/，这两个网站提供了这些数据集更详细的说明，可供此研究方向上的研究者使用。
5 总结与展望
5.1 总结
互联网的普及和社交平台的发展极大地改变了人们的生活和沟通方式，随着“口碑营销”、“病毒传播”等问题的出现以及研究者对网络科学的深入研究，社交网络中的信息传播成了人们的一个极大关注点，而影响最大化问题也是近几年研究信息传播的一个热门研究方向。虽然该问题的研究目前取得了一些成果，但也存在一些局限。例如，基于贪心算法框架的改进算法能够取得较好的传播影响范围，但此算法框架需要进行大量的蒙特卡洛模拟来选择下一个边际收益最高的种子节点，这需要大量的时间来计算。显然，在网络规模日益壮大的今天，是不适用的。研究者们提出启发式算法来求解影响最大化问题，启发式算法虽然时间复杂度低，但由于网络中普遍存在着“富俱乐部”现象，很多启发式算法不能有效地避免此现象的产生，所以造成种子节点传播范围的重叠，这不利于信息在网络中广泛传播。如何在较短的时间内在大规模的网络中求解影响最大化问题是一个非常具有挑战性的问题。
本文首先对影响最大化问题的研究背景与意义、国内外对该领域的研究现状进行了分析和阐述。接着对影响最大化问题是如何从市场营销领域转化为算法问题进行了介绍，对影响最大化问题给出了形式化定义并介绍求解过程。然后，研究了影响最大化领域主流的信息传播模型和目前流行的影响最大化算法，并通过具体示例、伪代码等作了进一步的说明。最后，为了解决算法耗时久和种子集传播范围重叠的问题，给出解决方案，本文主要研究工作和创新点如下：
(1)提出了一种基于动态筛选的影响最大化算法。针对算法耗时的问题，本文将节点的度和节点的路径综合考虑起来，通过限制广度优先遍历的深度来控制时间开销，且通过生成候选节点集来减少种子节点生成的时间开销。针对种子集传播范围重叠的问题，本文通过衰减种子节点和邻居节点的度来降低种子节点邻域内的节点被选为种子节点的可能，并在候选节点集中选择离当前种子集最远的节点作为下一个种子节点加入种子集中。对衰减节点度的策略，提出了两种算法分别名为 Zero-IMax 和 Half-IMax 算法。
(2)为验证 Zero-IMax 和 Half-IMax 算法有效性，本文引入当前流行的信息传播模型，SIR 模型对算法进行模拟实验，并于当前流行的 5 种影响最大化算法进行对比实验，通过改变种子节点数量、信息传播概率等因素来验证本文提出算法的有效性和稳定性。实验结果表明，本文提出的 Zero-IMax 和 Half-IMax 算法相较于当前流行的 5 种影响最大化算法有更好的传播范围和良好的稳定性。
参考文献（略）
