学位论文简介
随着信息技术的发展，图数据的应用场景不断增加。二部图是一种特殊的图，可用于描述两类实体之间的联系。关于二部图的子图模型有很多，其中，最稠密的是二分团。然而，现有研究工作没有充分考虑二部图的边权重。为此，本文针对二部图，结合边权重的实际意义，开展以下工作：
为了提取关联性较强的社团，研究带权二部图中的最大边权重二分团查询算法。首先，基于传统的搜索框架，引入一种基线算法。然后，提出先进的上界和顶点访问顺序以降低搜索分支数目。最后，利用并行算法加速搜索，并设计高精度、高效率的启发式算法。实验结果表明，上述技术均十分有效。
为了保证稠密子图的存在性，研究不确定性二部图中的极大二分团枚举算法。首先，设计一种包含多个约束条件的分支限界算法。接着，综合考虑子图的顶点个数和概率信息以增强剪枝能力。最后，使用高效的实现方式，降低时间和内存开销。实验结果反映了各项技术的优越性。
为了发现核心积极团体，研究带符号二部图中的极大二分团枚举算法。首先，提出一种高效算法。然后，利用局部信息，尽早终止无用搜索分支，同时改进顶点访问策略，提升剪枝效果。最后，引入两种约简技术以降低图规模。实验结果表明，上述技术是十分必要且有效的。
主要学术成果
Jianhua Wang, Jianye Yang, Wenjie Zhang. Top-k Tree Similarity Join [C]. Proceedings of the 30th ACM International Conference on Information & Knowledge Management, 2021: 1939-1948. (EI，第一作者)
Jianhua Wang, Jianye Yang, Ziyi Ma, Chengyuan Zhang, Shiyu Yang, Wenjie Zhang, Efficient Maximal Biclique Enumeration on Large Uncertain Bipartite Graphs [J]. IEEE Transactions on Knowledge and Data Engineering, 2023, 35(12): 12634-12648. (SCI，第一作者)
