学位论文简介
大规模图数据处理已成为大数据处理的重要组成部分，也是国家实施大数据战略的关键支撑。作为图数据处理中的核心任务之一，社区挖掘旨在从图中发现满足特定约束条件的顶点群体（即社区）。随着时代的发展，图数据逐渐呈现出图类型多样和数据规模巨大的特点，为社区挖掘带来了新的挑战与需求，亟需高性能的社区挖掘算法、高效的索引技术和面向新型图的社区模型。本文主要研究大规模图中社区挖掘关键技术，面向超图、二部图和无向图三种代表性图中的社区挖掘子问题，设计高性能挖掘算法和高效的索引结构，以提升社区挖掘效率，同时，提出新颖有效的社区挖掘模型。本文的主要工作和创新点如下：
1. 二部图中最大biplex社区搜索。从CPU算法优化和FPGA硬件加速两个角度对最大k-biplex社区搜索算法进行改进。首先，从理论角度证明了该问题是NP-Hard问题及其不可近似性。其次，提出了基于Core的搜索框架，并进一步改进该框架。还提出了基于对称分支的分支限界搜索算法。基于FPGA，设计了启发式k-biplex社区搜索算法。
2. 无向图中结构化社区检测。提出了一种新的结构化社区检测索引设计原则，通过直接检索社区来替代基于广度优先搜索的结构化社区检测过程。基于参数对之间的支配关系和结构化社区的嵌套结构，提出了森林索引，在特定参数维度上，将嵌套的社区组织为树结构，将社区检测过程变为在特定树中遍历收集社区，以提升搜索性能。还提出了参数对阈值索引，从两个维度对社区的嵌套关系进行组织，并显式刻画社区之间的连通性。
3. 超图中结构化社区检测。面向大规模超图，首次提出了以超边为中心的超图结构化社区检测新模型，利用不同超边连接的顶点之间的余弦相似度来判断超边的相似度，并根据超边之间的公共顶点来判定超边的连通性，进而定义超边结构化社区。此外，提出了顺序索引和相应的查询算法，以加速社区检测。
主要学术成果
[1] Dong Pan, Xu Zhou*, Lingwei Li, Quanqing Xu*, Chuanhui Yang, Chenhao Ma, and KenLi Li, 2025. Efficient Structural Clustering over Hypergraphs. IEEE International Conference on Data Engineering (ICDE 2025) . (CCF推荐A类会议，第一作者)
[2] Dong Pan, Xu Zhou, Wensheng Luo*, Zhibang Yang, Qing Liu, Yunjun Gao, and Kenli Li. 2024. Accelerating maximum biplex search over large bipartite graphs. The VLDB Journal . (CCF推荐A类期刊，第一作者)
