Danish computer scientist has developed a superb algorithm for shortest path problem

One of the most classic algorithmic problems deals with calculating the shortest path between two points. A more complicated variant of the problem is when the route traverses a changing network--whether this is a road network or the internet. For 40 years, an algorithm has been sought to provide an optimal solution to this problem. Now, computer scientist Christian Wulff-Nilsen of the University of Copenhagen and two research colleagues have come up with a recipe.

When heading somewhere new, most of us leave it to computer algorithms to help us find the best route, whether by using a car's GPS, or public transport and map apps on our phone. Still, there are times when a proposed route doesn't quite align with reality. This is because road networks, public transportation networks, and other networks aren't static. The best route can suddenly be the slowest, e.g. because a queue has formed due to roadworks or an accident.

People probably don't think about the complicated math behind routing suggestions in these types of situations. The software being used is trying to solve a variant for the classic algorithmic "shortest path" problem, the shortest path in a dynamic network. For 40 years, researchers have been working to find an algorithm that can optimally solve this mathematical conundrum. Now, Christian Wulff-Nilsen of the University of Copenhagen's Department of Computer Science has succeeded in cracking the nut along with two colleagues.

"We have developed an algorithm, for which we now have mathematical proof, that it is better than every other algorithm up to now--and the closest thing to optimal that will ever be, even if we look 1000 years into the future," says Associate Professor Wulff-Nilsen. The results were presented at the FOCS 2020 conferenceChristian Wulff-Nilsen

Optimally, in this context, refers to an algorithm that spends as little time and as little computer memory as possible to calculate the best route in a given network. This is not just true of road and transportation networks, but also the internet or any other type of network.

Networks as graphs

The researchers represent a network as a so-called dynamic graph". In this context, a graph is an abstract representation of a network consisting of edges, roads for example, and nodes, representing intersections, for example. When a graph is dynamic, it means that it can change over time. The new algorithm handles changes consisting of deleted edges--for example if the equivalent of a stretch of a road suddenly becomes inaccessible due to roadworks.

"The tremendous advantage of seeing a network as an abstract graph is that it can be used to represent any type of network. It could be the internet, where you want to send data via as short a route as possible, a human brain, or the network of friendship relations on Facebook. This makes graph algorithms applicable in a wide variety of contexts," explains Christian Wulff-Nilsen.

Traditional algorithms assume that a graph is static, which is rarely true in the real world. When these kinds of algorithms are used in a dynamic network, they need to be rerun every time a small change occurs in the graph--which wastes time.

More data necessitates better algorithms

Finding better algorithms is not just useful when traveling. It is necessary for virtually any area where data is produced, as Christian Wulff-Nilsen points out:

"We are living in a time when volumes of data grow at a tremendous rate and the development of hardware simply can't keep up. To manage all of the data we produce, we need to develop smarter software that requires less running time and memory. That's why we need smarter algorithms," he says.

He hopes that it will be possible to use this algorithm or some of the techniques behind it in practice, but stresses that this is theoretical evidence and first requires experimentation.

Multiple factors synergistically drive socioeconomic disparities in flu burden

Supercomputational modeling identifies areas where inequities are most severe and overlooked

A comprehensive modeling study sheds new light on socioeconomic-based mechanisms that drive disparities in influenza burden across the U.S. Casey Zipfel of Georgetown University in Washington D.C. and colleagues present this analysis in the open-access journal PLOS Computational Biology.

People of lower socioeconomic status experience an increased burden of influenza. Past studies have identified various factors that underlie this health inequity, including decreased flu vaccination, lack of access to paid sick leave, lack of healthcare access, increased susceptibility to infection, and different exposure patterns. However, no previous study has considered all of these factors at once. Flu  CREDIT Flockine, Pixabay

For the new study, Zipfel, and colleagues considered how multiple underlying factors independently and synergistically drive health disparities in influenza burden. They combined large-scale disease datasets and observations from past studies to develop data-driven computational models, enabling them to explore how various factors impact influenza transmission and burden for people of varying socioeconomic status across the U.S.

The analysis showed that people of lower socioeconomic status bear a disproportionate burden of influenza infection in the U.S., and this disparity arises from the synergistic combination of multiple social-economic and healthcare factors. The researchers also identified geographic regions where disparities are most severe and where existing systems to track influenza tend to overlook flu cases among people of low socioeconomic status.

"As the divide in health disparities grows wider across the world, it is imperative that we continue to understand how social determinants impact health, and how this is reflected geographically," Zipfel says. "Our work spotlights inequities in respiratory disease transmission, currently on display due to the COVID-19 pandemic."

