The Laplacian Paradigm: Emerging Algorithms for Massive Graphs

摘要: This presentation describes an emerging paradigm for the design of efficient algorithms massive graphs paradigm, which we will refer to as Laplacian Paradigm, is built on a recent suite nearly-linear time primitives in spectral graph theory developed by Spielman and Teng, especially their solver linear systems Ax=b, where A matrix weighted, undirected n-vertex b n-place vector. In Paradigm solving problem (on graph), reduce optimization or computational one multiple algebraic problems that can be solved efficiently applying So far, already has some successes It been applied obtain nearly-linear-time applications semi-supervised learning, image process, web-spam detection, eigenvalue approximation, elliptic finite element also used faster generalized lossy flow computation random sampling spanning trees. The goal this encourage more researchers consider use develop fundamental combinatorial (e.g., matchings, flows cuts), scientific computing approximation), machine learning data analysis (such detection social network analysis), other involve graphs.