图上影响最大化问题算法分析实践

发布时间：2018-02-04 20:30

本文关键词： 社交网络影响最大化图　出处：《复旦大学》2014年硕士论文　论文类型：学位论文

【摘要】：随着21世纪互联网时代和大数据时代的到来,信息传播的速度和广度达到了前所未有的高峰。在互联网诸多实例应用中,社交网络(social network)及如何利用社交网络进行网络营销(social network marketing)成为了学术界研究的热门话题。网络营销的常见问题是,如何定义营销影响的范围,以及如何选取目标受众达到营销影响的最大化。在一个联系紧密的人群关系中,社交网络可以看作一种用图关系表示的结构,其中每个个体作为图上节点,个体之间的相互关系和影响作为图上边的权重。这样就得到了人群关系的社交网络。利用社交网络的图关系,可以设计相应的算法试图使网络营销在图上影响达到最大化。经典的算法如CELF Greedy, MIA和DegreeDiscount在这一领域中有成熟的发展,又各自具有自身的特点和优势。本文对以上算法及互联网网络分析的其他常用算法(PageRank, HITS)进行了实现,利用真实数据进行模拟,探讨在某一特定社交网络中达到影响最大化的最佳策略。通过比较,得出结论为CELF Greedy算法能够得到稳定的输出结果,而MIA,DegreeDiscount等启发性算法对参数的依赖性较强,需要多次调整输入参数才能达到较优良的性能。作者作为某实际项目的算法设计负责人,将本文介绍的理论和算法在实际项目中进行了实践应用。作为本文贡献的一部分,在文中提出了对“图上影响最大化”问题进行评价的新方法,这种改进的方法可以有效缩短现有算法的运行时间。
[Abstract]:With the advent of the Internet era and big data era in 21th century, the speed and breadth of information dissemination has reached an unprecedented peak. Social network and how to use social network to market social network). Has become the hot topic of academic research. The common problem of network marketing is. How to define the scope of marketing influence, and how to select the target audience to maximize the impact of marketing. In a closely connected crowd relationship, social network can be regarded as a structure represented by graph relationship. Where each individual as the node on the graph, the relationship between the individual and the influence of the graph as the weight of the graph, so as to get the social network of crowd relations. Using the graph of the social network relationship. The corresponding algorithms can be designed to maximize the impact of network marketing on the graph. Classical algorithms such as CELF Greedy. MIA and DegreeDiscount have mature development in this field. Each has its own characteristics and advantages. In this paper, the above algorithms and other commonly used algorithms of Internet network analysis, such as Page Rank (HITS), are implemented, and the real data are used to simulate them. This paper discusses the best strategy to maximize the influence in a particular social network. By comparison, the conclusion is that CELF Greedy algorithm can get stable output results, while MIA algorithm can get stable output results. The heuristic algorithm such as DegreeDiscount has a strong dependence on the parameters, so it is necessary to adjust the input parameters several times to achieve better performance. The author is the person in charge of the algorithm design of a practical project. The theory and algorithm introduced in this paper are applied in practice. As part of the contribution of this paper, a new method to evaluate the problem of "maximum impact on graph" is put forward. This improved method can effectively shorten the running time of existing algorithms.
【学位授予单位】：复旦大学
【学位级别】：硕士
【学位授予年份】：2014
【分类号】：TP393.01

【相似文献】