大规模图中图性质求解的低复杂度分布式算法研究

Graph Diameter, Radius, Girth, Centralities (including Closeness Centrality and Betweenness Centrality) and Clustering Coefficient are the key graph properties of large scale graphs. Due to the tremendous data volume (typical PB or EB level) and the rapid change of the data itself (such as the rapid change of the topology and weights), we need to solve the graph properties as quick as possible. The state-of-the-art centralized algorithms can only compute these graph properties either in Cubic or Subcubic time. As a result, this project aims at designing either linear or even sub-linear time low complexity distributed algorithms or distributed approximation algorithms for computing the key graph properties. We target on both unweighted and weighted large-scale graphs. In addition, we employ a system model like the mainstream distributed large-scale graph processing system called Pregel, i.e., we employ synchronous communications and message passing. Because the network bandwidth is limited and the message transmissions dominate the overal time complexity, we employ a standard CONGEST model which restricts that each link (edge) can only transmit O(log n) bits size message where n is the graph size. The CONGEST model poses the greatest challenge for designing linear or sub-linear time distributed algorithms or distributed approximation algorithms. We believe this project will not only enrich the theoretical studies of distributed algorithms but also give a good opportunity for combining distributed computing theory and practical large-scale graph applications.

图的直径、半径、围长(Girth)、中心度(Centralities)及聚类系数(Clustering Coefficient)是大规模图重要性质。大规模图由于数据量大(PB级)和数据变化快(如拓扑变化)，如何快速求解这些图性质是大规模图应用核心问题。集中式算法求解这些图性质需要立方或者亚立方时间。本项目旨在为这些图性质求解设计线性甚至亚线性时间低复杂度分布式算法或分布式近似算法。项目不仅针对无权图也针对有权图。算法采用大图主流处理系统Pregel模型，即同步通信和消息传递。由于网络带宽有限且大图处理系统中消息传递主导分布式算法运行时间，本项目采用经典的拥塞模型(CONGEST)，即限定每条链路(边)仅能传递O(log n)位(n为大图节点个数)大小消息。该拥塞模型的限制是设计低复杂度分布式算法或分布式近似算法最大挑战。本项目开展不仅对分布式算法理论研究而且对大规模图实际应用都有重要意义。

大规模图计算是大数据处理领域的核心问题，而面向大规模图设计低复杂度图性质求解算法是大图计算研究的关键挑战。课题组从并行分布式处理角度对大图分析中常用图性质，包括图的直径、半径、围长、介数中心度、聚类系数以及k-核中心性等设计了一系列基于拥塞模型(CONGEST Model)的低轮数复杂度，特别是线性和亚线性轮数复杂度分布式算法。此外，课题组还从图性质分布式计算难度方面进行了深入研究，针对最短路径介数中心度、随机游走介数中心度、图的围长等给出了国际上首个分布式计算下界，从而验证了所提相关分布式图性质求解算法为最优或近似最优。.课题组以上研究成果均发表于网络和并行与分布式计算理论和系统领域的顶级期刊和会议，包括CCF A类IEEE Transactions on Parallel and Distributed Systems期刊论文3篇，CCF A类INFOCOM会议论文2篇，CCF B类World Wide Web Journal论文1篇，CCF B类ICDCS会议论文3篇(其中1篇为短文)，以及CCF B类SPAA会议短文1篇。课题组还受邀在国内期刊发表2篇关于大图分布式计算以及大数据计算理论和算法综述方面的中文论文。此外，课题组还就相关研究结果申请了4项国内专利(1项已获授权)以及1项美国专利。人才培养方面，课题负责人基于该项目已经培养了5名硕士毕业生(另有3名合作指导硕士毕业生)。国内外学术交流方面，课题负责人作为程序委员会共同主席在ICDCS 2017会议上成功组织了一次大规模图计算的国际研讨会Big Graph Processing (BGP) 2017；此外课题负责人还多次应邀在国内复杂性与算法研讨会以及CCF大数据计算理论启智会上就低复杂度大图分布式计算展开了研讨，促进了国内外同行在大图分布式处理研究的深入交流。