The deformed graph Laplacian and its applications to network centrality analysis

We introduce and study a new network centrality measure based on the concept of nonbacktracking walks; that is, walks not containing subsequences of the form uvu where u and v are any distinct connected vertices of the underlying graph . We argue that this feature can yield more meaningful rankings than traditional walk-based cent rality measures. We show that the resulting Katz-style centrality measure may be computed via the so -called deformed graph Laplacian?a quadratic matrix polynomial that can be associated with any graph. By proving a range of new results about this matrix polynomial, we gain insights into the behavior of the algorithm with respect to its Katz-like parameter. The results also inform implementation issues. In particular we show that, in an appropriate limit, the new measure coincide s with the nonbacktracking version of eigenvector centrality introduced by Martin, Zhang and New man in 2014. Rigorous analysis on star and star-like networks illustrates the benefits of the new approach, and further results are given on real networks.