Network Analysis via Partial Spectral Factorization and Gauss Quadrature
Caterina Fenu, Duncan H. Martin, Lothar Reichel, Giuseppe Rodriguez · SIAM Journal on Scientific Computing · 2013
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 $\mathbf{u}^Tf(A)\mathbf{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 $\mathbf{u}$ and $\mathbf{w}$ are vectors, for instance, axis vectors. This paper describes a novel technique for determining upper and lower bounds for expressions $\mathbf{u}^Tf(A)\mathbf{w}$ when $A$ is symmetric and bounds for many vectors $\mathbf{u}$ and $\mathbf{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 $\mathbf{u}$ and $\mathbf{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 $\mathbf{u}$ and $\mathbf{w}$ accurate bounds for $\mathbf{u}^Tf(A)\mathbf{w}$ should be computed. Several computed examples, including an application to software engineering, illustrate the performance of the hybrid method.