社交网络中的概率支配集问题  

On probabilistic dominating sets in social networks

作　　者：钟昊 陈卫东[1] ZHONG Hao;CHEN Weidong(School of Computer Science,South China Normal University,Guangzhou 510631,China)

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

出　　处：《华中科技大学学报（自然科学版）》2021年第2期85-88,107,共5页Journal of Huazhong University of Science and Technology(Natural Science Edition)

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

摘　　要：针对一种边权重取值范围为[0,1]的无向带权图,提出在社交网络中有实际应用的概率支配集概念。在图中寻找最少点数的概率支配集称为最小概率支配集问题。证明最小概率支配集问题是NP(非确定性多项式)难问题,表明不太可能存在多项式时间复杂度的精确算法。基于次模函数提出了多项式时间复杂度的贪心近似算法,用于求解最小概率支配集问题,得出近似比结果。在真实的社交网络实例上进行实验,结果表明贪心算法所求的概率支配集中节点个数平均占总节点个数的14%~15%.For the undirected weighted graph whose edge weight range was [ 0,1 ],a concept named probabilistic dominating set was proposed,which had practical application in social network. Finding a probabilistic dominating set with the minimum number of nodes in a graph,it was called the minimum probabilistic dominating set problem. It is proved that the minimum probabilistic dominating set problem is NP(non-deterministic polynomial)-hard,which means it is unlikely to be solved precisely in polynomial time. Based on the submodular function,a greedy approximation algorithm with polynomial time complexity was proposed to solve the minimum probabilistic dominating set problem,and the approximation ratio was obtained. The experiments on real social network instances were conducted.The number of nodes in the probabilistic dominating set generated by greedy algorithm accounts for 14% to 15% of the total number of nodes on average.

关 键 词：概率支配集 社交网络 NP难 次模函数 近似算法 

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