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
- A new status index derived from sociometric analysis
- A Survey of Eigenvector Methods for Web Information Retrieval
- 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
- 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?)
- 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
(54)- Gaussianization of the spectra of graphs and networks. Theory and applications
- Ranking hubs and authorities using matrix functions
- The e-MoM approach for approximating matrix functionals
- Orthogonal expansion of network functions
- The complex step approximation to the higher order Fréchet derivatives of a matrix function
- On Bernoulli matrix polynomials and matrix exponential approximation
- Characterising heavy-tailed networks using q-generalised entropy and q-adjacency kernels
- Dynamic Katz and related network measures
- On the exponential ranking and its linear counterpart
- Identifying influential spreaders in complex networks by considering the impact of the number of shortest paths
- Generalized tensor function via the tensor singular value decomposition based on the T-product
- A highly parallel algorithm for computing the action of a matrix exponential on a vector based on a multilevel Monte Carlo method
- Analysis of directed networks via partial singular value decomposition and Gauss quadrature
- A Monte Carlo method for computing the action of a matrix exponential on a vector
- Edge importance in a network via line graphs and the matrix exponential
- A probabilistic linear solver based on a multilevel Monte Carlo method
- On the convergence of the minimally irreducible Markov chain method with applications to PageRank
- Iterated endorsement deduction and ranking
- Analysis of directed networks via the matrix exponential
- Edge modification criteria for enhancing the communicability of digraphs
- PageRank beyond the web
- New block quadrature rules for the approximation of matrix functions
- Axioms for centrality scoring with principal eigenvectors
- Rational Krylov approximation of matrix functions: numerical methods and optimal pole selection
- Network properties revealed through matrix functions
- Stable Computation of Generalized Matrix Functions via Polynomial Interpolation
- Computation of generalized matrix functions
- Financial networks and interconnectedness in an advanced emerging market economy
- Exploring the “Middle Earth” of network spectra via a Gaussian matrix function
- On the stability of network indices defined by means of matrix functions
- Sublinear column-wise actions of the matrix exponential on social networks
- Mittag-Leffler functions and their applications in network science
- Quantum hub and authority centrality measures for directed networks based on continuous-time quantum walks
- A technique for improving the computation of functions of triangular matrices
- Computation of generalized matrix functions with rational Krylov methods
- Accounting for the role of long walks on networks via a new matrix function
- Higher-order rank functions on directed graphs
- Non-backtracking alternating walks
- On the limiting behavior of parameter-dependent network centrality measures
- Hubs and Authorities on Japanese Inter-Firm Network: Characterization of Nodes in Very Large Directed Networks
- Block matrix formulations for evolving networks
- The Radau-Lanczos method for matrix functions
- Numerical methods for Gremban's expansion of signed graphs
- Low-rank updates of matrix functions
- Matrix functions in network analysis
- Sensitivity of Matrix Function Based Network Communicability Measures: Computational Methods and A Priori Bounds
- Ranking nodes in directed networks via continuous-time quantum walks
- Euler polynomials for the matrix exponential approximation
- An Edge Centrality Measure Based on the Kemeny Constant
- Structured level-2 condition numbers of matrix functions
- A Fast Monte Carlo Algorithm for Evaluating Matrix Functions with Application in Complex Networks
- Simplified anti-Gauss quadrature rules with applications in linear algebra
- Efficient computation of f-centralities and nonbacktracking centrality for temporal networks
- Source-to-sink communicability: a new centrality measure for directed acyclic networks
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)
