论文部分内容阅读
随着互联网技术的飞速发展,人们进入了连接一切的互联网时代。作为新兴崛起的一种互联网应用,社交网络满足了人们固有的社交需求,成为了人们分享信息的重要平台。社交网络信息传播的便捷性带来巨大机遇的同时也带来了前所未有的挑战。一方面,社交网络促进了社会交流、方便了民众生活,催生了新的商业模式;另一方面,社交网络也成了各种网络舆情事件的滋生地。因此,深入探索社交网络中的信息传播规律对于舆情监控、社会治理、商业变革都有重要意义。基于以上背景,本文针对传统社交网络信息传播研究仅仅关注信息传播本身的局限性,展开了社交网络中的信息传播效应优化方法研究,分别从动态传播过程、静态网络结构以及结合动态传播过程和静态网络结构三个方面入手,研究了三个问题:信息传播覆盖最大化问题,稠密子图统一挖掘框架问题以及信息传播活跃度最大化问题。具体而言,本文主要的贡献如下。首先,从信息传播的动态过程出发研究了信息传播覆盖最大化问题。经典的影响力最大化问题只考虑信息传播中的激活结点,忽略非激活结点可能的价值,而实际上非激活结点中包含了知晓信息的信息感知结点。要探索信息传播产生的辐射效应,准确建模信息传播覆盖的范围,就必须同时考虑信息的传播者(激活结点)和信息的阅读者(信息感知结点)。为此,本文提出了信息覆盖最大化问题,该问题的目标函数在考虑了激活结点的数量的同时还考虑了信息感知结点的数量,因此能准确地度量信息传播的覆盖范围。为了深入理解信息传播的辐射效应,本文全面分析了信息覆盖最大问题的性质,证明了该问题的计算复杂度,探索了目标函数的性质。在此基础上,本文设计了贪心算法等三种不同的求解算法,并在三个真实数据集上验证了算法的良好性能,同时证实了影响力最大化问题与信息覆盖最大化问题的区别。最后,本文进一步探索了如何设定信息感知结点相对价值的问题,将信息覆盖最大化进行了泛化与推广。其次,从社交网络的静态结构出发研究了稠密子图统一挖掘框架问题。社交网络中的用户往往以紧密连接的社团存在,可以说社团是社交网络的骨架。对于单个用户而言,不同的社团意味着不同的社交圈子,因此为了探索用户的社交圈子,需要挖掘不同大小和密度的稠密子图。相关研究虽然能挖掘特定大小与密度权衡下的稠密子图,但是系统探索大小与密度权衡的统一框架仍是空白。为此,从二次规划的角度,本文提出了稠密子图的统一挖掘框架。该框架统一了已有的和本文新提出的目标函数,可以系统地探索大小与密度之间的权衡。为了深入探索框架的性质,本文分别从数值优化和图论的角度对框架对应的优化问题进行了分析,并扩展了收缩-扩展算法以求解框架对应的优化问题。在四个数据集上,本文对提出的统一框架进行了实验分析,实验结果证实框架确实能挖掘不同大小与密度的子图。最后,综合考虑传播的动态过程和静态的网络结构,研究了信息传播活跃度最大化问题。基于影响力传播的优化问题都是以"点"的视角看待问题的,把网络中的结点当成孤立的个体来对待,忽略了这些结点之间的联系。然而,结点之间存在复杂的网络结构,在信息传播过程中可能产生各种交互活动。因此,要探索信息传播产生的交互效应,准确建模信息在网络中的活跃度,就必须切换视角,从"边"的视角去看待网络中的激活结点,将他们当成一个相互之间有紧密联系和交互的整体来看待。为此,本文提出了活跃度最大化问题,该问题以传播导出子图为建模目标,优化传播导出子图上的交互强度总和,因此能准确刻画信息在网络中的活跃度。为了深入理解信息传播的交互效应,本文全面分析活跃度最大化问题的性质,证明了该问题的计算复杂度,讨论了该问题的可近似性,建立了该问题与最稠密子图发现问题之间的联系,并探索了目标函数的性质。为了求解该问题,本文为目标函数分别设计了上界和下界,并分析了上界和下界的优化性质。在此基础上,本文提出了活跃度及其上下界的无偏估计,然后设计并高效实现了一种基于采样的算法,并得到了该算法的一个依赖于数据的近似因子。在两个真实数据集和两个合成数据集上,本文验证了提出的算法的性能和近似因子,并分析了影响力和活跃度之间的关系。