学位论文简介
随着大数据在新时代的发展，大规模图数据处理已成为大数据处理的重要组成部分，也是国家实施大数据战略的关键内容。作为图数据处理的关键任务，社区挖掘旨在挖掘出图中满足特定需求的连通子图结构，拥有广泛的现实应用。然而，随着时代的发展，图数据逐渐呈现出图类型多样和数据规模巨大的特点，为社区挖掘带来了新的挑战与需求，亟需面向新型图的社区模型、高性能的社区挖掘算法和高效的图数据管理技术。面对新的挑战与需求，本文主要研究大规模多类型图中社区挖掘关键技术，着重研究超图、二部图和无向图三种代表性图类型，针对新类型图提出新颖有效的社区挖掘模型；针对已有社区挖掘模型，设计高性能挖掘算法；并设计索引对图数据进行管理，以提升社区挖掘效率。本文的主要工作和创新点如下：
1.提出了以超边为中心的超图结构化社区检测新模型。以超边所包含的顶点之间的余弦相似度计算超边之间的相似度，并根据超边是否有公共顶点判定超边之间的连通性，并定义核心超边和结构化可达性，最终获取超边社区，从而进一步获取顶点社区。此外，还提出了顺序索引，以加速社区检测。
2.从CPU算法优化和FPGA硬件加速两个角度，对最大biplex社区搜索算法进行改进。还从理论角度证明了该问题是NP-Hard问题及其不可近似性。在CPU算法优化方面，提出了基于Core的搜索框架及其改进框架，还提出了基于对称分支的分支限界搜索算法。在FPGA硬件加速方面，提出了基于FPGA的启发式biplex社区搜索算法。
3.提出了一种新的结构化社区检测索引设计原则。形式化了参数对之间的支配关系，并刻画了结构化社区的嵌套结构性质。基于该性质，本文提出了森林索引，通过固定一个参数，将嵌套的社区组织为树结构，从而将BFS式社区检测变为在树中遍历收集社区检测结果。为进一步提升性能，还提出了参数对阈值索引，从两个维度对社区的嵌套关系进行组织，并显式刻画社区之间的连通性。
主要学术成果
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类会议，第一作者)
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类期刊，第一作者)
