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

发布时间：2018-06-08 14:12

本文选题：影响最大化 + 社会网　；参考：《黑龙江大学》2016年硕士论文

【摘要】：在对社会网的研究中,影响传播问题的研究占有重要地位,一直是人们研究的重点问题。然而现有的大部分研究忽略了一个重要的事实,即地理位置信息对于社会网的影响传播问题是至关重要的,许多像位置敏感的口碑营销一类的真实应用都有地理位置的需求。为此,本文将地理位置因素引入到社会网中,分别研究了最小种集选取问题、利润最大化种集选取问题和影响事件组织者选取问题。本文的主要研究成果有: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问题。其次,参考前人的工作,将已有的两种贪心算法用于求解该问题,由于贪心算法可能遗漏结果,我们提出了两种近似算法。最后,在大量真实数据上进行实验,对这四种算法进行比较,证明我们算法的有效性和高效性。
[Abstract]:In the study of social network, the study of influence communication has been the focus of research. However, most of the existing studies ignore the important fact that geographical location information is essential to the influence of social networks, and many real applications such as location-sensitive word of mouth marketing have geographical needs. Therefore, this paper introduces geographical location factor into social network, and studies the selection of minimum set, profit maximization and event organizer respectively. The main research results of this paper are as follows: 1. In this paper, the geographical location factor is introduced into the traditional minimum set selection problem, and an algorithm for selecting the minimum set in a location-sensitive social network is proposed. It is found that the problem is NP-hard, and a simple greedy algorithm, MS-Greedy.MS-Greedy, is proposed. In order to meet the requirement of online query, we propose two other efficient algorithms, boundary-based and Partition-Assembly-based-based. Experimental results on a large number of real data show that the proposed algorithm can effectively solve the location-sensitive J-MIN-Seed problem. This paper introduces the geographical location factor into the traditional profit maximization problem, and puts forward the algorithm of selecting the profit maximization species set in the location-sensitive social network. In the classical IC model, a new IC-V model is proposed by incorporating the value and price factors, and it is proved that the problem studied in this model is NP-hard. A greedy algorithm named Greedyis proposed and three pricing strategies are incorporated into greedy algorithm. Three algorithms for selecting profit maximization sets in location-sensitive social networks are proposed. Finally, experiments are carried out on a large number of real data to verify the efficiency of the three algorithms. This paper introduces the geographical location factor into the traditional selection problem of event organizer, and puts forward the problem of how to select the event organizer in the location-sensitive social network. Firstly, the importance of the problem is illustrated, the problem is formalized and proved to be NP-hard. Secondly, referring to the previous work, two kinds of greedy algorithms are used to solve the problem. Because the greedy algorithm may miss the results, we propose two approximate algorithms. Finally, experiments on a large number of real data show that our algorithm is effective and efficient.
【学位授予单位】：黑龙江大学
【学位级别】：硕士
【学位授予年份】：2016
【分类号】：TP301.6

【相似文献】