计算机工程

作者：赵丹枫, 姚贤标, 包晓光, 黄冬梅, 郭伟其

单位：1. 上海海洋大学 信息学院, 上海 201306;2. 上海电力大学 电子与信息工程学院, 上海 200090;3. 国家海洋局 东海海洋环境调查勘察中心, 上海 200137

关键词：社团检测,<i>k</i>核,加权图,紧密子图,贪婪策略

基金：国家自然科学基金青年科学基金项目（42106190）；上海市科委地方能力建设项目（20050501900）。

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%以内。

来源：2022年第10期

《计算机工程》期刊编辑部

查看计算机工程杂志2022年第10期