学位论文简介
图的核分解用于计算图中所有顶点的核值，其有助于在挖掘重要图结构信息，在社区搜索、蛋白质结构分析和网络结构可视化等诸多应用中发挥着关键作用。本文以大规模图核分解作为研究对象，探索分布式环境下普通图、二部图核分解及动态维护算法模型。具体而言，本文取得的三项主要创新研究成果如下：
研究面向大规模图数据的分布式 k-core分解算法。当前基于以顶点为中心计算模式的分布式k-core分解算法中采用一种广播的消息传递机制，一方面，存在大量的冗余通信及计算开销；另一方面，处理大规模图k-core分解过程中易产生内存溢出问题。为此，分别提出了基于全局激活和层次剥离算法框架的分布式k-core分解新算法，通过引入基于顶点核值局部性特点的消息剪枝策略和以计算节点为中心的计算新模式，保证算法有效性的同时提升其性能。
研究面向大规模图数据的分布式核值维护算法。现有工作大多基于单机内存设计图k-core分解及其动态维护算法，无法有效处理大规模图数据。为此，提出了分布式核值维护算法。首先，为了得到初始化的顶点核值，基于以顶点为中心计算模式设计了一种分布式k-core分解算法，同时引入环式消息传递策略解决内存溢出问题。然后，探索了一种批-流结合的核值维护算法，并拟定一种合理的通信协议规避多任务并行执行时的消息串扰问题。
研究面向大规模二部图的分布式butterfly分析算法。Butterfly是二部图中最小的稠密子图单元，为系统化高效分析大规模二部图中butterfly结构，首次研究了分布式butterfly计数算法、分布式tip分解算法和分布式tip值维护算法。具体得，针对处理大规模二部图时可能发生的内存溢出问题，设计了基于顶点优先级的消息传递策略和消息聚合策略，提高了butterfly 计数算法和tip分解算法效率，并证明峰值通信量空间复杂度与图规模呈线性关系，解决了高并行度下内存溢出问题。针对当前在维护动态二部图tip分解结果方面研究的空白，提出了基于任务分解的分布式tip值维护算法，实现了对tip分解结果的增量式动态维护。
主要学术成果
Tongfeng Weng, Zhou X, Li K, et al. Efficient distributed approaches to core maintenance on large dynamic graphs[J]. IEEE Transactions on Parallel and Distributed Systems, 2021, 33(1): 129-143. (在线发表，CCF A类期刊，第一作者)
Tongfeng Weng, Zhou X, Li K, et al. Distributed Approaches to Butterfly Analysis on Large Dynamic Bipartite Graphs[J]. IEEE Transactions on Parallel and Distributed Systems, 2022. (在线发表，CCF A类期刊，第一作者)
Tongfeng Weng, Xu Zhou, Yixiang Fang, Kian-Lee Tan, Kenli Li. Finding Top-k Important Edges on Bipartite Graphs:Ego-betweenness Centrality-based Approaches. IEEE International Conference on Data Engineering (ICDE)（已接收，第一作者， CCF A 类会议）
周旭, 翁同峰, 杨志邦, 等. Distributed Algorithm for Tip Decomposition on Large Bipartite Graphs[J]. Journal of Software, 2021, 33(3): 1043-1056. (在线发表，CCF A类中文期刊，导师一作)
