基于位置社交网络的用户社区和属性位置簇搜索

宗传玉 李箬竹 夏秀峰

摘 要：针对当前社区搜索问题不能完全满足用户活动位置推荐的需求，提出了属性地理社会社区搜索问题（AGCS）。该问题是从带有属性的基于位置的社交网络中寻找紧密连接的用户社区和属性位置簇的工作。定义一个基于属性约束和签到信息的新社区度量用以衡量结果质量，并提出三种新的搜索算法来解决该问题：一种基本算法，一种基于贪心扩展策略的局部算法以及优化的局部算法。实验证明提出的算法能够在带有属性的基于位置的社交网络中有效地搜索高质量的用户社区和属性位置簇，局部算法社区分数较基本算法增加近1.5倍，优化的局部算法在保证社区质量的基础上将算法效率提升到原来的近40倍。

关键词：社区搜索； 用户社区； 属性位置簇

中图分类号：TP301.6   文献标志码：A

文章编号：1001-3695（2023）09-015-0000-00

doi：10.19734/j.issn.1001-3695.2023.01.0019

User community and attribute location cluster search in

location-based social networks

Zong Chuanyu， Li Ruozhu， Xia Xiufeng

（School of Computer Science， Shenyang Aerospace University， Shenyang Liaoning 110136， China）

Abstract：This paper proposed the attribute geosocial community search problem （AGCS） to address the current community search problem that does not fully satisfy the need for user activity location recommendations. This problem was the work to find closely connected user community and attribute location cluster from location-based social networks with attributes. It defined a new community metric based on attribute constraints and check-in information to measure the quality of results， and proposed three new search algorithms to solve the problem： a basic algorithm， a local algorithm based on a greedy expansion strategy， and an optimized local algorithm. Experiments demonstrate that the proposed algorithms can effectively search user community and attribute location cluster in location-based social networks with attributes. The community score of local algorithm results is nearly 1.5 times higher than that of basic algorithm， and the efficiency of optimization algorithm is improved to nearly 40 times on the basis of ensuring community quality.

Key words：community search; user community; location cluster with attribute

0 引言

社区是一个内部紧密连接、外部稀疏连接的子图。在图中搜索社区是许多图分析應用程序中的基本问题。社区搜索旨在图中搜索与一组查询节点和一些查询约束相关的社区［1，2］。从网络中检索社区可以用来组织活动，推荐用户可能认识的人等［3］。

随着数据种类的增加和用户需求的变化，仅以用户关系为搜索条件的社区搜索已不能完全满足社区搜索的需求。属性社区搜索是在常规社区搜索的基础上，通过向用户关系添加属性约束，使得可以搜索同时满足用户关系结构和关键字内聚性的属性社区。然而，单纯地添加属性约束的社区搜索可能返回一个具有大范围空间位置的社区。

随着基于位置的社交网络的出现，社区搜索不再局限于以用户之间的密切关系为搜索标准，还可以在用户关系的基础上添加位置条件。现有大多数包含有位置约束的社区搜索只产生了单个用户社区，很少有研究在与用户社区对应的基于位置的社交网络位置上探讨用户社区和位置簇的搜索问题，因此，基于位置的社交网络上的社区搜索出现了。Kim等人［4］提出的地理社会社区搜索（GCS）要求搜索到的社区网络和位置簇不仅与用户关系密切，而且在地理上也紧密相连。在基于位置的社交网络中搜索社区会产生一个用户社区和一个位置簇，簇中包含与用户社区对应的所有位置。

单一的属性约束或位置约束并不能完全满足所有用户的需求。本文结合两者共同作为社区搜索的约束条件，以获得在合理空间范围内的理想社区。为了获得同时满足属性和位置约束的社区，需要在带有属性的基于位置的社交网络上同时对位置和属性进行约束。所以本文提出了属性地理社会社区搜索（AGCS）问题，AGCS要求在带有属性的基于位置的社交网络中寻找一个紧密连接的用户社区和一个与用户社区紧密连接的属性位置簇。

图1表示一个带有属性的基于位置的社交网络，它包含用户网络、具有属性的位置节点集和签到信息。用户网络中的每个节点代表一个用户，位置节点集中的每个节点表示用户可能访问的位置，两者之间的边表示用户曾到达过该位置，ai表示位置li的属性/关键字。假设图1中的用户u11想去看电影，他需要一些关于电影院以及同行人的推荐，这时可以使用AGCS，找到一个用户社区和一个具有指定属性“电影”的空间位置簇。

