Majority Opinion Diffusion Model

Description

Motivation

How do people form their opinions? How does a rumor spread? How do the members of a community influence each other? Researchers from a wide spectrum of fields have devoted a substantial amount of effort to address these questions. From a theoretical perspective, it is natural to introduce and study mathematical models which mimic rumor spreading and opinion formation in a community. In the real world, such processes are too complex to be explained in purely mathematical terms. However, the main idea is to comprehend their general principles and make crude approximations at discovering certain essentials which are otherwise totally hidden by the complexity of the full phenomenon. In particular, there are recurring patterns that one can try to capture mathematically.

Basic Model

Consider a graph G and an initial configuration where each node is either black or white. Assume that in discrete time rounds, all nodes simultaneously update their color based on a predefined rule. One can think of graph G as a social network, the graph of relationships and interactions within a group of individuals. Furthermore, black and white stand for the state of an individual, for example, informed/uninformed about a rumor or positive/negative regarding a reform proposal. For the suitable choices of the updating rule, this model can potentially mimic the rumor spreading and opinion forming processes such as the diffusion of technological innovations in a community or the rise of a political movement in an unstable society.

Majority Model

The focus of this project is on the majority model, where each node updates its color to the most frequent color in its neighborhood in each round. One can also study different variants of the majority model. For example, consider the setup where some nodes have a higher influence factor than the others (i.e., influential nodes) or some nodes never change their color (i.e., stubborn nodes).

Goals

The goal of this project is to study the following questions, from both a theoretical and practical perspective:

What is the number of rounds that the majority process needs to stabilize?
How many nodes must be black initially so that black color takes over (i.e., the whole graph becomes black eventually)?
Assume that each node is black initially with some probability p, independently. What is the probability that black color takes over?

The project aims to investigate the majority model (and its variants) on the random and expander graphs and different graph models which mimic the real-world social networks. Furthermore, several experiments need to be designed and implemented on the graph data from real-world social networks to complement the theoretical findings of the project.

Requirements

Deep understanding of graph theory. (Familiarity with different random graph models and social networks is a plus, but not required.)
Good knowledge of probability theory. (Familiarity with Markov chains is an advantage.)
Decent programming skills (ideally Go, C++, or Python).