Research Repository

The deformed graph Laplacian and its applications to network centrality analysis

Grindrod, Peter and Higham, Desmond J and Noferini, Vanni (2018) 'The deformed graph Laplacian and its applications to network centrality analysis.' SIAM Journal on Matrix Analysis and Applications, 39 (1). 310 - 342. ISSN 0895-4798

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: 19 Jun 2020 19:15

Actions (login required)

View Item View Item