On optimal link creation for facilitation of consensus in social networks

Abstract

We consider the problem of reaching consensus in a social network of agents described by the DeGroot model. We develop a measure for the efficiency with which consensus is reached, where the measure quantifies the transient behavior of public opinion around the consensus value. We then propose an optimization problem that maximizes consensus-reaching efficiency via the creation of new social links, subject to a total link-creation budget. We employ the alternating direction method of multipliers, an algorithm well-suited to large optimization problems, to find the optimal location and weights of the new links. We demonstrate the utility of our results through an example, where we observe that for a social network described by a regular graph the addition of new links leads to an augmented graph that resembles a small-world network characterized by sparse long-range links.