论文部分内容阅读
近年来，随着在线社交网络和移动终端的迅速发展，社交网络愈来愈成为信息传播的重要载体。基于“病毒式营销”的思想，影响力最大化问题旨在寻找社交网络中k个初始激活用户，在一定的传播模型下，最终这k个用户最终能够激活的用户数目最大。传统的影响力最大化问题中是在理想的传播条件下求解，忽略了很多信息传播的细节，因而其求解结果往往不能直接应用实际中去。基于此，本文考虑现实情景中的影响力最大化问题，求解受限传播条件下的社交网络中具备影响力的节点。本文主要研究包括以下几点： 第一、在现实社交网络中，信息的传播是受限的，且不同的节点的传播能力是不同的，考虑到这个传播特性我们提出基于限制传播距离的影响力最大化问题，用节点的限制传播距离来表示其有限的传播能力。为了求解此问题，文章首先提出符合此场景的传播模型ICLPD模型。随后从理论上证明了在ICLPD模型下的影响力最大化问题的影响力函数具备子模性，继而可以用贪心算法得到一个至少63％精度保证的解。此外为了提高算法的效率，针对ICLPD模型的特点，文章还设计一种基于节点的局部影响力的启发式算法求解，相比于贪心算法其复杂度大大降低了。 第二、本文考虑现实场景中传播时间受限的竞争影响力最大化问题，即在现实场景中同时存在多个信源在网络中竞争性地传播，并且信息只能传播有限的时间。同样的，为了寻找上述场景中影响力最大的节点，文章首先提出适合此场景下的传播模型CIC-M模型，随后证明了在此限制传播的竞争市场中，一个后入市场者的影响力函数满足子模性。因而，对这个后入市场者，他在选择初始的推广用户时应当采用一个贪心的算法去选择，这同样是由子模性函数的性质而得到的结论。 第三、本文在真实的网络数据集上从算法精度和算法效率两方面对求解ICLPD模型和CIC-M模型下影响力最大化问题的算法进行对比验证。可以发现无论在ICLPD模型还是在CIC-M模型下，贪心算法的精度总是最高的，这是因为在两种受限情景下其影响力函数都是子模函数，可以应用子模性用贪心算法来求解，算法的结果能够保证(1?1/e)的算法精度。此外，贪心算法在应用于大规模网络时，其效率过低。本文提出的LIDH算法能够有效地解决大规模网络中的影响力最大化问题，算法在仅损失部分精度的条件下能够高效地求解ICLPD模型下的具备影响力的节点。