社会网络影响力最小化与谣言抑制问题研究

论文摘要

随着过去十几年在线社会媒体迅猛发展,人们越来越趋向于利用社交平台交流想法、分享信息甚至接受一些创新和新产品,从而加速了信息、产品等传播。此外,在很多其他网络化系统中我们也可以观察到类似传播现象,例如,人类或者动物真实社会网络中的疾病传播、工业网络中的级联失效传播以及计算机网络中的病毒传播。学者们针对如何用数学模型刻画这些复杂的个体行为来帮助人们更好地理解传播现象机制以及如何控制传播过程进行了大量的科学研究,其中被广泛研究的一个核心问题就是影响力最大化问题。影响力最大化问题是指,在指定的传播模型下如何选取初始传播者集合（也称为种子点集合）,使得这些节点可以最大程度影响社会网络中的其他节点,从而使信息或者产品在社会网络中可以获得最大程度的扩散。此类研究具有广泛的实际应用及商业价值,例如市场营销中广告投放、控制谣言传播、意见形成以及预测信息传播等。影响力最大化问题通常考虑积极正面的信息或者创新的传播。而一些不良或负面的东西,如失效、谣言、疾病等会以相似的方式在网络中传播,从而给社会带来不安定或者重大经济损失。因此,研究如何控制和抑制不良信息等传播具有重要意义。本文致力于社会网络谣言抑制与影响力最小化问题研究,主要研究成果分为三部分。在第一部分,本文在线性阈值模型（LTM）下定义了两种不同的影响力最小化问题以形式化及广泛化一些实际社会现象,分别是具有中断情况的损失最小化问题（LMD）与确保传播目标的传播最小化问题（DMGT）。针对LMD问题,首先证明了解决此问题等价于解决一个整数线性规划问题从而求得最优解,同时提出了两个启发式算法以求得近似解;针对DMGT问题,在某些特定情况下提出了求最优解的方法以及一种普遍适用的启发式算法以求得次优解。在第二和第三部分,通过采用不同的谣言抑制策略,我们重点研究和分析谣言抑制问题。首先采用抵消策略,其核心思想是通过传播正确信息与谣言相竞争以抵消掉谣言的影响。基于LTM模型提出了一种竞争型传播模型,称之为具有单向状态转移的线性阈值模型（LT1DT）。LT1DT模型很好地刻画了在同一网络中谣言和真相竞相传播的实际情况,同时克服了现已有竞争型模型中的一些缺陷。在LT1DT模型下,本文主要研究谣言传播最小化问题（MRS）,MRS问题被证明是NP-hard问题。由于其理论困难性,为解决此问题本文提出了三种不同的启发式算法,分别是PageRank,MinGreedy,ContrId。同时为了突出临近效应在抑制谣言传播中的效果,本文提出了它们的约束类型,分别是ProxPageRank,ProxMinGreedy,ProxContrId。其中新提出的启发式算法ContrId和ProxContrId可以保证MRS问题的目标函数在LT1DT模型下单调递减,此特性使得控制谣言的有限预算可以得到合理正确地应用。为了验证各个方法的效率,我们在四种不同的网络中做了仿真实验。仿真结果显示,基于传播动态的方法（ContrId）要优于基于中心性的方法（PageRank）。ContrId与PageRank具有相同计算复杂度,也就是与网络中节点个数呈线性关系,从而可以应用于大规模网络。通过引入临近效应,ContrId抑制谣言的效果与MinGreedy一样好,而其计算速度比MinGreedy要快两到三个数量级。为了控制谣言传播,本文继而采用了网络干扰策略,其核心思想是通过封锁网络中的一些节点来抑制传播。首先,识别最有效k个封锁节点问题的目标函数在LTM模型下被证明是单调但是非次模与非超模的。其次,在LTM模型下基于内聚力的概念我们将识别最有效k个封锁节点问题形式化为一个非线性规划问题。通过引入一些数学技术,本文对非线性问题进行了线性化操作,从而解决识别最有效k个封锁节点问题等价于求解一个整数线性规划。最后,本文证明了在给定的种子集合下,原网络中的传播过程等价于它的激活子网络中的传播过程。这一结论可以有效地削弱整数线性规划的复杂度。为了验证利用整数线性规划解决识别最有效k个封锁节点问题的有效性,我们将此方法与基于贪婪算法的方法以及两个不同的基于中心性的方法做了对比仿真测试。仿真结果显示,整数线性规划解决方法要优于其他三种方法,而且由于其合理的计算时间,此方法可以应用于大规模网络。

