Purdue University Graduate Research Day 2014
November 22, 2014 at Purdue University
Talk on joint work with David F. Gleich:
Functions like the exponential and resolvent can be applied to graph matrices to reveal connectivity properties and community structures in the underlying graph. Such functions are widely used for network analysis tasks like suggesting new Twitter Followers, categorizing Amazon products, and ranking Bing search returns. We present new algorithms for approximating a broader class of functions in sublinear time. Furthermore, we prove locality results for these functions that imply that these graph structures can be approximated by subgraphs of bounded size. Rephrased in the context of the above applications, the set of users/items most relevant to you on Twitter / Netflix / a list of search engine results can be epsilon-approximated by a set of bounded size.