高效搜索规模最大的半径有界k-core

Efficient search for the largest radius bounded k-core

摘要

近年来，作为对现实世界关系的重要抽象手段，地理社会网络吸引了大批学者对其进行研究，其中半径有界k-core搜索聚合空间上邻近且相互之间关系密切的用户构成子图集合，在广告投放、社交关系分析等方面具有广泛应用价值。但各子图间高度的用户重叠降低了搜索效率，过多的集合数量造成了用户选择困难。为了解决这两个问题，提出了规模最大的半径有界k-core（largest radius bounded k-core，LRBK）搜索问题，旨在搜索满足空间和内聚性约束且规模最大的社区。结合已知最佳的半径有界k-core搜索算法RotC+，首先提出了一个基本算法，又结合有效的剪枝和优化策略提出了一个优化算法，最后在5个真实世界数据集上进行了大量实验。实验结果表明，优化算法对比基本算法的效率最高提升了约20倍。

Abstract

In recent years，geo-social networks have attracted a large number of scholars to study them as an important means of abstracting real-world relationships. Among them，the radius bounded k-core search aggregates users who are spatially neighboring and closely related to each other to form subgraph sets，which is widely used in multiple aspects such as advertisement placement and social relationship analysis. However，the high degree of user overlap among subgraphs reduces the search efficiency，and the excessive number of aggregates causes difficulties in user selection. To solve these two problems，the largest radius bounded k-core （LRBK） search problem was proposed，which aimed to search for communities with the largest size that satisfied spatial and cohesion constraints.Combining the known best radius bounded k-core search algorithm RotC+，the basic algorithm was first proposed. Then，an optimization algorithm was proposed by combining effective pruning and optimization strategies. Finally，extensive experiments on five real-world datasets were conducted.The experimental results show that the efficiency of the optimized algorithm is improved by up to about 20 times compared to the basic algorithm.

Graphical abstract

关键词

地理社会网络 / 半径有界k-core / 规模最大 / 内聚性 / 空间约束

Key words

geo-social network / radius bounded k-core / largest scale / cohesiveness / spatial constraint

配备无线通信技术和定位功能的现代移动设备已广泛应用，极大方便了用户对互联网的访问。传统基于地域分布和社会关系链接的熟人网络在互联网上抽象出了诸如Twi-tter和Facebook等地理社交网络。地理社交网络结合了社交网络与用户的地理空间信息，由于其对现实和虚拟之间裂隙的弥合能力，近年来在地理社交网络中搜索具备高内聚性和紧密空间联系的社区成为了热门研究课题。

考虑一个现实生活中的应用场景，店家为了宣传店铺产品，店家计划邀请一群人举办线下品鉴会。为了方便参会人员到店，店家可以考虑邀请一群住所离店铺不远的人。同时考虑到紧密联系的朋友之间通常具有相似的消费习惯，更容易成为潜在客户，要求这些人中任意一个人至少在其余人中拥有一定数量的朋友。研究人员开发了半径有界k-core（radius bounded k-core，RB-k-core）搜索^［1-2］来满足这样的需求，对于任意一个RB-k-core B_i，B_i 中的顶点应该至少在B_i 中拥有k个邻居，且B_i 中所有的顶点落在一个半径为r的圆内。图1展示了一个使用RB-k-core搜索获取参会成员的例子。在k设置为2、r设置为1.5 km的情况下，S₁、S₂和S₃被推荐给店家。

此时店家可能面临一个问题，共有3个社区推荐给他，如何选择参会人员对店家来说是非常困难的。假如邀请3个社区中的所有人，这个品鉴会的成本可能过高，并且与会人员之间相互关系的紧密程度也会被破坏；假如只选择一部分用户，决定选择哪一部分是非常困难的，因为用户并不能直观地感受社区之间的关系。通常顶点规模最大的顶点集合能够覆盖搜索结果集合中尽可能多的顶点，更具备代表性。例如在图1的例子中，S₁中包含5个用户，相比于选择所有7个用户，参会人员间的内聚性得到满足，保证了品鉴会的氛围，又控制了成本；同时尽可能多地覆盖了结果集合，这意味着像John这样未被邀请参加品鉴会的用户有很大可能通过朋友了解店家。因此本文定义了搜索规模最大的RB-k-core问题（LRBK），旨在从一系列RB-k-cores顶点集合中搜索规模最大的一个作为代表性的RB-k-core提供给用户。

