论文部分内容阅读
影响最大化问题最先由Kempe，Kleinberg和Tardos等人定义的，它研究的是如何寻找少量的种子节点，使得在指定的影响传播模型下在社会网络中最大限度地提高种子节点集合的影响传播值。在影响最大化问题中可扩展性是一个很重要的因素。现有的贪心算法，如Kempe等人提出的贪心算法和该算法的改进算法，都运行得很慢，从而不能扩展到大规模的网络数据中，而现有的启发式算法虽然具有可扩展性，但在运算结果方面不如贪心算法。为了提高现有启发式算法的结果的准确性，本文在线性阈值模型下设计了基于联盟形成的影响最大化算法CFBIM;为了让CFBIM算法能够高效解决超大规模网络上的影响最大化任务，本文提出了基于社团结构挖掘的CFBIM算法。 本文的工作主要在如下两个方面: 1.针对社会网络影响最大化问题，设计了基于联盟形成的影响最大化算法CFBIM。该算法考虑了节点之间的合作特性，将社会网络影响最大化问题转换为节点之间的联盟形成问题，然后根据联盟的影响传播值择优选取指定数量的种子节点。针对联盟形成问题，在CFBIM中分别引入了两种联盟形成策略，即基于动态规划框架的联盟形成策略和简化的联盟形成策略。针对联盟的影响传播值计算问题，提出了CFBIM-Spread算法，使得在整个网络中所有节点的影响传播值的计算能够在网络规模的线性时间内完成。最终的实验表明CFBIM算法在时间效率和种子节点质量方面均优于现有的启发式算法。 2.针对CFBIM算法的可扩展性问题，提出了基于社团结构挖掘的CFBIM算法。该算法首先对社会网络进行社团发现，然后利用事先训练好的预测模型确定每个社团应挖掘多少个种子节点，最后利用CFBIM算法在各个社团中挖掘指定数量的种子节点。这种改进方案使原有的CFBIM算法能够适应超大规模网络（如100万节点以上）中的影响最大化任务。最终的实验表明基于社团结构挖掘的CFBIM算法在运算效率上优于原CFBIM算法。