Voter models and influencers in social networks

Goal:

Imagine a graph, i.e. a set of edges and vertices, in which each vertex is in one of two possible states. For example, the vertices could represent Facebook users, edges are friend relationships (two vertices are connected by an edge if the corresponding users are friends on Facebook) and the states represent whether a user is willing to buy some product (vote for a specific candidate in an election, holds some political view etc.). A voter model is such a graph, together with a set of random rules which describe how the states evolve over time. A simple rule for the Facebook example could be:

step 1: randomly choose a person
step 2: randomly choose a friend of that person with a different opinion. This friend then switches his opinion.

If you apply this rule ad infinitum, will the persons eventually reach a consensus, i.e. will each vertex be in the same state, no matter with which initial states you start? How about different rules? What happens if instead of two, there are n possible opinions?

Now we change the model a bit: At the beginning, all persons have the same opinion. We are allowed to choose k persons (so-called influencers), which then switch their opinion. Afterwards, the above rule (where step 2 is only executed if a person with the same opinion as the influencers has been chosen) is applied again ad infinitum. How can we choose the influencers so that in the short/medium/long run the number of persons with our preferred opinion is maximized on average? What happens if there are also "negative" influencers, i.e. persons who propagate the opposite opinion?

For obvious reasons, solutions to such questions are of very high interest to companies, political parties, lobbyists and governments, which is why quite a lot of research has been done in this direction. In this project, you will heuristically discover some known results and also test some conjectures by simulating models as described above.

Supervisors: Simon Campese

Difficulty level: Any (will be adjusted depending on the level and ambitions of the participants)

Tools: Any programming language (recommendations based on existing skills of participants will be given)

Bibliography: Upon request

FSTC -- University of Luxembourg