1 相关工作

1.1 社区搜索研究

社区搜索问题最开始由Sozio等^［3］提出，旨在搜索一个包含查询顶点的社区。截至目前，在社区搜索上进行的研究已经获得了广泛的应用，例如位置感知营销^［4］、影响力分析^［5］等。k-core^［6］、k-truss^［7］和k-clique^［8］等模型已成为用户间关系紧密程度的衡量标准，用来搜索内聚社区。k-core因其线性的核分解代价^［9］被广泛应用于社区搜索的研究中。Cui等^［10］提出了一种局部搜索策略，以评估社区中顶点的内聚程度。Li等^［11］基于加权图研究了捕获社区影响力的方法。Huang等^［12］和Fang等^［13］在属性图上进行了社区搜索问题的研究。然而这些工作都没有考虑用户的地理位置，不能用来解决LRBK问题。

1.2 基于位置的社区搜索研究

通过综合考虑数据的空间信息和社交特征，一些学者基于位置的社会网络（location based social network，LBSN）进行了社区搜索研究^［14-16］。Zhu等^［17］主要研究如何在一个给定的矩形范围内搜索社区。与文献［17］中以矩形覆盖不同的是，Fang等^［18］研究了如何搜索一个包含给定查询顶点的社区，要求这个社区被一个半径最小的圆覆盖。Haldar等^［19］研究了具备强社交凝聚力的用户密切相关的位置。Zhu等^［20］研究了当用户不断移动时如何有效更新地理社会群组。Trung等^［21］提出了强化学习模型以完成位置预测任务。Wang等^［1-2］的研究与本文工作最相关，他们研究了半径有界k-core搜索问题，该问题指定了结果社区的内聚性和空间分布应该满足的约束，向用户返回多个以给定参数r为半径的圆覆盖的连通k-core社区。以上所有工作都不能直接用来解决LRBK搜索问题。

2 预备知识和问题定义

基于位置的地理社交网络G（V，E，L）是一个无向无权图，其中V是顶点集合，E是边集合，任意边（v_i，v_j ）∈ E都有v_i ，v_j ∈ V，l_i （x_i，y_i ）∈ L是一个二维坐标系上的坐标，代表顶点v_i 的空间位置。nei _G （v）为顶点v在图G中的邻居集合，deg _G （v）为顶点v在图G中的顶点度，形式化为deg _G （v）=|nei _G （v）|。为了介绍规模最大的RB-k-core搜索，首先介绍如下定义。

定义1k-core。给定正整数k和图G，由顶点集合H构成的图G的一个子图G（H）如果满足：

（1）对于任意顶点v ∈ H，deg _G（H）（v）≥k；

（2）不存在任何图G的子图H_i 使得H⊆H_i 且满足（1），则称G（H）为G的一个k-core。

定义2 coreness。给定顶点v和图G，存在一个包含顶点v的k-core G（H）⊆G，对于任意顶点u ∈ H都有deg _G（H）（u）≥deg _G（H）（v），则记顶点v在图G中的coreness值为cnes _G （v）=k。

定义3 最小外接圆。给定顶点集合H，H的最小外接圆是将H中所有顶点覆盖到同一个圆内的半径最小的圆，记为C（H）。

定义4 二元顶点有界圆^［1］。给定顶点u和v、半径r，称以u和v为边界顶点、r为半径构造的圆为二元顶点有界圆，记作C_r （u，v）。当u和v的距离d（u，v）=2r，|C_r （u，v）|=1；当d（u，v）<2 r，|C_r （u，v）|=2；当d（u，v）>2r，|C_r （u，v）|=0。

