Ranking hubs and authorities using matrix functions
From MaRDI portal
Abstract: The notions of subgraph centrality and communicability, based on the exponential of the adjacency matrix of the underlying graph, have been effectively used in the analysis of undirected networks. In this paper we propose an extension of these measures to directed networks, and we apply them to the problem of ranking hubs and authorities. The extension is achieved by bipartization, i.e., the directed network is mapped onto a bipartite undirected network with twice as many nodes in order to obtain a network with a symmetric adjacency matrix. We explicitly determine the exponential of this adjacency matrix in terms of the adjacency matrix of the original, directed network, and we give an interpretation of centrality and communicability in this new context, leading to a technique for ranking hubs and authorities. The matrix exponential method for computing hubs and authorities is compared to the well known HITS algorithm, both on small artificial examples and on more realistic real-world networks. A few other ranking algorithms are also discussed and compared with our technique. The use of Gaussian quadrature rules for calculating hub and authority scores is discussed.
Recommendations
- Authority Rankings from HITS, PageRank, and SALSA: Existence, Uniqueness, and Effect of Initialization
- Link Analysis: Hubs and Authorities on the World Wide Web
- Analysis of directed networks via the matrix exponential
- Analysis of directed networks via partial singular value decomposition and Gauss quadrature
- Quantum hub and authority centrality measures for directed networks based on continuous-time quantum walks
Cites work
- scientific article; zbMATH DE number 5798606 (Why is no real title available?)
- scientific article; zbMATH DE number 2019639 (Why is no real title available?)
- scientific article; zbMATH DE number 1432797 (Why is no real title available?)
- A Survey of Eigenvector Methods for Web Information Retrieval
- A new status index derived from sociometric analysis
- Authoritative sources in a hyperlinked environment
- Authority Rankings from HITS, PageRank, and SALSA: Existence, Uniqueness, and Effect of Initialization
- Bounds for the entries of matrix functions with applications to preconditioning
- Complex networks: structure and dynamics
- Fast matrix computations for pairwise and columnwise commute times and Katz scores
- Functions of Matrices
- Google's PageRank and beyond. The science of search engine rankings
- Link Analysis: Hubs and Authorities on the World Wide Web
- Mapping directed networks
- Matrices, moments and quadrature with applications
- Network analysis. Methodological foundations.
- Network properties revealed through matrix functions
- Network science. Complexity in nature and technology
- Networks. An introduction.
- Quadrature rule-based bounds for functions of adjacency matrices
- Ranking hubs and authorities using matrix functions
- Scale-Free Networks
- The Scaling and Squaring Method for the Matrix Exponential Revisited
- The Structure and Function of Complex Networks
- The University of Florida sparse matrix collection
- Who's \#1? The science of rating and ranking
Cited in
(52)- The e-MoM approach for approximating matrix functionals
- Network properties revealed through matrix functions
- Simplified anti-Gauss quadrature rules with applications in linear algebra
- Analysis of directed networks via partial singular value decomposition and Gauss quadrature
- Matrix functions in network analysis
- Gaussianization of the spectra of graphs and networks. Theory and applications
- On the limiting behavior of parameter-dependent network centrality measures
- New block quadrature rules for the approximation of matrix functions
- Axioms for centrality scoring with principal eigenvectors
- On the stability of network indices defined by means of matrix functions
- PageRank beyond the web
- Identifying influential spreaders in complex networks by considering the impact of the number of shortest paths
- Numerical methods for Gremban's expansion of signed graphs
- Mittag-Leffler functions and their applications in network science
- Block matrix formulations for evolving networks
- On Bernoulli matrix polynomials and matrix exponential approximation
- Euler polynomials for the matrix exponential approximation
- The complex step approximation to the higher order Fréchet derivatives of a matrix function
- Non-backtracking alternating walks
- Orthogonal expansion of network functions
- Edge importance in a network via line graphs and the matrix exponential
- Hubs and Authorities on Japanese Inter-Firm Network: Characterization of Nodes in Very Large Directed Networks
- Analysis of directed networks via the matrix exponential
- Higher-order rank functions on directed graphs
- A technique for improving the computation of functions of triangular matrices
- On the convergence of the minimally irreducible Markov chain method with applications to PageRank
- Generalized tensor function via the tensor singular value decomposition based on the T-product
- Computation of generalized matrix functions with rational Krylov methods
- Quantum hub and authority centrality measures for directed networks based on continuous-time quantum walks
- Edge modification criteria for enhancing the communicability of digraphs
- Ranking hubs and authorities using matrix functions
- Structured level-2 condition numbers of matrix functions
- The Radau-Lanczos method for matrix functions
- Low-rank updates of matrix functions
- Sublinear column-wise actions of the matrix exponential on social networks
- An Edge Centrality Measure Based on the Kemeny Constant
- Sensitivity of Matrix Function Based Network Communicability Measures: Computational Methods and A Priori Bounds
- A Fast Monte Carlo Algorithm for Evaluating Matrix Functions with Application in Complex Networks
- Iterated endorsement deduction and ranking
- Characterising heavy-tailed networks using q-generalised entropy and q-adjacency kernels
- Exploring the “Middle Earth” of network spectra via a Gaussian matrix function
- Financial networks and interconnectedness in an advanced emerging market economy
- A highly parallel algorithm for computing the action of a matrix exponential on a vector based on a multilevel Monte Carlo method
- A probabilistic linear solver based on a multilevel Monte Carlo method
- Computation of generalized matrix functions
- Ranking nodes in directed networks via continuous-time quantum walks
- Accounting for the role of long walks on networks via a new matrix function
- A Monte Carlo method for computing the action of a matrix exponential on a vector
- Stable Computation of Generalized Matrix Functions via Polynomial Interpolation
- Rational Krylov approximation of matrix functions: numerical methods and optimal pole selection
- Dynamic Katz and related network measures
- On the exponential ranking and its linear counterpart
This page was built for publication: Ranking hubs and authorities using matrix functions
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1938702)
