A meme is a thought or action or behaviour that spreads in a social network. Memes are pervasive now with the abundance of on-line social media, ranging from fads like the ice bucket challenge, to popular gifs or sayings. The Big Bang Theory hilariously took on the topic of memes in the following clip.

Network scientists have been studying the spread of influence in social networks for some time. Given the prevalence of big data, there is a renewed interest in the topic among mathematicians and computer scientists studying complex networks.

The featured image in this post shows the spread of the “No one should” meme on Facebook.

Click to access Burning-IM-revised4.pdf

We introduced the notion of graph burning as a simplified model for the spread of memes in a network. Imagine someone trying to optimize the spread of a meme, hitting key actors in the network with the meme in a given priority sequence. To recap graph burning, nodes start off as dormant, and become active over time. If a dormant node is neighboring an active one, it too becomes active. This is similar to graph percolation, but with the major variation that we can activate a new node anywhere in the next network in each step.

Here is an example of burning a graph in three steps, with the active nodes chosen by different colors. We burned the red circled node first, followed by the green, then blue. Notice how the fire spread from each circled node over time to neighbours.

Our first published paper on the topic How to Burn a Graph considers the burning number of a graph, which measures how fast burning spreads. We considered characterizations of the burning number, as well as its values on trees and other graph families.

In a forthcoming paper, we  prove that computing the best way to burn a graph is hard, in the sense of being NP-complete. In other words, it is highly unlikely someone will find a fast way of compute how to burn a graph in the general case.

The cool thing is that the NP-completeness holds even in graphs with a simple structure. For example, the problem is NP-complete in trees, and even special trees like those with maximum degree three, or spiders (think of paths connected to a single root node).  The burning problem is even hard on the disjoint union of paths.

Our work suggests that determining how quickly to spread an aggressive meme in a social network is a non-trivial problem. We have some fast algorithms in restricted cases, but for now, heuristics are all we can suggest for spreading a meme in a general network.

In the meantime, memes will continue to propagate throughout our culture.

Anthony Bonato