A Dynamic Algorithm for Linear Algebraically Computing Nonbacktracking Walk Centrality

摘要

Dynamic graph data is used to represent the changing relationships in society, biology, web traffic, and more. When computing analytics on such evolving data, it is important to have algorithms that can update analytics quickly as data changes, without needing to recompute the analytics from scratch. A common analytic performed on graph data is that of centrality: identifying the most important (highly ranked) vertices in the graph. In this work we examine centrality scores based on nonbacktracking walks in graphs and propose methods to update such scores in dynamic graphs. We propose two dynamic methods and demonstrate that both are faster than statically recomputing the scores at each graph change. We additionally show that one of these methods is far superior than the other with regard to the quality of the scores obtained, and is able to produce good quality approximations with respect to a static recomputation. Our methods use properties of iterative methods to update local portions of the centrality vector as the graph changes (in this paper, we focus exclusively on edge additions). Experiments are performed on real-world networks with millions of vertices and edges.