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

发布时间：2018-03-14 17:45

本文选题：社交网络　切入点：影响最大化问题　出处：《江西理工大学》2017年硕士论文　论文类型：学位论文

【摘要】：近年来,随着互联网和Web2.0技术的不断完善,各种社交网络服务层出不穷,人们越来越习惯于在在线社交网络平台上进行互动交流和信息发布。社交网络因此成为人类知识共享、交互沟通和信息传播的重要媒介和平台。影响最大化问题是社交网络领域的关键问题之一,舆情监测中的源头寻找,市场营销中代理商的选择以及水质监测中的定位等都是影响最大化问题实际应用的展现。影响最大化问题旨在寻找最具影响力的种子节点集合,如何寻找这个集合已被证明是NP-Hard。目前已有的用来解决影响最大化问题的方法主要集中于贪心算法、启发式算法和社区算法。但在大规模网络的求解背景中,其存在时间复杂度高、影响精度低以及鲁棒性差的问题。因此寻求一种高效的方法来解决大规模网络中的影响最大化问题是目前很有意义的研究课题。针对以上问题,本文在研究网络的拓扑结构、影响传播模型、影响最大化算法以及节点影响力评估方法等关键问题的基础上,主要取得了以下成果:(1)本文基于线性阈值模型能够将影响力累积的特性,提出一种以度和影响力作为启发策略的混合启发式算法—DIH算法。该算法将影响最大化问题的求解过程分为度折启发和影响力启发这两个阶段进行处理。第一阶段进行度折启发,快速的找到网络中处于中心地位的节点并将其影响力传播开来,为第二阶段积累影响力;第二阶段进行影响力启发,在寻找影响力最大的节点过程中将第一阶段积累的影响力收集并爆发,从而激活更多的节点。(2)为了提高算法的效率,本文根据节点之间的影响力随着距离增大而减小的理论以及三度影响力原则,提出一种基于节点影响传播路径的影响力计算方法。该方法能够以较快的速度近似计算出DIH算法在第二阶段时所需的节点全局影响力。(3)为了验证DIH算法的有效性,本文在三个真实的网络中将其与几个经典的影响最大化算法进行了对比分析。实验结果表明,与传统的启发式算法相比,该算法能够在保持与其相当的运行效率下获得更好的影响效果,并且在面对不同的网络结构时具有良好的鲁棒性。
[Abstract]:In recent years, with the continuous improvement of the Internet and Web2.0 technology, a variety of social network services emerge in endlessly, people are more and more accustomed to interactive communication and information dissemination on the online social network platform. Therefore, social network has become human knowledge sharing. The problem of maximizing the impact is one of the key problems in the field of social networks. The selection of agents in marketing and the positioning of water quality monitoring are all examples of the practical application of the problem of impact maximization, which aims to find the most influential seed node set. How to find this set has been proved to be NP-Hard.At present, the existing methods to solve the problem of maximizing impact mainly focus on greedy algorithm, heuristic algorithm and community algorithm. It has the problems of high time complexity, low precision and poor robustness. Therefore, it is a meaningful research topic to find an efficient method to solve the problem of maximizing the impact in large-scale networks. Based on the research of the network topology, the influence propagation model, the influence maximization algorithm and the evaluation method of the node influence, etc. This paper is based on the linear threshold model, which can accumulate the influence. This paper presents a hybrid heuristic algorithm, DIH algorithm, which uses degree and influence as heuristic strategy. The algorithm divides the solution process of the problem into two stages: degree heuristic and influence heuristic. Quickly find the central nodes in the network and spread their influence to accumulate influence for the second stage, the second stage of influence inspiration, In order to improve the efficiency of the algorithm, the influence accumulated in the first stage is collected and exploded during the search for the most influential node, thus activating more nodes. Based on the theory that the influence between nodes decreases with the increase of distance, and the principle of three degrees of influence, In order to verify the effectiveness of the DIH algorithm, a new method for calculating the influence of nodes on the propagation path is proposed. The method can approximate the global influence of the nodes in the second stage of the DIH algorithm at a faster speed. In this paper, three real networks are compared with several classical influence maximization algorithms. The experimental results show that, compared with the traditional heuristic algorithm, The algorithm can obtain better effect under the condition of keeping running efficiency equal to it, and has good robustness in the face of different network structure.
【学位授予单位】：江西理工大学
【学位级别】：硕士
【学位授予年份】：2017
【分类号】：TP393.09

【参考文献】