High-Level Processing of Huge-Scale Networks: Challenges from Graph Decomposition Theory to Practically Efficient Algorithms

对于Web链接图、社交网络、地图路网等大规模网络，我们的目标是基于图小理论和相关领域发展快速、高水平的图数据处理，并在这些领域获得新的基础性成果。具体来说，我们开发了一种新的图分解，称为核心树分解，作为复杂网络的模型，并利用该模型的良好特性，我们设计了新的快速算法，用于这些大规模社交网络的最短路径查询和可达性查询。我们还研究了精确指数算法，通过提出一类具有小图参数的可处理问题，从而增强了中等大小图的精确解在NP-hard棘手问题中的广泛应用。本文还介绍了量子计算的一些应用。

For huge-scale networks such as Web link graph, social network and map road network, we aim at developing fast and high-level graph data processing based on graph minor theory and related filed, together with deriving new fundamental results in those fields. Specifically, we develop a new graph decomposition, called a core-tree decomposition, as a model for complex networks, and by making use of this model with its nice characteristics, we devise new fast algorithms for shortest-path queries and reachability queries on these huge-scale social networks. Exact exponential algorithms are also investigated to enhance the wide use of exact solutions of moderately large graphs for NP-hard intractable problems by presenting a class of tractable problems having small graph parameters which hold for large social networks. Some applications to quantum computing are also shown.