为了定义本文的问题，定义core _G （k，u）⊆G代表一个包含顶点u的连通的k-core子图。

问题定义：给定图G，查询顶点q、半径r、正整数k。规模最大的RB-k-core搜索问题要求搜索一个顶点集合B_max，满足：

（1） G（B_max）是一个core _G （k，u）；

（2） C（B_max）的半径≤r；

（3） 不存在另一个顶点集合B_j 满足（1）、（2）且|B_max|<|B_j |。

3 搜索规模最大的RB-k-core

3.1 基本算法

作为当前已知最佳的RB-k-cores搜索算法，RotC+算法被认为是最有效的搜索所有RB-k-cores的方法。其基本思路分为如下几步：

（1）选取以查询顶点q为圆心、2r为半径的圆C（q，2r），从C（q，2r）中搜索一个包含q的连通的k-core子图G（H）。

（2）顺序从H中选取顶点v同C（v，2r）范围内属于H的所有顶点，以r为半径构造二元顶点有界圆集合C_B。

（3）如果C（v，2r）中存在一个RB-k-core或者cnes _{G（C（v，2 r））}（q）<k，回到第（2）步并选取下一个顶点。

（4）以v为极点构造极坐标系，将C_B 中所有的圆以其圆心同v构成的直线按与极坐标系0°轴极角大小升序排序。

（5）由于排序C_B 后相邻的圆之间顶点差异只有一个，依据这个发现设计了修剪策略，修剪后从剩余的圆中选取顶点构造子图，并在子图中搜索RB-k-cores。

基本算法的一个思路是先使用RotC+算法搜索所有的RB-k-cores，然后从中提取规模最大的一个作为最终结果返回，然而问题并非如此简单。Zong等^［22］指出了RotC+算法中的一个谬误，即上述第（5）步提到排序后C_B 中相邻的圆之间顶点差异只有一个，实际上相邻圆顶点差异可能是多个，即提出的修剪策略将会失效，RotC+算法不能被直接使用。因而接下来本文介绍了一个可用的RotC+算法的修正版本，并结合它提出了规模最大的RB-k-core搜索问题的基本算法。

算法1.基本算法（Baseline）

输入：地理社交网络G、查询顶点q、半径r、正整数k；

输出：规模最大的RB-k-core B_max；

1） B_max=Null； R=Null；

2） G（H）←core _{G（C（q，2r））}（k，q）；

3） Foreachv∈Hdo

4） If there exists an RB-k-core B within C（v，2r） then

5） update R by using B； continue；

6） If cnes _{G（C（v，2r））}（q）<kthen

7） continue；

8） C_B =Null；

9） Foreachu∈Hdo

10） Ifu≠v and d（u，v）≤2rthen

11） insert C_r （u，v） into C_B；

12） sort and de-duplication C_B；

13） ForeachC（c，r）∈C_B do

14） If there exists a core _{G（C（c，r））}（k，q） B within C（c，r） then

15） update R by using B；

16） B_max←the maximal vertices set in R；

17） ReturnB_max；

如算法1所示，基本算法首先初始化顶点集合B_max和结果集合R为空，然后从C（q，2r）中选取顶点生成一个包含查询顶点q的连通的k-core子图G（H）。对于H中的任一顶点v，如果在C（v，2r）中存在一个RB-k-core B，使用B更新R，更新方法是如果B是R中任意集合的子集，则丢弃B；如果B是R中任意集合的超集，则使用B覆盖这个集合；否则将B插入到R中，然后修剪顶点v。如果顶点q在G（C（v，2r））中的coreness值小于k，同样修剪顶点v。接下来初始化圆集合C_B 为空，选取H中与顶点v距离在2r以内的顶点u构造二元顶点有界圆并插入C_B，对C_B 中的圆按照极角排序并去重。最后从C_B 中按序取出圆C（c，r），并从这些圆中搜索RB-k-core，同时更新R。最后选择R中顶点规模最大的一个赋值给B_max并作为搜索结果返回。

