基于最小点覆盖和反馈点集的社交网络影响最大化算法

许宇光 潘惊治 谢惠扬



基于最小点覆盖和反馈点集的社交网络影响最大化算法

许宇光①潘惊治①谢惠扬*②

①(北京大学信息科学技术学院 北京 100871)②(北京林业大学理学院 北京 100083)

社交网络中的影响最大化问题是指在特定的传播模型下，如何寻找个最具影响力的节点使得在该模型下社交网络中被影响的节点最多，信息传播的范围最广。该问题是一个优化问题，并且已经被证明是NP-难的。考虑到图的最小点覆盖和反馈点集中的顶点对图的连通性影响较大，该文提出一种基于最小点覆盖和反馈点集的社交网络影响最大化算法(Minimum Vertex Covering and Feedback Vertex Set, MVCFVS)，并给出了具体的仿真实验和分析。实验结果表明，与最新的算法比较，该算法得到的节点集在多种模型下都具有优异的传播效果，例如在独立级联模型和加权级联模型中超过当前最好的算法，并且还具有更快的收敛速度。

社交网络；影响最大化；传播模型；最小点覆盖；反馈点集

1 引言

社交网络是指由个体及个体之间的关系所组成的一个复杂网络，它与交通网络，通讯网络和生物网络等其他复杂网络相比，包含了更加海量和多元化的信息。自从社交网络出现以来[1,2]，它便在社会个体的信息传播、思想引导和相互影响中发挥着重大作用。近年来，随着大规模在线社交网络(如人人，Facebook, Twitter和微博等)的迅速发展，从个人到个人和从个人到群体的相互作用中探索社会影响引起了人们的广泛兴趣，这是因为社会影响可以作为一种微妙的力量控制社交网络的动态性。……