Functions and eigenvectors of partially known matrices with applications to network analysis

DOI10.1016/J.APNUM.2020.08.020zbMATH Open1459.65046arXiv2005.05903OpenAlexW3083341466MaRDI QIDQ2227656FDOQ2227656

Authors: Mohammed Al Mugahwi, Omar De la Cruz Cabrera, Silvia Noschese, Lothar Reichel 

Publication date: 15 February 2021

Published in: Applied Numerical Mathematics (Search for Journal in Brave)

Abstract: Matrix functions play an important role in applied mathematics. In network analysis, in particular, the exponential of the adjacency matrix associated with a network provides valuable information about connectivity, as well as about the relative importance or centrality of nodes. Another popular approach to rank the nodes of a network is to compute the left Perron vector of the adjacency matrix for the network. The present article addresses the problem of evaluating matrix functions, as well as computing an approximation to the left Perron vector, when only some of the columns and/or some of the rows of the adjacency matrix are known. Applications to network analysis are considered, when only some sampled columns and/or rows of the adjacency matrix that defines the network are available. A sampling scheme that takes the connectivity of the network into account is described. Computed examples illustrate the performance of the methods discussed.

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

Recommendations

• Network analysis via partial spectral factorization and Gauss quadrature
• Network properties revealed through matrix functions
• Analysis of directed networks via partial singular value decomposition and Gauss quadrature
• Centrality measures for node-weighted networks via line graphs and the matrix exponential
• Analysis of directed networks via the matrix exponential

zbMATH Keywords

low-rank approximationmatrix functioncentrality measureArnoldi processcross approximationcolumn subset selection

Mathematics Subject Classification ID

Eigenvalues, singular values, and eigenvectors (15A18) Numerical computation of eigenvalues and eigenvectors of matrices (65F15) Matrix exponential and similar functions of matrices (15A16) Numerical methods for low-rank matrix approximation; matrix compression (65F55)

Cites Work

• Functions of Matrices
• Block Gauss and anti-Gauss quadrature with application to networks
• Network properties revealed through matrix functions
• Title not available (Why is that?)
• A theory of pseudoskeleton approximations
• Parallel iterative methods for sparse linear systems
• Networks. An introduction.
• Title not available (Why is that?)
• Pseudo-skeleton approximations by matrices of maximal volume
• Adaptive cross approximation for ill-posed problems
• Title not available (Why is that?)
• Solving a large dense linear system by adaptive cross approximation
• Vector extrapolation methods. Applications and numerical comparison
• The simplified topological \(\varepsilon\)-algorithms for accelerating sequences in a vector space
• LU implementation of the modified minimal polynomial extrapolation method for solving linear and nonlinear systems
• Mapping directed networks
• Error Estimates and Evaluation of Matrix Functions via the Faber Transform
• The structure of scientific collaboration networks
• Accelerating the Arnoldi-type algorithm for the PageRank problem and the ProteinRank problem
• Solution of large scale evolutionary problems using rational Krylov subspaces with optimized shifts
• Rational extrapolation for the PageRank vector
• Lanczos-based exponential filtering for discrete ill-posed problems
• The genesis and early developments of Aitken's process, Shanks' transformation, the \(\varepsilon\)-algorithm, and related fixed point methods
• The Lanczos algorithm and complex Gauss quadrature
• Analysis of directed networks via the matrix exponential
• Shifted and extrapolated power methods for tensor \(\ell^p\)-eigenpairs

Cited In (8)

• Network properties revealed through matrix functions
• Analysis of directed networks via partial singular value decomposition and Gauss quadrature
• Generalized eigenvectors of isospectral transformations, spectral equivalence and reconstruction of original networks
• On the stability of network indices defined by means of matrix functions
• Network analysis via partial spectral factorization and Gauss quadrature
• Orthogonal expansion of network functions
• Low-rank updates of matrix functions
• Sublinear column-wise actions of the matrix exponential on social networks

Uses Software

• EPSfun
• mftoolbox
• blgaussexp

This page was built for publication: Functions and eigenvectors of partially known matrices with applications to network analysis

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