Rumor Has It An Algorithm Could Scope Out Gossip

(Inside Science) -- Remember those rumors in high school? Maybe you'll finally learn who was spreading them.

Research over the last few years has explored ways to identify the origin of a rumor that has spread through a network, armed only with information on who has heard it. These kinds of mathematical studies are useful beyond weeding out gossip. They could help find the sources of memes on social media, trends, computer viruses and epidemics.

But, according to one recently published study, whether you can find a rumor's origin depends on the network's complexity.

"The network structure basically dictates when you can and can't find someone," said Tauhid Zaman of the Massachusetts Institute of Technology in Cambridge. "People hadn't made that connection yet, that the network complexity tells you when you can hide or when you can't hide."

If a network is too simple—one in which everyone knows each other, or one that's linear where Alice only knows Bob, who only knows Cathy, who only knows David, and so on—then it's impossible to find the origin of a rumor. If everyone has heard the rumor, it’s impossible to figure out the most likely route a rumor took and track down its origin; every path is possible. In a more complex and realistic network, though, there is a good chance at locating the source.

"If a network isn't complex enough, you'll never find the rumor source," he said. "But if it's just a little complex, I'll find you with a one in three chance."

And if you just want to narrow down the rumor source to eight suspects, then, according to the analysis, the probability that one of them is the real culprit is about 99 percent.

The study, published in the journal Operations Research, expands on work from 2010 in which Zaman and Devavrat Shah, also of MIT, were one of the first to explore the problem of finding the source of a rumor and to work out its math in detail.

Although other research had looked at how information spreads over time, the catch here is that you don't know when anyone first heard the rumor. "You just know that they heard it and they're connected to each other," Zaman said. "The question is how to find the guy who started the rumor."

To find the answer, they showed, you count how many ways the rumor could have spread from each and every person. The one who could spread the rumor through the most number of paths is likely the one who started it, and the researchers could calculate that probability.

The 2010 study focused on a tree network, whose structure has branches but no loops; no one has a circle of friends. For instance, Alice knows Bob, who knows Cathy, David, and Emily—but none of them knows Alice. It was also a simpler, specialized case where every person has the same probability of spreading the rumor to the next person.

But the analysis is general. It extends to more random networks, mathematically proving that the method works for all tree networks. Because more complex and realistic networks are difficult to mathematically prove, Zaman said, the researchers used computer simulations to show their results would also apply to most other networks.

There's another limitation. If the rumor didn't spread very far, and the network has a few celebrities with an abnormally large number of friends, then the algorithm will be biased toward those popular individuals. But by accounting for the number of friends, the researchers could correct some of this bias, Zaman said. While they couldn't mathematically prove anything, their simulations showed that the adjusted algorithm did work better in more realistic scenarios. 

Still, this particular study may not have real-world applications just yet.

"I won't even pretend it's a really game-changing algorithm," Zaman said. "It's a cool idea, but it is theoretical in nature."

Indeed, other researchers have been developing other algorithms for finding rumor sources in more realistic scenarios, said Lei Ying of Arizona State University in Tempe, who, together with Kai Zhu, developed an algorithm that works on a more realistic network, called the Erdos-Renyi random graph.

"Of course, their results are still fundamental," Ying said about Shah and Zaman's work. "Given their network, they're able to quantify the detection probability—that's a very significant contribution to theory."

In fact, the 2010 study helped inspire this entire area of rumor-related research, including his own work, Ying said.

"When I first read the paper, I immediately got interested in the problem. Now I have several students working on it," he said. For example, Ying is exploring ever more realistic cases, like when you don't know how far the rumor has spread.

"These are very important applications," he said. "We are living in a world that's ever more connected. Information diffusion happens every day."