复杂度分析：记G（H）=core _{G（C（q，2r））}（k，q）中顶点数量为n，边数量为m。算法第4 —7行包含子图构造、核分解和连通性判断，复杂度为O（n（n+m））。由于最多有n²个圆可能被生成，第9 —14行的复杂度为O（n²（n+m））。因此算法的总时间复杂度为O（n²（n+m）+n（n+m））。

3.2 优化算法

基本算法从一系列二元顶点有界圆中预先计算所有的RB-k-cores，再选取其中规模最大的一个来获取结果，这种方法导致了额外的代价，尤其是判断找到的RB-k-core B同已知RB-k-cores集合R之间的关系时引入的开销是没有必要的。优化算法的基本思路是不维护RB-k-cores结果集合R，只保存已知规模最大的结果集B_max，同时结合一些修剪和优化策略获取规模最大的RB-k-core。

由于并非所有的二元顶点有界圆中都可能包含有用结果，首先提出了如下性质用以修剪不必要验证的圆。

性质1.给定当前已知规模最大的RB-k-core B_max、查询顶点q、正整数k。如果任意圆C中包含的顶点集合|V（C）|≤|B_max|或者|core _G（C）（k，q）|≤|B_max|，圆C可以被直接修剪。

修剪策略1：根据性质1可知，对于任意的极点v，如果C（v，2r）满足性质1，该极点可以被直接修剪，同时任意的二元顶点有界圆C如果满足性质1，也可以直接被修剪。

在基本算法中，对于使用任意一个极点构造的二元顶点有界圆集合C_B，在对C_B 进行排序和去重后，算法的处理方式是在C_B 中每一个圆C中搜索顶点，构造子图并进行核分解，然后判断其中是否存在RB-k-core。即假如对于每一个极点对应的C_B，这轮操作的时间复杂度都是O（|C_B |·（m'+n'）），其中m'是C_B 中所有圆内包含的边数量的平均值，n'是顶点数量平均值。尽管已经证明在C_B 中相邻的圆之间顶点的差异不只一个^［22］，可能给顶点差异计算带来困难，本文依旧探索了新的方法快速计算相邻圆之间的顶点差异，然后使用其进行快速核维护^［23］。

对于任意一个排序但不去重的圆集合C_B，及任意的圆（C_i，C_i+1）∈C_B，计算C_i+1同C_i 中顶点差异的一个基本方法是首先搜索对应的顶点集合V_i+1和V_i，然后一一对比两个集合中的顶点，这个过程复杂度高达O（|V_i+1|·|V_i |）。为了加速这个过程，本文开发了一种基于生成圆边界顶点的方法快速计算顶点差异。

相邻圆顶点差异快速计算（Q₁）：给定查询半径r和以极点u构造并排序的圆集合C_B，对于任意的C_i ∈C_B，i∈［1，|C_B |］，有C_i =｛｛x_i，y_i ｝，V（C_i ）｝，其中｛x_i，y_i ｝是圆心坐标，V（C_i ）是一个顶点集合，存储同u构造的二元顶点有界圆中，圆心坐标在｛x_i，y_i ｝的所有顶点。差异顶点计算方法是：初始化顶点集合S为以｛x₁，y₁｝为圆心，r为半径的圆中的所有顶点，初始化S_Bound=V（C₁）。当圆从C_i 旋转到C_i+1，向S和S_Bound中添加属于V（C_i+1）但不属于S的顶点，然后从S和S_Bound中扣除属于S_Bound且同｛x₂，y₂｝距离超过r的顶点。

