Non-backtracking walk centrality for directed networks

Francesca Arrigo, Peter Grindrod, Desmond J. Higham, Vanni Noferini

Research output: Contribution to journalArticle

5 Citations (Scopus)

Abstract

The theory of zeta functions provides an expression for the generating function of nonbacktracking walk counts on a directed network. We show how this expression can be used to produce a centrality measure that eliminates backtracking walks at no cost. We also show that the radius of convergence of the generating function is related to the spectrum of a three-by-three block matrix involving the original adjacency matrix. This gives a means to choose appropriate values of the attenuation parameter. We find that three important additional benefits arise when we use this technique to eliminate traversals around the network on the grounds that they are unlikely to be of relevance. First, we obtain a larger range of choices for the attenuation parameter. Second, a natural approach for determining a suitable parameter range is invariant under the removal of certain types of nodes, so we can gain computational efficiencies through reducing the dimension of the resulting eigenvalue problem. Third, the dimension of the linear system defining the centrality measures may be reduced in the same manner. We show that the new centrality measure may be interpreted as standard Katz on a modified network, where self loops are added, and where nonreciprocal edges are augmented with negative weights. We also give a multilayer interpretation, where negatively weighted walks between layers compensate for backtracking walks on the only non-empty layer. Studying the limit as the attenuation parameter approaches its upper bound also allows us to propose a generalization of eigenvector-based nonbacktracking centrality measure to this directed network setting. In this context, we find that the two-by-two block matrix arising in previous studies focused on undirected networks must be extended to a new three-by-three block structure to allow for directed edges. We illustrate the centrality measure on a synthetic network, where it is shown to eliminate a localization effect present in standard Katz centrality. Finally, we give results for real networks.
LanguageEnglish
Number of pages24
JournalJournal of Complex Networks
Early online date24 Jul 2017
DOIs
Publication statusE-pub ahead of print - 24 Jul 2017

Fingerprint

Directed Network
Centrality
Walk
Attenuation
Eliminate
Backtracking
Block Matrix
Computational efficiency
Eigenvalues and eigenfunctions
Generating Function
Linear systems
Multilayers
Radius of convergence
Block Structure
Adjacency Matrix
Riemann zeta function
Computational Efficiency
Range of data
Eigenvector
Eigenvalue Problem

Keywords

  • generating function
  • inverse participation ratio
  • Katz
  • localization
  • loops
  • multilayer
  • graph spectrum
  • backtracking walks

Cite this

Arrigo, Francesca ; Grindrod, Peter ; Higham, Desmond J. ; Noferini, Vanni. / Non-backtracking walk centrality for directed networks. In: Journal of Complex Networks. 2017.
@article{809cc19e8a444c25b9a512818ba26aa5,
title = "Non-backtracking walk centrality for directed networks",
abstract = "The theory of zeta functions provides an expression for the generating function of nonbacktracking walk counts on a directed network. We show how this expression can be used to produce a centrality measure that eliminates backtracking walks at no cost. We also show that the radius of convergence of the generating function is related to the spectrum of a three-by-three block matrix involving the original adjacency matrix. This gives a means to choose appropriate values of the attenuation parameter. We find that three important additional benefits arise when we use this technique to eliminate traversals around the network on the grounds that they are unlikely to be of relevance. First, we obtain a larger range of choices for the attenuation parameter. Second, a natural approach for determining a suitable parameter range is invariant under the removal of certain types of nodes, so we can gain computational efficiencies through reducing the dimension of the resulting eigenvalue problem. Third, the dimension of the linear system defining the centrality measures may be reduced in the same manner. We show that the new centrality measure may be interpreted as standard Katz on a modified network, where self loops are added, and where nonreciprocal edges are augmented with negative weights. We also give a multilayer interpretation, where negatively weighted walks between layers compensate for backtracking walks on the only non-empty layer. Studying the limit as the attenuation parameter approaches its upper bound also allows us to propose a generalization of eigenvector-based nonbacktracking centrality measure to this directed network setting. In this context, we find that the two-by-two block matrix arising in previous studies focused on undirected networks must be extended to a new three-by-three block structure to allow for directed edges. We illustrate the centrality measure on a synthetic network, where it is shown to eliminate a localization effect present in standard Katz centrality. Finally, we give results for real networks.",
keywords = "generating function, inverse participation ratio, Katz, localization, loops, multilayer, graph spectrum, backtracking walks",
author = "Francesca Arrigo and Peter Grindrod and Higham, {Desmond J.} and Vanni Noferini",
year = "2017",
month = "7",
day = "24",
doi = "10.1093/comnet/cnx025",
language = "English",
journal = "Journal of Complex Networks",
issn = "2051-1310",

}

