Research Repository

The deformed graph Laplacian and its applications to network centrality analysis

Grindrod, P and Higham, DJ and Noferini, V (2018) 'The deformed graph Laplacian and its applications to network centrality analysis.' SIAM Journal on Matrix Analysis and Applications. ISSN 0895-4798 (In Press)

Jan17.pdf - Accepted Version

Download (426kB) | Preview


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.

Item Type: Article
Uncontrolled Keywords: centrality index, deformed graph Laplacian, matrix polynomial, nonbacktracking, complex network, generating function
Subjects: Q Science > QA Mathematics
Divisions: Faculty of Science and Health > Mathematical Sciences, Department of
Depositing User: Vanni Noferini
Date Deposited: 27 Jan 2017 13:22
Last Modified: 05 Jul 2018 15:15

Actions (login required)

View Item View Item