Ranking hubs and authorities using matrix functions

Michele Benzi, Ernesto Estrada, Christine Klymko

Research output: Contribution to journalArticle

37 Citations (Scopus)

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.
LanguageEnglish
Pages2447-2474
Number of pages28
JournalLinear Algebra and its Applications
Volume438
Publication statusPublished - 2013

Fingerprint

Matrix Function
Adjacency Matrix
Directed Network
Ranking
Centrality
Matrix Exponential
Gaussian Quadrature
Quadrature Rules
Symmetric matrix
Subgraph
Computing
Graph in graph theory
Vertex of a graph

Keywords

  • hubs
  • authorities
  • centrality
  • communicability
  • matrix exponential
  • directed networks
  • digraphs
  • bipartite graphs
  • HITS
  • Katz
  • PageRank
  • Gauss quadrature

Cite this

Benzi, M., Estrada, E., & Klymko, C. (2013). Ranking hubs and authorities using matrix functions. Linear Algebra and its Applications, 438, 2447-2474.
Benzi, Michele ; Estrada, Ernesto ; Klymko, Christine. / Ranking hubs and authorities using matrix functions. In: Linear Algebra and its Applications. 2013 ; Vol. 438. pp. 2447-2474.
@article{91b2af9afc304e6db020762af238f9f9,
title = "Ranking hubs and authorities using matrix functions",
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 withour technique. The use of Gaussian quadrature rules for calculating hub and authority scores is discussed.",
keywords = "hubs, authorities, centrality, communicability, matrix exponential, directed networks, digraphs, bipartite graphs, HITS, Katz, PageRank, Gauss quadrature",
author = "Michele Benzi and Ernesto Estrada and Christine Klymko",
year = "2013",
language = "English",
volume = "438",
pages = "2447--2474",
journal = "Linear Algebra and its Applications",
issn = "0024-3795",

}

Benzi, M, Estrada, E & Klymko, C 2013, 'Ranking hubs and authorities using matrix functions' Linear Algebra and its Applications, vol. 438, pp. 2447-2474.

Ranking hubs and authorities using matrix functions. / Benzi, Michele; Estrada, Ernesto; Klymko, Christine.

In: Linear Algebra and its Applications, Vol. 438, 2013, p. 2447-2474.

Research output: Contribution to journalArticle

TY - JOUR

T1 - Ranking hubs and authorities using matrix functions

AU - Benzi, Michele

AU - Estrada, Ernesto

AU - Klymko, Christine

PY - 2013

Y1 - 2013

N2 - 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 withour technique. The use of Gaussian quadrature rules for calculating hub and authority scores is discussed.

AB - 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 withour technique. The use of Gaussian quadrature rules for calculating hub and authority scores is discussed.

KW - hubs

KW - authorities

KW - centrality

KW - communicability

KW - matrix exponential

KW - directed networks

KW - digraphs

KW - bipartite graphs

KW - HITS

KW - Katz

KW - PageRank

KW - Gauss quadrature

UR - http://arxiv.org/abs/1201.3120

M3 - Article

VL - 438

SP - 2447

EP - 2474

JO - Linear Algebra and its Applications

T2 - Linear Algebra and its Applications

JF - Linear Algebra and its Applications

SN - 0024-3795

ER -