基于团体的竞争影响力最大化方法研究

论文摘要

竞争影响力最大化问题（Competitive influence maximization,CIM）是指在已知网络中竞争对手种子集分布的情况下,如何选取我方种子集使得我方影响力最大。现有的竞争影响力最大化问题在计算影响力时通常以计算全局受影响的节点数来代表影响范围,即将网络中的多个小团体看作为一个大的整体,而并没有将团体影响考虑在其中。这就可能会导致两个极端问题:一是虽在多个团体具有影响,但并不足以影响任一团体的决策,进而导致的影响丢失;二是对某些团体有过量影响,造成的影响过度（比如,影响某团体超过一半的人就足够争取整个团体,但仍选种试图影响更多其余的）。针对该问题,本文提出并深入研究了基于团体的竞争影响力最大化（Group-based Competitive Influence Maximization,GCIM）问题,主要进行了以下几部分工作:1)在竞争影响力最大化问题中引入团体影响并进行深入研究。将团体影响分为团体内影响和团体间影响,并用一种有效的方式来估算团体影响。将团体影响引入竞争影响力最大问题计算中,改变了现有的以全局受影响节点总数衡量的标准,避免了未考虑到团体效应所产生的影响丢失和影响过度这两种极端情况。2)从预算限制和影响范围限制两个方面对GCIM问题进行研究,提出团体竞争传播（Competitive Group-Linear Threshold,CG-LT）模型,并形式化证明了CG-LT模型下给定预算的团体竞争影响力最大化（B-GCIM）问题是NP难问题,根据对偶性,则CG-LT模型下给定影响范围的团体竞争影响力最大化（S-GCIM）问题也是NP难问题。3)本文中用社区代表团体,通过使划分的社区大小与ground-truth数据集中的基础事实社区的大小分布一致且覆盖率较高,来拟合真实世界。通过在Amazon和Youtube两个真实数据集中的大量实验,验证了团体影响的存在性及其对影响力最大化问题的影响,并分析了团体影响力传播过程的特点以及团体效应与网络团体规模之间的关系。

论文目录

摘要

Abstract

第1章绪论

1.1 影响力最大化问题概述

1.2 研究背景和意义

1.3 国内外研究现状

1.3.1 单实体研究现状

1.3.2 多实体研究现状

1.4 本文主要工作

1.5 论文组织结构

第2章影响力最大化问题相关研究基础

2.1 信息传播模型

2.1.1 线性阈值模型

2.1.2 独立级联模型

2.1.3 多实体传播模型

2.2 社区划分

2.2.1 GN算法

2.2.2 Louvain算法

2.3 影响力最大化问题常用算法

2.3.1 影响力最大化中的贪心算法

2.3.2 影响力最大化中的启发式算法

2.4 本章小结

第3章问题定义与数据预处理

3.1 团体竞争传播模型

3.2 问题定义

3.2.1 团体内影响与团体间影响

3.2.2 NP难证明

3.3 数据集预处理

3.3.1 数据集介绍

3.3.2 实验预处理

3.4 本章小结

第4章给定影响范围的团体竞争影响力最大化

4.1 团体内种子节点选择算法

4.2 团体间团体选择算法

4.3 算法举例说明

4.4 实验验证

4.4.1 数据集

4.4.2 实验设置

4.4.3 评估标准

4.4.4 对比算法

4.4.5 实验结果

4.5 本章小结

第5章给定预算的团体竞争影响力最大化

5.1 团体间团体选择算法

5.2 算法举例说明

5.3 实验验证

5.3.1 数据集

5.3.2 实验设置

5.3.3 对比算法

5.3.4 实验结果

5.3.5 团体影响力传播过程

5.4 本章小结

总结与展望

参考文献

附录A 攻读硕士学位期间所发表的学术论文目录

附录B 攻读硕士学位期间所参与的科研活动

附录C Amazon数据集中MPC算法结果

附录D Youtube数据集中MPC算法结果

致谢

文章来源

类型: 硕士论文

作者: 戴雅君

导师: 李肯立

关键词: 影响力最大化,团体效应,竞争,成本

来源: 湖南大学

年度: 2019

分类: 基础科学

专业: 数学

单位: 湖南大学

分类号: O224

DOI: 10.27135/d.cnki.ghudu.2019.000152

总页数: 64

文件大小: 2916K

下载量: 18

基于团体的竞争影响力最大化方法研究

论文摘要

论文目录

文章来源

相关论文文献

猜你喜欢