典型文献
基于贪婪策略的紧密k核子图查询
文献摘要：
k核查询是一种社团查询,由于其可以在线性时间内被有效计算,因此在社团检测中具有较广泛的应用.图中边的权值在很多场景下具有较强的语义关系,但现有研究较少考虑图中边的权值.为提升k核查询的效率,在k核的基础上定义加权图中的紧密k核子图查询(CRKSQ)问题,并使用归约方法证明该问题是NP-难的.基于贪婪策略设计启发式算法CRK-G,通过迭代删除节点为CRKSQ问题找到一个近似解.在此基础上,从降低图规模和减少迭代次数两方面研究CRK-G算法的优化策略,分别提出使用图压缩策略的算法CRK-C及使用单次多节点删除策略的算法CRK-F.在Bio-GRID、Email-Enron、DBLP 3个数据集上的实验结果表明,相对于CRK-G算法,CRK-C、CRK-F算法在查询速度上有较大的提升,且平均误差均在8％以内.
文献关键词：
社团检测;k核;加权图;紧密子图;贪婪策略
中图分类号：
作者姓名：
赵丹枫;姚贤标;包晓光;黄冬梅;郭伟其
作者机构：
上海海洋大学 信息学院,上海 201306;上海电力大学 电子与信息工程学院,上海 200090;国家海洋局 东海海洋环境调查勘察中心,上海 200137
文献出处：
引用格式：
[1]赵丹枫;姚贤标;包晓光;黄冬梅;郭伟其-.基于贪婪策略的紧密k核子图查询)[J].计算机工程,2022(10):55-66
A类：
CRKSQ,Enron,紧密子图
B类：
贪婪策略,核子,子图查询,核查,线性时间,社团检测,权值,多场景,语义关系,加权图,归约,NP,策略设计,启发式算法,近似解,迭代次数,出使,压缩策略,多节点,节点删除,Bio,GRID,Email,DBLP,平均误差
AB值：
0.331633
相似文献
机标中图分类号，由域田数据科技根据网络公开资料自动分析生成，仅供学习研究参考。
