Skyline Community Search over Edge-Attributed Bipartite Graphs

基本信息

• 论文标题：Skyline Community Search over Edge-Attributed Bipartite Graphs（边属性二分图上的 Skyline 社区搜索）
• 作者：Fangda Guo, Xuanpu Luo, Shiyuan Xu, Haowen Gao, Yanghao Liu, Huawei Shen, Xueqi Cheng
• arXiv 编号：arXiv:2401.12895（v2）
• 提交时间：2024 年 1 月 23 日（v1）；最后修订于 2026 年 4 月 27 日（v2）
• 录用信息：被 DASFAA 2026 接收
• 主题分类：Social and Information Networks (cs.SI)；Graphics (cs.GR)
• DOI：https://doi.org/10.48550/arXiv.2401.12895

摘要

二分图用于建模两类实体之间的关系，在实际应用中广泛使用。社区搜索作为二分图中的基础问题，已受到较多关注。然而，现有研究主要关注衡量顶点集合之间的结构内聚性，要么忽略边属性，要么只考虑一维重要性。

本文提出一种新的社区模型——边属性 Skyline 社区（edge-attributed skyline community, ESC），它既保持结构内聚性，又刻画二分图中多维边属性固有的支配（dominance）关系。为搜索 ESC，作者：

• 设计了一种高效的剥离算法（peeling algorithm），迭代删除每个维度上属性值最小的边；
• 设计了扩展算法（expanding algorithm），利用已证明的上界来缩减搜索空间并加速过滤无前景的顶点。

在大规模真实数据集上的大量实验验证了该方法的高效性、有效性与可扩展性。与已有方法相比的案例研究表明，该设计提升了结果的精确度与多样性。

关键词

二分图（bipartite graph）、社区搜索（community search）、边属性（edge attributes）、Skyline 社区、剥离算法、扩展算法