Network analysis via partial spectral factorization and Gauss quadrature
FENU, CATERINA;RODRIGUEZ, GIUSEPPE
2013-01-01
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.File | Size | Format | |
---|---|---|---|
sgcenlr13.pdf Solo gestori archivio
Type: versione editoriale
Size 2.19 MB
Format Adobe PDF
|
2.19 MB | Adobe PDF | & nbsp; View / Open Request a copy |
Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.