UM Today UM Today University of Manitoba UM Today UM Today UM Today
Karen Gunderson

The speed of a rumour

How information travels through a network

August 19, 2019 — 

Pure mathematics is all about the long game, according to mathematician and alumna Karen Gunderson.

You hope that some of the ideas that you have now, someday, will help people to answer a real-world problem in the future,” says Gunderson, still in the early years of her career as an assistant professor in the mathematics department in the Faculty of Science. “You hope that when you’re not so focussed on a particular real world problem, your mind is a little freer to be imaginative and creative. You might come up with ideas that people wouldn’t see if they were too focused on a particular application. Maybe you can see a more general structure of what’s going on.”

Karen Gunderson

Karen Gunderson

Gunderson works within the fields of graph theory and combinatorics. Graph theory is the study of networks – systems of nodes with links between nodes. Combinatorics encompasses both the mathematics of counting (not necessarily just large sets) and the study of finite structures such as systems of sets.

An example of how these two fields are applied to the every day, is trying to understand how information—or rumours, or an infection—can travel through a large net­work. Another real-world application of similar research could be applied to how rumours—such as political mud­slinging—would travel between people through phone calls, face-to-face conversations or social media, but there’s also potential to apply her research to computer science, linguistics, physics or animal conservations.

One of Gunderson’s projects, a collaboration with Ryerson’s Anthony Bonato and post-doc researcher Amy Shaw, could be described as an attempt to come up with a model for viral marketing. For example, assume a com­pany is trying to spread a rumour (or promote a product) in a network, using their resources to spread the message every day, with the goal to spread it everywhere.

“But of course the network is also growing and chang­ing over the time. So the question is, can you keep up?” explains Gunderson.

If the world’s growing population keeps growing, can a company ever find enough of the right influencers so that even as the network keeps growing, the rumour (or sales pitch) covers more and more of the network?

“We were able to come up with an exact speed. If the network is growing this fast, you can make sure that almost everybody in the network knows over time,” says Gunderson, with some satisfaction. “If it’s growing this fast, you can make sure that a reasonable proportion of people know. And if it’s growing faster than a certain speed, there’s no hope. Over time, almost nobody knows, no matter how well-chosen your influencers are.”

Mathematics was a gradual career choice for Gunderson. While she thought algebra was “the most fun and amazing thing in the world” in junior high school, she hadn’t realized mathematics could be an occupation until her undergraduate years at the U of M. She became progressively interested in graph theory and combinatorics, with her imagination fired by the six degrees of separation theory (pop-culture fans might recall a game called Six Degrees of Kevin Bacon, trying to figure out how Hollywood actors are connected to Kevin Bacon). Gunderson was intrigued by the techniques used by mathematicians to figure out how many degrees of separation there were in an acquaintance network.

She came back to U of M after completing her PhD at the University of Memphis. On what drew her back (her husband is also a faculty member):

TOP TO BOTTOM: Graphics representing a run of a bootstrap percolation process, showing infection and recovery spreading through neighbours across the plane. The darkest red are the patches that were infected the longest and the bits of blue/purple represent patches that recovered from infection at least once before finally succumbing. The last graph is an amalgam of all steps.

TOP TO BOTTOM: Graphics representing a run of a bootstrap percolation process, showing infection and recovery spreading through neighbours across the plane. The darkest red are the patches that were infected the longest and the bits of blue/purple represent patches that recovered from infection at least once before finally succumbing. The last graph is an amalgam of all steps.

“We were keen to end up working in the same city after seven years apart (four while dating and three after we got married). I was very happy to get the job here, not only to solve our “two-body problem”, but also because I think this is a great university and one where I thought I could contribute something positive and that would also have good opportunities for my research.”

Her current research interests are random graphs, percolation, hypergraphs and extremal combinatorics.

“I’ve worked on making my explanations of what I do understandable,” Gunderson says, because when she travels to the U.S. for mathematics conferences, border security guards always ask what she does, and then ask, fascinated, “What kind of mathematics?”

Her work is sometimes inspired by real life problems, seeking a more abstract version, such as when she sees a rumour spreading on a social network such as Facebook and thinks, oh, there are some interesting math problems there.

“You’re always going around inventing problems. You see something from real life, or a physical application, and say, okay, well I don’t actually want to answer that question, but what would be an interesting thought experiment, an abstract problem that gets to the heart of what’s going on there,” explains Gunderson. “And then you have to dream up how to answer these questions.”

It’s a thought process that involves a large dose of creativity: to see the problem and abstract it. To come up with examples typical of the problem being considered. If you decrease the size of the network, or loosen the restriction—will the thing that you’re trying to prove still be true?

To start off by trying to use one technique to solve the problem, only to realize after days of writing on whiteboards that approach will never work, and something completely new will have to be attempted. “It’s always that thing of trying to dream up something that’s completely unique and brand new to address these problems people come up with,” says Gunderson. “It’s really creative in mathematics.”

From physics to infections

On Karen Gunderson’s website, an image illustrates a project she worked on with Tom Coker (International Mathematical Olympiad), then a grad student at Cambridge. A panel of eight boxes shows a succession: the first box is white, and contains a few red and blue dots like the spatter from an artist’s paint brush. The boxes progressively fill with more and more red dots until the final panel is entirely red.

As an example of graph theory, the boxes filling with red represent several things. It depicts how infections can travel through a large group of people, but also how information or rumours can travel through a network, such as news travelling through a social network like Facebook—the red dots represent infected people, or those who know the rumour, while the blue dots represent healthy people, those who don’t know the rumour or stopped believing.

But the problem was originally proposed by physicists who wanted to understand the behaviour of particles laid out in a configuration, where a negatively charged particle surrounded by lots of positively charged particles will tend to change its charge to match its neighbour, and vice versa.

“The question that I was working on was, if you scatter the sick people initially randomly on the grid, what’s the cut-off density for where everybody eventually will recover or everybody eventually will get sick,” says Gunderson. They were able to find the turning point, where if enough people are initially sick, everyone is eventually infected.

This story originally appeared in the Summer 2019 issue of ResearchLIFE. 

Research at the University of Manitoba is partially supported by funding from the Government of Canada Research Support Fund.

, ,

© University of Manitoba • Winnipeg, Manitoba • Canada • R3T 2N2

Emergency: 204-474-9341