Non-backtracking walk centrality for directed networks. / Arrigo, Francesca; Grindrod, Peter; Higham, Desmond J.; Noferini, Vanni.

In: Journal of Complex Networks, 24.07.2017.

Research output: Contribution to journalArticle

TY - JOUR

T1 - Non-backtracking walk centrality for directed networks

AU - Arrigo, Francesca

AU - Grindrod, Peter

AU - Higham, Desmond J.

AU - Noferini, Vanni

PY - 2017/7/24

Y1 - 2017/7/24

N2 - The theory of zeta functions provides an expression for the generating function of nonbacktracking walk counts on a directed network. We show how this expression can be used to produce a centrality measure that eliminates backtracking walks at no cost. We also show that the radius of convergence of the generating function is related to the spectrum of a three-by-three block matrix involving the original adjacency matrix. This gives a means to choose appropriate values of the attenuation parameter. We find that three important additional benefits arise when we use this technique to eliminate traversals around the network on the grounds that they are unlikely to be of relevance. First, we obtain a larger range of choices for the attenuation parameter. Second, a natural approach for determining a suitable parameter range is invariant under the removal of certain types of nodes, so we can gain computational efficiencies through reducing the dimension of the resulting eigenvalue problem. Third, the dimension of the linear system defining the centrality measures may be reduced in the same manner. We show that the new centrality measure may be interpreted as standard Katz on a modified network, where self loops are added, and where nonreciprocal edges are augmented with negative weights. We also give a multilayer interpretation, where negatively weighted walks between layers compensate for backtracking walks on the only non-empty layer. Studying the limit as the attenuation parameter approaches its upper bound also allows us to propose a generalization of eigenvector-based nonbacktracking centrality measure to this directed network setting. In this context, we find that the two-by-two block matrix arising in previous studies focused on undirected networks must be extended to a new three-by-three block structure to allow for directed edges. We illustrate the centrality measure on a synthetic network, where it is shown to eliminate a localization effect present in standard Katz centrality. Finally, we give results for real networks.

AB - The theory of zeta functions provides an expression for the generating function of nonbacktracking walk counts on a directed network. We show how this expression can be used to produce a centrality measure that eliminates backtracking walks at no cost. We also show that the radius of convergence of the generating function is related to the spectrum of a three-by-three block matrix involving the original adjacency matrix. This gives a means to choose appropriate values of the attenuation parameter. We find that three important additional benefits arise when we use this technique to eliminate traversals around the network on the grounds that they are unlikely to be of relevance. First, we obtain a larger range of choices for the attenuation parameter. Second, a natural approach for determining a suitable parameter range is invariant under the removal of certain types of nodes, so we can gain computational efficiencies through reducing the dimension of the resulting eigenvalue problem. Third, the dimension of the linear system defining the centrality measures may be reduced in the same manner. We show that the new centrality measure may be interpreted as standard Katz on a modified network, where self loops are added, and where nonreciprocal edges are augmented with negative weights. We also give a multilayer interpretation, where negatively weighted walks between layers compensate for backtracking walks on the only non-empty layer. Studying the limit as the attenuation parameter approaches its upper bound also allows us to propose a generalization of eigenvector-based nonbacktracking centrality measure to this directed network setting. In this context, we find that the two-by-two block matrix arising in previous studies focused on undirected networks must be extended to a new three-by-three block structure to allow for directed edges. We illustrate the centrality measure on a synthetic network, where it is shown to eliminate a localization effect present in standard Katz centrality. Finally, we give results for real networks.

KW - generating function

KW - inverse participation ratio

KW - Katz

KW - localization

KW - loops

KW - multilayer

KW - graph spectrum

KW - backtracking walks

U2 - 10.1093/comnet/cnx025

DO - 10.1093/comnet/cnx025

M3 - Article

JO - Journal of Complex Networks

T2 - Journal of Complex Networks

JF - Journal of Complex Networks

SN - 2051-1310

ER -