The deformed graph Laplacian and its applications to network centrality analysis

Peter Grindrod, Desmond J. Higham, Vanni Noferini

Research output: Contribution to journalArticle

6 Citations (Scopus)

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 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.
LanguageEnglish
Pages310-341
Number of pages32
JournalSIAM Journal on Matrix Analysis and Applications
Volume39
Issue number1
DOIs
Publication statusPublished - 1 Mar 2018

Fingerprint

Graph Laplacian
Centrality
Walk
Matrix Polynomial
Quadratic Polynomial
Graph in graph theory
Subsequence
Eigenvector
Star
Ranking
Distinct
Range of data

Keywords

  • centrality index
  • deformed graph Laplacian
  • matrix polynomial
  • nonbacktracking
  • complex networks
  • generating function

Cite this

Grindrod, Peter ; Higham, Desmond J. ; Noferini, Vanni. / The deformed graph Laplacian and its applications to network centrality analysis. In: SIAM Journal on Matrix Analysis and Applications. 2018 ; Vol. 39, No. 1. pp. 310-341.
@article{945342ea41194a85a35dbabb7bc899a6,
title = "The deformed graph Laplacian and its applications to network centrality analysis",
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 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.",
keywords = "centrality index, deformed graph Laplacian, matrix polynomial, nonbacktracking, complex networks, generating function",
author = "Peter Grindrod and Higham, {Desmond J.} and Vanni Noferini",
year = "2018",
month = "3",
day = "1",
doi = "10.1137/17M1112297",
language = "English",
volume = "39",
pages = "310--341",
journal = "SIAM Journal on Matrix Analysis and Applications",
issn = "0895-4798",
number = "1",

}

The deformed graph Laplacian and its applications to network centrality analysis. / Grindrod, Peter; Higham, Desmond J.; Noferini, Vanni.

In: SIAM Journal on Matrix Analysis and Applications, Vol. 39, No. 1, 01.03.2018, p. 310-341.

Research output: Contribution to journalArticle

TY - JOUR

T1 - The deformed graph Laplacian and its applications to network centrality analysis

AU - Grindrod, Peter

AU - Higham, Desmond J.

AU - Noferini, Vanni

PY - 2018/3/1

Y1 - 2018/3/1

N2 - 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.

AB - 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.

KW - centrality index

KW - deformed graph Laplacian

KW - matrix polynomial

KW - nonbacktracking

KW - complex networks

KW - generating function

UR - https://www.siam.org/journals/simax.php

U2 - 10.1137/17M1112297

DO - 10.1137/17M1112297

M3 - Article

VL - 39

SP - 310

EP - 341

JO - SIAM Journal on Matrix Analysis and Applications

T2 - SIAM Journal on Matrix Analysis and Applications

JF - SIAM Journal on Matrix Analysis and Applications

SN - 0895-4798

IS - 1

ER -