Diffusion Models in Social Networks: Algorithmic and Game-theoretic Aspects

Thursday, July 25, 2013, 4:45pm – 8:15pm
Presented by Vangelis Markakis
Located in Main Amphitheatre – Science bldg.
In track Tutorials

Diffusion in social networks has developed over the years into a large interdisciplinary research area with important links to sociology, computer science, economics, epidemiology, and mathematics. A flurry of numerous articles and recent books shows the growing relevance of this field.

The tutorial will evolve around the question: how do ideas and behaviors spread through a social network and how do we achieve optimal propagation of a new trend or a new product? The processes by which new behavioral patterns spread in a population have been an object of study in the social sciences for the last decades. Typical examples include the adoption of new technologies or innovations, the spread of a virus, or the popularity of a political leader. Inspired by empirical studies, some basic mathematical models have been developed to capture diffusion. The value of such models is that they help us understand better the diffusion mechanisms and make predictions about the success of a new product. In all such models, a user is influenced only by the behavior of its neighbors in the graph of the social network, i.e., his social circle. Hence, the propagation typically begins by a relatively small set of people who adopt the new product (early adopters) and then the spread continues as the remaining people adjust their behavior based on word-of-mouth effects.

In the tutorial, we will first introduce the various models that have been proposed in the literature. We will then study algorithmic and game-theoretic questions that arise naturally in this context. Namely, from an algorithmic point of view, we are interested in finding the most influential set of nodes in the network so as to maximize the spread of a product. Concerning game-theoretic aspects, we will consider models with two or more competing products that spread simultaneously over a network. In this case, we will overview recent work in the literature involving the properties of Nash equilibria in such games, as well as the computation of a firm’s optimal strategy, given the opponents’ choices.