Consider a random Erdős–Rényi graph with random edge weights and one chosen source vertex. We consider a process called First Passage Percolation (FPP) where we annotate each vertex in the graph (other than the source) with the shortest-path distance between the vertex and the source. This can be thought of as pouring water into the network at the source and noting when the water first reaches all the other nodes.

Clearly, how fast the nodes are reached depends on the structure of the underlying graph. Therefore, this project is concerned with developing a method for distinguishing graphs based on the first passage distance measurements we obtain from them. There exists theoretical work on the asymptotics (n → infty) of FPP in complete graphs [1] and Erdős–Rényi graphs [2] which can be used as a basis.

Aims of the Project:

• simulate FPP processes on a range of graphs
• develop a method for distinguishing tree graphs, ER graphs with chosen density and complete graphs
• Test and evaluate up to which thresholds of density ER graphs are distinguishable from trees and complete graphs
• Theoretically describe the accuracy bounds on the method

Requirements:

• Strong background in probability and stochastic processes
• Knowledge and interest in networks/graph theory
• Knowledge and interest in graph algorithms
• Strong programming skills

References:

[1] S. Janson, “One, Two and Three Times log n/n for Paths in a Complete Graph with Random Weights,” Combinatorics, Probability and Computing, vol. 8, no. 4, pp. 347–361, Jul. 1999, doi: 10.1017/S0963548399003892.

[2] S. Bhamidi, R. V. D. Hofstad, and G. Hooghiemstra, “First Passage Percolation on the Erdős–Rényi Random Graph,” Combinatorics, Probability and Computing, vol. 20, no. 5, pp. 683–707, Sep. 2011, doi: 10.1017/S096354831100023X.

If you are interested, send your CV and transcript to Paula (see contact above)