Asynchronous Averaging on Dynamic Graphs with Selective Neighborhood Contraction

We study a discrete-time consensus model in which agents iteratively update their states through interactions on a dynamic social network. At each step, a single agent is selected asynchronously and averages the values of its current neighbors. A distinctive feature of our model is that an agent’s neighborhood may contract following an update, while non-selected agents may add or remove neighbors independently. This creates a time-varying communication structure with endogenous contraction. We show that under mild assumptions–specifically, that the evolving graph is connected infinitely often–the system reaches consensus almost surely. Our results extend classical consensus theory on time-varying graphs and asynchronous updates by introducing selective neighborhood contraction, offering new insights into agreement dynamics in evolving social systems.