社会网络信息传播与影响力最大化研究

发布时间：2018-01-19 11:21

本文关键词： 社会网络信息传播影响力最大化　出处：《南京大学》2016年博士论文　论文类型：学位论文

【摘要】：随着互联网的普及和在线社会网络的发展,研究者可以获取丰富的历史数据,并对社会网络中的信息传播进行分析、预测和利用。作为一种新型的媒介,社会网络中的信息可以像“病毒”一样迅速地在人与人之间传播,因此受到了普遍的关注：一方面,相比于电台、报纸、电视等大众传媒广播的方式,社会网络中的信息传播具有“口口相传”的效应,更容易被人们所信任；另一方面,信息的传播还可能具有级联效应,造成广泛的影响。然而,社会网络中难以预测的个体行为和复杂的拓扑结构,为信息传播的分析和利用带来了极大的挑战。因此,如何通过历史数据挖掘,对信息传播进行分析预测,并进一步利用信息传播达到影响力最大化,为企业宣传、广告营销、舆情监控等提供决策辅助,已成为当前社会网络研究的一个热点问题。针对上述问题,本文首先对信息级联的结构进行挖掘,识别出社会网络信息级联几种典型结构模式,并利用结构模式对信息传播进行预测；然后基于信息传播的模式,分析了多种信息同时传播的交互模型,用信息回溯的方法找到最有影响力的节点；最后研究了在给定预算的情况下,如何通过预算分配来激励这些最有影响力的节点,从而使得影响力的扩散可以达到最大。论文的主要贡献可概括如下：(1)分析信息传播的级联结构,并通过级联结构预测信息未来的传播模式。在社会网络中,信息级联的结构往往和信息传播互相影响。首先,不同机制所驱动的信息传播会导致结构不同的级联,同质性主导的级联往往会发展为宽而浅的结构,而社会影响力主导的级联则会变得深而复杂；其次,不同结构的信息级联会传播到不同的范围和社群,从而影响信息的传播过程。本文采用数据驱动的方法,分析了大量信息级联的传播结构,通过对信息级联的结构进行降维嵌入(embedding)和谱聚类(spectral clustering)，识别出社会网络中的信息级联五种典型的结构模式,并且发现不同结构模式的信息级联之间具有明显差异的特征。根据以上观察,本文引入级联结构来预测信息未来的传播模式,实验结果表明,该方法可以显著提升预测的准确率。(2)研究了多种信息同时传播的交互模型,并识别其中有影响力的节点。社会网络中往往有多种信息在同时传播,而且信息之间可能存在竞争、互利等交互关系。针对这种情况,本文设计了交互信息级联模型来刻画多种信息之间的传播,可以同时考虑信息之间的交互关系和用户对交互信息的选择偏好。在这个模型下,本文首先证明了该问题是NP难的,并提出了一种基于回溯的马尔科夫随机游走(markov random walk)算法：假设信息传播可以达到所有节点,然后通过传播模型进行回溯,找出信息最有可能的来源,即为影响力最大的节点。模拟实验表明,相比于其它常用的算法,本文提出的算法可以在绝大多数情况下取得最好的效果。同时,该算法还可以快速地收敛,因此有很高的运行效率。(3)提出了一个基于预算分配的策略,通过激励社会网络中的初始用户实现影响力最大化。为了激励初始用户实现影响力最大化,以往的工作一般理想地假设用户具有确定的估值,只有分配的预算高于该估值,用户才会成为初始用户；而在实际情况中,在不同的预算下,用户都有可能成为初始用户。本文使用效用函数(utility function)来刻画用户的满意度,假定用户的估值满足一定的概率分布函数。在这个模型下,通过归约证明了该问题的难度。同时,提出了一个离散贪心的算法来找出预算分配的方案：首先将预算均匀地离散化,然后采用迭代的方式将预算依次分配给具有边际增益最大的用户。该方法可以在离散的设置中取得近似最优的结果。进一步,本文还证明了当合理地选择一个离散的粒度后,该算法可以在预算连续的设置下取得1-1/e-o(1)的性能保证。最后,本文还通过更新边际增益的计算和估算传播概率的方法来提升算法的执行效率。实验结果表明,相比于其它已有的方法,离散贪心的算法能显著提高信息覆盖的范围,同时还有非常好的可扩展性。
[Abstract]:With the popularity of the Internet and online social networks, researchers can obtain rich historical data, and the dissemination of information in social network analysis, prediction and use. As a new media, social network information can be like a virus as fast speed in communication between people, so widespread attention: on the one hand, compared to newspapers, radio, television and other mass media broadcast mode, the dissemination of information in social networks with "word of mouth" effect, more likely to be discredited; on the other hand, the dissemination of information also may have a cascading effect, causing widespread influence. However, it is difficult to prediction of individual behavior in social network and complex topology, analysis and utilization of information dissemination has brought great challenges. Therefore, how to use historical data mining, the dissemination of information analysis The prediction, and further use of information dissemination to the influence maximization, for business promotion, advertising and marketing, to provide decision support public opinion monitoring, has become a hot topic of current social network research. Aiming at the above problems, firstly the structure of the cascade of information mining, identified several typical patterns of structure of social network information cascade, and to predict the structure of information dissemination and utilization mode; then based on the mode of information dissemination, the analysis of the interactive model as well as information dissemination, find the most influential nodes for information back; at the end of the budget in a given situation, how to motivate the most influential nodes through the budget allocation, which makes the influence the diffusion can reach the maximum. The main contributions of this thesis can be summarized as follows: (1) the cascade structure analysis of information dissemination, and through the connection level The communication model of forecast information in the future. In the social network, information structure and information dissemination cascade often influence each other. First of all, the dissemination of information driven by different mechanisms lead to a cascade of different structure, leading the development tend to homogeneity cascade structure wide and shallow, and cascade leading social influence will become deep and complex; secondly, information cascades with different structures will spread into different ranges and communities, thus affecting the process of information dissemination. This paper uses the method of data drive, analyzes the structure of communication information cascade, dimensionality reduction through the structure of embedded information cascade (embedding) and spectral clustering (spectral, clustering) identify the information cascade of social networks in five typical modes of the structure, and found the obvious characteristic differences between different modes of the information cascade. According to the above observations, the The introduction of cascade structure to predict the mode of transmission of information in the future, the experimental results show that this method can significantly improve the prediction accuracy. (2) the interaction model studied a variety of information dissemination and recognition at the same time, one of the nodes influential. Social network often has many kinds of information in the dissemination of information at the same time, but also may exist between competition, mutual benefit relations. In view of this situation, this paper designs the interactive information cascade model to describe the spread of a variety of information, can also choose the preference information of the interaction between the user and the interactive information. In this model, the paper proves that this problem is NP hard, and put forward a backtracking based on Markov random walk (Markov random walk) algorithm: the assumption that information transmission can reach all nodes, and then through the back propagation model, find out the information May be the source of the node is the most influential. Simulation results show that compared with other algorithms, the proposed algorithm can achieve the best effect in most cases. At the same time, the algorithm can also fast convergence, so it is very efficient. (3) proposed a budget based on distribution strategy, realize the influence maximization through initial user incentive in social networks. In order to realize the influence maximization incentive initial users, previous work generally assume that the user has a certain ideal valuation, only the allocation of budget is higher than the valuation, the user will become the initial user; but in fact, in the different budget, users are likely to become the initial user. This paper use the utility function (utility function) to describe the user's satisfaction, assume that the user valuations meet the probability distribution function of some. This model is proved by reduction, the difficulty of the problem. At the same time, we propose a discrete greedy algorithm to find the budget allocation scheme: first the budget will be uniformly discrete, then iterative method using the budget successively assigned to the user with maximum marginal gain. This method can obtain near optimal results in the discrete setting. Further, this paper also proves that when selecting a discrete particle size, the algorithm can achieve 1-1/e-o in the setting of budget under continuous (1) performance guarantee. Finally, through the method of updating the marginal gain of the calculation and estimation of propagation probability to enhance the efficiency of the algorithm. The experimental results show that compared with other existing methods, discrete greedy algorithm can significantly improve the coverage of information, also have very good scalability.

【学位授予单位】：南京大学
【学位级别】：博士
【学位授予年份】：2016
【分类号】：G206;TP301.6

【相似文献】