社交网络中正影响支配集问题的轮转贪心算法

2020-09-15 02:10:54万科
计算机与现代化 2020年9期
关键词:策略影响实验

万 科

(华南师范大学计算机学院,广东 广州 510631)

0 引 言

随着时代的发展,包括社交网络在内的各种各样的复杂网络逐渐兴起,人们也越来越关注和研究这种类型的网络。如果将复杂网络建模成图,图中点代表对象,图中的点与点之间的关系代表着网络中对象之间的联系。那么对复杂网络的研究就变成了对图的研究。近年来,支配集问题由于其在现实世界中的广泛应用而受到了关注[1-3]。随之而来也有一系列支配集的变体,例如连通支配集、符号支配集、k-重支配集等,这些概念也被广泛应用于优化理论、通讯网络的设计与分析、社会科学、计算复杂性和算法设计等许多领域[3-4]。

最近,有关支配集的一种新的变体被提出来,即正影响支配集(Positive Influence Dominating Set, PIDS)[5-6]。通过找到社交网络的正影响支配集就可以通过该集合对这个网络起到一个积极的影响。例如想在一个社区推广某种产品,如果对社区的每一个用户逐一进行推荐,就会非常费时费力。但可以针对网络中一小群有影响力的用户,选定这些用户可以在市场上产生最大的影响力覆盖范围,先向他们推荐让其接受这项产品,然后通过他们就可以影响到整个社区。当然,要达到时间最短、代价更小,就必须使有影响力的用户更少,即图中的正影响支配集的点数更小。点数最小的正影响支配集叫最小正影响支配集(MPIDS)。求解最小正影响支配集已被证明是一个NP难问题[7-9]。

对于NP难度问题,不太可能有多项式时间的精确求解算法。……

登录APP查看全文

猜你喜欢
策略影响实验
记一次有趣的实验
哪些顾虑影响担当?
当代陕西(2021年2期)2021-03-29 07:41:24
例谈未知角三角函数值的求解策略
做个怪怪长实验
我说你做讲策略
高中数学复习的具体策略
数学大世界(2018年1期)2018-04-12 05:39:14
NO与NO2相互转化实验的改进
实践十号上的19项实验
太空探索(2016年5期)2016-07-12 15:17:55
扩链剂联用对PETG扩链反应与流变性能的影响
中国塑料(2016年3期)2016-06-15 20:30:00
Passage Four