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

对于Web链接图、社会网络和地图道路网络等大规模网络，本文的目标是基于图子式理论和相关领域，发展快速、高层次的图数据处理，并在这些领域中得到新的基础性结果。 具体来说，我们开发了一种新的图分解，称为核心树分解，作为复杂网络的模型，并利用这个模型的良好特性，我们设计了新的快速算法，这些巨大的社交网络上的最短路径查询和可达性查询。 精确指数算法也被研究，以提高广泛使用的NP-难处理的问题，提出了一类易于处理的问题，具有小的图参数，适用于大型社交网络的中等大的图的精确解。 还展示了量子计算的一些应用。

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.