Consider a sparse random Erdős–Rényi graph with n vertices, edge probability p and random exponential edge weights. We consider the weighted shortest path distances between two randomly chosen vertices in the graph. Say, we query K such distances, how accurately can we recover the edge probability p without knowing the network? Say we plant high degree vertices or cliques in the graph, what are the parameters for recovering their existence and what is the sample complexity?

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 distance measurements we obtain from them. There exists theoretical work on the asymptotics (n → infty) in complete graphs [1] and Erdős–Rényi graphs [2] which can be used as a basis.

Aims of the Project:

• simulate distance measurements on a range of graphs
• develop a method for distinguishing ER graphs of different densities
• Test and evaluate accuracy and sample complexity of the method
• 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)