On the Number of Strongly Structurally Controllable Networks

Network controllability is a structural property, that is, mild and well-understood conditions on the network interconnection pattern ensure controllability from a given set of control nodes for most choices of the edge weights. To ensure network controllability for all choices of edge weights, namely strong structural controllability, more stringent connectivity conditions need to be satisfied. In this paper we derive an alternative algebraic characterization of strong structural controllability of networks with self-loops. This characterization allows us to systematically enumerate all strongly structurally controllable networks with given cardinality and number of control nodes. Differently from the case of (weak) structural controllability we show that, when the ratio of control nodes to the total number of nodes converges to zero, then the fraction of strongly structurally controllable networks decreases to zero. Conversely, when the ratio of control nodes to the total number of nodes converges to one, then the fraction of strongly structurally controllable networks remains lower bounded. Altogether, the results in this paper complement existing studies on the asymptotic number of controllable graphs.