Not your grandma’s network

by Tyler Shendruk

Published: 10/13/10

The problem THE WORLD IS more interconnected than ever before. Social networks, the global economy, the Internet, and even delivery routes can all seem like a jumbled mess. Nowadays, it is common to see complex nets of relationships everywhere we look.
The simplest network we can imagine is life as an employee on a production line: Our neighbour to our left passes us some widget, we add our component and pass it on to the neighbour on the right. It isn’t a web at all; it’s just a chain.
Now imagine we work in a more complicated factory. Imagine we can get different widgets from multiple neighbours. In fact, even coworkers far from our workstation can toss us widgets. To make matters worse, the foreman lets us wander to and work at any part of the production line we want! What a disaster. We’d be doing a random walk on a random network while receiving random input to deal with.

The researcher
Vadim Kaimanovich, a professor in the Department of Mathematics and Statistics, creates mathematical methods that can predict the nature of complex networks. His goal is to understand when the chaotic evolution of random systems can lead to stable and predictable output.

The project
Kaimanovich uses the analogy of a production line to ask: if we start the production line at a slightly different workstation—one that is close but not exactly the same—will we get a similar widget or something completely different? If the widget doesn’t change, the production is stable. If it’s different, the production diverges.
Scientists have noted many systems that seem as complicated as our crazy production line, but seem to have stable output. However, there were no mathematically rigorous proofs for the existence of stable solutions.

The key
Using a mathematically precise measure to decipher which widgets are similar and which are different, Kaimanovich demonstrated that certain sorts of abstract “random production lines” must have groups of workstations that give stable solutions for the same kind of random input. Not surprisingly, this is the first proof of it’s kind.