开放科学（资源服务）标志码（OSID）：

0 概述

图查询是图数据分析与处理的基础，其中社团检测作为一种子图查询，其目标是从给定的图中寻找所有紧密连接的子图，并且各个图内部的节点是连通的^[1]。紧密子图查询作为社团检测的核心，在很多领域都有着重要的应用，例如：在社交网络中，查询联系紧密的社团有助于用户的特征分析^[2]；在作者的合作网络中，联系紧密的作者之间可能具有相似的研究领域^[3]；在商品销售数据中，联系紧密的商品更有可能被相似的消费者所关注^[4]；在蛋白质网络中，关系紧密的蛋白质通常更有可能形成特定的官能团^[5]。

在现有的研究中，研究人员提出许多社团检测方法，如基于模块度优化的算法^[6]、谱方法^[7]、非负矩阵分解^[8]等。对于社团的定义也有多种，常见的有$ k $架（$ k $-truss）、$ k $团（$ k $-clique）、$ k $核（$ k $-core）等，其中$ k $核的定义^[9]要求图中每个节点至少有$ k $个邻接节点，即每个节点的度至少为$ k $。$ k $核可以在线性时间复杂度内计算得到，具有较好的应用基础^[10-12]。近年来的研究多结合部分场景的应用需求，讨论各类属性图上的$ k $核子图查询^[13-15]。然而，由于考虑边权值的研究较少，但在很多场景下，图中边的权值往往具有很强的语义关系。例如在社交网络中，两个用户之间的交流越频繁意味两者之间的联系越紧密。在作者的合作网络中，若两个作者之间合作的次数越多，则说明他们的联系越紧密，对应图中边的权值越大。因此，为了使社团检测更加符合实际的语义场景，提高查询结果的合理性，则需要将图中边的权值考虑在内。

此外，考虑到查询最紧密社团往往会耗费较多的时间，并且在一些应用场景下不需要查询社团权重的最值，例如在蛋白质网络中，有时仅需要找到满足一定紧密关系的蛋白质集合即可。为此，不局限于社团检测中最值的查询，给定核值$ k $、节点平均权值$ {w}_{\mathrm{Q}} $，在加权图中查询联系紧密的连通$ k $核子图问题，记为紧密$ k $核子图查询（Closely Related $ k $-Core Subgraph Query，CRKSQ）问题。该问题要求查询得到的连通$ k $核子图的节点平均权值大于等于$ {w}_{\mathrm{Q}} $，其进一步限制了子图的紧密程度，且由于$ {w}_{\mathrm{Q}} $可以根据实际需求给出，具有更好的灵活性，更加切合实际应用场景。

为解决CRKSQ问题，本文首先证明该问题是一个NP-难问题，即无法为其找到一个在多项式时间复杂度内的最优算法，并基于贪婪策略设计启发式算法CRK-G。在此基础上，研究CRK-G算法的优化策略，提出CRK-C和CRK-F算法，分别从降低图规模和减少迭代次数两个方面提高查询效率。最后通过实验对比3种算法在不同场景下的效率。

1 相关工作

目前针对社团的查询已经有了广泛的研究，除$ k $核外，主要还包括基于$ k $-truss和$ k $-clique的查询问题。$ k $-truss和$ k $-clique相对于$ k $核有着更加严格的定义，但都与$ k $核类似，其本身并未考虑图中的其他属性，仅仅只是从图中寻找稠密且内聚的结构。近年来的很多研究也开始结合图的语义关系，探索更加高质量的$ k $-truss和$ k $-clique社团^[16-18]。

与上述两种社团的定义相比，$ k $核可以被有效地在线性时间内计算，其概念最初由SEIDMAN^[9]在1983年提出。为了高效地进行$ k $核的查询，BATAGELJ等^[19]于2003年提出了$ k $核分解算法，其能在$ O\left(m\right) $时间复杂度下得到每个节点的最大核值，进而能够在线性时间内得到$ k $核查询的结果。文献[20]为应对大图的查询，又提出了效率更高且能在个人计算机上运行的3种$ k $核分解算法，其查询速度有了很大的提升。为提升$ k $核查询的效率，文献[21]提出了面向$ k $核查询的图压缩算法SC，进一步将压缩图转化为树的算法TC，其算法效率比可以比直接在原图上查询的效率高出1$ ~ $2个数量级。

为了优化$ k $核社团查询，文献[22]提出一种能够支持多个节点查询的社团搜索问题，解决了以往单节点查询带来的通用性的不足。文献[23]考虑到现有的社团查询方法使用的都是全局搜索，算法代价较高，故提出一种局部搜索方法。上述两种方法虽然在查询条件上做了优化，但却都未结合图上的其他属性，仅面向简单图的查询。

近年来，研究人员开始致力于寻找更加紧密的$ k $核子图，文献[13]结合图中节点的影响力，提出了$ k $-influential社团模型，用于在大图中查询最具影响的社团。文献[14]考虑边的有向性，研究了有向图上的社团搜索问题，其利用最小内度和外度的度量方法寻找紧密连接的子图。文献[15]研究了轮廓图的社团搜索（PCS）问题，其能够识别具有语义共性的节点，从而发现更多高质量的社团。上述研究结合了图上的其他属性，在相应的场景下能得到更加合理有效的社团，而对于边权值属性的社团查询方面，目前的研究还不充分。虽然文献[24]提出了查询加权图的亲密核心组问题，但由于其模型属于社团搜索，仅针对给定节点集的查询，并且是查询总权值最小的子图，与部分应用场景不符，具有一定的局限性。

本文考虑了节点的语义关系，不局限于社团检测中最值的查询，提出了在加权图中查询联系紧密的连通$ k $核子图问题，以实现更好的灵活性，且更贴合实际应用场景。

2 定义与证明 2.1 紧密$ k $核子图的定义

本文研究的是无向加权图上的子图查询，该研究是在$ k $核的基础上进行的，故先给出$ k $核的定义。

定义1（$ k $核）^[9]  给定图$ G=\left(V, E\right) $，$ k $核是图$ G $的极大子图$ H $，使得$ H $中的每个节点至少有$ k $个邻节点。

定义2（核值）  给定图$ G=(V, E) $，对于$ G $中的节点$ u $，$ u\in V $，$ u $的核值$ \mathrm{c}\mathrm{o}\mathrm{r}\mathrm{e}\left(u\right) $为$ u $所在全部$ k $核中的最大值，即：

