Successive Shortest Structures in Random Graphs

点击翻译按钮获取中文摘要

We are surrounded by networks: Transport networks, social networks, infection networks, the internet, and electrical grids to name just a few. The natural way to model these kind of networks mathematically are graphs. Some networks, for example most transport networks, are rather static or develop slowly whereas many networks change fast and often in a manner that is hard to predict. To capture this unpredictable nature of networks one considers random graphs where each connection is chosen (independently) at random or, as in our project, one considers random weights on all possible connections. The research of random graphs does not only give us insights in real-world networks but also yields interesting and beautiful mathematics.In this project we want to consider the effects of repeatedly removing structures from a complete graph with random edge weights. For example, we start with a network in which all connections are present and have a weight or length that is randomly distributed (independently from all the other weights). We have two special sites in our network and want to find the shortest path between them. With current methods that is easy to do as one can exploit the independence of the edges and can give a very precise prediction on the length of the path. When one removes this path and wants to find the next best path one cannot use the independence straight forwardly as one has already revealed most of the weights of the network when finding the first shortest path. In this project we investigate new approaches and methods to give very precise estimations on the length of the second shortest path, the third shortest path and so on. We also consider different structures to shortest paths to find common themes or differences.