万 科
(华南师范大学计算机学院,广东 广州 510631)
随着时代的发展,包括社交网络在内的各种各样的复杂网络逐渐兴起,人们也越来越关注和研究这种类型的网络。如果将复杂网络建模成图,图中点代表对象,图中的点与点之间的关系代表着网络中对象之间的联系。那么对复杂网络的研究就变成了对图的研究。近年来,支配集问题由于其在现实世界中的广泛应用而受到了关注[1-3]。随之而来也有一系列支配集的变体,例如连通支配集、符号支配集、k-重支配集等,这些概念也被广泛应用于优化理论、通讯网络的设计与分析、社会科学、计算复杂性和算法设计等许多领域[3-4]。
最近,有关支配集的一种新的变体被提出来,即正影响支配集(Positive Influence Dominating Set, PIDS)[5-6]。通过找到社交网络的正影响支配集就可以通过该集合对这个网络起到一个积极的影响。例如想在一个社区推广某种产品,如果对社区的每一个用户逐一进行推荐,就会非常费时费力。但可以针对网络中一小群有影响力的用户,选定这些用户可以在市场上产生最大的影响力覆盖范围,先向他们推荐让其接受这项产品,然后通过他们就可以影响到整个社区。当然,要达到时间最短、代价更小,就必须使有影响力的用户更少,即图中的正影响支配集的点数更小。点数最小的正影响支配集叫最小正影响支配集(MPIDS)。求解最小正影响支配集已被证明是一个NP难问题[7-9]。
对于NP难度问题,不太可能有多项式时间的精确求解算法。……