Applied Math Seminar, UNC - Chapel Hill
September 9, 2016
Network analysis provides tools for addressing fundamental applications in graphs such as webpage ranking, protein-function prediction, and product categorization and recommendation. As real-world networks grow to have billions of nodes and edges, the scalability of network analysis algorithms becomes increasingly important. Whereas many standard graph analysis algorithms require exploring the entire graph, local algorithms explore only the graph region near the nodes of interest. This talk will focus on local algorithms for graph diffusions, as well as the localized behavior of global algorithms. We show how two well-studied matrix functions for graph analysis, PageRank and the matrix exponential, stay localized on networks that have a skewed degree sequence related to the power-law degree distribution common to many real-world networks. These results give the first theoretical explanation of a localization phenomenon that has long been observed in diffusions on real-world networks. We then present a sublinear local algorithm for computing a generalized class of these diffusions, and discuss uses in graph analysis tasks like community detection and node ranking.