例1.相邻圆顶点维护如图2所示。图2给定以P为极点构造的极坐标系及以P为极点生成的二元顶点有界圆。首先初始化S=｛P，A，D，E，Z｝，S_Bound=｛A，D，E｝。当圆旋转到C₂，V（C₂）=｛D｝，判断S_Bound中顶点同｛x₂，y₂｝距离，将顶点A从S和S_Bound中丢弃；当圆旋转到C₃，V（C₃）=｛Z｝，将顶点D从S和S_Bound中丢弃；当圆旋转到C₄，V（C₃）=｛E，F，I｝，向S和S_Bound中添加顶点F和I，移除顶点Z。以此类推迭代以上过程。

算法2.优化算法

输入：地理社交网络G、查询顶点q、半径r、正整数k；

输出：规模最大的RB-k-core B_max；

1） B_max=Null； G（H）←core _{G（C（q，2r））}（k，q）；

2） Foreachv ∈ Hdo

3） If cnes _{G（C（v，2r））}（q）<k or |V（C）|≤|B_max| or |core _G（C）（k，q）|≤|B_max| then

4） continue；

5） If there exists an RB-k-core B within C（v，2r） and |B|>|B_max| then

6） B_max=B； continue；

7） C_B =Null；

8） Foreachu ∈ Hdo

9） Ifu≠v and d（u，v）≤2rthen

10） insert C_r （u，v） into C_B；

11） sort C_B； initialize S and S_bound；

12） ForeachC_i ∈C_B，i=［2，|C_B |］do

13） maintenance S，G（S） and S_Bound；

14） If |S|>|B_max| and vertices in V（C_i ） are inserted into Sthen

15） If there exists a core _{G（C（c，r））}（k，q） B within G（S） and |B|>|B_max| then

16） B_max=B；

17） ReturnB_max；

新方法从子图中添加新进入的顶点和边的复杂度是O（1），移除从圆中丢弃的顶点和边也只需要对S_Bound中少量顶点进行计算，复杂度是线性的。快速维护相邻圆间顶点差异意味着圆旋转后不需要重新提取顶点构造子图并进行核分解，也就是说问题转化成了在动态图上进行核维护。本文使用了已知最佳的动态核维护方法^［23］，其基本思路是基于核分解过程中产生的k-order信息，每次只处理少量可能发生coreness变化的顶点。

结合以上策略，优化算法如算法2所示，首先初始化结果集B_max和图G（H）。接下来按照修剪策略1对H中的顶点进行修剪，如果在C（v，2r）中存在规模更大的RB-k-core B，则使用B替换B_max。在初始化C_B 为空后，根据Q₁生成和排序C_B，使用Q₁中的方法维护集合S、G（S）、S_bound和G（S）中顶点的coreness。当插入新的顶点到S，且|S|>|B_max|，可能从G（S）中找到规模更大的RB-k-core B，如果找到这样的B，则更新B_max。迭代以上过程，最后返回B_max。

复杂度分析：记G（H）中顶点数量为n，边数量为m。设修剪策略1修剪后顶点数量为n₁（n₁<<n），边数量为m₁（m₁<<m）。优化算法第3— 6行中子图构造、核分解和连通性判断的复杂度为O（n₁（n₁+ m₁））。生成二元顶点有界圆数量至多为（n₁）²，相邻圆顶点差异计算代价为O（1），因此搜索二元顶点有界圆的代价为O（（n₁）²），总时间复杂度为O（（n₁）²+n₁m₁）。

4 实验结果分析

4.1 实验设置

实验在5个真实世界数据集上进行。详细信息如表1所示，|V |代表顶点数量，|E |代表边数量，|d_ave|代表平均顶点度。表2展示了参数k、r和数据集大小n的取值范围及默认值。所有算法使用GNU C++实现并运行在一台Ubuntu系统、3.9 GHz CPU和256 GB RAM的计算机上。

所有实验均使用在每个数据集上随机生成的100个查询顶点进行，并对实验结果取均值以评估算法。定义Baseline代表基本算法，Optimal-代表只包含修剪策略1、不包含Q₁的算法，Optimal代表完整的优化算法。限定算法超时记为ENF。

4.2 实验评估

