Characterizing network directedness using the containing pseudospectral frontier of the network Laplacian

A large number of complex systems can be represented as directed networks, where the connections (edge weights) between nodes (system states) are such that the flux of the quantity of interest (e.g., energy or information) from node <a:math xmlns:a="http://www.w3.org/1998/Math/MathML"> <a:mi>i</a:mi> </a:math> to <b:math xmlns:b="http://www.w3.org/1998/Math/MathML"> <b:mi>j</b:mi> </b:math> is not equal to that from <c:math xmlns:c="http://www.w3.org/1998/Math/MathML"> <c:mi>j</c:mi> </c:math> to <d:math xmlns:d="http://www.w3.org/1998/Math/MathML"> <d:mi>i</d:mi> </d:math> . The network Laplacian underpins a suite of techniques for studying diffusion and random walks on networks, but many such methods have been developed for undirected graphs. In this paper, we propose a method for characterizing the relative degree of directedness of a network. Our approach is based on the pseudospectrum of the Laplacian and examines the difference in the nature of the “containing pseudospectral frontier” between the Laplacian itself and a variant formed by removing its non-normal structure. The distance between the containing and comparator frontiers then characterizes relative directedness as a function of the shape of the underlying pseudospectral surface. We demonstrate how this metric's behavior is consistent with that expected for a cyclic permutation adjacency matrix and is appropriate for a network where directedness is controlled systematically. We also extend an existing definition of network directedness and then apply our method in detail to a network capturing the Lagrangian dynamics of a turbulent flow. Two local maxima for our metric arise in distinct regions of the complex plane, but the eigenvalues driving these maxima are dominated by nodes from the network that are both very similar to each other and highly atypical in terms of the physics they embody. These nodes are also very different in nature from those highlighted by a stochastic differential equation model for these dynamics that successfully captures many key features of turbulence. This highlights the sensitivity of our approach and its potential utility in model validation, in addition to network characterization.