动态社交网络中的影响力最大化问题研究

发布时间：2018-04-15 22:15

本文选题：影响力最大化 + 动态生长社交网络　；参考：《西安电子科技大学》2014年硕士论文

【摘要】：近年来,随着Twitter等在线社交网站的发展,在社交网络中寻找前k个最具有影响力的用户问题变得越来越重要。即在有限的预算前提下,如何借助“病毒式营销”和“口碑效应”在社交网络中选择若干个最具有影响力的用户开始营销活动,并使得营销活动覆盖尽可能大的范围。目前该问题已经得到众多学者的广泛研究,并且已经提出了相对成熟的贪婪算法和启发式算法。然而,上述工作均基于网络拓扑结构静态不变的假设,忽略了实际社交网络的高度动态性。因为真实的社交网络中个体和个体之间的交互关系随着时间的推移是按照一定的生长规律动态变化的。因此,已有的影响力传播的研究对实际的高动态性的社交网络上的产品推广价值十分有限,如果继续采用静态网络上选择的种子节点可能无法在网络动态变化的环境下达到满意的效果。本文将影响力最大化问题和社交网络图的动态演化相结合,提出一种解决动态生长网络上影响力最大化问题的算法。首先,简单介绍了传统静态社交网络上影响力最大化问题的相关理论知识,包括影响传播模型、种子节点选择策略以及经典的贪心算法和启发式算法;其次,又介绍了动态社交网络的相关理论知识,包括真实网络的特征度量标准、常见的网络分类标准以及ER、BA和FF等经典的动态网络生长模型;最后,针对动态生长网络的影响力最大化问题,提出了解决此问题的D-MGreedyIC算法。该算法将社交网络演化的Forest Fire Model引入影响力传播过程,在考虑到社交网络的动态演化因素的情况下,找到更具有延展性和预见性的种子节点作为影响传播的初始节点。最后,在模拟社交网络数据集以及真实的社交网络数据集上进行了实验,并给出相应的时间复杂度分析。实验验证,该算法较传统算法选择的种子节点在网络拓扑动态变化的环境中具有更高的传播效果,相比传统解决静态社交网络上的影响力最大化算法,该算法考虑到了社交网络图的动态生长因素。因此所选择的种子节点具有延展性和预见性,对于社交网络产品推广具有更好的指导意义。同时,将影响力最大化问题应用到市场营销、消息传播以及广告发布等方面也有着十分重要的现实意义。
[Abstract]:In recent years, with the development of online social networking sites such as Twitter, it has become increasingly important to find the top k most influential user problems in social networks.That is, under the limited budget, how to select several most influential users in social networks with the help of "viral marketing" and "word-of-mouth effect", and make the marketing activities cover as wide a range as possible.At present, the problem has been widely studied by many scholars, and has proposed a relatively mature greedy algorithm and heuristic algorithm.However, the above work is based on the assumption that the network topology is static invariant and ignores the highly dynamic nature of the actual social network.Because the interaction between individuals and individuals in real social networks changes dynamically with the passage of time.As a result, existing research on the spread of influence is of limited value to the promotion of products on practical, highly dynamic social networks.If we continue to use the seed nodes selected on the static network, we may not be able to achieve satisfactory results under the dynamic environment of the network.In this paper, we combine the influence maximization problem with the dynamic evolution of the social network graph, and propose an algorithm to solve the influence maximization problem on the dynamic growth network.Firstly, this paper briefly introduces the theory of influence maximization on traditional static social networks, including influence propagation model, seed node selection strategy, classical greedy algorithm and heuristic algorithm.It also introduces the relevant theoretical knowledge of dynamic social networks, including the real network feature metrics, common network classification criteria, as well as the classic dynamic network growth model such as Ernba and FF. Finally,Aiming at the problem of maximizing the influence of dynamic growth networks, a D-MGreedyIC algorithm is proposed to solve this problem.In this algorithm, the Forest Fire Model of social network evolution is introduced into the process of influence propagation. Considering the dynamic evolution factors of social network, the seed nodes with more ductility and predictability are found as the initial nodes of influence propagation.Finally, experiments are carried out on the simulated social network data set and the real social network data set, and the corresponding time complexity analysis is given.Experimental results show that the algorithm has a higher propagation effect than the seed nodes selected by the traditional algorithm in the dynamic network topology environment, compared with the traditional algorithm to solve static social network impact maximization algorithm.The algorithm takes into account the dynamic growth factor of social network graph.Therefore, the selected seed nodes have ductility and predictability, which has better guiding significance for the promotion of social network products.At the same time, it is of great practical significance to apply the problem of maximization of influence to marketing, news dissemination and advertising.
【学位授予单位】：西安电子科技大学
【学位级别】：硕士
【学位授予年份】：2014
【分类号】：TP393.09

【共引文献】