基于贪婪策略的紧密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核、加权图、紧密子图、贪婪策略

所属期刊栏目：48

分类号：TP18(自动化基础理论)

资助基金：国家自然科学基金;上海市科委地方能力建设项目

在线出版日期：2022-10-20（万方平台首次上网日期，不代表论文的发表时间）

页数：共12页

页码：55-66