Source localization consists in finding the starting point of a diffusion process on a network. This is an important problem, whose applications range from finding the patient-zero of a disease to identifying who spread a false rumour in a social network.

We define the metric dimension (MD) of a network as the minimum number of sensors required to guarantee a correct source identification. The MD has been studied theoretically in random graphs such as Erdos-Renyi graphs and random geometric graphs (see for example [1]). Those are random graph models without community structure. In most real networks, nodes tend to form communities (or groups) such that a given node will tend to have more neighbours inside its own group. A popular class of random graphs with community structure is the Stochastic Block Model (SBM).

The goal of this project is to study the effect of the community structure on the metric dimension. The first step consists in performing numerical simulations on synthetic networks to show how the metric dimension varies with the community strength. Depending on student interest, the student could extend the simulations to real networks in a second time, or study theoretically the MD in SBMs graphs.

Requirements

• programming skills (python)
• good knowledge of probability

Preferred:

• familiarity with (random) graphs, and python packages such as networkx.

References: [1] Bollobás, Béla, Dieter Mitsche, and Pawel Pralat. "Metric Dimension for Random Graphs." The Electronic Journal of Combinatorics (2013): P1-P1.

Contact: maximilien.dreveton@epfl.ch.