How Complex is a Complex Network? Insights from Linear Systems Theory

Abstract

This paper leverages linear systems theory to propose a principled measure of complexity for network systems. We focus on a network of first-order scalar linear systems interconnected through a directed graph. By locally filtering out the effect of nodal dynamics in the interconnected system, we propose a new quantitative index of network complexity rooted in the notion of McMillan degree of a linear system. First, we show that network systems with the same interconnection structure share the same complexity index for almost all choices of their interconnection weights. Then, we investigate the dependence of the proposed index on the topology of the network and the pattern of heterogeneity of the nodal dynamics. Specifically, we find that the index depends on the matching number of subgraphs identified by nodal dynamics of different nature, highlighting the joint impact of network architecture and component diversity on overall system complexity.

6 pages, 2 figures, 1 table, published on Control Systems Letters (L-CSS), to be presented at the 64th IEEE Conference on Decision and Control, IEEE Control Systems Letters (2025)

References in corpus (7)

• Emergence of scaling in random networks
• Characterization of complex networks: A survey of measurements
• Structural Properties of the Caenorhabditis elegans Neuronal Network
• Control Principles of Complex Networks
• Offdiagonal Complexity: A computationally quick complexity measure for graphs and networks
• Distances and Riemannian metrics for multivariate spectral densities
• On Minimal Spectral Factors with Zeroes and Poles lying on Prescribed Region