4.2.1 算法效率评估

表3统计了在各数据集上算法的平均执行时间，对比Baseline，Optimal-算法在各数据集上的算法效率有2~4倍的提升。Optimal算法对比Baseline有约10~20倍的效率提升，证明本文提出的优化策略有效。因为不能在10⁶ms内执行结束，Baseline算法在Foursquare数据集上超时，但优化后的算法保证了解的获取，并优化了约10倍效率。由于具有最高的算法执行效率，Optimal算法是最有效的算法。

4.2.2 可伸缩性评估

如图3所示，通过在BK、GW、FK和FS等4个较大数据集上设置其他参数为默认值，数据集规模为20%~100%，这一部分评估了提出算法的可伸缩性。随着数据集规模的增长，所有算法的执行效率都随之降低，原因之一是算法计算了更多的顶点和边；其二是图的密度在逐渐增大。在图3d中，对于Foursquare数据集，即使是20%的规模也比其余3个数据集100%规模更大，约有42万个顶点，因此Baseline算法一直超时。观察图3a—3c可知，3个算法在数据集规模从20%增长到40%时执行时间增长幅度最大，原因是这个阶段增长并参与算法执行的顶点和边对图局部的内聚性影响较大，局部内聚性越大则算法执行时间越长。从80%变化到100%时执行时间增长幅度放缓，这是因为此时再加入运算的顶点和边对图局部的内聚性影响较小。总而言之，各算法在各数据集上都保证了其伸缩性。

4.2.3 参数影响评估

（1）参数k影响评估。通过固定其他参数为默认值，变化内聚性约束k为4~16，图4评估了参数k对算法执行效率的影响。随着参数k从4增长到16，算法执行效率不断提升，原因是k-core具备包含性，k值较小的k-core是k值较大的k-core的子图，这意味着k越大，满足内聚性条件的顶点数量越少，相应算法的计算量也就越小。图4b中，在Gowalla数据集上当参数k为4和7时，Baseline算法超时，因为此时由于满足内聚性要求参加算法执行的顶点过多，极大地加重了Baseline算法负载。同理如图4d所示，Baseline算法在Foursquare数据集上，参数k为4~13时超时。

（2）参数r影响评估

通过设定其余参数为默认值，并在1~9范围内变化参数r，图5展示了查询半径r对各算法效率的影响。首先在各数据集上，对于任意算法而言，随着r的增长，算法执行效率都在降低，效率降低的原因是参与算法运算的顶点所处区域是C（q，2r）。显然查询半径r越大，这个区域的范围越大，意味着范围内有更多的顶点，算法也就需要对更多顶点进行处理。在图5a—5d中，当r从1变化到5时，各算法执行时间波动最剧烈，原因是在这个阶段半径的增长带来的顶点数量变化和内聚性变化是最大的。此后当r从5增长到9时，算法效率随顶点数量及内聚性变化的放缓而缓慢降低。表3展示了在Foursquare数据集上，当r取值为5时，Baseline算法超时，如图5d所示，Baseline算法在Foursquare数据集上，r从5变化到9时也发生了超时，这与整体算法效率随r变化而受影响的情况一致。

5 结论

本文提出了规模最大的半径有界k-core搜索问题（LRBK），该问题可用于在地理社会网络中搜索同时满足内聚性、空间约束且规模最大的社区。通过修正过往工作，提出了LRBK问题的基本算法，结合有效的剪枝策略和快速的相邻旋转圆间顶点维护方法提出了优化算法，最后在5个真实世界数据集上评估了提出的算法。考虑到更广泛的应用场景需求，未来计划在地理社会网络上结合用户的属性、时序信息等方面进行查询研究。

参考文献

[1] Wang K， Cao X， Lin X M，et al.Efficient computing of radius-bounded k-cores［C］//2018 IEEE 34th International Conference on Data Engineering.Paris：IEEE，2018：233-244.

