Sign In

Communications of the ACM

ACM TechNews

Can the 'Belief Propagation' Algorithm Accurately Describe Complex Networked Systems?

Theoretical predictions compared to experiments  the new methods make accurate theoretical predictions for realistic networks.

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

Sign In for Full Access
» Forgot Password? » Create an ACM Web Account