本文的主要贡献如下：a）基于属性约束和签到信息，定义了一种新的社区度量。b）提出了在带有属性的基于位置的社交网络上的属性地理社会社区搜索（AGCS）问题。据调查，这是第一个找到具有高社区度量的一个用户社区和一个满足属性约束的空间位置簇的工作。c）提出基本算法得到属性地理社会社区搜索（AGCS）问题的近似解，在基本算法的基础上提出了局部算法提高了结果社区的质量。d）提出了优化的局部扩展算法，在保证了社区质量的基础上，算法的效率平均提高了近40倍。e）在真实数据集和合成数据集上进行了大量的实验，结果表明，本文提出的算法可以有效地在带有属性的基于位置的社交网络中搜索用户社区和属性位置簇。

1 相关工作

在基于结构约束的社区搜索的基础上，还有以下几种搜索条件下的研究：

基于地理位置约束的社区搜索研究，Zhu等人［5］提出了一组满足最小认知约束的地理社会集群查询（GSGQs），以在LBSN上生成一个有凝聚力的群体。Wang等人［6］提出了一个包含地理半径约束的社区搜索问题，在一个基于位置的社会网络上寻找一组空间邻近的群体。

基于属性约束的社区搜索研究，Fang等人［7］提出了属性社区查询（ACQ），得到了基于关键字内聚性的属性社区（AC）。Zhang等人［8］在属性图上研究了以关键字为中心的社区搜索（KCCS），提出了一种不输入查询节点只用查询关键字来搜索社区的方法。Chen等人［9］基于属性社区搜索提出的无参数上下文社区模型只需要一组描述与期望匹配的社区上下文关键字，就可以返回满足约束的社区。Liu等人［10］提出了一个以顶点为中心的属性社区（VAC）问题来解决属性设置困难和单一查询属性类型的问题。Apon等人［11］提出了基于社会和空间文本的灵活的top-k社会空间关键字感知组查询（SSKGQ）问题。文献［12］设计了属性网络中结合用户偏好的社区搜索和离群点检测方法。

同时基于位置和属性的社区搜索的研究，Guo等人［13］提出了多属性社区（MAC）搜索，并研究了两种有效计算top-j多属性社区的方法。Chen等人［14］提出了共定位社区搜索（LCD）问题，其得到的社区满足k-truss约束和用户的空间位置约束。Chen等人［15］还提出了地理社会群体搜索问题，来获得一个与某一地点相近并且社会关系密切的一群人，并提出MKCSSG模型，在找到最佳的社区结果的同时缩小了搜索空间。文献［16］提出了异质网络中基于元路径P和元结构S的P-距离和S-距离及（k，d，P）-truss和（k，d，S）-truss社区模型以度量子图的结构内聚性，同时提出了关键词属性得分函数用于度量不同子图的关键词属性相关性。

在当前的社区搜索研究中，同时基于位置和属性的社区搜索只考虑了用户的需求，返回的结果只包含独立的用户社区，不能完全满足用户活动位置推荐的需求。基于位置的社交網络上的社区搜索［4］的出现为用户提供了一组紧密联系的用户社区和位置簇，但当用户对推荐的活动位置有属性需求，例如用户希望推荐的位置可以用来举行一个生日聚会，已有的工作返回的结果会包含大量与“生日聚会”无关的位置，不能完全满足用户的需求。基于以上情况，本文在带有属性的基于位置的社交网络上进行了基于位置和属性的社区搜索的研究，返回同时满足内聚性约束、空间约束和属性覆盖率的一组具有高访问次数的用户社区和属性位置簇。

2 属性地理社会社区搜索

带有属性的基于位置的社交网络（location-based social network with attributes，LBSNA）：给定一个无向图G=（V，E），G表示由一组节点V和一组边EV×V组成的社交网络。VH是V中节点的子集，H=（VH，EH）表示由VH诱导的G的子图。签到图由一个二分图GC=（VU，VL，EC）表示，其中VU是一组用户节点，VL={（li，A（li））}是一组具有A（li）={a1，a2，a3，…，aj}属性标签的位置点，（u，l）∈EC是一条签到边，代表用户u到位置l的签到，W（u，l）∈R表示边（u，l）∈EC的权重。签到权重W可以用来表示用户到位置的签到频率。LBSNA表示为N=（GU，VL，GC），该网络由一个社交网络GU、一组带有属性标签的位置节点集VL和一个签到图GC组成。

