Consensus on Open Multi-Agent Systems Over Graphs Sampled from Graphons

-- We show how graphons can be used to model and analyze open multi-agent systems, which are multi-agent systems subject to arrivals and departures, in the specific case of linear consensus. First, we analyze the case of replacements, where under the assumption of a deterministic interval between two replacements, we derive an upper bound for the disagreement in expectation. Then, we study the case of arrivals and departures, where we define a process for the evolution of the number of agents that guarantees a minimum and a maximum number of agents. Next, we derive an upper bound for the disagreement in expectation, and we establish a link with the spectrum of the expected graph used to generate the graph topologies. Finally, for stochastic block model (SBM) graphons, we prove that the computation of the spectrum of the expected graph can be performed based on a matrix whose dimension depends only on the graphon and it is independent of the number of agents. Open multi-agent systems are a framework used to analyze networks subject to arrivals, departures or replacements of agents at a rate similar to the scale time of the process [1], [2]. This type of systems are essentially characterized by the agent internal dynamics, the evolution of the network and the arrivals and departures [3]. This is usually done by considering trivial dynamics like complete graphs [4]-[6], bounds on the algebraic connectivity or diameter [7], [8] or just connectivity at all time instants [9].