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.