社区通常是一个满足结构内聚性的子图，结构内聚性是对社区联系紧密程度的度量，有k-core、k-truss和k-clique等［1］。尽管本文方法可以简单地拓展到别的结构，但在本文中使用k-core作为结构内聚性的度量［17］。定义deg（v）为直接连接到节点v的节点数，即节点v的邻居数，deg（v）也被称为一个节点的度。此外，给定一个子图H=（VH，EH），δ（H）返回节点v∈VH的最小度。k-core的定义如下。

定义1 k-Core。给定正整数k，当图的子图Hk满足v∈Hk，δ（Hk）≥k，并且Hk连通时，称Hk是一个k-core。

如图2所示，节点{u1，u2，u3，u4，u5，u6，u10，u11，u12}诱导的子图为一个2-core，由{u3，u4，u5，u6，u10，u11，u12}诱导的子图为一个3-core。

定义2 用户社区（user community）。给定一个社交网络GU，和一个度阈值k，用户社区HU=（VHU，EHU）是图GU的一个连通子图，满足度约束k，即v∈VHU，deg（v）≥k。

定义3 距离可达（distance reachable）。给定位置节点集VL中的两个位置节点li和lj，距离阈值r，假设i=1，j=n。若存在节点集{l1，l2，l3，…，ln}∈VL，任意节点集中节点lx和lx+1之间的距离dis（lx，lx+1）≤r（dis（lx，lx+1）表示lx到lx+1之间的距离），则称li和lj距离可达。

定义4 属性位置簇（attribute location cluster）。给定一个位置节点集VL，一个距离阈值r，一个查询属性集AQ={a1，a2，…，an}和一个度阈值k。如果满足以下条件，则一组位置点LAC构成位置簇。

a）li，lj∈LAC，li和lj是距离可达的；

b）li∈LAC，AQA（li）；

c）LAC按半径r约束生成的位置网络满足k-core。

基于属性位置簇的性质，需要从属性位置网络中获取属性位置簇。通过为满足属性约束并且距离小于等于半径约束的点创建边，可以得到属性位置网络。

图3（a）所示是一个属性位置节点集，由l1～l18共18个带有不同属性标签的位置节点组成。图3（b）为图3（a）中的位置节点以r=0.5为半径划分并创建的属性位置网络。可以看出，基于位置节点集和半径阈值r构造的位置网络包含{l1，l2，l3，l4，l5，l6，l7}、{l8，l9，l10，l11，l12}和{l14，l15，l16，l17，l28}三个连通分量，连通分量中的任意两个节点都是距离可达的。在距离阈值r=0.5和度阈值k=2约束下，可以得到位置网络{l8，l9，l10，l11，l12}和{l14，l15，l16，l17，l28}，如圖3（c）。节点{l14，l15，l16，l17，l28}的集合满足AQ={a1，a5}属性约束，该集合构成的网络就是属性位置簇。

基于第1章中给出的应用和本文模型对属性覆盖密度、内聚性约束和用户对满足属性要求的位置的高签到偏好的需求，本文定义了一个社区质量度量。

定义5 社区分数（community score）。根据属性约束和签到信息，定义社区分数如下：

SG=x×|Vt||Va|+y×∑μ∈HU，v∈HALW（μ，v）∑μ∈HU，ω∈GALW（μ，ω）（1）

其中：|Vt|表示搜索到的属性位置簇中位置节点的个数；|Va|表示原始位置节点集中满足属性约束的位置节点的数量；W（μ，v）是（μ，v）边的权重;∑μ∈HU，v∈HALW（μ，v）是用户社区中用户到属性位置簇的签到边的权重和；∑μ∈HU，ω∈GALW（μ，ω）是用户社区中用户到原始位置节点集中满足属性约束的位置上签到边的权重和；x+y=1。最大化的社区分数的含义是希望结果属性位置簇尽可能多地覆盖满足属性约束的位置点，且结果用户社区尽可能多地在结果属性位置簇中签到。

x和y的取值描绘了用户对属性覆盖和访问密度的偏好。在本文中设置系数x=y=12。边权重W（μ，v）=1。图1所示为一个带有属性的基于属性的社交网络，其中存在一个AGCS结果社区由{〈u10，u11，u12，u13〉，〈l14，l15，l16，l17，l18〉}组成，该属性地理社会社区的社区分数为SG=1/2×5/16+1/2×8/18=109/288。

