翻译：Fang Y ,  Huang X ,  Qin L , et al. A survey of community search over big graphs[J]. The VLDB journal, 2020, 29(1):353-392.

在本节中，我们首先正式介绍常用的社区内聚性指标，然后比较它们的内聚性和计算效率。

2.1 凝聚力指标

        为便于说明，我们考虑一个简单的无向图G(V, E)，图G(V, E)中有顶点集V和边集E。设n和m为V和E的相应大小，G的顶点v的度用degG(v)表示。

• k-core。我们将它的正式定义介绍如下

定义1 (k-core[17,170])给定一个整数k (k≥0)， G的k-core记为Hk，是G的极大子图，使任意v∈Hk，degHk (v) ≥k。

        我们说Hk有一个k的阶，注意Hk可能不是一个连通图[17]。注意k-cores是“嵌套的”[17]：给定两个正整数i和j，如果iHi。

例1：在图2a中，{A, B, C, D}的子图是3核。1核有顶点{A, B, C, D, E, F, G, H, I}，由两个连通子图{A, B, C, D, E, F, G}和{H, I}组成。每个圆中的数字k表示该椭圆中包含的k核。很明显，H3 H2 H1。

定义2（核数/核值）给定顶点vV，其核数用coreG[v]表示，其为包含v的k核的最大值。

        图2b显示了例1的核值及其各自的顶点集。也就是说，k核是顶点集的诱导子图，其各个顶点的核数至少为k。

• k-truss。K-truss是基于三角形定义的。具体来说，G中的三角形是一个长度为3的循环。设u, v, wV是环上的三个顶点。我们用Δuvw表示这个三角形。

定义3(支撑度support)给定一个图G(V, E)，一条边(u, V) E的支撑度定义为|{Δuvw: u, v, w  V}|

定义4 (k-truss[41,166,212])给定一个图G，G的k-truss记为Jk，是G的最大子图，使任意eJk，sup(e, Jk)  (k-2)。

例2。让我们重新考虑图2a中的图G。由顶点集{A, B, C, D}导出的G的子图是4-truss。3-truss有顶点{A, B, C, D, E}。每个圆中的数字k表示该椭圆中包含的k-truss。

定义5(truss数[184])给定一个图G，一条边eÎG的truss数(truss度)记为τ(e)，是最大的k，因此存在一个包含e的k-truss。

        图3b所示为例2的truss数及其各自的边。也就是说，k-truss是边的诱导子图，其truss数至少为k。与k-core类似，k-truss可以包含多个连通子图。

• k-clique定义如下：

定义6 (k-clique[2,151]) k-clique是一个有k个顶点的完全图，每个顶点对之间都有一条边。

例3：在图2a中，{A, B, C, D}的子图是一个4-clique，它们的任意三个顶点构成一个3-clique(即三角形)。{A, B, E}的子图也是3-clique。任何一条边都是2-clique。

• k-ECC。我们首先介绍一些相关概念。

定义7(边连通性[76,95]) 给定一个图G(V, E)和两个顶点u, v∈V,  u和V之间的连通性λ(u, V)是去掉u和V后的最小边数。

定义8(图的连通性[76,95]) 给定一个图G(V, E)，图G的连通性λ(G) = ，是G中任意两个不同顶点之间的最小连通性，即去掉它使G不连通的最小边数。

定义9 (k-ECC[76,95]) 给定图G(V, E)，G’是G的子图，如果λ(G’)≥k且G’在G中的任何超图的连通性都小于k，则G的子图G'是k边连通分量（k-edge-connected component），即k-ECC。

例4。在图2a中，{A, B, C, D}的子图是3-ECC，因为对于其中的任何一对顶点，要断开它们，我们需要至少去掉3条边。2-ECC有顶点{A, B, C, D, E}。有两个1-ECC，分别包含顶点{H, I}和{A，...，G}

2.2 内聚性和计算效率

        一般来说，就结构内聚性而言，k-clique的内聚性最强，因为k-clique的每个顶点都与其他所有(k-1)顶点相连。对于k-truss的每个连接子图，它比k-ECC更具凝聚力。这是因为k-truss是基于三角形定义的，限制更严格，这是一个局部概念，而k-ECC是全局[7]。

        显然，k-truss比k-core更具凝聚力，因为在k-truss中，一条边内的每个顶点对必须有(k-2)个共同邻节点，而在k-core中，一条边内的任何顶点对可能没有共同邻节点。此外，k-ECC比k-core更具内聚性，因为它是一个连通子图，要求每个顶点至少有k个邻节点，而k-core可能包含多个连通子图。我们进一步分析了它们的包含性如下：设G(V, E)是一个图，k是一个整数(k³0)。我们有：

1. k-clique必须是k-truss的子图;
2. k-truss的每个连通子图必须是特定k-ECC的子图;
3. k-truss必须是(k-1)-core的子图;
4. k-ECC必须是k-core的子图。

        综上所述，在结构内聚性方面，以上四个指标大致可分为：k-core  k-ECC  k-truss k-clique

        接下来，我们讨论它们的计算效率（这里，我们只考虑假设图可以保存在一台机器的内存中的算法）。注意，对于每个指标，可能存在多个算法来枚举它的子图，但这里我们只讨论最有效的算法的复杂性。

        在[17]中，一个线性k核分解算法，计算图G中的所有k核，需要O(m + n)时间和O(m + n)空间。在[26]中，Chang等人提出了一种算法，该算法计算特定k的所有k-ECC，它需要O(h·l·m)时间和O(m+n)空间，其中h和l通常被更小的常数限制在实图[26]中。在[184]中，一个计算k-truss的有效算法，对于所有k3，需要O(m1.5)时间和O(m+n)空间。在[47]中的一种算法为一个特定的k，枚举出所有的k团，时间复杂度为O(c(G)· )，空间复杂度为O(m+n)，其中c(G)表示G中顶点的最大核数， 为 -clique的个数。注意 可以呈指数级的大小。最后，根据它们的计算效率，我们可以将这些指标排序为：k-core k-ECC k-truss k-clique

        综上所述，结构内聚性与计算效率之间存在权衡关系，如图4所示。也就是说，更紧密的度量通常需要更多的计算成本。此外，我们已经在四个真实的图上进行了比较研究，分别为Email-Enron (|V| = 36.7K, |E|= 183.8K)，Google(|V|= 876K, |E| = 5.1M), Livejournal (|V| = 4.8M, |E| = 69M)，和Wise(|V|= 58.6M, |E| = 265.1M), 其中K = 103和M = 106。如表2所示，效率结果很好地证实了上述分析。

基于以上对比分析，我们有几点建议:

(1)对于小型或中等规模的图，k-clique和k-truss不仅可以获得较高的内聚性，而且可以获得合理的效率。

(2)对于较大的图，k-core和k-ECC应该是更好的选择，因为它们的计算效率更高。

(3)对于聚集系数较高且能分解成更多三角形的图，k-truss较好。

(4)对于一些特殊的图(如二部图)，可能不存在任何三角形，因此k-truss模型可能不起作用。