权益分类	功能权益	普通用户	{{item.name}}会员
{{category.name}}	{{benefitItem.name}}

Successive Shortest Structures in Random Graphs

随机图中的连续最短结构

基本信息

批准号：
EP/W015404/1
负责人：
Stefanie Gerke
金额：
$ 9.45万
依托单位：
Royal Holloway University of London
依托单位国家：
英国
项目类别：
Research Grant
财政年份：
2022
资助国家：
英国
起止时间：
2022 至无数据
项目状态：
已结题

来源：
https://gtr.ukri.org/projects?ref=EP%2FW015404%2F1
关键词：
Successive Shortest Structures 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.

我们被网络所包围：交通网络、社交网络、传染网络、互联网和电网，仅举几例。对这类网络进行数学建模的自然方法是图形。一些网络，例如大多数传输网络，相当静态或发展缓慢，而许多网络变化迅速，往往难以预测。为了捕捉网络的这种不可预测性，我们考虑随机图，其中每个连接都是随机选择的（独立地），或者像我们的项目一样，我们考虑所有可能连接的随机权重。对随机图的研究不仅能让我们深入了解真实世界的网络，还能产生有趣而美丽的数学。在这个项目中，我们想考虑从一个具有随机边权重的完整图中重复删除结构的影响。例如，我们从一个网络开始，其中所有连接都存在，并且具有随机分布的权重或长度（独立于所有其他权重）。我们有两个特殊的网站在我们的网络，并希望找到它们之间的最短路径。目前的方法很容易做到，因为人们可以利用边缘的独立性，并可以给出一个非常精确的预测路径的长度。当一个删除这条路径，并希望找到下一个最佳路径，不能直接使用的独立性，因为一个已经透露了大部分的权重网络时，找到第一个最短路径。在这个项目中，我们研究新的途径和方法，给出了次最短路径、第三最短路径等的长度的精确估计，并考虑了不同结构的最短路径，找出了它们的共同点或差异点。