The new findings could help inform efforts to eliminate public health disparities due to socioeconomic status and systemic racism. Meanwhile, the researchers note the need to collect better data on healthcare access and usage among people of low socioeconomic status to validate their model findings and inform future research and public health efforts.

Freely available article in PLOS Computational Biologyhttps://journals.plos.org/ploscompbiol/article?id=10.1371/journal.pcbi.1008642

NCCR PlanetS simulations show how the habitability of exoplanets is influenced by their rocks

The weathering of silicate rocks plays an important role to keep the clement climate on Earth. Scientists led by the University of Bern and the Swiss national center of competence in research (NCCR) PlanetS, investigated the general principles of this process. Their results could influence how we interpret the signals from distant worlds including such that may hint towards life.

The conditions on Earth are ideal for life. Most places on our planet are neither too hot nor too cold and offer liquid water. These and other requirements for life, however, delicately depend on the right composition of the atmosphere. Too little or too much of certain gases – like carbon dioxide and Earth could become a ball of ice or turn into a pressure cooker. When scientists look for potentially habitable planets, a key component is therefore their atmosphere. Weathering of silicate rocks is part of the so-called carbon cycle that balances the temperate climate of Earth over long periods of time. Illustration by Jenny Leibundgut

Sometimes, that atmosphere is primitive and largely consists of the gases that were around when the planet formed – as is the case for Jupiter and Saturn. On terrestrial planets like Mars, Venus, or Earth, however, such primitive atmospheres are lost. Instead, their remaining atmospheres are strongly influenced by surface geochemistry. Processes like the weathering of rocks alter the composition of the atmosphere and thereby influence the habitability of the planet.

How exactly this works, especially under conditions very different from those on Earth, is what a team of scientists, led by Kaustubh Hakim of the Centre for Space and Habitability (CSH) at the University of Bern and the NCCR PlanetS, investigated. Their results were published today in The Planetary Science Journal.

Conditions are decisive Kaustubh Hakim is a post-doctoral researcher at the Centre for Space and Habitability at the University of Bern and the NCCR PlanetS. Credit: Vandana S. Kushwaha

“We want to understand how the chemical reactions between the atmosphere and the surface of planets change the composition of the atmosphere. On Earth, this process – the weathering of silicate rocks assisted by water – helps to maintain a temperate climate over long periods of time”, Hakim explains. “When the concentration of CO2 increases, temperatures also rise because of its greenhouse effect. Higher temperatures lead to more intense rainfall. Silicate weathering rates increase, which in turn reduce the CO2 concentration and subsequently lower the temperature”, says the researcher.

However, it need not necessarily work the same way on other planets. Using supercomputer simulations, the team tested how different conditions affect the weathering process. For example, they found that even in very arid climates, weathering can be more intense than on Earth if the chemical reactions occur sufficiently quickly. Rock types, too, influence the process and can lead to very different weathering rates according to Hakim. The team also found that at temperatures of around 70°C, contrary to popular theory, silicate weathering rates can decrease with rising temperatures. “This shows that for planets with very different conditions than on Earth, weathering could play very different roles”, Hakim says.

Implications for habitability and life detection

If astronomers ever find a habitable world, it will likely be in what they call the habitable zone. This zone is the area around a star, where the dose of radiation would allow water to be liquid. In the solar system, this zone roughly lies between Mars and Venus.

“Geochemistry has a profound impact on the habitability of planets in the habitable zone”, study co-author and professor of astronomy and planetary sciences at the University of Bern and member of the NCCR PlanetS, Kevin Heng, points out. As the team’s results indicate, increasing temperatures could reduce weathering and its balancing effect on other planets. What would potentially be a habitable world could turn out to be a hellish greenhouse instead.

As Heng further explains, understanding geochemical processes under different conditions are not only important to estimate the potential for life, but also for its detection. “Unless we have some idea of the results of geochemical processes under varying conditions, we will not be able to tell whether bio-signatures – possible hints of life like the Phosphine that was found on Venus last year – indeed come from biological activity”, the researcher concludes. Kevin Heng is a professor of astronomy and planetary sciences at the University of Bern and member of the NCCR PlanetS. Credit: Alessandro Della Bella

Publication details:
Kastubh Hakim et al.: Lithologic Controls on Silicate Weathering Regimes of Temperate Planets, The Planetary Science Journal, April 2021 DOI: https://doi.org/10.3847/PSJ/abe1b8