AF: Small: Scalable Algorithms for Data and Network Analysis

点击翻译按钮获取中文摘要

Data-based decision-making involving big input data sets require a lot of time for algorithms to process them. In computer science, efficient algorithms are generally considered to be the ones whose running time does not increase "too fast" when input size grows. "Scalable algorithms" are among the most efficient algorithms, because their running time is required to be nearly linear or even sub-linear with respect to the problem size. In other words, their complexity scales gracefully when the input size scales up. In the age of Big Data, efficient algorithms are in higher demand now more than ever before. While big data takes us into the asymptotic world envisioned by the pioneers of computer science, the explosive growth of problem size has also significantly challenged the classical notion of efficient algorithms: Algorithms that used to be considered efficient, according to the traditional polynomial-time characterization, may no longer be adequate for solving today's problems. It is not just desirable, but essential, that efficient algorithms should be scalable. Thus, scalability, instead of polynomial-time computability, should be elevated to the central complexity notion for characterizing efficient computation, and this will be the focus of algorithm design for network sciences and big data. This project will focus on the design and analysis of scalable algorithms. One of its primary objective is to build bridges between the area of algorithm design and the fields of network sciences and machine learning. If successful, the project will help to provide a rigorous algorithmic framework for designing new scalable data and network analysis algorithms. By focusing on notions of algorithmic efficiency --- such as scalability --- that respect the sensibilities of researchers in these disciplines as to what constitutes a practical algorithm in the age of big data, this project aims to increase the value of theoretical analyses to researchers in these fields. As this project combines ideas from many disciplines within one coherent research effort, lectures and tutorials presented on the fruits of the project will help cross-fertilize the disciplines within its scope. The development of theoretical algorithms that might have practical applicability should simplify education in algorithms for students beyond theoretical computer science, and allow discussion of practically important heuristics at early stages of computer science education. The interdisciplinary nature of this research will enable broader engagements with PhD students and researchers in network sciences, machine learning, numerical analysis, and social science and hence will enhance the chance to be successful in supporting and working with women and minority researchers.The technical goal of this project is to systematically extend the family of algebraic, numerical, and combinatorial techniques from the recent breakthroughs in Laplacian linear solvers and max-flows/min-cuts, to a wide-range of problems that arise in network analysis, data mining, and machine learning. This project aims to show that these techniques --- including advanced sampling, sparsification, and local exploration of networks --- will play increasing roles in improving algorithmic scalability. It contains several open questions and conjectures ranging from network analysis to distribution sampling to social influences towards this goal. By providing new algorithmic insights into various dynamic processes over graphs, the project also aims to improve the understanding of network facets beyond static graph structures in order to develop better algorithmic theory for network sciences.This award reflects NSF's statutory mission and has been deemed worthy of support through evaluation using the Foundation's intellectual merit and broader impacts review criteria.