Network analysis using Krylov subspace trajectories

We describe a set of network analysis methods based on the rows of the Krylov subspace matrix computed from a network adjacency matrix via power iteration using a non-random initial vector. We refer to these node-specific row vectors as Krylov subspace trajectories. While power iteration using a random initial starting vector is commonly applied to the network adjacency matrix to compute eigenvector centrality values, this application only uses the final vector generated after numerical convergence. Importantly, use of a random initial vector means that the intermediate results of power iteration are also random and lack a clear interpretation. To the best of our knowledge, use of intermediate power iteration results for network analysis has been limited to techniques that leverage just a single pre-convergence solution, e.g., Power Iteration Clustering, or techniques focused on node similarity, e.g., the flow profile approach of Cooper and Barahona. In this paper, we explore methods that apply power iteration with a non-random initial vector to the network adjacency matrix to generate Krylov subspace trajectories for each node. These non-random trajectories provide important information regarding network structure, node importance, and response to perturbations.