A messaging-passing algorithm known as “belief propagation” can be used to analyze large systems by breaking them down into smaller pieces and ensuring all of the smaller solutions are consistent with each other. To model the spread of disease when people are in close contact, for example, researchers tend to explore infected individuals’ network of contacts because they are large systems.
In principle, calculating how a disease will spread among a huge network of contacts is a difficult challenge. But to predict what will happen to any of these individuals, we only need to know what happens to people they’re actually in contact with—not everyone within their network.
To explain what happens to these contacts, we only need to look at their contacts and so on. This is the recursive logic of belief propagation, and it enables a huge and unwieldy calculation to be reduced to a series of much simpler ones. While this sounds great, in practice it can all unravel.
In a paper published in Science Advances, University of Michigan and Santa Fe Institute (SFI) researchers Alec Kirkley, George Cantwell, and Mark Newman report a novel belief propagation algorithm for the solution of probabilistic models on networks containing short loops.
“Suppose Alice was in close contact with Bob, who was in contact with Charlotte. To know what happens to Alice, we need to know about Bob, and then Charlotte,” explains Cantwell, a physicist and SFI Program Postdoctoral Fellow. “But suppose it turns out that Charlotte was already in contact with Alice, now we’ve backed ourselves into a sort of infinite regress. To predict what happens to Alice, we need to first predict what happens to Bob, then Charlotte, then Alice again.”
Remarkably, the belief propagation algorithm can still be run for such apparently self-referential questions, and not just to predict disease spread. Unfortunately, the answers it provides aren’t correct and can often be wrong by a large margin—particularly for realistic-looking structures.
“In our work, we develop practical methods to fix this shortcoming,” says Cantwell. “For example, we show how the method can be used to solve one of the canonical models from the physics literature, demonstrating that we can accurately calculate the physical behavior of the system. Moving forward, we hope this style of analysis will prove useful for all manner of statistical models built on complex structures such as human networks.”
To find the right network model, compare all possible histories
More information:
Alec Kirkley et al. Belief propagation for networks with loops, Science Advances (2021). DOI: 10.1126/sciadv.abf1211
Provided by
Santa Fe Institute
Citation:
Can the ‘belief propagation’ algorithm accurately describe complex networked systems? (2021, April 28)
retrieved 28 April 2021
from https://techxplore.com/news/2021-04-belief-propagation-algorithm-accurately-complex.html
This document is subject to copyright. Apart from any fair dealing for the purpose of private study or research, no
part may be reproduced without the written permission. The content is provided for information purposes only.
