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, 39 (1). 310 - 341. ISSN 0895-4798

[img]
Preview
Text
Jan17.pdf - Accepted Version

Download (426kB) | Preview

Abstract

© 2018 Society for Industrial and Applied Mathematics. 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 centrality 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 coincides with the nonbacktracking version of eigenvector centrality introduced by Martin, Zhang, and Newman 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
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: 30 Apr 2018 22:15
URI: http://repository.essex.ac.uk/id/eprint/18919

Actions (login required)

View Item View Item