问题定义 属性地理社会社区搜索（attribute geosocial community search，AGCS）。给定一个带有属性的基于位置的社交网络N=（GU，VL，GC）、一个查询节点集QVGU∪VL、一个距离阈值r、一个度阈值k和查询属性集AQ={a1，a2，…，ai}。属性地理社会社区搜索问题旨在找到一个满足所有查询约束的用户社区HUGU和一个属性位置簇LAC，并且最大化社区分数。

3 属性地理社会社区搜索方法

3.1 基本算法

为了得到一个高质量的结果社区，首先需要得到一些满足查询半径约束和内聚性约束的用户候选结果和同时满足属性约束的位置候选结果。然后，通过计算，在候选结果中找到具有最大社区分数的社区。

通过对位置节点中距离小于半径约束的节点创建边，构建了一个位置网络。为了加快建立和删除位置网络的过程，在建立网络之前需要先删除不满足属性约束的位置节点。然后找到两个网络图中度不小于k的所有候选连通分量，这些候选连通分量满足结构内聚性约束。最后对两组候选连通分量一一进行分数计算并得到最大社区分数的结果。

算法1 基本算法

输入：图N=（GU，VL，GC）;查询节点集QVGU∪VL;查询属性集AQ;半径r;度阈值k。

输出：用户社区HU;属性位置簇LAC;社区分数Score 。

CU←OCC（GU，Q，k）；

从VL中删除所有不包含查询属性的位置节点；

for each v∈VL

通过R-tree获得节点v的可能邻居NL；

将节点v加入到属性位置网络GAL中；

for each nj∈NL

计算v与nj之间的欧式距离Dj；

if Dj

将节点nj和边（v，nj）添加到GAL中；

CL←OCC（GAL，Q，k） ；MaxScore←0；

从CU和CL中删除不包含Q的候选网络；

for each ci∈CU

for each cj∈CL

计算由ci、cj组成的社区的社区分数Score；

if Score>MaxScore

MaxScore←Score；HU←ci，HAL←cj；

返回HU←ci，HAL←cj，Score。

基本算法由两个部分组成，用户社区搜索和属性位置网络搜索。如算法1所示，首先获得候选用户连通分量的集合，利用OCC（GU，Q，k）函数得到满足约束条件的节点集。OCC（）的主要过程是移除所有度小于k的节点，同时移除因为受删除其他节点影响导致度小于k的节点，直到所有节点的度大于或等于k。然后删除位置节点集中所有不满足属性约束的节点。属性位置网络的生成是借助R-tree完成的，下一步生成候选属性位置连通分量集，并将不包含查询节点的连通分量从两个连通分量集合中删除，最后计算每组连通分量（一个用户连通分量和一个位置连通分量）的社区得分，社区分数最大的一对连通分量就是属性地理社会社区搜索的结果。

3.2 局部算法

由于k-core的搜索算法隐含有找最大连通分量的约束，基本算法得到的结果社区分数并不是当前图可以得到的最大分数，为了得到具有较高社区分数的结果，提出了局部算法。

局部算法的基本思想是从给定的查询节点出发，使用给定的贪心扩展策略向当前解决方案中迭代的添加节点，逐步扩大当前解决方案的规模。

局部算法初始化当前解决方案为查询节点构成的网络，对两个网络分别初始化一个优先队列，优先队列存储可能要插入到当前解决方案中的候选节点。初始化优先队列为查询节点的邻居节点，如果不包含任何用户或位置查询节点，则当前解决方案对应的签到图的邻居节点将被插入到优先队列中。然后根据队列优先级标准维护两个优先队列。

局部算法的关键在于优先队列的排序标准，如下：a）优先队列中的节点到当前解决方案的签到边权重和;b）优先队列中的节点在当前解决方案的邻居个数。

第一个标准隐含的意义是保证插入到当前解决方案的节点对社区分数的贡献，可以增加当前解决方案的签到权重。第二个标准是保证加入的节点能更快地使解决方案满足结构内聚性。第一个标准的优先级高于第二个标准。

性质1 给定修剪后的属性位置网络GL，不存在HLGL可以使社区分数更高。

由性质1可以看出基本算法可以直接得到最优社区分数的属性位置网络，因此，局部算法只需要重新生成用户网络即可。

算法2 局部算法

输入：用户网络图GU，属性位置网络GAL，查询节点集QVGU∪VL，查询属性集AQ，度阈值k。

输出：用户社区HU，属性位置簇LAC，社区分数Score。

初始化用户当前解决方案HU、位置解决方案HAL、用户优先队列UWait；

while δ（HU）

for each vi∈UWait

