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

A Carousel Greedy Algorithm for Positive Influence Dominating Set Problem in Social Network

作　　者：万科 WAN Ke(School of Computer Science, South China Normal University, Guangzhou 510631, China)

机构地区：[1]华南师范大学计算机学院,广东广州510631

出　　处：《计算机与现代化》2020年第9期49-53,59,共6页Computer and Modernization

基　　金：国家自然科学基金资助项目(61370003)。

摘　　要：社交网络中最小正影响支配集问题是一个NP难度的组合优化问题,针对该问题,目前有2种典型的贪心求解算法求解速度较快,但贪心解的质量却有待提高。轮转贪心策略是在不增加贪心算法时间复杂度的前提下提升贪心解的质量,且通过实验研究表明能有效增强一些NP难度问题效果的贪心算法。本文将轮转贪心策略求解正影响支配集的2个贪心算法进行融合来提升贪心算法解的质量,提出相应的轮转贪心算法。实验表明,在典型的真实社交网络实例上,与原有贪心算法相比,本文的轮转贪心算法所获解的质量有一定的提高。The problem of the smallest positive influence dominating set in a social network is a NP-hard combinatorial optimization problem.Aiming at this problem,there are two typical greedy algorithms with fast solving speed at present,but the quality of greedy solution needs to be improved.The carousel greedy method is to improve the quality of greedy solution without increasing the time complexity of greedy algorithm,and for some classical NP-hard problems,the experimental results show that the carousel greedy method can effectively improve their greedy algorithms.In this paper,the carousel greedy method is combined with the two greedy algorithms that have positive influence on the dominant set to improve the solution quality of the greedy algorithm,so as to propose the corresponding rotation greedy algorithm.The experimental results on several real social network instances show that,compared with the original greedy algorithms,the solution quality of the proposed carousel greedy algorithm is improved.

关 键 词：社交网络 NP难度问题 正影响支配集 贪心算法 轮转贪心 

分 类 号：TP301[自动化与计算机技术—计算机系统结构]