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

DOI10.1016/J.JMAA.2016.12.062zbMATH Open1355.05233arXiv1607.06807OpenAlexW2481360228MaRDI QIDQ509007FDOQ509007

Authors: Ernesto Estrada, Grant Silver 

Publication date: 8 February 2017

Published in: Journal of Mathematical Analysis and Applications (Search for Journal in Brave)

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.

Full work available at URL: https://arxiv.org/abs/1607.06807

Recommendations

• Exploring the “Middle Earth” of network spectra via a Gaussian matrix function
• Ranking hubs and authorities using matrix functions
• Network properties revealed through matrix functions
• Gaussianization of the spectra of graphs and networks. Theory and applications
• Functional centrality in graphs

zbMATH Keywords

complex networkschordless cyclescommunicability functionsdouble-factorialmatrix error functionsmatrix tanh function

Mathematics Subject Classification ID

Applications of graph theory (05C90) Small world graphs, complex networks (graph-theoretic aspects) (05C82)

Cites Work

• Functions of Matrices
• Network properties revealed through matrix functions
• Title not available (Why is that?)
• The Structure and Function of Complex Networks
• A new status index derived from sociometric analysis
• Estimating the Estrada index
• The Estrada index
• Title not available (Why is that?)
• Ranking hubs and authorities using matrix functions
• Topological evolution in dense granular materials: a complex networks perspective
• Generalized walks-based centrality measures for complex biological networks
• Network bipartivity and the transportation efficiency of European passenger airlines
• Robustness of regular ring lattices based on natural connectivity
• Vulnerability of complex networks under intentional attack with incomplete information
• Updating and downdating techniques for optimizing network communicability
• Title not available (Why is that?)
• On the limiting behavior of parameter-dependent network centrality measures
• A note on the graph's resolvent and the multifilar structure
• Clustering of spectra and fractals of regular graphs

Cited In (14)

• Centrality measures for node-weighted networks via line graphs and the matrix exponential
• COVID-19 and SARS-CoV-2. Modeling the present, looking at the future
• Double Gaussianization of graph spectra
• Gaussianization of the spectra of graphs and networks. Theory and applications
• Mittag-Leffler functions and their applications in network science
• A note on some bounds of the \(\alpha\)-Estrada index of graphs
• A matrix-based measure of inter-node walk relatedness in a network
• The deformed graph Laplacian and its applications to network centrality analysis
• Equitable partition and star set formulas for the subgraph centrality of graphs
• Dissecting graph measure performance for node clustering in LFR parameter space
• Tuned communicability metrics in networks. The case of alternative routes for urban traffic
• Similarities on graphs: kernels versus proximity measures
• The many facets of the Estrada indices of graphs and networks
• Parametric controllability of the personalized PageRank: Classic model vs biplex approach

Uses Software

• mftoolbox

This page was built for publication: Accounting for the role of long walks on networks via a new matrix function

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q509007)