分别计算节点vi两个优先级标准的分数；

对UWait中节点按照优先级标准进行排序；

将UWait中的第一个节点插入到HU中，并将这个节点的邻居插入到UWait中；

reScore←Score←HU和GAL組成的社区的社区分数；

while reScore=Score

找到优先队列中优先级较高且保证结构内聚性的点vu；计算插入vu后的社区分数reScore；

if reScore>Score

将vu插入HU中；Score←reScore；

else

reScore=0；

返回HU，HAL，Score。

算法2描述如下，初始化解决方案为用户查询节点和输入的属性位置网络，将查询节点的邻居插入到优先队列中，按照优先级a）b）计算优先队列中的节点标准分数并排序。将优先队列的第一个节点插入到社区解决方案中，然后将这个节点的邻居插入到优先队列中，迭代以上过程直到社区解决方案满足结构内聚性，然后计算社区分数。为保证最终得到的解决方案的社区分数最大，对优先队列的排序标准进行了修改，继续对解决方案进行扩展。

修改后的排序标准如下：a）优先队列中的节点到当前解决方案的签到边权重和/优先队列中的节点到原始网络的签到边权重和;b）优先队列中的节点在当前解决方案的邻居个数。

使用新标准重新计算优先队列标准分数，取标准b）分数满足k约束的节点并按标准a）降序排序。然后假设将优先队列中的第一个节点插入到社区解决方案，并计算插入后的社区分数，如果分数变大则更新社区解决方案和社区分数。重复上述过程直到社区分数不在增长，返回社区分数最大的结果社区。

复杂度分析：判断结果社区是否满足结构内聚性并且对优先队列进行维护的复杂度是O（n（c+n log n+m+n）+n），其中对每个点都计算一次优先级分数的复杂度是O（c），c是用户社区到位置社区总签到次数。优先队列排序的时间复杂度为O（n log n），UWait的维护代价是O（n），k-core判断的代价是O（m+n），m是用户社区中边的数量，n是用户社区节点数量。第二个循环的代价同上，所以最终时间复杂度为O（n（c+n log n+m+n）+n）。

3.3 优化算法

局部算法优化了基本算法的结果质量，但局部算法的执行效率不高，为了提升局部算法的执行效率，首先通过对图的结构内聚性判断过程进行分析，开发了一种快速对节点度进行维护的优化策略。然后由于局部算法在每一次优先队列发生变化时，都需要对优先队列进行重排操作维护其优先级。分析算法流程，通过将优先队列重构和最佳节点选择组合到一起，排序过程可以从局部算法中剔除。结合以上两种优化策略，最终得到了优化的局部算法。

3.3.1 图结构判断

局部算法要求在每次插入新节点后对当前解决方案进行结构内聚性判断，当前最优的结构内聚性判断算法时间复杂度是O（m+n），随着解决方案规模的增长，这部分算法的执行代价也在持续增长。为了优化这个过程，优化算法首先初始化变量kmin为当前解决方案中度最小的节点。每次产生新的节点插入时，kmin维护为新解决方案中度最小的节点，直到kmin大于等于k。合理的数据结构设计使得更新过程中不需要遍历全图，只需要比对当前插入节点及受当前插入节点影响导致度增加的节点的度。优化后的时间复杂度为O（1）。

3.3.2 优先队列维护

局部算法中，优先队列的维护要求每次向优先队列插入节点都需要对优先队列进行排序，即使最佳的排序策略也具有O（n log n）的代价，由于每次只需要提取当前最佳节点插入到结果中，优化算法把排序和节点分数计算结合，在计算分数时保留了最佳节点，去掉了排序的过程。

算法3 优化算法

输入：用户网络图GU，属性位置网络GAL，查询节点集QVGU∪VL，查询属性集AQ，度阈值k。

输出：用户社区HU，属性位置簇LAC，社区分数Score。

初始化用户当前解决方案HU位置解决方案HAL、用户优先队列UWait，指针m指向待插入节点及其两个标准的分数sm1，sm2 ；

kmin←δ（HU）；

while kmin

for each vi∈UWait

计算节点vi两个优先级标准的分数s1，s2；

if s1

m指向vi，sm1←s1；

else if s1==sm1并且s2>sm2

m指向vi，sm1←s1， sm2←s2

将m指向的节点插入到HU中，将kmin更新为HU的最小度，

reScore←Score←HU和GAL组成的社区的社区分数；

while reScore=Score

找到优先队列中优先级较高且保证结构内聚性的点vu，计算插入 vu后的社区分数reScore；

