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