[2] Wang K， Wang S T， Cao X，et al.Efficient radius-bounded community search in geo-social networks［J］.IEEE Transactions on Knowledge and Data Engineering，2022，34（9）：4186-4200.

[3] Sozio M， Gionis A.The community-search problem and how to plan a successful cocktail party［C］//Proceedings of the 16th ACM SIGKDD international conference on Knowledge discovery and data mining.Washington，D.C.：ACM，2010：939-948.

[4] McKenzie-Mohr D.Fostering sustainable behavior：an introduction to community-based social marketing［M］.New York：New Society Publishers，2011.

[5] Kitsak M， Gallos L K， Havlin S，et al.Identification of influential spreaders in complex networks［J］.Nature Physics，2010，6：888-893.

[6] Seidman S B.Network structure and minimum degree［J］.Social Networks，1983，5（3）：269-287.

[7] Cohen J. Trusses：cohesive subgraphs for social network analysis［J］.National Security Agency Technical Report，2008，16（3）：1-29.

[8] Luce R D， Perry A D.A method of matrix analysis of group structure［J］.Psychometrika，1949，14（2）： 95-116.

[9] Batagelj V， Zaversnik M.An o（m） algorithm for cores decomposition of networks［EB/OL］.（2003-10-25）［2023-10-11］.

[10] Cui W Y， Xiao Y H， Wang H X，et al.Local search of communities in large graphs［C］//Proceedings of the 2014 ACM SIGMOD International Conference on Management of Data.Snowbird Utah：ACM，2014：991-1002.

[11] Li R H， Qin L， Yu J X，et al.Influential community search in large networks［J］.Proceedings of the VLDB Endowment，2015，8（5）：509-520.

[12] Huang X， Lakshmanan L ．Attribute truss community search［EB/OL］．（2016-09-01）［2023-04-15］.

[13] Fang Y X， Cheng R， Luo S Q，et al.Effective community search for large attributed graphs［J］.Proceedings of the VLDB Endowment，2016，9（12）：1233-1244.

[14] 赵琳琳，吴安彪，袁野，等.位置社交网络上的图表示学习［J］.计算机学报，2022，45（4）：838-857.

[15] 龚卫华，陈彦强，裴小兵，等.LBSN中融合多维关系的社区发现方法［J］.软件学报，2018，29（4）：1163-1176.

[16] 刘向宇，安云哲，周大海，等.保持结点间可达性的社会网络图匿名技术［J］.沈阳航空航天大学学报，2015，32（6）：50-58.

[17] Zhu Q J， Hu H B， Xu C，et al.Geo-social group queries with minimum acquaintance constraints［J］.The VLDB Journal，2017，26（5）：709-727.

[18] Fang Y X， Cheng R， Li X D，et al.Effective community search over large spatial graphs［J］.Proceedings of the VLDB Endowment，2017，10（6）：709-720.

[19] Haldar N， Li J X， Akhtar N.Co-engaged location group search in location-based social networks［J］.IEEE Transactions on Knowledge and Data Engineering，2024，36（7）：2910-2926.

[20] Zhu H J， Liu W， Yin J，et al.Continuous geo-social group monitoring in dynamic LBSNs［J］.IEEE Transactions on Knowledge and Data Engineering，2023，35（8）：7815-7828.

[21] Trung H T， Van V T， Tam N T，et al.Learning holistic interactions in LBSNs with high-order，dynamic，and multi-role contexts［J］.IEEE Transactions on Knowledge and Data Engineering，2023，35（5）：5002-5016.

[22] Zong C Y， Dong Z F， Yang X C，et al.Efficiently answering why-not questions on radius-bounded k-core searches［M］.Lecture Notes in Computer Science.Cham：Springer Nature，2023：93-109.

[23] Zhang Y K， Yu J X， Zhang Y，et al.A fast order-based approach for core maintenance［C］//2017 IEEE 33rd International Conference on Data Engineering.San Diego：IEEE，2017：337-348.

基金资助

辽宁省教育厅重点攻关项目(JYT19007)