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

Closely Related k-Core Subgraph Query Based on Greedy Strategy

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-core query is a type of community query because it can be calculated effectively in linear time and has a wide range of applications in community detection.In some scenarios,the weights of edges in graphs exhibit strong semantics,but the weights of edges in graphs were rarely considered in previous studies.First,the Closely Related k-core Subgraph Query(CRKSQ)problem in weighted graphs is defined based on the k-core,and the problem is confirmed to be Non-deterministic Polynomial-time hard(NP-hard)using the reduction method.Second,a heuristic algorithm CRK-G is designed based on the greedy strategy to obtain an approximate solution to the CRKSQ problem by iteratively deleting nodes.Finally,the optimization strategy of the CRK-G algorithm is evaluated based on two aspects:reducing the graph size and the number of iterations.This study proposes a CRK-C algorithm using the graph compression strategy and a CRK-F algorithm using the single-time multinode deletion strategy.The experimental results for three datasets(Bio-GRID,Email-Enron,and DBLP)show that compared with the CRK-G algorithm,the CRK-C and CRK-F algorithms exhibited significantly improved query speed,and the average error is within 8%.