学位论文简介

随着大规模图数据在社交网络、路网系统及空间众包等场景中的广泛应用，路径作为刻画节点间关联关系的核心结构，其分析与优化直接影响结构稳定性评估、可达性度量及资源调度效率。然而，路径相关问题通常面临组合爆炸与多约束耦合带来的高计算复杂性，传统方法难以在保证精度的同时实现高效处理。因此，本文围绕路径分析与优化展开研究，针对不同图模型设计高效分析与优化方法。

本文的主要创新点如下：

（1）在有向图中，针对节点退出引发的级联退化问题，提出有向$(k,l)$-core锚定最大化模型，刻画路径传播下的结构稳定性。设计FAD算法，通过候选剪枝与路径追踪机制，高效评估锚点影响范围，在有限预算下显著提升稳定社区规模，并在大规模数据上实现数量级性能提升。

（2）在带权路网图中，针对多约束条件下路径数量难以高效计算的问题，提出单源与多源有界路径查询模型（SSR/MSR）。设计基于枢轴分解的路径计数框架PSCD，将全局计数转化为局部子问题，避免指数级枚举，在保证精确性的同时显著降低计算复杂度，实现高效查询优化。

（3）在动态时空图中，针对空间众包中任务分配效率与稳定性不足的问题，提出双边偏好感知的动态任务分配模型（BDTA）。设计基于批处理与延迟接受机制的匹配算法（TIB、TIDA等），综合考虑轨迹路径、时间约束与偏好关系，在动态环境下有效提升总体满意度与匹配稳定性。

（4）从路径视角出发，系统研究不同图模型中的路径相关问题，形成覆盖结构优化、路径计数与动态匹配的方法体系，在保证解质量的同时显著提升计算效率，为大规模图数据分析与优化提供技术支撑。

主要学术成果

[1] Yang Huang, Yumeng Liu, Xu Zhou*, Tianyue Ren and, Zhibang Yang, Keqin Li and Kenli Li. 2026. Optimizing Dynamic Task Assignment in Spatial Crowdsourcing: Bilateral Preference-Aware Approaches. IEEE Transactions on Mobile Computing. (CCF推荐A类期刊, 第一作者)

[2] Yang Huang, Xu Zhou*, Yan Ding, Qing Liu, Haoxian Xu, and Kenli Li. 2026. Anchored Maximum Communities over Large Directed Graphs. PVLDB. (CCF推荐A类会议, 第一作者)