$ \mathrm{c}\mathrm{o}\mathrm{r}\mathrm{e}\left(u\right)=\underset{V\left(H\right)\subseteq V}{\mathrm{m}\mathrm{a}\mathrm{x}}\left\{k|u\in V(H){且}{H}{为}{k}{核}\right\} $

(1)

例如，在图 1中，节点集{a，b，c，d，f }和{o，p，r，s}的导出子图中节点核值都为3。但需要注意的是，节点的核值并不等于节点的度，如图 1中的节点c，其节点的度为4，但核值却为3。此外，$ k $核并不一定是一个连通的图，如图 1（b）表示的是图 1（a）中加权图$ G $的3核子图，该图并不是连通的。

定义3（连通$ k $核）  给定图$ G=(V, E) $，连通$ k $核是图$ G $的极大连通子图$ H $，使得$ H $中的每个节点至少有$ k $个邻节点。

连通$ k $核是在$ k $核的基础上定义的，其表示的子图一定是一个连通的图。本文研究的是连通$ k $核，若不加特别说明，下文中提到的$ k $核均表示的是连通$ k $核。

定义4（节点权值$ \omega $）  给定一个加权图$ G=(V, E, W) $，对于$ G $中的节点$ u $，$ u\in V $，节点$ u $的权值为与其相连边的权值之和，即节点权值：

$ \omega \left(u\right)=\sum\limits_{e=(u, v), v\in V}w\left(e\right) $

(2)

例如，在图 1中，与节点a相连的边有3条，各边权值分别为7、8、10，故其节点的权值$ \omega $（a）=7+8+10=25。

定义5（节点平均权值$ Aw $）  给定一个加权图$ G=(V, E, W) $，图$ G $节点平均权值为每个节点的权值之和除以图$ G $的节点数，即图$ G $节点平均权值为：

$ Aw\left(G\right)=\frac{\sum\limits_{u\in V}\omega \left(u\right)}{\left|V\right|} $

(3)

节点平均权值反映的是整个子图内部的紧密程度，节点平均权值越大则说明子图内部节点之间的交互越多，子图就越紧密。

下面给出紧密$ k $核子图（Closely Related $ k $-Core Subgraph）的定义。

定义6（紧密$ k $核子图）  给定一个加权图$ G=\left(V, E, W\right) $，核值$ k $，节点平均权值$ {w}_{\mathrm{Q}} $，紧密$ k $核子图$ H=\left({V}^{\text{'}}, {E}^{\text{'}}, W\right) $，$ H $满足以下条件：1）$ H\subseteq G $；2）$ H $是连通$ k $核；3）图$ H $的节点平均权值$ Aw\left(H\right)\ge {w}_{\mathrm{Q}} $。

紧密$ k $核子图的定义在$ k $核的基础上进一步限制了子图的节点平均权值，该限制将会消除图中权值较小的节点，使得图整体的紧密性有所提高。

紧密连接k核子图查询如图 2所示，其中图 2（b）为加权图$ G $（见图 1（a））在给定$ k $=2、$ {w}_{\mathrm{Q}} $=20时得到的紧密2核子图$ H $。图$ H $的每个节点都至少有2个邻节点，且图的节点平均权值为21.6，满足给定条件。对比图 2（a）和图 2（b），可以看出后者节点之间的联系更加紧密，整体也更加紧凑。

定义7（紧密$ k $核子图查询）  给定一个加权图$ G=\left(V, E, W\right) $，核值$ k $，节点平均权值$ {w}_{\mathrm{Q}} $，在图$ G $中寻找紧密$ k $核子图$ H $。

紧密$ k $核子图查询（CRKSQ）问题的目的是在图中找到满足条件的紧密$ k $核子图。需要注意的是，紧密$ k $核子图在图中不一定只有一个，有可能存在多个。

2.2 QCRKS问题的证明

引理1  给定一个加权图$ G=(V, E, W) $，图$ G $中节点权值之和等于图$ G $中各边权值之和的两倍，即：

$ \sum\limits_{u\in V}\omega \left(u\right)=2\times \sum\limits_{e\in E}w\left(e\right) $

(4)

证明  由于图G中的每条边连接两个节点，而根据节点权值的定义可知图中每条边的权值会被相连的两个节点各计算一次，故上述结论成立。

定理1  CRKSQ问题是NP-难的。

