作者及机构
本研究由Nur Al Hasan Haldar（科廷大学）、Jianxin Li（迪肯大学）、Naveed Akhtar（墨尔本大学）、Yan Jia（哈尔滨工业大学深圳校区）、Ajmal Mian（西澳大利亚大学）合作完成，发表于2024年7月的《IEEE Transactions on Knowledge and Data Engineering》第36卷第7期。
研究领域与动机
本研究属于基于位置的社交网络（Location-Based Social Networks, LBSN）领域的图计算与空间数据分析交叉方向。随着Foursquare、Yelp等LBSN平台的普及，用户通过“签到”（check-in）行为产生了大量社会-空间交互数据。传统研究多关注如何从LBSN中发现紧密连接的用户社区，但极少工作聚焦于从用户群体共同兴趣的角度挖掘地理位置组。本研究首次提出“协同参与位置组搜索”（Co-Engaged Location Group Search, CLS）问题，旨在识别一组空间邻近且被高度社会凝聚的用户群体频繁访问的地理位置。
科学问题与目标
CLS问题的核心是：给定一个查询位置，如何找到包含该位置的k个地理点的集合，满足：
1. 这些地点被多个满足最小社交连接数m的社会凝聚用户群体频繁访问；
2. 地点之间空间距离不超过阈值θ；
3. 通过设计的评分函数最大化社会连接性与签到密度的综合得分。
数据模型
LBSN被建模为四元组G=(V, E, L, E′)，其中V为用户，E为社交边，L为位置，E′为用户-位置签到边。通过构建位置网络（Definition 2）和m-core用户群体（Definition 1），定义θ-可达性（Definition 3）和参与用户组（Definition 4）。
评分函数
提出协同参与评分（Co-Engagement Score, SCE）（Definition 7）：
$$SCE(L_i, \hat{P}_m) = \alpha \cdot SSC(\hat{P}_m) + (1-\alpha) \cdot SCH(L_i, \hat{P}_m)$$
其中SSC衡量用户群体的社会连接密度，SCH衡量用户对位置组的签到密度，α为权重参数（默认0.5）。
Filter-and-Verify Algorithm (FVA)
- 过滤阶段：基于θ-可达性生成候选位置集CL，通过m-core分解候选用户组，剔除无效位置（Lemma 2-3）。
- 验证阶段：枚举所有k大小位置组合，验证其是否满足m-core参与用户组条件，保留SCE最高的组合。
- 复杂度：O(|CL|^k)，通过剪枝策略优化实际耗时。
Greedy Forward Expansion (GFA)
- 贪心策略：逐步添加使SCE增益最大的位置（公式3-4），通过推导δh的下界（公式6）快速剪枝（Lemma 4）。
- 复杂度：O(|CL|²t + |E|)，显著优于FVA。
Greedy Incremental Algorithm (GIA)
- 启发式规则：按三条优先级规则选择位置：
1. 与当前集合的共享签到边数；
2. 用户间的社交连接强度；
3. 单点签到用户数。
- 复杂度：O(|CL| log |CL| + k)。
数据集
在Gowalla、Brightkite和Yelp三个真实LBSN数据集上验证：
- SCE评分：FVA最优（Gowalla 0.41 vs. Baseline 0.22），GFA接近FVA但速度快3倍（图3）。
- 参数敏感性：
- k增大时，参与用户规模线性增长（图6），但GCS（对比算法）仅返回单一社区。
- θ扩大提升SCE，因搜索空间扩展（图8）。
- 计算效率：GFA在θ=30km、k=40时仍保持线性耗时，而FVA和GCS指数级增长（图10）。
科学价值
1. 首个系统研究LBSN中协同参与位置组的工作，填补了用户社区发现与地理位置分析的交叉空白；
2. 提出的SCE评分函数综合社会-空间双维度指标，为LBSN分析提供新范式。
创新性方法
- GFA的δh下界剪枝策略（Lemma 4）将组合搜索转化为贪心优化；
- GIA的三规则启发式实现O(n log n)高效求解。
应用前景
- 商业：精准广告投放（如Yelp商户定向优惠）；
- 城市规划：通过群体活动热点优化公共设施布局。
（注：专业术语如m-core、θ-reachable等首次出现时保留英文并在括号内标注中文翻译，后续直接使用中文术语。）