Consider a given weighted graph G. The weights are independent and exponentially distributed. We assume that most edge weights are generated with mean 1 while there is a set of vertices V_1 between which the edge weights are much larger. 
Let a query return the shortest path distance between two given vertices. We ask how many random queries it takes to identify the vertex set V_1, how this depends on the structure of the graph and what improvement can be gained from choosing queries (adaptively or non-adaptively).



Aims of the Project:

• Read and understand the relevant literature
• Simulation of distance measurements on a range of graphs
• 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/experimental skills

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