社交网络影响力最大化的研究

发布时间：2018-04-16 03:30

  本文选题：影响力最大化 + 积极影响力　； 参考：《南京航空航天大学》2016年硕士论文

【摘要】：近几年来随着社交网络的兴起和快速发展,越来越多的学者开始研究社交网络,并挖掘其应用价值。社交网络影响力最大化问题成为社交网络研究领域的热点之一。社交网络影响力最大化是指在社交网络中找出一定数量影响力高的用户,使社交网络中受到他们影响的用户数量最多。该研究通常被应用于病毒营销。社交网络影响力最大化问题通常从传播模型和算法两个方面进行研究。本文通过深入地分析近年来该问题的研究工作,对现有工作存在的不足进行改进,提出新的传播模型和算法,并通过在真实数据集上的实验验证了所提传播模型和算法的有效性。本文的主要研究工作体现在以下几个方面:(1)通过分析符号网络的特性和积极影响力在病毒营销中的重要性,提出了符号网络中积极影响力最大化问题。为了解决这个问题,首先在线性阈值模型上加入用户的态度和用户之间的关系,提出LT-A模型;随后证明影响力传播函数在该模型下具单调性和子模性,积极影响力最大化问题在该模型上是NP难问题,进而可以用贪婪算法解决该问题;本文最终提出LT-A Greedy算法解决该问题;通过在真实社交网络数据集上的实验验证了所提模型和算法的有效性。(2)贪婪算法在解决积极影响力最大化问题时,时间效率低,不适用于大规模社交网络,在上述研究工作的基础上,本文根据三度影响力原则提出了基于三度影响力的启发式算法。三度影响力原则是指社交网络中用户的行为会影响到三度之内的朋友,超出这三度自身的影响力就会逐渐消失;它是影响力在社交网络上传播所遵循的规律,并且社交网络的规模越大三度影响力原则就会越明显。基于三度影响力的启发式算法就是根据这个特性选择出三度影响力大的节点作为种子节点的启发式算法。通过在真实社交网络数据集上的实验验证了该启发式算法的运行时间比贪婪算法更短,且算法精度接近于贪婪算法。
[Abstract]:In recent years, with the rise and rapid development of social networks, more and more scholars began to study social networks and explore their application value.The problem of maximizing the influence of social networks has become one of the hot topics in the field of social networks.To maximize the influence of social networks is to find out a certain number of high-impact users in the social network, so that the number of users affected by them is the most in the social network.The study is usually applied to viral marketing.The problem of maximizing the influence of social networks is usually studied from two aspects: propagation model and algorithm.By deeply analyzing the research work of this problem in recent years, this paper improves the shortcomings of the existing work, and puts forward a new propagation model and algorithm.The validity of the proposed propagation model and algorithm is verified by experiments on real data sets.The main research work of this paper is as follows: 1) by analyzing the characteristics of symbol network and the importance of positive influence in virus marketing, this paper puts forward the problem of maximizing positive influence in symbol network.In order to solve this problem, the LT-A model is proposed by adding the user's attitude to the linear threshold model, and then the influence propagation function is proved to be monotonic and submodular under the model.The positive influence maximization problem is NP-hard problem in this model, which can be solved by greedy algorithm. Finally, this paper proposes LT-A Greedy algorithm to solve the problem.Experiments on real social network datasets demonstrate the effectiveness of the proposed model and algorithm. The greedy algorithm is not suitable for large-scale social networks because of its low time efficiency in solving the problem of maximizing the positive influence.Based on the above research work, this paper presents a heuristic algorithm based on the three-degree influence principle.The principle of three degrees of influence refers to the fact that the behavior of users in social networks will affect friends within three degrees, and that beyond the three degrees of influence will gradually disappear; it is the law followed by the spread of influence on social networks.And the greater the size of social networks, the more obvious is the principle of influence.The heuristic algorithm based on three degrees of influence is to select the node with three degrees of influence as the heuristic algorithm of seed node according to this characteristic.Experiments on real social network datasets show that the heuristic algorithm has shorter running time than greedy algorithm and the accuracy of the algorithm is close to that of greedy algorithm.
【学位授予单位】：南京航空航天大学
【学位级别】：硕士
【学位授予年份】：2016
【分类号】：TP393.09
，

本文编号：1757122