【作者】 徐浩；

【导师】 潘理；

【作者基本信息】 上海交通大学 ， 信息与通信工程， 2018， 硕士

【摘要】 近年来,随着微信、微博等在生活的中普及,社交网络在人们的生活中逐渐变得不可或缺。利用在线社交网络,人们可以建立社会关系,对同一件热点事件进行交流并分享想法,社交网络逐渐成为一种有价值的营销媒体。同时,人们逐渐发现在社交网络上进行广告投放可以取得很好的反馈,影响力最大化问题也就随之产生。传统的影响力最大化问题主要从个体层面去进行影响力分析,很少考虑在线社交网络中的用户一般都会形成社区这样一个客观事实。从个体层面去挖掘网络中最具影响力的节点是一个NP-hard问题,现有研究中的贪婪算法可以保证其解的近似最优,但是其不足之处在于,在大规模网络上该算法运行时间成本较高。基于此,为了提高在大规模网络上解决此问题的算法的运行效率,本文提出基于社区的影响力最大化算法NVPA-IM(Neighborhood Vector Propagation Algorithm-Influence Maximization)算法,该算法主要利用网络的社区结构选择影响力最大的k个节点。本文主要包括以下几点:第一、在社交网络中,具有同样属性的用户联系更趋向于紧密,那么在社交网络中就会形成各种虚拟社区结构。而挖掘网络中的社区结构对于人们理解信息在网络中的传播具有重要的作用。本文提出的解决影响力最大化问题的算法的第一步就是获取网络的社区结构。选择何种社区划分算法是一个需要考量的问题,本文基于社区划分算法的性质,选择NVPA社区划分算法,并且选择具有代表性的贪心算法快速纽曼算法FN(Fast Newman),基于相似度的聚合算法HClustering(Hierarchical Clustering)及经典的标签传播算法LPA(Label Propagation Algorithm)作为对比算法对网络进行社区划分,并从影响力的角度对划分结果进行对比分析。第二、本文分析了从社区角度出发的种子节点选取算法。传统的从网络中选择节点的策略主要有两种:启发式策略和贪心策略。算法效率较高的是启发式策略,度中心算法和随机算法是两种典型的启发式策略,一般情况下作为对比算法使用。贪心策略主要是贪婪爬山算法。该算法精度很高,但是效率低。而本文基于NVPA社区划分算法的性质,提出了一种度中心算法的扩展算法NVPA-IM种子节点选取算法,并且从影响覆盖的角度对NVPA-IM算法进行了性能验证。更多还原

【Abstract】 In recent years,with the popularity of WeChat,Weibo,etc.,in life,social networks have gradually become indispensable in people’s lives.Using online social networks,people can establish social relationships.Two people in the real world that are far apart can communicate and share ideas,and review the same hot events.Social networks have gradually become a valuable marketing medium.At the same time,people gradually found that advertising on social networks can get good feedback,and the problem of maximizing influence arise too.The traditional problem of influence maximizaton is mainly from the individual level to analyze influence,and it was seldomly considered that users in an online social network generally form an objective fact such as a community.It is an NP-hard problem to mine the most influential node in the network from the individual level.The greedy algorithm in the existing research can guarantee the approximate optimality of its solution,but its disadvantage is that the algorithm is on a large-scale network.Runtime costs are higher.Based on this,in order to improve the efficiency of the algorithm to solve this problem in large-scale networks,this paper proposes an algorithm NVPA-IM(Neighborhood Vectorhood Propagation Algorithm-Influence Maximization)based on network coarsening to maximize the influence.This algorithm uses the community structure of the network to select the K nodes that have the greatest influence.This article mainly includes the following points:First,in social networks,user relationships with the same attributes tend to be closer so that community structures formed.Mining community structure in the network plays an important role in understanding the spread of information in the network.Therefore,the first step in solving the problem of maximizing influence is to obtain the community structure of the network.For community division,this paper selects NVPA algorithms.At the same time,this paper selects some representative algorithms such as greedy algorithm FN(Fast Newman)and similarity aggregation algorithm H-Clustering and the label propagation algorithm LPA(Label Propagation Algorithm)for comparision.At last,this paper analysis the results of the division comparative from the perspective of influence.Second,this paper analyzes the seeds node selection algorithm from the perspective of the community.There are two main strategies for selecting nodes from the network: heuristic strategy and greedy strategy.The higher efficiency of the algorithm is the heuristic strategy.The degree center algorithm and the random algorithm are two typical heuristic strategies.In general,they are comparison algorithms.Greedy strategies are mainly greedy hill climbing algorithms.The accuracy of this algorithm is high,but its efficiency is low.Based on the nature of NVPA community partitioning algorithm,this paper proposes a new NVPA-IM seeds node selection algorithm based on degree center algorithm and analysis the NVPA-IM algorithm from the perspective of influence.更多还原