Burning a Graph as a Model for the Spread of Social Contagion

Abstract

The spread of social contagion is an active area in social network analysis. Assume that we want to spread a message among all the users of a network. Knowing the structure of the network, we may ask how fast can we do this and what is the best strategy? Graph burning is a new graph process which is used as a model for the spread of social contagion. Burning number is a graph parameter associated with the burning process and measures the speed of contagion in the underlying graph of a social network.

In the thesis, we provide several results on the burning number. In particular, we study the relationship of the burning number to other graph structural parameters, the burning number of some specific graphs, the computational complexity of this problem, and the probabilistic versions of this parameter. We also consider the competitive diffusion game on graphs that was our first motivation to define the graph burning process, and we discuss the existence of pure Nash-equilibrium for this game on some specific graph families.