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.