if reScore>Score

将vu插入HU中；Score←reScore；

else

reScore=0；

返回HU，HAL，Score。

算法3描述如下，將用户查询节点插入到社区结果HU中，将查询节点的邻居插入到优先队列UWait中，指针m指向队列中的节点，sm1为指向节点的标准a）的分数，sm2为指向节点的标准b）的分数，记录社区结果HU中节点的最小度值kmin。当kmin

复杂度分析：记录并维护社区结果的最小度和可能插入结果社区的节点，这个过程的复杂度是O（n×c+n），其中对用户社区中每个点都计算一次优先级分数的代价是c，c是用户社区到位置社区总签到次数。n是用户社区节点数量。第二个循环同上，所以最终时间复杂度为O（n×c+n）。

4 实验与评价

4.1 数据描述与实验设置

本文使用了以下三个数据集进行实验：

a）Yelp（YP）［3］。Yelp数据集包括1 987 897名用户，177 969个商家，908 915次签到记录，以及超过120 000个属性。本文从中随机抽取了100 000个用户节点，177 969个商家和908 915条签到信息生成数据集。

b）Gowalla（GL）［17］。Gowalla是一个基于位置的社交网站，Gowalla数据集包括196 591名用户，172 979个地点，6 442 890条签到信息。从中随机抽取了100 000用户，100 000位置，6 442 890条签到信息生成数据集。

c）Brightkite（BK）［18］。Brightkite数据集包括58 227个用户和772 967个地点，4 491 143条签到信息。从中随机抽取一个了58 227个用户和100 000个带有183 384条签到记录的位置节点生成数据集。

因为数据集Gowalla、Brightkite不包含属性，所以将数据集进行分组，给每组位置节点，随机分配数量不等的10种属性，由此合成需要的数据集。

实验设置各参数默认值为：k=20，|Q|=2（一个用户查询点，一个位置查询点），|A|=1，r=50 m。

实验首先研究了三个算法在同样的参数设置下、不同数据集上的社区质量，然后研究了优化策略的有效性。参数的变化可能会对算法的执行效率产生影响，所以接下来通过改变参数k、参数r和属性个数研究了算法的执行效率变化，最后通过改变数据集的大小，证明了算法的可伸缩性。

所有算法使用GNU C++实现。实验运行在一台Windows 10系统、3.9 GHz CPU、256 GB RAM和1 TB磁盘的PC上。

4.2 实验评估

a）模型差异。与本文模型最相近的工作是文献［4］中的地理社会社区搜索（GCS），在同样的内聚性和半径约束下，通过设置不同的查询点进行实验，地理社会社区搜索中质量最佳的GRA算法推荐的位置簇中满足属性需求的位置点覆盖率最多达到了32.3%，所以GCS并不能满足用户对属性的需求。任意条件下，AGCS都可以在保证内聚性和紧密的空间关系的同时，保证提供的位置簇100%的属性覆盖。

b）社区分数评估。如图4所示，通过设置k，r及查询属性数量为默认值，本文评估了三个算法在三个数据集上的社区得分表现，可以发现local和optimization算法的社区分数都在basic算法的基础上获得了提升，实际通过观察实验结果和实验过程，local和optimization的最终结果社区签到贡献相较basic更加紧密，规模也缩小了。

优化策略有效性评估：如图5所示，通过设置各项参数为默认值，在YP、BK和GL数据集上，分别取出10组不同的查询点，并在实验后取均值评估了本文提出的优化策略的有效性，观察实验图可以发现，在真实世界的数据集Yelp上效率提升了约14倍，在Gowalla和Brightkite数据集上效率各提升了约44和55倍，平均下来optimization相较local获得了约40倍的效率提升。

d）参数k对效率影响评估。参数k衡量了用户对查询结果内聚程度的偏好，k从结构内聚性方面约束查询结果，通常情况下越高的k值带来越少的图节点数量。

为了研究内聚性变化对算法执行效率的影响。如图6所示，通过设置r和查询属性数量为默认值，在YP和GL数据集上设置k为20～40，在BK数据集上设置k为5～20。分别研究了参数k的变化对实验效率的影响，k取值范围的差异是因为数据集平均节点度不一致。一种直觉是随着参数k的增大，算法效率应该获得提高，因为参与运算的点和边的数量可能减少。但实际上通过实验发现k并不与local和optimization需要运算的社区规模正相关，k的变化导致Basic获得不同规模的用户社区，用户社区规模越大，local和optimization算法的执行时间就越长，但总体来说optimization在不同规模的社区下都能获得较好的执行效率。

