Advanced Monte Carlo methods for complex networks

Rare events such as the state-wide power blackout in South Australia in September 2016, natural disasters such as floods and bushfires, or the ensuing chaos when parts of a complex interconnected systems such as the internet fail, are difficult for researchers to simulate or model. They're the primary interest of Professor Dirk Kroese.


Prof Dirk Kroese

“If you simulate a complex system such as a power grid, you don’t normally experience a rare event, even if you run it for a long time,” says Dirk, who is a chief investigator at the ARC Centre of Excellence for Mathematical and Statistical Frontiers (ACEMS) and Professor of Mathematics and Statistics at the University of Queensland.

“But you need to be able to understand rare events to gauge reliability, and identify bottlenecks or sensitive points that might trigger a series of component failures, and have a big impact.”

The answer is to speed up the simulation somehow to make rare events occur more frequently, to explore their consequences and then map back to the original system. And that’s exactly what Dirk does. He essentially loads the dice in his simulations to increase the probability of rare events occurring, and make them more likely.

“You can also use rare event simulation to optimise things. If you design a power grid for example, you want to make links between its components that minimise cost, minimise the chances of outages, and ensure the grid can distribute enough electricity for all,” Dirk says.

“You could try all the possibilities to see which is best—but there are far too many to evaluate. Or you could randomly select options, but there are so many that you would almost never hit an optimal solution. In fact, finding the optimal solution randomly is a rare event, and our techniques are exactly tailored to simulating such an event efficiently.”

Another type of rare event increasingly in the news is when someone contracts a rare but scary infectious disease—such as the Ebola virus, or the 2016 outbreak of measles in Sydney. What is the best public health strategy to implement? The answer depends on how quickly the virus spreads—it depends on how often the infected person encounters other people, who contact other people—in other words, on the dynamics of the local social network. But how can you measure that? What statistics might provide a useful indicator of the activity of a social network? That’s what Dirk and his PhD student Morgan Grant have been working on, and Morgan has developed a new and efficient means of doing so. His research was presented at the Winter Simulation Conference in Washington DC in December 2016 and published in its proceedings.

It’s based on estimating a property called typical distance, a measure of the time it takes something to pass through a network. In a social network where the typical distance is small, for instance, a few people are connected to many and disease can spread widely in just a few steps. But where the typical distance is large, there are not many connections between people, and a virus takes longer to spread through the network.

“If you can describe such networks, you can describe the spread of disease,” Dirk says.

But in the real world, social networks are often large, change frequently and are usually difficult to measure accurately, which is why the work on estimating the typical distance