证明  将clique问题多项式归约到CRKSQ问题。由于clique问题是一个NP-完全问题^[25]，进而得出CRKSQ问题是NP-难的。给定clique问题的一个实例$ I $，其由一个无权图$ G=\left(V, E\right) $和一个正整数$ k $构成。构造CRKSQ问题的一个实例$ I\text{'} $：一个加权图$ G\text{'}=\left(V, E, W\right) $，这里每条边权值都为1；另一个正数$ {w}_{\mathrm{Q}}=k-1 $。显然，这是一个多项式归约。下面只需证明实例$ I $存在一个$ k $阶完全子图，当且仅当，实例$ {I}^{\text{'}} $存在一个节点平均权值大于等于$ {w}_{\mathrm{Q}}({w}_{\mathrm{Q}}=k-1) $的紧密$ (k-1) $核子图。

假设clique问题存在一个$ k $阶完全子图$ H $。现证明$ H $作为$ G\text{'} $的子图，其是一个满足条件的紧密$ (k-1) $核子图。由完全子图的定义可知，$ H $中的每个节点具有$ (k-1) $个邻接节点，且平均权值为：

$ Aw\left(H\right)=\frac{\sum\limits_{u\in V\left(H\right)}\omega \left(u\right)}{\left|V\right(H\left)\right|} $

(5)

根据引理1，式（5）可化为：

$ Aw\left(H\right)=\frac{2\times \sum\limits_{e\in E}\omega \left(e\right)}{\left|V\right(H\left)\right|} $

(6)

因$ G\text{'} $中每条的权值都为1，故：

$ Aw\left(H\right)=\frac{2\times \left|E\right(H\left)\right|}{\left|V\right(H\left)\right|}=\frac{k(k-1)/2\times 2}{k}=k-1 $

(7)

得证。

反之，假设$ G\text{'} $中存在一个满足条件的紧密$ (k-1) $核子图$ H $。由子图$ H $是一个$ (k-1) $核知，$ H $具有至少$ k $个节点；由节点平均权值大于等于$ {w}_{\mathrm{Q}}({w}_{\mathrm{Q}}=k-1) $，并由引理1可知，$ H $具有$ k(k-1) $条边，因此作为$ G\text{'} $的子图$ H $是一个$ k $阶完全子图。得证。

3 基于贪婪策略的查询算法

由定理1可知，无法为CRKSQ问题找到一个多项式时间复杂度的最优算法，为解决该问题并在可接受的时间内找到合适的解，本文基于贪婪策略提出了启发式算法CRK-G。首先从图中找到候选$ k $核子图，然后通过不断地迭代删除候选子图中权值最小的节点，进而得到满足条件的紧密$ k $核子图。

3.1 CRK-G算法

CRK-G算法步骤如下：

步骤1  使用$ k $核分解算法^[20]计算每个节点的核值。

步骤2  使用广度优先搜索，得到候选$ k $核子图集合。

步骤3  判断子图节点平均权值是否小于$ {w}_{\mathrm{Q}} $，若小于则迭代删除图中权值最小的节点。

步骤4  为了保证剩余子图的$ k $核连通性，还需要删除图中节点度小于$ k $的节点，随后判断子图是否连通，若不连通则将每个独立的连通子图分隔，并加入候选子图集合等待后续的处理。

步骤5  重复上述操作，直到剩余子图的节点平均权值大于等于$ {w}_{\mathrm{Q}} $，或节点被全部迭代删除为止。算法最后返回满足条件的紧密$ k $核子图集。

例如，在图 2中，给定图$ G $（见图 1（a）），核值$ k $=2，节点平均权值$ {w}_{\mathrm{Q}} $=20。算法首先查询得到候选2核子图$ H\text{'} $，随后开始判断子图$ H\text{'} $的节点平均权值是否大于等于$ {w}_{\mathrm{Q}} $，经计算可知节点平均权值小于20。因此，开始删除最小权值的节点e。删除节点e后，节点平均权值仍然小于20，则再依次删除节点s、节点r。其中，删除节点s和节点r导致节点p的度小于2，则再将节点p删除，此时剩余子图仍然是连通的。重复上述步骤再依次删除节点o、节点h，最终得到图 2（b）中满足条件的紧密2核子图$ H $。

算法1  紧密$ k $核子图查询算法CRK-G

输入  图$ G=\left(V, E, W\right) $，核值$ k $，节点平均权值$ {w}_{\mathrm{Q}} $

输出  满足条件的紧密子图集$ {S}_{H}=\left\{H|H\subseteq G\mathrm{且}\right. $$ H\mathrm{为}G\mathrm{的} $ $ \left.\mathrm{紧}\mathrm{密}k\mathrm{核}\mathrm{子}\mathrm{图}\right\} $

1.$ \mathrm{k} $-Core$ \left(\right) $；/*$ \mathrm{k} $核分解算法计算每个节点的核值*/

2.$ {\mathrm{S}}_{\mathrm{H}}=\mathrm{\varnothing } $；

3.FOR每个节点$ \mathrm{u}\in \mathrm{V} $ DO

4.IF节点$ \mathrm{u} $还未被访问过THEN

5.$ \mathrm{H}= $BFS_Core（u，k）；/*使用广度优先搜索，找到从节点$ \mathrm{u} $开始的连通$ \mathrm{k} $核子图，并将其中的节点标记为已访问*/

6.$ {\mathrm{S}}_{\mathrm{H}}={\mathrm{S}}_{\mathrm{H}}\cup \mathrm{H} $；

7.END IF

8.END FOR

9.FOR每个子图$ \mathrm{H}\subseteq {\mathrm{S}}_{\mathrm{H}} $ DO

10.IF子图$ \mathrm{H} $的节点平均权值$ \ge {\mathrm{w}}_{\mathrm{Q}} $ THEN

11.CONTINUE；

12.ELSE THEN

13.WHILE子图$ \mathrm{H} $的节点平均权值$ \le {\mathrm{w}}_{\mathrm{Q}} $ DO

14.删除子图$ \mathrm{H} $中节点权值最小的节点；

15.删除剩余子图中度小于$ \mathrm{k} $的节点；

16.IF子图$ \mathrm{H} $的节点数等于0 DO

17.从$ {\mathrm{S}}_{\mathrm{H}} $中移除$ \mathrm{H} $；

18.BREAK；

19.END

20.IF Disconnected（$ \mathrm{H} $）DO /*检查$ \mathrm{H} $是否连通*/

21.$ {\mathrm{D}}_{\mathrm{H}} $ = Divide（$ \mathrm{H} $）；/*将$ \mathrm{H} $分割为独立的连通图，得到集合$ {\mathrm{D}}_{\mathrm{H}} $*/

22.$ {\mathrm{S}}_{\mathrm{H}}={\mathrm{S}}_{\mathrm{H}}\bigcup {\mathrm{D}}_{\mathrm{H}} $；

23.$ \mathrm{H} $ = $ {\mathrm{D}}_{\mathrm{H}} $ get（0）；/*将$ {\mathrm{D}}_{\mathrm{H}} $中的第一个元素赋给$ \mathrm{H} $*/

24.END IF

25.END WHILE

26.END IF

27.END FOR

28.RETURN $ {\mathrm{S}}_{\mathrm{H}} $；

3.2 CRK-G算法的复杂度分析

CRK-G算法采用贪婪思想，通过迭代删除节点而使得子图满足条件，其主要时间花费包括$ k $核候选子图查询、节点平均权值计算、子图连通性判断以及子图$ k $核的维护。首先，在$ k $核候选子图的查询方面，使用的是广度优先搜索算法，其时间复杂度为$ O\left(\right|V|+|E\left|\right) $。其次，在节点平均权值计算和子图连通性判断方面，计算节点平均权值需要耗时$ O\left(\right|E\left|\right) $，寻找最小权值的节点需要耗时$ O\left(\right|V\left|\right) $，若算法需要迭代$ t $次，则计算节点平均权值耗时$ O\left(t\right(\left|V\right|+\left|E\right|\left)\right) $。连通性判断使用的是广度优先搜索，耗时也为$ O\left(t\right(\left|V\right|+\left|E\right|\left)\right) $。最后，在子图$ k $核的维护方面，查询节点的度耗时为$ O\left(\right|E\left|\right) $，若算法需要迭代$ t $次，则这一步总耗时为$ O\left(t\right(\left|E\right|\left)\right) $。最终CRK-G算法的时间复杂度为$ O\left(t\right(n+m\left)\right) $，其中$ n $和$ m $分别表示原图的节点数和边数。

下文分析CRK-G算法的空间复杂度，对于原图中的每个节点，需要存储其邻节点以及其与邻节点之间边的权值，所以空间消耗为$ O\left(2\right|E\left|\right) $。另外，还需要存储候选子图中节点的邻节点以及节点与邻节点之间边的权值，空间消耗为$ O\left(2\right|E\left|\right) $。总共空间消耗为$ O\left(4\right|E\left|\right) $，故CRK-G算法的空间复杂度为$ O\left(m\right) $。

4 CRK-G算法的优化

CRK-G算法对于CRKSQ问题的求解是有效的，它能在$ O\left(t\right(n+m\left)\right) $时间内找到一个解，但对于在大规模图上的查询而言，该算法求解需要花费大量的时间，效率较低。

根据对CRK-G算法时间复杂度的分析，影响其效率的主要因素是图的规模和迭代的次数，因此可以通过使用降低图规模或减少迭代次数的方法，使得算法的效率提高。基于该思路，本节提出了CRK-G算法的两种改进算法：1）使用图压缩策略的CRK-C算法，其适用于节点权值差异性较小的图数据；2）使用单次多节点删除策略的CRK-F算法，该算法实现简单，效率提高明显，适用于差异性较大或无法确定差异性的图数据。

4.1 基于图压缩的优化策略

目前关于面向特定查询的图压缩已经有了广泛的研究，常见的如面向保持可达查询的图压缩^[26]、面向邻节点查询的压缩^[27]以及面向$ k $核查询的图压缩^[21]。与大部分面向特定查询的压缩技术类似，本文的压缩方法遵循查询等价原则，通过将权值相近的节点合并得到超节点，判断超节点所包含的节点在原图中是否存在边来构建超边以及超边的权值。

定义8（超节点和超边）  给定图$ G=(V, E) $，其经过压缩后得到$ {G}_{C}=(V\text{'}, E\text{'}) $，其中，$ V\text{'}=\{{v}_{1}^{\text{'}}, {v}_{2}^{\text{'}}, \cdots , {v}_{n}^{\text{'}}\} $由原图节点集$ V $分割得到，即$ v{\text{'}}_{i}\subset V(i=\mathrm{1, 2}, \cdots , n)，$并且$ {v}_{i}^{\text{'}}\bigcap {v}_{j}^{\text{'}}=\mathrm{\varnothing }(i\ne j) $，则节点$ v\text{'}\in V\text{'} $被称为超节点，边$ e\text{'}\in E\text{'} $被称为超边。

例如，图 3（b）的图$ {H}_{C}^{\text{'}} $表示的是一个压缩图，其每个节点表示的即为超节点，如超节点s₁包含了原图$ H\text{'} $中的节点a、节点c和节点d。压缩图$ {H}_{C}^{\text{'}} $中的边即为超边。

定义9（压缩比$ cr $）  给定图$ G=\left(V, E\right) $，其经过压缩得到$ {G}_{C}=\left({V}^{\text{'}}, {E}^{\text{'}}\right) $，则压缩比为：

$ cr=\frac{\left|{E}^{\text{'}}\right|}{\left|E\right|} $

(8)

压缩比是衡量图压缩是否有效的重要指标，根据压缩比的定义可知，压缩比越小，则压缩后的图规模也越小。

4.1.1 CRK-C算法

CRK-C算法在CRK-G算法的基础上进行，查询到候选$ k $核子图集后，对每个候选子图进行压缩，得到压缩后的图$ {G}_{C} $，在后续的迭代删除过程中直接对$ {G}_{C} $进行操作。压缩算法步骤如下：

步骤1  遍历图中的所有节点，将权值相近的节点合并，从而得到超节点。

步骤2  超节点包含的节点若在原图中存在边，则在超节点之间构建超边。

步骤3  超边的权值设为两个超节点所包含的原节点在原图中边权值之和。

其中，步骤1的节点合并是通过设置压缩阈值$ \theta $（$ \theta \in （\mathrm{0, 1}） $），根据起始节点的权值$ \omega $，将节点权值在$ \pm \theta \omega $之间的连通节点进行合并。

例如，图 3（a）表示的是一个2核候选子图，节点a、节点c和节点d的权值分别为$ \omega \left(a\right)=25 $、$ \omega \left(c\right)=26 $、$ \omega \left(d\right)=27 $，节点之间的最大差值为2，当压缩阈值$ \theta =0.01 $时，最大允许的权值差值为$ 2.5 $（$ \theta \omega \left(a\right)=2.5 $），所以节点a、节点c和节点d可以被压缩为一个超节点s₁。由于图$ H\text{'} $中节点a、节点c与节点b存在边，而节点b压缩后由超节点s₂表示，因此超节点s₁和超节点s₂之间存在边，边的权值为原图中边（a，b）和边（c，b）的权值之和，即7+3=10。重复上述压缩步骤，最终该候选子图$ H\text{'} $经过压缩得到了图$ {H}_{C}^{\text{'}} $，压缩后图的规模与原图$ H\text{'} $对比明显有所降低，压缩比$ cr $=7/18$ \approx $0.39。

压缩算法GC-W见算法2，算法最后返回压缩后的图$ {G}_{C} $和映射表$ M $，$ M $中记录了原图$ G $中每个节点所对应的超节点。借助$ M $，可以在$ O\left(n\right) $时间内将压缩后的图解压缩，$ n $表示的是原图的节点数。

需要注意的是，压缩阈值$ \theta $越大，算法查询速度越快，但对应着查询结果的误差也会增大。根据算法特点，压缩阈值$ \theta $的取值误差主要取决于候选子图节点权值的波动或偏移程度，故可以使用子图中节点权值的差异系数（Coefficient of Variation，CV）作为$ \theta $的取值依据，其反映了子图节点权值的离散程度，计算公式为：

$ {C}_{\mathrm{C}\mathrm{V}}=\frac{{\sigma }_{w}}{Aw} $

(9)

其中$ ：{\sigma }_{w} $为子图权值的标准差；$ Aw $为子图平均节点权值。

算法2  压缩算法GC-W

输入  需要压缩的子图$ G=\left(V, E, W\right) $，压缩阈值$ \theta $

输出  压缩后的图$ {G}_{C}=\left({V}_{C}, {E}_{C}, {W}_{C}\right) $，映射表$ M $

1.FOR每个节点$ \mathrm{u}\in \mathrm{V} $ DO

2.IF节点$ \mathrm{u} $还未被访问过THEN

3.$ \mathrm{B}=\mathrm{B}\mathrm{F}\mathrm{S}\_\mathrm{w}\mathrm{e}\mathrm{i}\mathrm{g}\mathrm{h}\mathrm{t}\left(\mathrm{u}, \mathrm{\theta }\right) $；/*找到与节点$ \mathrm{u} $在阈值范围内的连通节点集合*/

4.FOR每个节点$ \mathrm{v}\in \mathrm{B} $ DO

5.$ \mathrm{M}\left[\mathrm{v}\right]={\left[\mathrm{u}\right]}_{\mathrm{C}} $；

6.将节点$ \mathrm{v} $设为已访问；

7.END FOR

8.$ {\mathrm{V}}_{\mathrm{C}}={\mathrm{V}}_{\mathrm{C}}\bigcup {\left[\mathrm{u}\right]}_{\mathrm{C}} $；

9.$ \mathrm{M}\left[\mathrm{u}\right]={\left[\mathrm{u}\right]}_{\mathrm{C}} $；

10.将节点$ \mathrm{u} $设为已访问；

11.END IF

12.END FOR

13.FOR每个节点对$ {\left[\mathrm{u}\right]}_{\mathrm{C}}\in {\mathrm{V}}_{\mathrm{C}}, {\left[\mathrm{v}\right]}_{\mathrm{C}}\in {\mathrm{V}}_{\mathrm{C}} $ DO

14.IF $ (\mathrm{u}, \mathrm{v})\in \mathrm{E} $ THEN

15.$ {\mathrm{E}}_{\mathrm{C}}={\mathrm{E}}_{\mathrm{C}}\cup \left({\left[\mathrm{u}\right]}_{C}, {\left[\mathrm{v}\right]}_{C}\right) $；

16.$ {\mathrm{W}}_{\mathrm{C}}\left({\left[\mathrm{u}\right]}_{\mathrm{C}}, {\left[\mathrm{v}\right]}_{\mathrm{C}}\right)={\mathrm{W}}_{\mathrm{C}}\left({\left[\mathrm{u}\right]}_{\mathrm{C}}, {\left[\mathrm{v}\right]}_{\mathrm{C}}\right)+\mathrm{W}(\mathrm{u}, \mathrm{v}) $；

17.END IF

18.END FOR

19.RETURN $ {\mathrm{G}}_{\mathrm{C}}=\left({\mathrm{V}}_{\mathrm{C}}, {\mathrm{E}}_{\mathrm{C}}, {\mathrm{W}}_{\mathrm{C}}\right), \mathrm{M} $；

4.1.2 CRK-C算法的复杂度分析

CRK-C算法在原有贪婪策略的基础上新增了图压缩的步骤，其主要的时间花费包括$ k $核候选子图查询、图压缩、节点平均权值计算、子图连通性判断、子图$ k $核维护以及最后压缩图的解压缩。

1）在$ k $核候选子图查询方面，其时间复杂度与CRK-G算法一致，都为$ O\left(\right|V|+|E\left|\right) $。

2）在图压缩方面，其主要由超节点划分和创建超边两部分组成。其中超节点划分是通过广度优先搜索算法，不断地扩展与节点$ u $权值相近的节点，直至无法扩展为止，该步可以在$ O\left(\right|V|+|E\left|\right) $时间内完成；而超边的创建是通过依次访问原图$ G $中的每一条边，从而确定压缩图的边集，则其时间复杂度为$ O\left(\right|E\left|\right) $。因此，整个图压缩算法GC-W的耗时为$ O\left(\right|V|+2|E\left|\right) $。

3）在节点平均权值计算和子图连通性判断方面，假设图压缩的压缩比为$ cr $，则压缩后节点和边的数量大致可以表示为$ \left(cr\right)\left|V\right| $和$ \left(cr\right)\left|E\right| $。此外，由于节点和边的数量减少，算法迭代的次数也会相应减少。若压缩前需要的迭代次数为$ t $，则压缩后需要的迭代次数大致为$ \left(cr\right)t $。因此，节点平均权值的计算需要耗时$ O\left(t\right(\left|V\right|+\left|E\right|\left){\left(cr\right)}^{2}\right) $。子图连通性判断使用的是广度优先搜索，所以耗时也为$ O\left(t\right(\left|V\right|+\left|E\right|\left){\left(cr\right)}^{2}\right) $。

4）在子图$ k $核的维护方面，由于压缩图没有保留原节点的度信息，因此查询节点度的耗时没有变，仍然为$ O\left(\right|E\left|\right) $，算法需要迭代$ \left(cr\right)t $次，则此步的总耗时为$ O\left(t\right(cr\left)\right|E\left|\right) $。

5）在压缩图的解压缩方面，由于压缩算法GC-W会返回一个映射表$ M $，$ M $中记录了原图$ G $中每个节点所对应的超节点。借助$ M $，可以在$ O\left(\right|V\left|\right) $时间内将压缩后的图解压缩。

最终CRK-C算法的时间复杂度为$ O\left(t\right(cr\left)m\right) $，其中，$ t $表示迭代次数，$ cr $表示压缩比，$ m $表示原图的边数。

接下来分析CRK-C算法的空间复杂度，由于该算法在CRK-G算法的基础上引入了图压缩过程，因此在计算过程中除了原有的空间消耗外，还需要额外存储压缩图的信息，压缩图信息包括每个超节点的邻节点和超边的权值，假设图压缩的压缩比为$ cr $，则其空间消耗为$ O\left(2\right(cr\left)\right|E\left|\right) $。原有的空间消耗为$ O\left(4\right|E\left|\right) $，故CRK-C算法的空间复杂度为$ O\left(m\right) $。

4.1.3 CRK-C算法的误差分析

CRK-C算法虽然提高了效率，但是其相对于CRK-G算法存在一定的误差。CRK-C算法可能导致的误差是其多迭代删除的节点数。假设经过压缩算法压缩后的压缩比为$ cr $，在压缩图中平均一个节点对应原图$ 1/cr $个节点。在最坏的情况下，某次迭代删除中正常迭代删除一个节点即可达到紧密$ k $核子图的要求，而由于采用的是压缩图进行迭代，则该次删除的节点数为$ 1/cr $，误差为$ (1/cr)-1 < 1/cr $，即CRK-C算法的平均误差小于$ 1/cr $，压缩比$ cr $越大则误差越小。

需要说明的是，压缩比$ cr $取决于压缩阈值$ \theta $的取值，$ \theta $和$ cr $的具体关系则还要结合候选子图中节点权值的情况。但若在同一个图数据中，$ \theta $越大则会有更多的节点被合并，伴随着压缩比$ cr $会越小。

4.2 基于单次多节点删除的优化策略

提高CRK-G算法效率的改进策略除降低图规模外，另一种方法是减少算法的迭代次数，而减少迭代次数的一个有效且直接的方法是批量删除节点。通过在单次迭代中一次性删除多个节点来减少迭代次数，从而提高算法的效率。

4.2.1 CRK-F算法

基于单次多节点删除策略，对CRK-G算法进行改进，得到效率更高的快速贪婪算法CRK-F。CRK-F算法设置了每次迭代时的删除比率$ \gamma $，其中$ \gamma \in \left(\mathrm{0, 1}\right) $。若候选子图$ H $的节点数为$ \left|V\left(H\right)\right| $，设迭代时删除的节点集为$ S $，则节点集$ S $的数量$ \left|S\right|=\gamma \left|V\right(H\left)\right| $。节点集$ S $的取值是通过对每次迭代后剩余子图的节点按节点权值进行排序，权值最小的前$ \gamma \left|V\right(H\left)\right| $个节点组成的集合即为节点集$ S $。在下一次迭代删除时，$ S $即作为需要从候选子图中删除的节点集。

需要说明的是，$ \gamma $越大则每次迭代删除的节点数就越多，总的迭代次数就越少，可能导致的误差就越大。$ \gamma $的参考取值可经过计算得到，假设迭代删除一个节点后，子图的节点权值平均上升$ \mathrm{\Delta }\overline{Aw} $，则：

$ \mathrm{\Delta }\overline{Aw}=\frac{\sum\limits_{u\in V}\omega \left(u\right)-Aw}{n-1}-\frac{\sum\limits_{u\in V}\omega \left(u\right)}{n} $

(10)

目标节点平均权值$ {w}_{\mathrm{Q}} $和当前候选子图的节点平均权值$ Aw $之间的差值$ \Delta {w}_{\mathrm{Q}}={w}_{\mathrm{Q}}-Aw $，假设需要删除$ K $个节点后子图节点平均权值为$ {w}_{\mathrm{Q}} $，则：

$ {w}_{\mathrm{Q}}-Aw=\mathrm{\Delta }\overline{Aw}\times K $

(11)

而迭代删除的节点数$ K=\gamma \left|V\right| $，则：

$ \gamma =\frac{K}{\left|V\right|}=\frac{{w}_{\mathrm{Q}}-Aw}{\mathrm{\Delta }\overline{Aw}\times \left|V\right|} $

(12)

在实际应用时，式（12）可作为$ \gamma $的取值依据。一般来讲，取值时考虑目标节点平均权值$ {w}_{\mathrm{Q}} $和当前候选子图的节点平均权值$ Aw $之间的差值。当差值较大时，$ \gamma $取值可适当增大，使其能更快地迭代到目标值附近；反之，$ \gamma $取值可适当减小。

4.2.2 CRK-F算法的复杂度分析

CRK-F算法克服了CRK-G算法效率低下的问题，通过利用单次多节点删除的方法，极大地减少了算法的迭代次数，接下来对该算法进行时间复杂度与空间复杂度分析。

CRK-F算法与CRK-G算法相比，前者的迭代次数减少。首先分析改进后算法的迭代次数，初始时候选子图$ H $的节点数为$ \left|V\left(H\right)\right|\le \left|V\left(G\right)\right| $，其中$ G $为给定需要查询的原图。若每次迭代删除的节点集为$ S $，则经过$ i $次迭代后，$ \left|S\right|=\gamma \left|V\right({H}_{i}\left)\mathrm{ }\right| $，即此时节点集$ S $将从剩余子图$ {H}_{i} $中删除。这表明在经过第$ i+1 $次迭代后，剩余子图$ {H}_{i+1} $中至多有$ (1-\gamma )\left(\mathrm{ }\right|V\left({H}_{i}\right)\left|\mathrm{ }\right) $个节点，即$ \left|V\right({H}_{i+1}|\le （1-\gamma ）\left(\left|V\left({H}_{i}\right)\right|\right) $。假设需要进行$ {t}^{\text{'}} $次迭代后算法才结束，则：

$ 1\le \left|V\right({H}_{{t}^{\text{'}}}\left)\mathrm{ }\right|\le (1-\gamma )\left(\mathrm{ }\right|V\left({H}_{{t}^{\text{'}}-1}\right)\left|\mathrm{ }\right)\le \mathrm{ }\cdots \le {(1-\gamma )}^{{t}^{\text{'}}} \\ \;\;\;\;\left(\mathrm{ }\mathrm{ }\mathrm{ }\mathrm{ }\mathrm{ }\right|V\left(H\right)\left|\mathrm{ }\mathrm{ }\mathrm{ }\mathrm{ }\mathrm{ }\right)\le {(1-\gamma )}^{{t}^{\text{'}}}\left|V{\left(G\right)\mathrm{ }\left|\gamma \right)}^{{t}^{\text{'}}}\right|V\left(G\right)\mathrm{ }\mathrm{ }\mathrm{ }\mathrm{ }\mathrm{ }|$

上式经过化简可得$ t\text{'}\le ⌈\mathrm{l}\mathrm{o}{\mathrm{g}}_{(1-\gamma )}\frac{1}{\left|V\right(G\left)\right|}⌉ $，因为CRK-G算法的时间复杂度为$ O\left(t\right(n+m\left)\right) $，所以最终CRK-F算法的时间复杂度为$ O\left((n+m)\mathrm{l}\mathrm{o}{\mathrm{g}}_{(1-\gamma )}\frac{1}{n}\right) $。

CRK-F算法与CRK-G算法在空间上的消耗没有区别，所以CRK-F算法的空间复杂度也是$ O\left(m\right) $。

4.2.3 CRK-F算法的误差分析

根据CRK-F算法特点可知，其相对于CRK-G算法的误差是由于批量删除时多删除的节点导致。

假设给定删除比率$ \gamma $，当算法迭代到第$ t $次时结束，那么在$ t-1 $次时候选子图剩余的节点数为$ {(1-\gamma )}^{t-1}\left(\right|V\left|\right) $。随后进行第$ t $次迭代，在最坏情况下，本次迭代原本只需要删除一个节点即可达到紧密$ k $核子图的要求，而由于采用批量删除，实际删除的节点数为$ {(1-\gamma )}^{t-1}\left(\right|V\left|\right)\gamma $，误差为$ {(1-\gamma )}^{t-1}\left(\right|V\left|\right)\gamma -1 < (1-{\gamma }^{t-1} $ $ \left(\right|V\left|\right)\gamma $，即CRK-F算法误差不超过$ {(1-\gamma )}^{t-1}\left(\right|V\left|\right)\gamma $。

4.3 CRK-C与CRK-F算法对比分析

通过对CRK-C与CRK-F算法的原理分析，对两者的特点总结如下：

1）CRK-C算法使用了图压缩策略，通过将节点权值在阈值范围内的连通节点进行合并，从而降低子图的规模，也相应减少了迭代次数，算法效率相对CRK-G算法而言有了较大的提升。根据算法的特点，若图中节点权值较为相近时，节点压缩策略将会起较大的作用。在节点压缩时，更多节点权值相近的节点将会被合并，并且由于被合并的节点权值相近，其在迭代删除过程中所造成的误差也较小，因此CRK-C算法更适用于图中节点权值差异性较小的数据。

2）CRK-F算法利用单次多节点删除策略，每次迭代删除多个节点，显著减少了迭代次数。由于CRK-F算法仅需要在迭代删除时设置删除比率$ \gamma $，从而进行节点的批量删除，其实现相较于CRK-C算法而言更加简单，效率提升也较为明显。并且根据算法的特点，其误差能够较好地被预测，有利于控制算法的误差。当图中节点权值差异性较大或无法确定差异性时，可优先考虑使用CRK-F算法。

5 实验结果与分析

本文在3个真实数据集上进行了实验，对比了算法在不同查询条件下和不同规模图上查询的耗时，并分析压缩算法GC-W和紧密$ k $核子图模型的有效性，最后结合实例进一步说明模型的优越性。

5.1 数据集

本文实验使用的数据集主要有以下3个：

1）生物通用交互数据集Bio-GRID，其中节点表示基因或蛋白质，边表示基因或蛋白质之间存在交互，边的权值表示节点之间交互的得分，得分越高说明节点之间的联系越紧密。

2）美国安然公司的邮件网络Email-Enron，其中顶点表示邮箱，边表示一个邮箱向另一邮箱发送过邮件，边的权值表示邮箱之间邮件的互通次数，次数越高说明邮箱之间的联系越紧密。

3）由DBLP数据构成的作者协作网络，其中节点表示作者，边表示两个作者共同合作发表过文章，边的权值表示作者合作过的次数，次数越高说明作者之间的联系越紧密。

上述数据集经预处理转化为图数据，各个图的基本特性如表 1所示。其中：节点数和边数反映了图的规模；最大核值为$ k $核分解后图中节点最大的核值，反映了图中最稠密社团的稠密度；平均核值反映了图整体的稠密程度；节点平均权值反映了图节点之间整体联系的紧密程度。

5.2 实验分析

本文在上述3个数据集上进行实验，对比了算法CRK-G、CRK-C、CRK-F在不同条件下的查询效率和图压缩算法GC-W的压缩效率，并验证了模型的有效性。实验使用C++实现，在2.90 GHz Intel^ⓐ Core^TM i5-9400 CPU、8.0 GB内存、Windows10系统的台式机上运行。

5.2.1 算法效率分析

在查询紧密$ k $核子图时，需要给定核值$ k $和节点平均权值$ {w}_{\mathrm{Q}} $。为验证算法的效率，本文设计了控制变量的对比实验，记录3个算法随着给定值变化时其查询所消耗的时间。在下文实验中，CRK-C算法的压缩阈值$ \theta =0.01 $，CRK-F算法的删除比率$ \gamma =0.1 $。

由于查询参数的取值不是本文的研究重点，实验中的参数值是通过前期的初步实验并结合数据集的特性得到。其中，参数$ {w}_{\mathrm{Q}} $的给定是通过初步的实验，大致计算得到各个数据集子图的最大节点平均权值，将该值取整十或整百，然后等差递减得到$ {w}_{\mathrm{Q}} $的取值范围。在实际应用中可以根据对子图紧密程度的需求来选择核值$ k $和节点平均权值$ {w}_{\mathrm{Q}} $，以及对误差允许的范围来选择合适的压缩阈值$ \theta $和删除比率$ \gamma $。

本文分别控制$ k $和$ {w}_{\mathrm{Q}} $的变化，在3个数据集上进行以下两组实验：

1）随着给定节点平均权值$ {w}_{\mathrm{Q}} $的变化，实验并记录在3个数据集上算法CRK-G、CRK-C、CRK-F查询所需要的时间。对于数据集Bio-GRID，给定$ k=20 $，变量$ {w}_{\mathrm{Q}} $的取值范围为$ \left\{\mathrm{20, 30, 40, 50, 60}\right\} $；对于数据集Email-Enron，给定$ k=30 $，变量$ {w}_{\mathrm{Q}} $的取值范围为$ \left\{9\mathrm{ }\mathrm{000, 10}\mathrm{ }\mathrm{000, 11}\mathrm{ }\mathrm{000, 12}\mathrm{ }\mathrm{000, 13}\mathrm{ }000\right\} $；对于数据集DBLP，给定$ k=40 $，变量$ {w}_{\mathrm{Q}} $的取值范围为$ \left\{\mathrm{200, 225, 250, 275, 300}\right\} $。

3种算法随$ {w}_{\mathrm{Q}} $变化的运行效率对比结果如图 4所示，随着节点平均权值$ {w}_{\mathrm{Q}} $增大，各算法在不同数据集上的查询耗时总体均增加。之所以如此，是因为当给定节点平均权值$ {w}_{\mathrm{Q}} $增大时，算法所需要的迭代次数增多，故耗时增加。在3种算法的效率对比中，CRK-G算法的查询耗时明显高于另两种算法。在Bio-GRID数据集上，CRK-C算法的速度略快于CRK-F算法，通过对数据集特性的分析，发现Bio-GRID数据集中存在较多权值相近的节点，使得该数据集的候选子图经过压缩后的压缩比较低，故CRK-C算法的查询速度较快。反之，在DBLP数据集上，CRK-F算法速度快于CRK-C算法是由于该数据集上权值相近的节点较少。

2）随着给定核值$ k $的变化，实验并记录在3个数据集上算法CRK-G、CRK-C、CRK-F查询所需要的时间。对于数据集Bio-GRID，给定$ {w}_{\mathrm{Q}}=40 $，变量$ k $的取值范围为$ \left\{\mathrm{10, 15, 20, 25, 30}\right\} $；对于数据集Email-Enron，给定$ {w}_{\mathrm{Q}}=11\mathrm{ }000 $，变量$ k $的取值范围为$ \left\{\mathrm{10, 20, 30, 40, 50}\right\} $；对于数据集DBLP，给定$ {w}_{\mathrm{Q}}=250 $，变量$ k $的取值范围为$ \left\{\mathrm{20, 30, 40, 50, 60}\right\} $。

3种算法随k变化的运行效率对比结果如图 5所示，随着核值$ k $增大，各算法在不同数据集上的查询耗时总体均减少。之所以如此，是因为当给定核值$ k $增大时，得到的候选$ k $核子图规模减小，算法迭代次数减少，故耗时减少。另外，在3种算法的效率对比中，当$ k $值较小时，CRK-G算法的查询耗时明显高于另两种算法。

上述实验结果与本文对各个算法的时间复杂度分析结果相符合，CRK-G算法的查询耗时总体均高于CRK-C和CRK-F算法。而CRK-C算法和CRK-F算法两者耗时大致相近，具体耗时高低主要取决于数据集的特点，当数据集中存在较多权值相近的节点时，图压缩算法压缩后得到的图规模较小，使得CRK-C算法的查询耗时低于CRK-F算法。

5.2.2 算法误差分析

由于CRKSQ问题是NP-难的，无法在多项式时间复杂度内找到最优解，CRK-G算法虽然能够找到一个可行解，但其与最优解之间的偏离程度无法被预计。CRK-C和CRK-F算法是在CRK-G算法基础上的改进，效率有了很大的提升，但两者相对于CRK-G算法存在一定的误差。接下来以CRK-G算法为参考，在不同$ k $值条件下，对CRK-C和CRK-F算法查询结果的误差进行分析。

根据算法的原理，评判误差的依据是CRK-C和CRK-F算法相对于CRK-G算法是否过多删除了节点。实验在3个数据集上进行：对于数据集Bio-GRID，给定$ {w}_{\mathrm{Q}}=40 $，变量$ k $的取值范围为$ \left\{\mathrm{10, 15, 20, 25, 30}\right\} $；对于数据集Email-Enron，给定$ {w}_{\mathrm{Q}}=11\mathrm{ }000 $，变量$ k $的取值范围为$ \left\{\mathrm{10, 20, 30, 40, 50}\right\} $；对于数据集DBLP，给定$ {w}_{\mathrm{Q}}=250 $，变量$ k $的取值范围为$ \left\{\mathrm{20, 30, 40, 50, 60}\right\} $。

实验记录了各个算法在上述条件下查询得到的子图节点数，计算了CRK-C和CRK-F算法相对于CRK-G算法的误差百分比，结果分别如表 2~表 4所示，多次实验的平均误差均在8%以内，误差较小。

5.2.3 图压缩算法有效性分析

为验证图压缩算法GC-W的有效性，实验记录了不同$ k $值条件下，GC-W算法在3个数据集上压缩候选子图的耗时。

对于数据集Bio-GRID，变量$ k $的取值范围为$ \left\{\mathrm{10, 15, 20, 25, 30}\right\} $；对于数据集Email-Enron，变量$ k $的取值范围为$ \left\{\mathrm{10, 20, 30, 40, 50}\right\} $；对于数据集DBLP，变量$ k $的取值范围为$ \left\{\mathrm{20, 30, 40, 50, 60}\right\} $。实验结果如图 6所示，当$ k $值增大时，压缩时间减少。由于当$ k $值增大时候选$ k $核子图的规模减小，因此压缩算法GC-W的耗时减少。

压缩耗时相较于查询耗时低了1或2个数量级，其可以在相对短的时间内对候选子图进行压缩，有效地减少了查询时间，压缩算法是有效的。

5.2.4 模型有效性分析

为验证紧密$ k $核子图（CRKS）模型的有效性，本文实验对比了CRK-F算法与忽略权值的$ k $核（$ k $-core）算法，记录两者在不同$ k $值条件下查询得到的子图节点平均权值。

实验分别在3个数据集上进行，考虑到CRK-F算法和$ k $-core算法每次查询得到的子图都有可能存在多个，并且前者会由于给定的$ {w}_{\mathrm{Q}} $不同而得到不同的结果。因此，本文将CRK-F算法在不同$ {w}_{\mathrm{Q}} $条件下查询得到的子图最大节点平均权值与$ k $-core算法查询得到的所有子图最大节点平均权值进行对比。

对于数据集Bio-GRID，变量$ k $的取值范围为$ \left\{\mathrm{10, 15, 20, 25, 30}\right\} $；对于数据集Email-Enron，变量$ k $的取值范围为$ \left\{\mathrm{10, 20, 30, 40, 50}\right\} $；对于数据集DBLP，变量$ k $的取值范围为$ \left\{\mathrm{20, 30, 40, 50, 60}\right\} $。实验结果如图 7所示。从实验结果可以看出，CRK-F算法得到的子图节点平均权值均大于$ k $-core算法，验证了CRKS模型的有效性和优越性。

5.2.5 实例分析

为进一步说明CRKS模型的合理性，本文选取一个实例进行分析。图 8（a）所示是作者协作网络中选取的部分数据，其包含了30个节点和46条边，图的节点平均权值为40.67，存在一些联系较为松散的节点。若忽略权值，仅给定$ k $=3，进行3核查询，查询结果如图 8（b）所示。从图中可以看出，虽然所有节点的度均大于等于3，对应着至少3个邻接节点，但结合边的权值就可发现节点“Bin Zhou”所对应的权值较小，该节点将左右两部分的图连接成一体，使得图整体结构并不紧凑，左右两部分节点之间联系的紧密程度不足。若考虑权值，给定$ {w}_{\mathrm{Q}} $=50，对图 8（a）所示的图进行紧密3核子图查询，得到图 8（c）所示的结果。该结果包含两个子图，每个图相较于图 8（b），内聚性更强，节点之间的联系也更加紧凑。两个子图的节点平均权值分别为50.8和53.2，相较于图 8（b）的47.08，两个子图整体的联系也更加紧密。

综合上述分析，CRKS模型可以检测出加权图中紧密联系的子图，相较于现有的方法更加合理有效。

6 结束语

本文提出一种在加权图中查询联系紧密的连通$ k $核子图问题，并证明了该问题是NP-难的。为解决CRKSQ问题，设计基于贪婪策略的启发式算法CRK-G，其能在可接受的时间内为CRKSQ问题找到一个近似解，分别从降低图规模和减少迭代次数两个方面出发，提出两个改进算法CRK-C和CRK-F，其在查询速度上有明显提升。在不同规模数据集上进行多次实验，结果表明，CRK-C和CRK-F算法的平均误差都在8%以内。下一步将研究本文算法参数的取值和优化问题，并探索其他更加高效的紧密$ k $核子图查询算法，以满足超大图的查询要求。