Complexity Theory Seminar, Purdue University
March 3, 2014
Talk on joint work with David F. Gleich:
Functions such as the exponential, the resolvent, and p^th roots are used to analyze sparse matrices from large social networks. We present a fast algorithm, related to the Gauss-Seidel linear solver, for approximating a column of these matrix functions. Assuming a power-law degree distribution on the underlying graph, we can show that the method is sub-linear for these functions, and as a corollary we have that such columns must be local. For real-world networks with over 1 billion edges, it runs in less than 10 seconds on a standard desktop computer.