论文目录

• 中文摘要
• ABSTRACT
• 摘要
• List of Symbols
• List of Abbreviations
• Chapter 1 Introduction
•   1.1 Background
•   1.2 Related work
•     1.2.1 Influence diffusion models
•     1.2.2 Influence maximization
•     1.2.3 Influence minimization
•     1.2.4 Learning diffusion models
•   1.3 Contributions of the dissertation
•   1.4 Dissertation organization
• Chapter 2 Preliminary
•   2.1 Graph theory
•     2.1.1 Graphs
•     2.1.2 Structural properties
•   2.2 Linear Threshold model
•     2.2.1 Linear Threshold network
•     2.2.2 Properties of linear threshold networks
•     2.2.3 Cohesiveness
•     2.2.4 Algebraic characterization of steady state
•   2.3 Stochastic diffusion models
•     2.3.1 Independent Cascade model
•     2.3.2 Epidemic models
•   2.4 Network data collections and software tools
• Chapter 3 Influence Minimization in Linear Threshold Networks
•   3.1 Introduction
•   3.2 Loss minimization with disruption
•     3.2.1 Problem statement
•     3.2.2 Optimal solution
•     3.2.3 Heuristic solutions
•   3.3 Diffusion minimization with guaranteed target
•     3.3.1 Problem statement
•     3.3.2 Existence of a solution
•     3.3.3 A sufficient condition for optimality
•     3.3.4 Heuristic solution
•   3.4 Experimental study and discussion
•     3.4.1 Experimental set up
•     3.4.2 Experimental results for the LMD problem
•     3.4.3 Experimental results for the DMGT problem
•   3.5 Conclusion
• Chapter 4 Rumor Containment by Spreading Correct Information in Social Networks
•   4.1 Introduction
•   4.2 Linear threshold model with one direction state transition
•     4.2.1 Network structure
•     4.2.2 Diffusion dynamics
•     4.2.3 Analysis of the system’s dynamics
•     4.2.4 Analysis of the steady state
•   4.3 Minimizing rumor spread
•     4.3.1 Problem statement
•     4.3.2 Complexity
•   4.4 Heuristic solutions
•     4.4.1 Unconstrained approaches
•     4.4.2 Constrained approaches
•     4.4.3 Analysis of monotonicity guarantee
•   4.5 Experimental study and discussions
•     4.5.1 Experimental set up
•     4.5.2 Experimental results and discussions
•   4.6 Conclusion
• Chapter 5 Rumor Containment by Blocking Nodes in Social Networks
•   5.1 Introduction
•   5.2 Network evolution with blocking of nodes
•   5.3 Problem statement and properties
•     5.3.1 Problem statement
•     5.3.2 Properties
•   5.4 Optimal solution by NLP and ILP
•     5.4.1 Non-linear formulation
•     5.4.2 Linearized formulation
•     5.4.3 Reducing decision variables and constraints
•   5.5 Heuristic solutions
•   5.6 Experimental study and discussions
•     5.6.1 Experimental set up
•     5.6.2 Experimental results and discussions
•   5.7 Conclusion
• Chapter 6 Conclusions and future research
•   6.1 Contributions
•   6.2 Challenges and future work
• Reference
• Acknowledgement
• Biography

文章来源

类型: 博士论文

作者: 杨兰

导师: 李志武,Alessandro GIUA

关键词: 社会网络,网络化系统,线性阈值模型,影响力最小化,抑制谣言传播

来源: 西安电子科技大学

年度: 2019

分类: 基础科学

专业: 数学,数学

单位: 西安电子科技大学

分类号: O157.5;O221

DOI: 10.27389/d.cnki.gxadu.2019.003144

总页数: 119

文件大小: 3673K

下载量: 61