$6.25M MURI project will decode world’s most complex networks

Michael Wellman

Lynn A Conway Collegiate Professor of Computer Science and Engineering

Mingyan Liu

Professor of Electrical Engineering and Computer Science

Networks have always been key drivers of society, and a new $6.25 million project built on game theory and led by Mingyan Liu at the University of Michigan will develop tools to understand and shape online and on-the-ground networks that drive human decision making. It will focus on areas such as international diplomacy, street crime, cyber-terrorism, military strategy, financial markets and industrial supply chains.

Funded by the Department of Defense, the tools developed by the project could help researchers and officials tease out the innermost workings of networks as small as a group of online bots or as large as the global financial system. Also participating in the project are the University of Southern California, Vanderbilt University and the University of California, Los Angeles.

At the heart of their effort is game theory—a mathematical method of analyzing and understanding strategic interactions among individuals. It has been in use for decades, but the U-M team, led by Mingyan Liu, Professor of Electrical Engineering and Computer Science, is taking it to a new level using what are called multi-scale network structures.

“In the past, game theory was mostly limited to flat, or single-scale networks where interactions are governed by one type of relationship—family affiliation, for example,” Liu said. “But in reality, there are many other types of relationships that affect decision making: religious affiliation, political groups and so on. This leads to a complex and overlapping web of networks. Multi-scale network structures take all those different dimensions into account, mapping out how they influence decision-making and overall network stability.”

The project will apply multi-scale network modeling to the rich trove of data unleashed by electronic recordkeeping—social media posts, crime statistics, demographic trends and countless other sources. The researchers will crunch all this data to develop algorithmic tools that could, for example: illuminate the labyrinthine network behind global securities trading based on just a few scraps of information, help law enforcement stay one step ahead of criminal gangs or help international diplomats reach better decisions.

Michael Wellman, the Lynn A. Conway Professor of Computer Science and Engineering and investigator on the project, believes that the project could provide an important window into the world’s very largest networks, which have grown so complex that in many cases, even those who run them don’t fully understand them.

“In financial markets, for example, you sometimes see a shock to the system that takes everyone by surprise, and that causes things to freeze up because even the traders don’t fully understand what has happened,” he said. “If we could develop a better understanding, it would help to unfreeze things more quickly and improve the stability of the system.”

For smaller networks, such as a group of negotiating countries or even criminal street gangs, the tools could help diplomats and law enforcement predict future behavior and influence decisions more effectively. That could lead to more fruitful negotiations, or it could help law enforcement tamp down gang activity by staying one step ahead.

Also key to the project is the computing power and algorithmic sophistication to crunch through the staggering number of variables in multi-scale networks. It’s a level of complexity that, without modern computing horsepower and machine learning technology, would be unmanageable.

“Ultimately, the utility of a model is limited by the solutions that we can obtain from it,” Liu said. “But new technology is making it possible to predict and influence the outcomes of network games. We’re also developing technology that enables us to generalize a small number of very finely analyzed decisions into a coarser analysis of a larger group. That makes analysis of even the largest networks more computationally feasible.”

At the end of the five-year project, the group plans to provide fundamental algorithms and tools, as well as a cohort of experts who are trained to use them. Those resources will initially be built into software used by the Department of Defense and researchers. Down the road, Liu envisions them being used in other areas as well, like business decision making, supply chain management and even healthcare, where they could help the many different players in the system work together more effectively on behalf of patients.

The award is one of 24 funded by the Department of Defense’s Multidisciplinary University Research Initiative (MURI) program, which supports research by funding teams of investigators from different science and engineering disciplines, with the goal of accelerating the research process.