二十一世纪的计算大会 | Scalable Algorithms for Big Data and Network Analysis

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 our pioneers, 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 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. In other words, their complexity should be nearly linear or sub-linear with respect to the problem size. Thus, scalability, not just polynomial-time computability, should be elevated as the central complexity notion for characterizing efficient computation.

In this talk, I will discuss a family of algorithmic techniques for the design of provably-good scalable algorithms, focusing on the emerging Laplacian Paradigm, which has led to breakthroughs in scalable algorithms for several fundamental problems in network analysis, machine learning, and scientific computing.  These techniques include local network exploration, advanced sampling, sparsification, and graph partitioning. Network analysis subject include four recent applications: (1) Sampling from Graphic Models (2) Network Centrality Approximation (3) Social-Influence Maximization (4) Random-Walk Sparsification.

Solutions to these problems exemplify the fusion of combinatorial, numerical, and statistical thinking in network analysis.