基于Memetic计算的社交网络影响最大化研究

发布时间：2018-03-06 03:20

本文选题：社交网络　切入点：社区结构　出处：《西安电子科技大学》2015年硕士论文　论文类型：学位论文

【摘要】：社交网络影响力分析已经成为社交网络分析的重要方面,而其中的社交网络影响最大化问题也受到越来越多的关注,特别是Web 2.0时代下在线社交网络平台的兴起为影响最大化问题的研究提供了更加丰富的平台和研究数据。社交网络影响最大化问题是研究如何在社交网络中选择有限个数的影响力节点而使影响力传播达到最大。这个问题的研究对病毒式营销,推荐系统和突发事件检测等领域有重要意义。近年来,越来越多的影响最大化方法被提了出来,这些算法大致可以分为三类:针对贪婪算法的改进算法,基于社交网络社区结构特性的算法,基于社交网络节点特性的启发式方法。其中,针对贪婪算法的改进算法可以提升贪婪算法的效率,但仍不适合用于大规模社交网络中;基于社交网络社区结构特性的算法可以获得较好的效果和效率;基于社交网络节点特性的启发式方法的效率最高,但其得到的影响力节点的效果却不好。Memetic算法是近年来进化计算领域的一个研究热点,它是一种基于群体的全局搜索和基于个体的局部搜索的结合体,可以弥补这两者单方面的不足,获得较快的搜索效率和令人满意的结果。本文利用社区结构和Memetic算法的优点,将其应用于社交网络影响最大化问题中。本文所做的主要工作如下:(1)研究了社交网络中节点之间的结构相似性对社交网络影响最大化问题的影响,提出了基于节点相似性的度中心性方法。在该方法中,我们用节点之间的结构相似性来排除与度大的节点相似的节点,以此来减少影响力节点之间影响力传播的重叠,从而获得较大的影响力传播。(2)研究了Memetic算法在社交网络影响最大化问题上的应用。我们提出了基于Memetic算法的影响最大化问题,将局部搜索策略加入Memetic算法中,改善了传统遗传算法收敛速度慢,容易陷入局部最优的缺点。同时,该算法与社交网络的社区结构特性结合,缩小了影响力节点的搜索空间,改善了网络规模大算法搜索空间大的缺点,加快了算法的收敛。(3)我们针对前面两方面的工作分别在三个不同规模的真实网络上进行实验。针对第一个工作,我们研究了节点相似性对不同网络的影响和基于节点相似性方法对影响最大化问题的有效性。针对第二个工作,我们首先对社区结构和局部搜索策略的有效性进行实验,然后对提出的算法的效果和效率进行实验。
[Abstract]:Social network impact analysis has become an important aspect of social network analysis, and the problem of maximizing the impact of social network has attracted more and more attention. In particular, the rise of online social networking platforms in the era of Web 2.0 provides a richer platform and research data for the study of impact maximization. The problem of maximizing the impact of social networks is to study how to choose among them. A limited number of influence nodes to maximize the spread of influence. In recent years, more and more impact maximization methods have been proposed. These algorithms can be divided into three categories: improved algorithms for greedy algorithms, The algorithm based on the community structure characteristic of social network and the heuristic method based on the characteristic of social network node, among them, the improved algorithm for greedy algorithm can improve the efficiency of greedy algorithm, but it is still not suitable for large-scale social network. The algorithm based on the characteristics of social network community structure can obtain better effect and efficiency, and the heuristic method based on the characteristics of social network nodes is the most efficient. However, the effect of its influence nodes is not good. Memetic algorithm is a hot topic in the field of evolutionary computing in recent years. It is a combination of global search based on population and local search based on individual. It can make up for the shortcomings of these two methods and obtain fast search efficiency and satisfactory results. This paper makes use of the advantages of community structure and Memetic algorithm. The main work of this paper is as follows: 1) the influence of structural similarity between nodes in social network on the problem of maximizing the influence of social network is studied. In this method, the structural similarity between nodes is used to eliminate nodes similar to large nodes, so as to reduce the overlap of influence propagation between influential nodes. In this paper, we study the application of Memetic algorithm in the problem of maximizing the influence of social networks. We propose the problem of maximizing the influence based on Memetic algorithm and add the local search strategy to the Memetic algorithm. The traditional genetic algorithm has the disadvantage of slow convergence and easy to fall into local optimum. At the same time, the algorithm combines with the community structure characteristics of social network, and reduces the search space of the influential nodes. It improves the shortcoming of large network size algorithm search space, and accelerates the convergence of the algorithm.) We do experiments on three real networks of different scales in view of the first two aspects of the work. For the first work, we do experiments on three real networks of different scales. We study the effect of node similarity on different networks and the effectiveness of node similarity based approach for maximizing impact. In the second work, we first test the effectiveness of community structure and local search strategy. Then the effect and efficiency of the proposed algorithm are tested.
【学位授予单位】：西安电子科技大学
【学位级别】：硕士
【学位授予年份】：2015
【分类号】：TP393.09

【相似文献】