期刊导航
期刊开放获取
cqvip
退出
期刊文献
+
任意字段
题名或关键词
题名
关键词
文摘
作者
第一作者
机构
刊名
分类号
参考文献
作者简介
基金资助
栏目信息
任意字段
题名或关键词
题名
关键词
文摘
作者
第一作者
机构
刊名
分类号
参考文献
作者简介
基金资助
栏目信息
检索
高级检索
期刊导航
共找到
1
篇文章
<
1
>
每页显示
20
50
100
已选择
0
条
导出题录
引用分析
参考文献
引证文献
统计分析
检索结果
已选文献
显示方式：
文摘
详细
列表
相关度排序
被引量排序
时效性排序
社交网络中的概率支配集问题
1
作者
钟昊
陈卫东
《华中科技大学学报（自然科学版）》
EI
CAS
CSCD
北大核心
2021年第2期85-88,107,共5页
针对一种边权重取值范围为[0,1]的无向带权图,提出在社交网络中有实际应用的概率支配集概念。在图中寻找最少点数的概率支配集称为最小概率支配集问题。证明最小概率支配集问题是NP(非确定性多项式)难问题,表明不太可能存在多项式时间...
针对一种边权重取值范围为[0,1]的无向带权图,提出在社交网络中有实际应用的概率支配集概念。在图中寻找最少点数的概率支配集称为最小概率支配集问题。证明最小概率支配集问题是NP(非确定性多项式)难问题,表明不太可能存在多项式时间复杂度的精确算法。基于次模函数提出了多项式时间复杂度的贪心近似算法,用于求解最小概率支配集问题,得出近似比结果。在真实的社交网络实例上进行实验,结果表明贪心算法所求的概率支配集中节点个数平均占总节点个数的14%~15%.
展开更多
关键词
概率支配集
社交网络
NP难
次模函数
近似算法
原文传递
题名
社交网络中的概率支配集问题
1
作者
钟昊
陈卫东
机构
华南师范大学计算机学院
出处
《华中科技大学学报（自然科学版）》
EI
CAS
CSCD
北大核心
2021年第2期85-88,107,共5页
基金
国家自然科学基金资助项目(61370003)。
文摘
针对一种边权重取值范围为[0,1]的无向带权图,提出在社交网络中有实际应用的概率支配集概念。在图中寻找最少点数的概率支配集称为最小概率支配集问题。证明最小概率支配集问题是NP(非确定性多项式)难问题,表明不太可能存在多项式时间复杂度的精确算法。基于次模函数提出了多项式时间复杂度的贪心近似算法,用于求解最小概率支配集问题,得出近似比结果。在真实的社交网络实例上进行实验,结果表明贪心算法所求的概率支配集中节点个数平均占总节点个数的14%~15%.
关键词
概率支配集
社交网络
NP难
次模函数
近似算法
Keywords
probabilistic
dominating
set
social
network
NP-hard
submodular
function
greedy
approximation
algorithm
分类号
TP301 [自动化与计算机技术—计算机系统结构]
原文传递
题名
作者
出处
发文年
被引量
操作
1
社交网络中的概率支配集问题
钟昊
陈卫东
《华中科技大学学报（自然科学版）》
EI
CAS
CSCD
北大核心
2021
0
原文传递
已选择
0
条
导出题录
引用分析
参考文献
引证文献
统计分析
检索结果
已选文献
上一页
1
下一页
到第
页
确定
用户登录
登录
IP登录
使用帮助
返回顶部
