社会网中三种类型种集发现算法研究

摘要

在对社会网的研究中，影响传播问题的研究占有重要地位，一直是人们研究的重点问题。然而现有的大部分研究忽略了一个重要的事实，即地理位置信息对于社会网的影响传播问题是至关重要的，许多像位置敏感的口碑营销一类的真实应用都有地理位置的需求。为此，本文将地理位置因素引入到社会网中，分别研究了最小种集选取问题、利润最大化种集选取问题和影响事件组织者选取问题。本文的主要研究成果有:
　　1.在传统的最小种集选取问题中引入地理位置因素，提出了位置敏感的社交网中最小种集选取算法问题。对该问题进行了深入研究，发现该问题是NP-hard问题，并提出一种朴素的贪心算法MS-Greedy。MS-Greedy虽具有近似保证，但其计算量太大。为满足在线查询的需求，我们又提出了另外两种高效的算法Bound-based和Partition-Assembly-based。在大量真实数据上进行实验，实验结果表明:本文算法能够有效地解决位置敏感的J-MIN-Seed问题。
　　2.在传统的利润最大化问题中引入地理位置因素，提出了位置敏感的社交网中利润最大化种集选取算法问题。在经典的IC模型中，融入价值和售价因素，提出了新的IC-Ⅴ模型，并证明在该模型下研究的问题是NP-hard问题。提出一种贪心算法Greedy，并在Greedy算法中融入三种制定售价的策略，提出求解位置敏感的社交网中利润最大化种集选取问题的三种算法。最后，在大量真实的数据上进行实验，验证三种算法的效率。
　　3.在传统的影响事件组织者选取问题中引入地理位置因素，提出了位置敏感的社交网中影响事件组织者选取算法问题。首先举例说明该问题的重要性，形式化该问题，并证明其是NP-hard问题。其次，参考前人的工作，将已有的两种贪心算法用于求解该问题，由于贪心算法可能遗漏结果，我们提出了两种近似算法。最后，在大量真实数据上进行实验，对这四种算法进行比较，证明我们算法的有效性和高效性。

目录

摘要

第1章 绪论

1．1 研究背景和意义

1．2 国内外研究现状

1．2．1 影响传播模型

1．2．2 影响最大化算法

1．2．3 最小种集选取算法

1．2．4 利润最大化种集选取算法

1．2．5 影响事件组织者选取算法

1．3 本文主要研究内容

1．4 本文的组织安排

第2章 位置敏感的社交网中最小种集选取算法

2．1 引言

2．2 问题定义

2．2．1 预备知识

2．2．2 基于树的近似模型

2．2．3 问题定义

2．3 算法

2．3．1 MS-Greedy算法

2．3．2 Bound-based算法

2．3．3 Partition-Assembly-based算法

2．4 实验结果与分析

2．4．1 实验设置

2．4．2 实验结果

2．5 本章小结

第3章 位置敏感的社交网中利润最大化种集选取算法

3．1 引言

3．2 问题定义

3．2．1 IC-V模型和问题定义

3．2．2 约束条件的利润最大化问题

3．2．3 一般情况的利润最大化问题

3．3 算法

3．3．1 种集选择算法

3．3．2 售价策略算法

3．4 实验结果与分析

3．4．1 实验设置

3．4．2 实验结果

3．5 本章小结

第4章 位置敏感的社交网中事件影响组织者选取算法

4．1 引言

4．2 问题定义

4．3 算法

4．3．1 贪心算法

4．3．2 近似算法

4．4 实验结果与分析

4．4．1 实验设置

4．4．2 实验结果

4．5 本章小结

结论

参考文献

致谢

攻读硕士学位期间发表的学术论文

声明