社交网络中的信息传播效应优化方法研究

发布时间：2018-01-07 02:29

本文关键词：社交网络中的信息传播效应优化方法研究　出处：《中国科学技术大学》2017年博士论文　论文类型：学位论文

【摘要】：随着互联网技术的飞速发展,人们进入了连接一切的互联网时代。作为新兴崛起的一种互联网应用,社交网络满足了人们固有的社交需求,成为了人们分享信息的重要平台。社交网络信息传播的便捷性带来巨大机遇的同时也带来了前所未有的挑战。一方面,社交网络促进了社会交流、方便了民众生活,催生了新的商业模式;另一方面,社交网络也成了各种网络舆情事件的滋生地。因此,深入探索社交网络中的信息传播规律对于舆情监控、社会治理、商业变革都有重要意义。基于以上背景,本文针对传统社交网络信息传播研究仅仅关注信息传播本身的局限性,展开了社交网络中的信息传播效应优化方法研究,分别从动态传播过程、静态网络结构以及结合动态传播过程和静态网络结构三个方面入手,研究了三个问题:信息传播覆盖最大化问题,稠密子图统一挖掘框架问题以及信息传播活跃度最大化问题。具体而言,本文主要的贡献如下。首先,从信息传播的动态过程出发研究了信息传播覆盖最大化问题。经典的影响力最大化问题只考虑信息传播中的激活结点,忽略非激活结点可能的价值,而实际上非激活结点中包含了知晓信息的信息感知结点。要探索信息传播产生的辐射效应,准确建模信息传播覆盖的范围,就必须同时考虑信息的传播者(激活结点)和信息的阅读者(信息感知结点)。为此,本文提出了信息覆盖最大化问题,该问题的目标函数在考虑了激活结点的数量的同时还考虑了信息感知结点的数量,因此能准确地度量信息传播的覆盖范围。为了深入理解信息传播的辐射效应,本文全面分析了信息覆盖最大问题的性质,证明了该问题的计算复杂度,探索了目标函数的性质。在此基础上,本文设计了贪心算法等三种不同的求解算法,并在三个真实数据集上验证了算法的良好性能,同时证实了影响力最大化问题与信息覆盖最大化问题的区别。最后,本文进一步探索了如何设定信息感知结点相对价值的问题,将信息覆盖最大化进行了泛化与推广。其次,从社交网络的静态结构出发研究了稠密子图统一挖掘框架问题。社交网络中的用户往往以紧密连接的社团存在,可以说社团是社交网络的骨架。对于单个用户而言,不同的社团意味着不同的社交圈子,因此为了探索用户的社交圈子,需要挖掘不同大小和密度的稠密子图。相关研究虽然能挖掘特定大小与密度权衡下的稠密子图,但是系统探索大小与密度权衡的统一框架仍是空白。为此,从二次规划的角度,本文提出了稠密子图的统一挖掘框架。该框架统一了已有的和本文新提出的目标函数,可以系统地探索大小与密度之间的权衡。为了深入探索框架的性质,本文分别从数值优化和图论的角度对框架对应的优化问题进行了分析,并扩展了收缩-扩展算法以求解框架对应的优化问题。在四个数据集上,本文对提出的统一框架进行了实验分析,实验结果证实框架确实能挖掘不同大小与密度的子图。最后,综合考虑传播的动态过程和静态的网络结构,研究了信息传播活跃度最大化问题。基于影响力传播的优化问题都是以"点"的视角看待问题的,把网络中的结点当成孤立的个体来对待,忽略了这些结点之间的联系。然而,结点之间存在复杂的网络结构,在信息传播过程中可能产生各种交互活动。因此,要探索信息传播产生的交互效应,准确建模信息在网络中的活跃度,就必须切换视角,从"边"的视角去看待网络中的激活结点,将他们当成一个相互之间有紧密联系和交互的整体来看待。为此,本文提出了活跃度最大化问题,该问题以传播导出子图为建模目标,优化传播导出子图上的交互强度总和,因此能准确刻画信息在网络中的活跃度。为了深入理解信息传播的交互效应,本文全面分析活跃度最大化问题的性质,证明了该问题的计算复杂度,讨论了该问题的可近似性,建立了该问题与最稠密子图发现问题之间的联系,并探索了目标函数的性质。为了求解该问题,本文为目标函数分别设计了上界和下界,并分析了上界和下界的优化性质。在此基础上,本文提出了活跃度及其上下界的无偏估计,然后设计并高效实现了一种基于采样的算法,并得到了该算法的一个依赖于数据的近似因子。在两个真实数据集和两个合成数据集上,本文验证了提出的算法的性能和近似因子,并分析了影响力和活跃度之间的关系。
[Abstract]:With the rapid development of Internet technology, people have entered into the connection of all Internet era. As a kind of emerging Internet applications, social network to meet the people's inherent social needs, has become an important platform for people to share information. The convenience of the social network information dissemination has brought great opportunities but also brought hitherto unknown challenge. On the one hand, the social network promotes social communication, facilitate the people's lives, the birth of a new business model; on the other hand, the social network has become a breeding ground for a variety of network public opinion events. Therefore, deep into the exploration of information propagation in social networks for monitoring public opinion, social governance, has important significance for business transformation. Based on the above background, this paper studies the traditional social network information dissemination only focus on the limitations of the dissemination of information itself, the dissemination of information in social network Research on the optimization method of effect, from the dynamic propagation process, static network structure and communication process combined with dynamic and static network structure of the three aspects of three issues: the problem of maximizing the coverage of information dissemination, dense subgraph mining framework and unified information dissemination activity maximization problem. Specifically, the main contribution of this paper as follows. First, research on the dissemination of information covering the maximization problem starting from the dynamic process of information dissemination. The influence maximization problem classic only consider the active nodes in the dissemination of information, ignoring the non value node may be activated, but actually non active nodes contain information perception node information. To explore the knowledge radiation effect of information the scope of information dissemination, accurate modeling coverage, we must also consider the disseminator of information (active nodes) and information reader (letter Information sensing node). For this reason, this paper presents an information coverage maximization problem, the objective function of the problem in consideration of the number of active nodes also consider the number of sensing nodes, so it can accurately measure the coverage of information dissemination. In order to understand the effect of information dissemination, this paper makes a comprehensive analysis the nature of information covering the biggest problem, proved that the computational complexity of the problem, explore the nature of the objective function. On this basis, this paper design a greedy algorithm with three different algorithms, and in three real data sets show the excellent performance of the algorithm, and confirm the difference of influence maximization the maximum problem and information coverage. Finally, this paper further explores how to set the node information perception of relative value, to cover the information maximization of generalization and promotion. Secondly, Based on the static structure of the social network of the dense subgraph mining framework. The unified social network users often exist in close connection with society, can be said that the association is a social network framework. For individual users, different society means the social circle is different, so in order to explore the user's social circle, need the size and density of different mining dense sub graph mining. Although related research to the size and density of dense sub specific balance under the map, but the system of unified framework is still blank size and density balance. Therefore, two from the planning point of view, this paper proposes a unified dense Subgraph Mining Framework. The framework of a unified objective function the existing and proposed in this paper, systematically explores the trade-off between size and density. In order to explore the properties of the framework, this paper from the numerical optimization and graph theory The angle of the corresponding optimization problem framework are analyzed, and expanded the contraction expansion algorithm to solve the optimization problem. The corresponding framework on four data sets, this paper carries on the experimental analysis framework proposed, experimental results show that the framework can tap the different size and density of the sub graph. Finally, considering the the network structure of dynamic and static communication, research information dissemination activity maximization problem. The optimization problem of influence propagation are based on the view of "points" from the perspective of the network as a node in the isolated to treat, ignoring the links between these nodes. However, the complexity of the network structure the presence of nodes in the information dissemination process may produce a variety of interactive activities. Therefore, to explore the interactive effects of information dissemination of accurate information in network modeling activity, must be cut Change the perspective to look at active nodes in the network from the perspective of "edge", they will be as a close contact and interaction between the whole. Therefore, the proposed activity maximization problem, the problem is to spread the induced subgraph for modeling, optimization of transmission interaction strength sum induced subgraph on the map, so it can accurately describe the information in the network activity. In order to understand the interaction of information dissemination, this paper makes a comprehensive analysis of the nature of the activity maximization problem, proved that the computational complexity of the problem, discussed the approximability of the problem, the problem is established and the most dense sub graph links between problems, and explores the nature of the objective function. In order to solve this problem, this paper designed the objective function of the upper and lower bounds, and analyzes the properties of the upper and lower bounds on the optimization. Based on this, proposed to live Jump of the lower and upper bounds of unbiased estimation, then design and efficient implementation of a sampling based algorithm, and get a dependence on the algorithm for data approximation factor. In two real data sets and two synthetic data sets, this paper verified the performance of the proposed algorithm and the approximation factor. And analyzes the relationship between influence and activity.

【学位授予单位】：中国科学技术大学
【学位级别】：博士
【学位授予年份】：2017
【分类号】：TP393.09;G206

【相似文献】