|
|||||
|
|
| 社交网络中的概率支配集问题 | |
| 作者单位： | 华南师范大学计算机学院,广东 广州 510631;华南师范大学计算机学院,广东 广州 510631 |
| 摘 要： | 针对一种边权重取值范围为0,1]的无向带权图,提出在社交网络中有实际应用的概率支配集概念。在图中寻找最少点数的概率支配集称为最小概率支配集问题。证明最小概率支配集问题是NP(非确定性多项式)难问题,表明不太可能存在多项式时间复杂度的精确算法。基于次模函数提出了多项式时间复杂度的贪心近似算法,用于求解最小概率支配集问题,得出近似比结果。在真实的社交网络实例上进行实验,结果表明贪心算法所求的概率支配集中节点个数平均占总节点个数的14%～15%. |
| 关 键 词： | 概率支配集 社交网络 NP难 次模函数 近似算法 |
| 本文献已被 CNKI 万方数据 等数据库收录！ | |