论文总字数：35151字

摘 要

社交网络中的影响力最大化问题是指在网络中选择影响力最大的指定数量的节点，使得这些节点可以最大程度地将信息传播到网络中的其他节点。

本课题的研究内容是实现目前较为常用的影响力最大化算法，设计可视化系统展示个体影响力和算法传播结果，并分析性能。具体分别采用度数、PageRank值、核数和介数四种个体影响力建模方法，实现五个影响力最大化算法：Degree算法、DegreeDiscount算法、PageRank算法、核覆盖算法CCA和介数中心性算法，基于新浪微博实证数据，利用独立级联模型模拟信息传播过程，对传播结果进行图形化展示，并分析对比各算法在影响范围和运行时间两方面的性能。在影响效果方面，当传播概率为0.01和0.02时，Degree算法和DegreeDiscount算法分别达到最佳；当传播概率大于0.02时，PageRank算法的影响范围最大；并且在本数据集中，取覆盖距离为1时核覆盖算法CCA的平均影响范围最佳。在时间效率方面，Degree算法最佳，DegreeDiscount算法、CCA和PageRank算法的运行时间稍长，而介数中心性算法的时间效率非常差。

关键词：社交网络；影响最大化；可视化；独立级联模型

Abstract

The problem of influence maximization in social network refers to selecting the specified number of nodes with the maximal influence in the network, so that these nodes can maximally spread information to other nodes in the network.

The research content of this paper is to realize the most common influence maximization algorithms, design a visualization system to show the individual influence and the propagation results of algorithms, and analyze their performance. Specifically, four individual influence modeling methods, namely Degree, Betweenness Centrality, PageRank, and Coreness, are used to realize five maximization algorithms: Degree algorithm, DegreeDiscount algorithm, Betweenness Centrality algorithm, PageRank algorithm, Core Coverage algorithm. Based on the empirical data of Sina Weibo, Independent Cascade Model is used to simulate the information propagation process, and the propagation results are graphically displayed. The performance of each algorithm in both influence effect and running time is also analyzed and compared. In terms of influence effect, Degree algorithm and DegreeDiscount algorithm perform best the propagation probabilities are 0.01 and 0.02; when the propagation probability is greater than 0.02, PageRank algorithm has the largest range of influence; and in this data set, when the coverage range is 1, CCA achieves a best average influence effect. In terms of time efficiency, Degree algorithm is the best, DegreeDiscount algorithm, CCA, and PageRank algorithms have a slightly longer runtime, but Betweenness Centrality algorithm is very time-inefficient.

KEY WORDS: social network; influence maximization; visualization; independent cascade model

目 录

摘 要 3

Abstract 4

第一章 绪论 1

1.1 研究背景 1

1.2 研究现状 1

1.2.1 贪心算法 1

1.2.2 启发式算法 2

1.2 研究目标及关键技术内容 3

1.3 论文的组织结构 3

第二章 影响最大化问题概述 4

2.1 节点影响力计算问题 4

2.2 信息传播模型 5

2.2.1 独立级联模型 5

2.2.2 线性阈值模型 5

2.3 影响力最大化问题 6

2.3.1 独立级联模型下的影响最大化 6

2.3.2 线性阈值模型下的影响最大化 7

2.4 影响最大化的子模函数研究方法 7

2.5 本章小结 8

第三章 实验设计与分析 9

3.1 实验数据集 9

3.2 实验设计 9

3.2.1 Degree算法 10

3.2.2 DegreeDiscount算法 10

3.2.3 介数中心性算法 12

3.2.4 PageRank算法 13

3.2.5 核覆盖算法CCA 15

3.3 实验结果分析 16

3.3.1 影响效果分析 17

3.3.2 时间效率分析 22

3.4 本章小结 22

第四章 原型系统 24

4.1 开发环境 24

4.2 技术概述 24

4.2.1 SSH框架 24

4.2.2 D3.js与力导向图 25

4.3 原型系统整体架构 26

4.4 原型系统实现 27

4.4.1 SSH框架搭建 28

4.4.2 原型系统功能实现 32

4.5 Web可视化 34

4.6 本章小结 42

第五章 总结与展望 43

5.1 总结 43

5.2 展望 43

致 谢 44

参考文献 45

第一章 绪论

1.1 研究背景

近年来，社交网络因为其信息传播范围广、速度快、用户和信息的数量庞大等特点，逐渐衍生成为巨大的产品营销平台，并从中诞生了一种全新的营销方式：基于用户交互模式的病毒式营销。病毒式营销是通过用户个体之间口头传播的方式将信息的影响力进行扩散的，由此引出其中的一个关键问题：如何寻找社交网络中影响力较大的用户集合作为信息传播的初始种子节点集合，使之能给网络中的其他用户带来最大的影响力，这就是社交网络中的影响力最大化问题的原型。Domingos等人^[1-2]最先提出了影响力最大化问题，之后Kempe等人^[3]进一步将该问题归纳为一个离散最优化问题，其具体描述是：基于信息传播模型寻找影响力最大的指定数量的节点，使得最终网络中受到影响的节点最多，同时还提出独立级联模型、线性阈值模型以及两者的泛化模型用于对社交网络中信息传播的过程进行建模，并得出在这些信息传播模型下，影响最大化问题是NP难的结论，此后涌现出许多解决影响最大化问题的贪心算法和启发式算法。

1.2 研究现状

解决影响力最大化问题的方法主要有两种：贪心算法和启发式算法。贪心算法的时间效率差，但能给出与理论最优解之间的近似度，而启发式算法的时间复杂度低，但由于其仅依赖于网络拓扑结构，所以只能给出一个可行解。

1.2.1 贪心算法

Kempe等人^[3]最早影响力最大化问题归纳为基于信息传播模型寻找影响力最大的k个节点，使得最终网络中受到影响的节点最多的离散最优化问题，得出在不同信息传播模型下，影响最大化问题是NP难的结论。并在此基础上提出了贪心爬山算法，贪心爬山算法的主要思想是随机选择个节点作为初始传播源，从这些初始节点出发模拟影响力在网络中的传播，根据每次传播的结果，将能使最终影响范围最大的节点选为种子节点，这样重复迭代次之后就能得到大小为的种子节点集合。利用贪心算法所求得的解能以近似最优解，即算法的精度能达到63%。由于计算给定种子节点集合的影响力扩散范围是NP难的，因此只有通过多次使用蒙特卡洛模拟的方式才能得到一个相对比较精确的扩散范围，但这样做会导致时间效率低下，所以贪心算法只适合于用来研究小型网络。

由于在独立级联传播模型和线性阈值传播模型下，节点的边际影响效益满足子模性，子模性可以理解为增加任意一个节点到某个集合时所得到的边际效益大于等于将该节点加入该集合所在的超集所得到的边际效益。于是Leskovec等人^[4]针对这一特性提出了CELF算法，大大提高了原始贪心爬山算法的效率。CELF算法在每轮迭代中，利用子模性只估计了部分最可能成为候选节点的边际影响力，避免了多次重复运算，使得该算法比原始贪心算法的运算时间快了700倍。之后Goyal等人^[5]又对CELF算法做出改进，提出了CELF 算法，实验结果表明，CELF 将CELF的时间效率提高了35%～55%。Chen等人^[6]提出了NewGreedy和MixGreedy算法，通过删除原网络图中对传播没有贡献的边有效减少了独立级联模型中的筛选次数。

剩余内容已隐藏，请支付后下载全文，论文总字数：35151字