Subscribe to the gold package and get unlimited access to Shamra Academy
Register a new userFinding Your Way: Shortest Paths on Networks
259
0
0.0
(
0
)
Added by
Mason A. Porter
Publication date
2020
fields
Informatics Engineering
and research's language is
English
Ask ChatGPT about the research
No Arabic abstract
Traveling to different destinations is a big part of our lives. We visit a variety of locations both during our daily lives and when were on vacation. How can we find the best way to navigate from one place to another? Perhaps we can test all of the different ways of traveling between two places, but another method is to use mathematics and computation to find a shortest path. We discuss how to construct a shortest path and introduce Dijkstras algorithm to minimize the total cost of a path, where the cost may be the travel distance, travel time, or some other measurement. We also discuss how to use shortest paths in the real world to save time and increase traveling efficiency.
rate research
Read More
In 1903, noted puzzle-maker Henry Dudeney published The Spider and the Fly puzzle, which asks for the shortest path along the surfaces of a square prism between two points (source and target) located on the square faces, and surprisingly showed that the shortest path traverses five faces. Dudeneys source and target points had very symmetrical locations; in this article, we allow the source and target points to be anywhere in the interior of opposite faces, but now require the square prism to be a cube. In this context, we find that, depending on source and target locations, a shortest path can traverse either three or four faces, and we investigate the conditions that lead to four-face solutions and estimate the probability of getting a four-face shortest path. We utilize a combination of numerical calculations, elementary geometry, and transformations we call corner moves of cube unfolding diagrams,
A localized method to distribute paths on random graphs is devised, aimed at finding the shortest paths between given source/destination pairs while avoiding path overlaps at nodes. We propose a method based on message-passing techniques to process global information and distribute paths optimally. Statistical properties such as scaling with system size and number of paths, average path-length and the transition to the frustrated regime are analysed. The performance of the suggested algorithm is evaluated through a comparison against a greedy algorithm.
We present a framework to simulate SIR processes on networks using weighted shortest paths. Our framework maps the SIR dynamics to weights assigned to the edges of the network, which can be done for Markovian and non-Markovian processes alike. The weights represent the propagation time between the adjacent nodes for a particular realization. We simulate the dynamics by constructing an ensemble of such realizations, which can be done by using a Markov Chain Monte Carlo method or by direct sampling. The former provides a runtime advantage when realizations from all possible sources are computed as the weighted shortest paths can be re-calculated more efficiently. We apply our framework to three empirical networks and analyze the expected propagation time between all pairs of nodes. Furthermore, we have employed our framework to perform efficient source detection and to improve strategies for time-critical vaccination.
Physarum Polycephalum is a slime mold that is apparently able to solve shortest path problems. A mathematical model has been proposed by biologists to describe the feedback mechanism used by the slime mold to adapt its tubular channels while foraging two food sources s0 and s1. We prove that, under this model, the mass of the mold will eventually converge to the shortest s0 - s1 path of the network that the mold lies on, independently of the structure of the network or of the initial mass distribution. This matches the experimental observations by the biologists and can be seen as an example of a natural algorithm, that is, an algorithm developed by evolution over millions of years.
Understanding how and how far information, behaviors, or pathogens spread in social networks is an important problem, having implications for both predicting the size of epidemics, as well as for planning effective interventions. There are, however, two main challenges for inferring spreading paths in real-world networks. One is the practical difficulty of observing a dynamic process on a network, and the other is the typical constraint of only partially observing a network. Using a static, structurally realistic social network as a platform for simulations, we juxtapose three distinct paths: (1) the stochastic path taken by a simulated spreading process from source to target; (2) the topologically shortest path in the fully observed network, and hence the single most likely stochastic path, between the two nodes; and (3) the topologically shortest path in a partially observed network. In a sampled network, how closely does the partially observed shortest path (3) emulate the unobserved spreading path (1)? Although partial observation inflates the length of the shortest path, the stochastic nature of the spreading process also frequently derails the dynamic path from the shortest path. We find that the partially observed shortest path does not necessarily give an inflated estimate of the length of the process path; in fact, partial observation may, counterintuitively, make the path seem shorter than it actually is.
Log in to be able to interact and post comments
comments
Fetching comments
Sign in to be able to follow your search criteria
