Research Repository

The deformed graph Laplacian and its applications to network centrality analysis

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

[img]
Preview
Text
Jan17.pdf - Submitted Version

Download (426kB) | Preview

Abstract

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
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: 17 Aug 2017 17:19
URI: http://repository.essex.ac.uk/id/eprint/18919

Actions (login required)

View Item View Item