Large-scale networks arise in many applications. It is often of interest to be able to identify the most important nodes of a network or to ascertain the ease of traveling between nodes. These and related quantities can be determined by evaluating expressions of the form uT f(A)w, where A is the adjacency matrix that represents the graph of the network, f is a nonlinear function, such as the exponential function, and u and w are vectors, for instance, axis vectors. This paper describes a novel technique for determining upper and lower bounds for expressions uT f(A)w when A is symmetric and bounds for many vectors u and w are desired. The bounds are computed by first evaluating a low-rank approximation of A, which is used to determine rough bounds for the desired quantities for all nodes. These rough bounds indicate for which vectors u and w more accurate bounds should be computed with the aid of Gauss-type quadrature rules. This hybrid approach is cheaper than only using Gauss-type rules to determine accurate upper and lower bounds in the common situation when it is not known a priori for which vectors u and w accurate bounds for uT f(A)w should be computed. Several computed examples, including an application to software engineering, illustrate the performance of the hybrid method.

Network analysis via partial spectral factorization and Gauss quadrature

FENU, CATERINA;RODRIGUEZ, GIUSEPPE
2013

Abstract

Large-scale networks arise in many applications. It is often of interest to be able to identify the most important nodes of a network or to ascertain the ease of traveling between nodes. These and related quantities can be determined by evaluating expressions of the form uT f(A)w, where A is the adjacency matrix that represents the graph of the network, f is a nonlinear function, such as the exponential function, and u and w are vectors, for instance, axis vectors. This paper describes a novel technique for determining upper and lower bounds for expressions uT f(A)w when A is symmetric and bounds for many vectors u and w are desired. The bounds are computed by first evaluating a low-rank approximation of A, which is used to determine rough bounds for the desired quantities for all nodes. These rough bounds indicate for which vectors u and w more accurate bounds should be computed with the aid of Gauss-type quadrature rules. This hybrid approach is cheaper than only using Gauss-type rules to determine accurate upper and lower bounds in the common situation when it is not known a priori for which vectors u and w accurate bounds for uT f(A)w should be computed. Several computed examples, including an application to software engineering, illustrate the performance of the hybrid method.
Complex networks; Low-rank approximation; Lanczos process; Gauss quadrature; Software networks
File in questo prodotto:
File Dimensione Formato  
sgcenlr13.pdf

Solo gestori archivio

Tipologia: versione editoriale
Dimensione 2.19 MB
Formato Adobe PDF
2.19 MB Adobe PDF   Visualizza/Apri   Richiedi una copia

I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.

Utilizza questo identificativo per citare o creare un link a questo documento: https://hdl.handle.net/11584/105517
Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus 29
  • ???jsp.display-item.citation.isi??? 26
social impact