In this work, we study the collective behavior of a multi-agent system of stochastically interacting leaders and followers. In this time-varying network, the nodes update their states through a noisy interaction with a randomly selected subset of neighbors, including leaders whose average orientation is not updated in time. By linearizing the system dynamics in the vicinity of the leaders' common trajectory, we establish a toolbox of closed-form expressions that aid in the understanding of the influence of noise, number of connected neighbors, network size, and proportion of leaders on the group coordination. (C) 2015 Elsevier Ltd. All rights reserved.