Almost equitable partitions and new necessary conditions for network controllability

In this paper, we consider the controllability problem for multi-agent networked control systems. The main results of the paper are new graph-theoretic necessary conditions for controllability involving almost equitable graph vertex partitions. We generalize the known results on the role of graph symmetries and uncontrollability to weighted digraphs with multiple-leaders and we also consider the broadcasted control scenario. Our results show that the internal structure of communities in a graph can induce obstructions to controllability that cannot be characterized by symmetry arguments alone and that in some cases depend on the number-theoretic properties of the communities. We show via examples that our results can be used to account for a large portion of uncontrollable inducing leader-selections that could not have otherwise been accounted for using symmetry results.