Sublinear Algorithms for Big Graphs

研究大型网络的一项基本任务是有效地分析其结构性质。例如，我们可能想知道网络是否连接良好，是否可很好地集群，是否具有某些特定子结构的许多副本(实例)等。鉴于现代网络很大，通常由数百万和数十亿个节点(网络图、社交网络等)组成，分析其结构的任务最近变得越来越具有挑战性，并且这项任务的运行效率变得至关重要。事实上，能够快速分析海量信息中的重要特征已经是一个价值数十亿美元的行业的一项关键技术(参见例如谷歌、雅虎、Facebook等)。在不久的将来，它的重要性可能会进一步增加。为了有效地管理和分析大型网络，近年来我们看到次线性时间算法的重要性上升，也就是说，使用比输入大小少得多的资源的算法。由于次线性算法只能处理一小部分输入，它们不适合于许多应用，特别是在寻求精确解的情况下；但最近我们看到一些次线性算法为各种不同领域的优化和决策问题计算近似解，这些问题出现在代数计算、网络、几何和计算机图形学等不同的领域。为了应对这些现代大型网络的挑战，该建议将利用PI在随机化算法领域的专业知识，通过在组合问题的次线性算法领域取得重大进展来开发新的算法技术来分析大图。中心目标是通过扩大次线性时间已知的问题的类别和刻画不可能存在次线性时间算法的问题来推进我们在图问题的次线性时间算法领域的知识障碍。主要的技术目标是在两个中心模型的背景下开发用于分析大型图的算法技术：属性测试算法和次线性时间近似算法。我们还计划将开发的技术应用于与次线性算法相关的进一步模型：数据流、动态和在线算法。我们的目标是应对次线性算法领域的重大挑战，我们的目标是取得重大进展。本项目的重点是这一领域的基础研究，旨在促进算法设计和分析的理论方面的进展。

A fundamental task in the study of large networks is to efficiently analyze their structural properties. For example, we may want to know if a network is well-connected, is well-clusterable, has many copies (instances) of some specific sub-structures, etc. Given that modern networks are large, often consisting of millions and billions of nodes (web graph, social networks, etc.), the task of analyzing their structure has become recently increasingly challenging, and the running-time efficiency of this task is becoming of critical importance. Indeed, being able to quickly analyze important features in the gigantic amount of information already is a key technology of a multi-billion dollar industry (see, e.g., Google, Yahoo, Facebook, etc.) and its significance will likely increase further in the near future. To efficiently manage and analyze large networks, in recent years we have seen a rise of the importance of sublinear time algorithms, that is, algorithms that use significantly less resources than the input size. Since sublinear algorithms can process only a small fraction of the input, they are not suitable for many applications, especially if exact solutions are sought; but recently we have seen a number of sublinear algorithms that compute approximate solutions for a variety of optimization and decision problems arising in such diverse areas as algebraic computations, networks, geometry, and computer graphics.To cope with these modern challenges of large networks, this proposal will exploit the expertise of the PI in the area of randomized algorithms to develop new algorithmic techniques for the analysis of big graphs by making significant advances in the area of sublinear algorithms for combinatorial problems. The central goal is to push forward the barriers of our knowledge in the area of sublinear-time algorithms for graph problems by enlarging the class of problems for which sublinear-time are known and by characterizing problems for which sublinear-time algorithms are impossible to exist. The main technical goal is to develop algorithmic technology for the analysis of large graphs in the context of two central models: property testing algorithms and sublinear-time approximation algorithms. We plan also to apply the techniques developed to further models related to sublinear algorithms: data streaming, dynamic and online algorithms. Our objective is to attack grand challenges in the area of sublinear algorithms and we aim to make major advances. The focus of this project is on fundamental research in this area, aiming at advances in the area of theoretical aspects of the design and analysis of algorithms.