社交网络影响力最大化传播模型与算法研究

发布时间：2018-07-10 05:33

本文选题：交网络 + 影响最大化　；参考：《安徽师范大学》2014年硕士论文

【摘要】：21世纪,人们获取信息的途径不再局限于报纸、广播和电视,随着 Twitter、Facebook、Flickr等重要社交网络的出现及迅速发展,社交网络逐渐成为了这个时代承载信息的主要媒介。由于社交网络影响力最大化问题的研究在实际应用中有着重要的指导意义,因此,该问题也成为了计算机科学研究的热点。本文围绕社交网络影响力最大化问题的模型与算法展开研究,具体包括：1.给出影响力最大化问题的形式化定义,针对信息传播方式(途径), 分析目前最重要的一些信息传播模型以及影响最大化问题在不同模型下的相应定义,并简要总结影响最大化问题的一些解决方法并分析其利弊,为研究影响力最大化的模型与算法打下理论基础。2.每个节点的不同父节点对该子节点的影响力是不同的,基于此, 指出传统信息传播模型假设的不合理性,提出了一种融合节点相关性与节点重要性的PRP模型(PageRank-based Propagation Model,简称PRP 模型),该模型考虑到社交网络中任何节点的不同父亲节点对该节点有不同的影响强度,实验表明,基于PRP模型的方法在解决影响最大化问题的效果比传统的基于线性阈值模型、加权级联模型和独立级联模型的方法更好,影响力范围更广。由于PRP模型考虑到了社交网络的实际情况,具有较好的实用价值。3.传统贪心算法及其改进算法在大规模的社交网络中解决影响最大化问题的时间复杂度很高,针对该问题,本文基于概率转移矩阵的思想提出了一种扩展的线性阈值模型,并基于该模型提出了一种新的基于概率转移矩阵的影响最大化算法(An New Algorithm Based on Probability Transfer Matrix Method,简称PTMA)。由于PTMA算法节省了每个时间间隔都要统计活跃节点数目的时间,因此,该算法与其他基本贪心算法相比,节省了算法时间,降低了时间复杂度,效率更高,并适用于大规模社交网络。
[Abstract]:In the 21st century, people's access to information is no longer confined to newspapers, radio and television, with the emergence and rapid development of important social networks such as Twitter Facebook Flickr. Social networking has gradually become the main medium for carrying information in this era. Because the research of social network influence maximization has important guiding significance in practical application, this problem has also become a hot spot in computer science research. This paper focuses on the model and algorithm of social network influence maximization problem, including: 1. This paper gives the formal definition of the problem of maximization of influence, analyzes some of the most important information dissemination models and the corresponding definitions of the problem of maximizing the influence under different models, aiming at the way of information dissemination. Some solutions to the problem of impact maximization are summarized briefly, and its advantages and disadvantages are analyzed, which lays a theoretical foundation for the study of the model and algorithm of the maximization of influence. Different parent nodes of each node have different influence on the child node. Based on this, it is pointed out that the assumption of traditional information dissemination model is not reasonable. In this paper, a PageRank-based Propagation Model (PRP Model) is proposed to integrate node correlation and node importance. This model takes into account the fact that any node in a social network has different Father's Day points. Different impact intensity, The experimental results show that the PRP model is more effective than the traditional linear threshold model, weighted cascade model and independent cascade model in solving the problem of impact maximization. Because PRP model takes into account the real situation of social network, it has good practical value. The time complexity of the traditional greedy algorithm and its improved algorithm in solving the most important problem in large-scale social networks is very high. This paper presents an extended linear threshold model based on the idea of probabilistic transition matrix. Based on this model, a new Algorithm based on probability transfer Matrix method (PTMA) is proposed. Because the PTMA algorithm saves the time of counting the number of active nodes at every time interval, it saves the algorithm time and reduces the time complexity compared with other basic greedy algorithms. More efficient and suitable for large-scale social networks.
【学位授予单位】：安徽师范大学
【学位级别】：硕士
【学位授予年份】：2014
【分类号】：TP393.09

【相似文献】