Network properties revealed through matrix functions

Ernesto Estrada, Desmond Higham

Research output: Contribution to journalArticle

136 Citations (Scopus)

Abstract

The emerging field of network science deals with the tasks of modeling, comparing, and summarizing large data sets that describe complex interactions. Because pairwise affinity data can be stored in a two-dimensional array, graph theory and applied linear algebra provide extremely useful tools. Here, we focus on the general concepts of centrality, communicability, and betweenness, each of which quantifies important features in a network. Some recent work in the mathematical physics literature has shown that the exponential of a network's adjacency matrix can be used as the basis for defining and computing specific versions of these measures. We introduce here a general class of measures based on matrix functions, and show that a particular case involving a matrix resolvent arises naturally from graph-theoretic arguments. We also point out connections between these measures and the quantities typically computed when spectral methods are used for data mining tasks such as clustering and ordering. We finish with computational examples showing the new matrix resolvent version applied to real networks.
LanguageEnglish
Pages696-714
Number of pages19
JournalSIAM Review
Volume52
Issue number4
DOIs
Publication statusPublished - 8 Nov 2010

Fingerprint

Matrix Function
Resolvent
Betweenness
Linear algebra
Centrality
Graph theory
Adjacency Matrix
Spectral Methods
Large Data Sets
Affine transformation
Data mining
Pairwise
Data Mining
Quantify
Physics
Clustering
Computing
Graph in graph theory
Interaction
Modeling

Keywords

  • centrality measures
  • clustering methods
  • communicability
  • Estrada index
  • Fiedler vector
  • graph Laplacian
  • graph spectrum
  • power series
  • resolvent

Cite this

Estrada, Ernesto ; Higham, Desmond. / Network properties revealed through matrix functions. In: SIAM Review. 2010 ; Vol. 52, No. 4. pp. 696-714.
@article{85efb819f1c44b39aa75ec10788be18a,
title = "Network properties revealed through matrix functions",
abstract = "The emerging field of network science deals with the tasks of modeling, comparing, and summarizing large data sets that describe complex interactions. Because pairwise affinity data can be stored in a two-dimensional array, graph theory and applied linear algebra provide extremely useful tools. Here, we focus on the general concepts of centrality, communicability, and betweenness, each of which quantifies important features in a network. Some recent work in the mathematical physics literature has shown that the exponential of a network's adjacency matrix can be used as the basis for defining and computing specific versions of these measures. We introduce here a general class of measures based on matrix functions, and show that a particular case involving a matrix resolvent arises naturally from graph-theoretic arguments. We also point out connections between these measures and the quantities typically computed when spectral methods are used for data mining tasks such as clustering and ordering. We finish with computational examples showing the new matrix resolvent version applied to real networks.",
keywords = "centrality measures, clustering methods, communicability, Estrada index, Fiedler vector, graph Laplacian, graph spectrum, power series, resolvent",
author = "Ernesto Estrada and Desmond Higham",
year = "2010",
month = "11",
day = "8",
doi = "10.1137/090761070",
language = "English",
volume = "52",
pages = "696--714",
journal = "SIAM Review",
issn = "0036-1445",
number = "4",

}

Network properties revealed through matrix functions. / Estrada, Ernesto; Higham, Desmond.

In: SIAM Review, Vol. 52, No. 4, 08.11.2010, p. 696-714.

Research output: Contribution to journalArticle

TY - JOUR

T1 - Network properties revealed through matrix functions

AU - Estrada, Ernesto

AU - Higham, Desmond

PY - 2010/11/8

Y1 - 2010/11/8

N2 - The emerging field of network science deals with the tasks of modeling, comparing, and summarizing large data sets that describe complex interactions. Because pairwise affinity data can be stored in a two-dimensional array, graph theory and applied linear algebra provide extremely useful tools. Here, we focus on the general concepts of centrality, communicability, and betweenness, each of which quantifies important features in a network. Some recent work in the mathematical physics literature has shown that the exponential of a network's adjacency matrix can be used as the basis for defining and computing specific versions of these measures. We introduce here a general class of measures based on matrix functions, and show that a particular case involving a matrix resolvent arises naturally from graph-theoretic arguments. We also point out connections between these measures and the quantities typically computed when spectral methods are used for data mining tasks such as clustering and ordering. We finish with computational examples showing the new matrix resolvent version applied to real networks.

AB - The emerging field of network science deals with the tasks of modeling, comparing, and summarizing large data sets that describe complex interactions. Because pairwise affinity data can be stored in a two-dimensional array, graph theory and applied linear algebra provide extremely useful tools. Here, we focus on the general concepts of centrality, communicability, and betweenness, each of which quantifies important features in a network. Some recent work in the mathematical physics literature has shown that the exponential of a network's adjacency matrix can be used as the basis for defining and computing specific versions of these measures. We introduce here a general class of measures based on matrix functions, and show that a particular case involving a matrix resolvent arises naturally from graph-theoretic arguments. We also point out connections between these measures and the quantities typically computed when spectral methods are used for data mining tasks such as clustering and ordering. We finish with computational examples showing the new matrix resolvent version applied to real networks.

KW - centrality measures

KW - clustering methods

KW - communicability

KW - Estrada index

KW - Fiedler vector

KW - graph Laplacian

KW - graph spectrum

KW - power series

KW - resolvent

UR - http://www.scopus.com/inward/record.url?scp=79952942310&partnerID=8YFLogxK

U2 - 10.1137/090761070

DO - 10.1137/090761070

M3 - Article

VL - 52

SP - 696

EP - 714

JO - SIAM Review

T2 - SIAM Review

JF - SIAM Review

SN - 0036-1445

IS - 4

ER -