Network analysis with the aid of the path length matrix

DOI10.1007/S11075-023-01577-YMaRDI QIDQ6145580zbMATH OpenOpenAlexFDO

Authors Silvia Noschese, Lothar Reichel

Publication date 9 January 2024

Published in Numerical Algorithms (Search for Journal in Brave)

Copyright license Creative Commons Attribution 4.0 International

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

zbMATH Keywords

global efficiencyharmonic centralitynetwork analysispath length matrix

Mathematics Subject Classification ID

Numerical computation of eigenvalues and eigenvectors of matrices (65F15) Graph theory (including graph drawing) in computer science (68R10)

Abstract: Let a network be represented by a simple graph $mathcalG$ with $n$ vertices. A common approach to investigate properties of a network is to use the adjacency matrix $A=[a_{ij}{]}_{i,j=1}^{n}in{R}^{nimesn}$ associated with the graph $mathcalG$, where $a_{ij}>0$ if there is an edge pointing from vertex $v_i$ to vertex $v_j$, and $a_{ij}=0$ otherwise. Both $A$ and its positive integer powers reveal important properties of the graph. This paper proposes to study properties of a graph $mathcalG$ by also using the path length matrix for the graph. The $(ij{)}^{th}$ entry of the path length matrix is the length of the shortest path from vertex $v_i$ to vertex $v_j$; if there is no path between these vertices, then the value of the entry is $infty$. Powers of the path length matrix are formed by using min-plus matrix multiplication and are important for exhibiting properties of $mathcalG$. We show how several known measures of communication such as closeness centrality, harmonic centrality, and eccentricity are related to the path length matrix, and we introduce new measures of communication, such as the harmonic $K$-centrality and global $K$-efficiency, where only (short) paths made up of at most $K$ edges are taken into account. The sensitivity of the global $K$-efficiency to changes of the entries of the adjacency matrix also is considered.

Review text

Even though the usual approach to investigate the properties of a graph representing a network is to exploit its adjacency matrix, here the authors address the study of properties of the graph using its path length matrix. It is shown that several known measures of communication (i.e. closeness centrality, harmonic centrality, eccentricity) are related to the path length matrix. Moreover, new measures of communication are introduced. Applications of the presented approach include city planning and information transmission. Several MATLAB codes are presented which implement useful functions. Some numerical examples are reported and discussed in details to enlighten the features of the presented approach

Recommendations

• Network properties revealed through matrix functions
• Matrix functions in network analysis
• Communication in complex networks
• A formula of average path length for unweighted networks
• Path intersection matrices and applications to networks

Cites work

• Analysis of directed networks via the matrix exponential
• Communication in complex networks
• Dynamical Processes on Complex Networks
• Edge importance in a network via line graphs and the matrix exponential
• Eigenvalue condition numbers: zero-structured versus traditional.
• Estimating and increasing the structural robustness of a network
• scientific article; zbMATH DE number 3988607 (Why is no real title available?)
• scientific article; zbMATH DE number 3791531 (Why is no real title available?)
• scientific article; zbMATH DE number 51019 (Why is no real title available?)
• Krylov-Schur-type restarts for the two-sided Arnoldi method
• Networks. An introduction.
• On the Addressing Problem for Loop Switching
• Perron communicability and sensitivity of multilayer networks
• The Structure of Complex Networks

Cited in

(5)

• Matrix functions in network analysis
• Enhancing multiplex global efficiency
• Communication in multiplex transportation networks
• Edge importance in complex networks
• Network connectivity analysis via shortest paths

This page was built for publication: Network analysis with the aid of the path length matrix

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