社会网中事件组织者选取算法研究

论文摘要

在社会网中,经典的影响最大化问题是寻找在社会网中的给定的正整数个种子用户,通过这些种子用户激活其他用户,能够获得最大化期望的影响范围。而影响事件组织者选取问题（Search Influential Event Organizers）的目标是选择一个种集,该种集不仅具有能够组织某事件的技能或属性,同时还能够影响最多的人参与到该事件中来。虽然传统的组织者选取问题得到了一定程度的研究,但是现有的研究却忽略了很多因素和问题,因此本文的主要研究成果有:1.在传统的权重级联模型（Weighted Cascade Model）中引入属性相似性对传播概率的影响,在权重级联模型中,一个节点被任意前驱节点影响的概率是其入度的倒数,这显然不能准确地描述真实的影响概率。例如:两个相邻节点的属性重复的越多,表明这两个节点的关系越密,影响概率应该越大。为了更好的对属性相似度进行度量,本文引入了Jaccard相似度公式来对影响概率进行更为准确地计算。2.在传统的组织者选取问题中加入时间因素,事件是在特定的时间范围内进行的,因此选取的组织者的活动时间应该包含事件运行的时间范围,加入时间因素后,影响最大化算法也要做出相应的变化。因为,如果组织者影响的节点的活动时间不能包含事件发生的时间,被影响的节点即使被成功激活,也不能参与到事件中来。3.将多重网络影响因素加入到组织者选取问题中,传统的组织者选取问题是针对单个网络的传播,而在真实情况下信息可以通过多个网络进行传播,考虑到信息可以在多个网络中传播,本文结合前人对多重网络影响最大化的研究,提出了基于多渠道影响最大化的组织者选取问题,并给出了两种解决方法。4.针对包含节点数量最少的组织者种集选取问题,在原始打分算法的基础上提出了Min-Score算法,首先通过理论和实验证明Min-Score算法同其他两种基于打分算法的衍生算法相比具有更小的时间复杂度,最后通过实验证明同基于鸽笼原理的两种衍生算法相比,Min-Score算法在时间方面优于这两种算法,且得到的种集产生的影响范围大于等于二者。

论文目录

• 中文摘要
• Abstract
• 第1章 绪论
•   1.1 研究背景和意义
•   1.2 国内外研究现状
•     1.2.1 影响传播模型研究
•     1.2.2 影响最大化研究
•     1.2.3 组织者选取研究
•   1.3 本文的组织安排
• 第2章 已提出的两种组织者选取算法
•   2.1 影响传播背景知识
•   2.2 问题定义
•   2.3 基于打分原理的组织者选取算法
•   2.4 基于鸽笼原理的组织者选取算法
•   2.5 本章小结
• 第3章 基于属性相似与时间因素的组织者选取算法
•   3.1 属性相似度
•   3.2 TDD算法
•   3.3 两种基于属性相似与时间因素的组织者选取算法
•     3.3.1 TSG算法
•     3.3.2 TPG算法
•   3.4 实验
•   3.5 本章小结
• 第4章 基于多重网络影响下的组织者选取算法
•   4.1 引言
•   4.2 基于蒙特卡罗模拟的方法
•   4.3 基于节点出度的方法
•   4.4 实验
•   4.5 本章小结
• 第5章 最小种集的组织者选取算法
•   5.1 引言
•   5.2 Min-Score算法
•   5.3 实验
•   5.4 本章小结
• 总结
• 参考文献
• 致谢
• 攻读硕士学位期间发表的学术论文

文章来源

类型: 硕士论文

作者: 李佳兴

导师: 张兆功

关键词: 影响最大化,属性相似度,最小种集,时间因素,多重网络,组织者选取

来源: 黑龙江大学

年度: 2019

分类: 基础科学,信息科技

专业: 数学,计算机软件及计算机应用

单位: 黑龙江大学

分类号: O157.5;TP301.6

DOI: 10.27123/d.cnki.ghlju.2019.001610

总页数: 57

文件大小: 2437K

下载量: 9