Orthogonal Expansion of Network Functions

The power series expansion of functions of the adjacency matrix for a network can be interpreted in terms of walks in the network. This makes matrix functions, such as the exponential or resolvent, useful for the analysis of graphs. For instance, these functions shed light on the relative importance of the nodes of the graph and on the overall connectivity. However, the power series expansions may converge slowly, and the coefficients of these expansions typically are not helpful in assessing how important longer walks are in the network. Expansions of matrix functions in terms of orthogonal or bi-orthogonal polynomials make it possible to determine scaling parameters so that a given network has a specified effective diameter (the length after which walks become essentially irrelevant for the connectivity of the network). We describe several approaches for generating orthogonal and bi-orthogonal polynomial expansions, and discuss their relative merits for network analysis.