参数r对效率影响评估：参数r衡量了用户对位置网络构建半径的偏好，r的变化影响位置网络构造的范围，通常情况下越大的r值会带来越高的图平均节点度，进而带来越多的待处理节点数量和边数量。

为了研究r的变化对算法执行效率的影响。如图7所示，通过设置k和查询属性数量为默认值，在YP和GL数据集上设置r为30～70，在BK数据集上设置r为25～125。分别研究了参数r的变化对实验效率的影响，r取值范围的差异是因为数据集节点分布密度的不一致。通过实验发现r的变化几乎不对local和optimization算法的執行效率造成影响，因为基于性质1，local和optimization不再对位置网络进行运算，而r的变化改变了位置网络的内聚性，但几乎不改变用户社区。

e）查询属性数量对效率影响评估。属性变化衡量了用户对具有某一类特殊标签的位置的喜好，一种直觉是越多、越精细的属性要求可能导致越少的待处理位置节点。

如图8所示，通过设置k和r为默认值，在三个数据集上设置查询属性数量为1～3，分别研究了查询属性数量的变化对实验效率的影响，观察实验图发现随着查询属性数量的增长，算法总体效率呈现增长趋势，这是因为查询属性数量的增长导致待运算的位置网络节点数量大幅降低，尽管用户社区规模变化不大，但是位置网络节点数量的减少造成算法运算代价的降低，图8（b）体现出了这种代价的降低。图8（a）（c）属性数量从1～2时算法运算时间变化不大是因为候选位置网络节点数量并未因属性数量的变化产生太大的波动。

f）算法可伸缩性评估。如图9所示，通过设置k和r和查询属性数量为默认值，分别伸缩三个数据集的规模为20%～100%，研究了算法的可伸缩性，也研究了规模变化对算法执行效率的影响。观察图9（a），算法执行效率的波动是因为数据集规模的变化导致结果社区大小一直在不规律波动，这是因为basic算法找到的社区作为local和optimization的待处理社区。这导致basic的结果规模可能随着数据集规模的变化产生无序的变化。也就造成了local和optimization效率的波动，但在GL和BK上，随着数据集规模的变化，尽管local和optimization的待处理节点产生了变化，但处理的规模并没有剧烈波动，这导致了整个算法的执行代价趋于平稳。

4.3 实例研究

通过在真实世界的Yelp数据集上，设置k=15，r=0.05 km，使用得到的社区质量最佳的优化算法。本文进行了一个案例研究来证明AGCS的有效性。

组织活动：用户准备举行一个聚会，并希望得到一群人和一个特定地点的推荐来帮助用户举办活动。被邀请参加活动的人应该和用户关系密切，并且他们相互间的联系也很密切。推荐举办活动的地点应该被参加活动的人群频繁访问，并且满足活动主题。在本例中推荐地点需要能够提供聚会的相关服务。

为了找到这样的受邀人员和举办活动的候选地点，本文发出了一个AGCS查询，它由组织者、用户访问过的地点以及用户需要地点满足的功能“相关服务”组成。AGCS找到了一组由150个用户组成的社区和69个可以用来举办聚会的地点，这些地点共被用户社区进行过652次历史访问，且在空间上邻近。最终社区分数为0.151。

5 结束语

本文提出了属性地理社区搜索问题（AGCS），该问题可以在包含属性的基于位置的社交网络文中找到一个紧密连接的用户社区和一个属性位置簇。定义了一个衡量社区质量的社区分数计算函数并设计了一个基本算法、一个局部算法和一个优化的局部算法。最后基于三个数据集对提出的算法进行了效率和有效性的评估。

AGCS需要用户提供k、r、查询点和查询属性四个查询参数，由于用户并不一定具备相关专业知识，或者对网络不甚熟悉。提供合适的参数以获取一组满足用户需求的社区对于用户来说可能是困难的。在未来的工作中，将研究如何以有限的时间成本，通过查询参数推荐的方法有效地帮助用户探索符合用户需求的一组社区及其对应的查询参数。

参考文献：

[1]Fang Yixiang，Huang Xin，Qin Lu，et al.A survey of community search over big graphs［J］.The VLDB Journal，2020，29（1）：353-392.

［2]Sozio M，Gionis A.The community-search problem and how to plan a successful cocktail party［C］//Proc of the 16th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining.New York：ACM Press，2010：939-948.

