Communications of the ACM
Can the 'Belief Propagation' Algorithm Accurately Describe Complex Networked Systems?
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 the smaller solutions are consistent with each other.
Credit: Santa Fe Institute
Researchers at the University of Michigan and the Santa Fe Institute (SFI) demonstrated a novel belief propagation algorithm to solve probabilistic models on networks containing short loops.
These algorithms can be used to model the spread of a disease, for instance, by looking at people in close contact with each other, not their entire network.
However, SFI's George Cantwell said, "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. 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."
The researchers showed their method could make accurate theoretical predictions for realistic networks.
From Santa Fe Institute
View Full Article
Abstracts Copyright © 2021 SmithBucklin, Washington, DC, USA
No entries found