基于贪婪策略的紧密k核子图查询

作     者：赵丹枫 姚贤标 包晓光 黄冬梅 郭伟其 ZHAO Danfeng;YAO Xianbiao;BAO Xiaoguang;HUANG Dongmei;GUO Weiqi

作者机构：上海海洋大学信息学院上海201306 上海电力大学电子与信息工程学院上海200090 国家海洋局东海海洋环境调查勘察中心上海200137 

出 版 物：《计算机工程》 (Computer Engineering)

年 卷 期：2022年第48卷第10期

页      面：55-66页

学科分类：12[管理学] 1201[管理学-管理科学与工程(可授管理学、工学学位)] 081104[工学-模式识别与智能系统] 08[工学] 0835[工学-软件工程] 0811[工学-控制科学与工程] 0812[工学-计算机科学与技术（可授工学、理学学位）] 

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

主　　题：社团检测 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%以内。