［3]Liu Yiding，Pham T，Cong Gao，et al.An experimental evaluation of point-of-interest recommendation in location-based social networks［C］//Proc of the VLDB Endowment.New York：ACM Press，2017，10（10）：1010-1021.

［4]Kim J，Guo Tao，Feng Kaiyu，et al.Densely connected user community and location cluster search in location-based social networks［C］//Proc of the 29th ACM SIGMOD International Conference on Management of Data.New York：ACM Press，2020：2199-2209.

［5]Zhu Qijun，Hu Haibo，Xu Cheng，et al.Geo-social group queries with minimum acquaintance constraints［J］.The VLDB Journal，2017，26（5）：709-727.

［6]Wang Kai，Wang Shuting，Cao Xing，et al.Efficient radius-bounded community search in geo-social networks［J］.IEEE Trans on Knowledge and Data Engineering，2022，34（9）：4186-4200.

［7]Fang Yixiang，Reynold C，Chen Yankai，et al.Effective and efficient attributed community search［J］.The VLDB Journal，2017，26（6）：803-828.

［8]Zhang Zhiwei，Huang Xin，Xu Jianliang，et al.Keyword-centric community search［C］//Proc of the 35th International Conference on Data Engineering.Piscataway，NJ：IEEE Press，2019：422-433.

［9]Chen Lu，Liu Chengfei，Liao Kewen，et al.Contextual community search over large social networks［C］//Proc of the 35th International Conference on Data Engineering.Piscataway，NJ：IEEE Press，2019：88-99.

［10]Liu Qing，Zhu Yifan，Zhao Minjun，et al.VAC：vertex-centric attributed community search［C］//Proc of the 36th International Conference on Data Engineering.Piscataway，NJ：IEEE Press，2020：937-948.

［11]Apon S H，Ali M E，Ghosh B，et al.Social-spatial group queries with keywords［J］.ACM Trans on Spatial Algorithms and Systems，2021，8（1）：1-32.

［12]楊成波，周丽华，黄亚群，等.异质网络中基于关键词属性的Truss社区搜索［J］.计算机应用研究，2023，40（6）：1708-1714.（Yang Chengbo，Zhou Lihua，Huang Yaqun，et al.Truss community search based on keyword attributes in heterogeneous networks［J］.Application Research of Computers，2023，40（6）：1708-1714.）

［13]Guo Fangda，Yuan Ye，Wang Guoren，et al.Multi-attributed community search in road-social networks［C］//Proc of the 37th International Conference on Data Engineering.Piscataway，NJ：IEEE Press，2021：109-120.

［14]Chen Lu，Liu Chengfei，Zhou Rui，et al.Maximum co-located community search in large scale social networks［C］//Proc of the VLDB Endowment.New York：ACM Press，2018，11（10）：1233-1246.

［15]Chen Lu，Liu Chengfei，Zhou Rui，et al.Finding effective geo-social group for impromptu activities with diverse demands［C］//Proc of the 26th ACM SIGKDD Conference on Knowledge Discovery and Data Mining.New York：ACM Press，2020：698-708.

［16]李青青，马慧芳，李举，等.属性网络中结合用户偏好的社區搜索和离群点检测［J］.电子学报，2022，50（9）：2172-2180.（Li Qingqing，Ma Huifang，Li Ju，et al.Community search and outlier detection combining user preferences in attribute networks［J］.Acta Electronica Sinica，2022，50（9）：2172-2180.）

［17]Cho E，Myers S，Leskovec J.Friendship and mobility：user movement in location-based social networks［C］//Proc of the 17th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining.New York：ACM Press，2011：1082-1090.

［18]Cui Wanyun，Xiao Yanghua，Wang Haixun，et al.Local search of communities in large graphs［C］//Proc of ACM SIGMOD International Conference on Management of Data.New York：ACM Press，2014：991-1002.

收稿日期：2023-01-28；

修回日期：2023-03-20

基金项目：国家自然科学基金资助项目（61802268）；辽宁省自然科学基金面上项目（2022-MS-303）

作者简介：宗传玉（1985-），男，山东潍坊人，副教授，CCF会员，博士，主要研究方向为数据清洗、数据溯源、查询处理与优化；李箬竹（1997-），女（蒙古族）（通信作者），辽宁朝阳人，硕士研究生，主要研究方向为查询处理与优化（liruozhu@stu.sau.edu.cn）；夏秀峰（1964-），男，山东胶南人，教授，CCF会员，博士，主要研究方向为数据库、数据仓库.