  We study concentration inequalities in gossip opinion dynamics over random
graphs. In the model, a network is generated from a random graph model with
independent edges, and agents interact pairwise randomly over the network.
During the process, regular agents average neighbors' opinions and then update,
whereas stubborn agents do not change opinions. To approximate the original
process, we introduce a gossip model over an expected graph, obtained by
averaging all possible networks generated from the random graph model. Using
concentration inequalities, we derive high-probability bounds for the distance
between the expected final opinion vectors over the random graph and over the
expected graph. Leveraging matrix perturbation results, we show how such
concentration can help study the effect of network structure on the expected
final opinions in two cases: (i) When the influence of stubborn agents is
large, the expected final opinions polarize and are close to stubborn agents'
opinions. (ii) When the influence of stubborn agents is small, the expected
final opinions are close to each other. With the help of concentration
inequalities for Markov chains, we obtain high-probability bounds for the
distance between time-averaged opinions and the expected final opinions over
the expected graph. In simulation, we validate the theoretical findings, and
study a gossip model over a stochastic block model that has community
structure.
