Accounting for the role of long walks on networks via a new matrix function

Ernesto Estrada, Grant Silver

Research output: Contribution to journalArticle

5 Citations (Scopus)

Abstract

We introduce a new matrix function for studying graphs and real-world networks based on a double-factorial penalization of walks between nodes in a graph. This new matrix function is based on the matrix error function. We find a very good approximation of this function using a matrix hyperbolic tangent function. We derive a communicability function, a subgraph centrality and a double-factorial Estrada index based on this new matrix function. We obtain upper and lower bounds for the double-factorial Estrada index of graphs, showing that they are similar to those of the single-factorial Estrada index. We then compare these indices with the single-factorial one for simple graphs and real-world networks. We conclude that for networks containing chordless cycles-holes-the two penalization schemes produce significantly different results. In particular, we study two series of real-world networks representing urban street networks, and protein residue networks. We observe that the subgraph centrality based on both indices produce significantly different ranking of the nodes. The use of the double factorial penalization of walks opens new possibilities for studying important structural properties of real-world networks where long-walks play a fundamental role, such as the cases of networks containing chordless cycles.
LanguageEnglish
Pages1581-1600
Number of pages20
JournalJournal of Mathematical Analysis and Applications
Volume449
Issue number2
Early online date3 Jan 2017
DOIs
Publication statusPublished - 15 May 2017

Fingerprint

Matrix Function
Walk
Factorial
Penalization
Centrality
Hyperbolic functions
Subgraph
Graph in graph theory
Tangent function
Hyperbolic tangent
Cycle
Hyperbolic function
Structural properties
Error function
Vertex of a graph
Simple Graph
Structural Properties
Proteins
Upper and Lower Bounds
Ranking

Keywords

  • matrix error functions
  • matrix tanh function
  • communicability functions
  • double-factorial
  • chordless cycles
  • complex networks

Cite this

@article{fc7048433fe1403c98f56732e93ab25f,
title = "Accounting for the role of long walks on networks via a new matrix function",
abstract = "We introduce a new matrix function for studying graphs and real-world networks based on a double-factorial penalization of walks between nodes in a graph. This new matrix function is based on the matrix error function. We find a very good approximation of this function using a matrix hyperbolic tangent function. We derive a communicability function, a subgraph centrality and a double-factorial Estrada index based on this new matrix function. We obtain upper and lower bounds for the double-factorial Estrada index of graphs, showing that they are similar to those of the single-factorial Estrada index. We then compare these indices with the single-factorial one for simple graphs and real-world networks. We conclude that for networks containing chordless cycles-holes-the two penalization schemes produce significantly different results. In particular, we study two series of real-world networks representing urban street networks, and protein residue networks. We observe that the subgraph centrality based on both indices produce significantly different ranking of the nodes. The use of the double factorial penalization of walks opens new possibilities for studying important structural properties of real-world networks where long-walks play a fundamental role, such as the cases of networks containing chordless cycles.",
keywords = "matrix error functions, matrix tanh function, communicability functions, double-factorial, chordless cycles, complex networks",
author = "Ernesto Estrada and Grant Silver",
year = "2017",
month = "5",
day = "15",
doi = "10.1016/j.jmaa.2016.12.062",
language = "English",
volume = "449",
pages = "1581--1600",
journal = "Journal of Mathematical Analysis and Applications",
issn = "0022-247X",
number = "2",

}

Accounting for the role of long walks on networks via a new matrix function. / Estrada, Ernesto; Silver, Grant.

In: Journal of Mathematical Analysis and Applications, Vol. 449, No. 2, 15.05.2017, p. 1581-1600.

Research output: Contribution to journalArticle

TY - JOUR

T1 - Accounting for the role of long walks on networks via a new matrix function

AU - Estrada, Ernesto

AU - Silver, Grant

PY - 2017/5/15

Y1 - 2017/5/15

N2 - We introduce a new matrix function for studying graphs and real-world networks based on a double-factorial penalization of walks between nodes in a graph. This new matrix function is based on the matrix error function. We find a very good approximation of this function using a matrix hyperbolic tangent function. We derive a communicability function, a subgraph centrality and a double-factorial Estrada index based on this new matrix function. We obtain upper and lower bounds for the double-factorial Estrada index of graphs, showing that they are similar to those of the single-factorial Estrada index. We then compare these indices with the single-factorial one for simple graphs and real-world networks. We conclude that for networks containing chordless cycles-holes-the two penalization schemes produce significantly different results. In particular, we study two series of real-world networks representing urban street networks, and protein residue networks. We observe that the subgraph centrality based on both indices produce significantly different ranking of the nodes. The use of the double factorial penalization of walks opens new possibilities for studying important structural properties of real-world networks where long-walks play a fundamental role, such as the cases of networks containing chordless cycles.

AB - We introduce a new matrix function for studying graphs and real-world networks based on a double-factorial penalization of walks between nodes in a graph. This new matrix function is based on the matrix error function. We find a very good approximation of this function using a matrix hyperbolic tangent function. We derive a communicability function, a subgraph centrality and a double-factorial Estrada index based on this new matrix function. We obtain upper and lower bounds for the double-factorial Estrada index of graphs, showing that they are similar to those of the single-factorial Estrada index. We then compare these indices with the single-factorial one for simple graphs and real-world networks. We conclude that for networks containing chordless cycles-holes-the two penalization schemes produce significantly different results. In particular, we study two series of real-world networks representing urban street networks, and protein residue networks. We observe that the subgraph centrality based on both indices produce significantly different ranking of the nodes. The use of the double factorial penalization of walks opens new possibilities for studying important structural properties of real-world networks where long-walks play a fundamental role, such as the cases of networks containing chordless cycles.

KW - matrix error functions

KW - matrix tanh function

KW - communicability functions

KW - double-factorial

KW - chordless cycles

KW - complex networks

UR - http://www.sciencedirect.com/science/article/pii/S0022247X16308587

U2 - 10.1016/j.jmaa.2016.12.062

DO - 10.1016/j.jmaa.2016.12.062

M3 - Article

VL - 449

SP - 1581

EP - 1600

JO - Journal of Mathematical Analysis and Applications

T2 - Journal of Mathematical Analysis and Applications

JF - Journal of Mathematical Analysis and Applications

SN - 0022-247X

IS - 2

ER -