Projection-Based Model Reduction of Multi-Agent Systems Using Graph Partitions

In this paper, we establish a projection-based model reduction method for multiagent systems defined on a graph. Reduced order models are obtained by clustering the vertices (agents) of the underlying communication graph by means of suitable graph partitions. In the reduction process, the spatial structure of the network is preserved and the reduced order models can again be realized as multiagent systems defined on a graph. The agents are assumed to have single-integrator dynamics and the communication graph of the original system is weighted and undirected. The proposed model reduction technique reduces the number of vertices of the graph (which is equal to the dynamic order of the original multi-agent system) and yields a reduced order multiagent system defined on a new graph with a reduced number of vertices. This new graph is a weighted symmetric directed graph. It is shown that if the original multiagent system reaches consensus, then so does the reduced order model. For the case that the clusters are chosen using an almost equitable partition (AEP) of the graph, we obtain an explicit formula for the H-2-norm of the error system obtained by comparing the input-output behaviors of the original model and the reduced order model. We also prove that the error obtained by taking an arbitrary partition of the graph is bounded from below by the error obtained using the largest AEP finer than the given partition. The proposed results are illustrated by means of a running example.