ASU researcher works to design algorithms for more robust networks

Our daily lives depend on various networks — from the electric grid and transportation systems to online social connections — running reliably.

At their most basic level, networks are a collection of nodes and links between those nodes. Using road systems as an example, a node would be an intersection, and a link would be the roads connecting those intersections. Looking at a nationwide transportation level, this can get complicated, with many opportunities for disruption.

An important area of study for many networks surrounds robustness, or the quantification of a network's ability to continue to function in the presence of an external disturbance, which could be severe weather, random failures or deliberate attacks. Attacks can also be cause for limiting network robustness, for example when trying to stop terrorist propaganda networks on social media.

Such a critical aspect of our society has generated much research for measuring networks and how their robustness changes as they evolve, as well as for comparisons of robustness between different networks.

However, Hanghang Tong, assistant professor of computer science at Arizona State University’s Ira A. Fulton Schools of Engineering, seeks to take the study of network robustification one step further: to design effective intervention strategies and algorithms when networks are likely to fail.

This work has earned Tong a five-year, $500,000 National Science Foundation CAREER Award project, “Network Robustification: Theories, Algorithms and Applications,” where he and his team will develop and test basic theories and algorithms to address network robustification.

“We’re looking at what we can do to intervene — by establishing or cutting out links or nodes to rewire them — so robustness changes in a desired way,” Tong said.

Two challenges have largely prevented this problem from being solved in the past: the theoretical side of what measures to take to intervene and the execution side of how to design an effective algorithm for intervention.

“Based on existing literature from the past 20 years, we don’t know exactly what the intrinsic relationship is between different robustness measures, or if there are any common building blocks for network intervention algorithms or optimization algorithms,” Tong said. “If we have a unified view, it’ll help us to simplify the algorithm design so we don’t need to design 20 different algorithms for 20 different robustness measures.”

Designing a unified suite of algorithms also means ensuring they’re scalable, adaptable and optimized for a wide variety of networks and robustification challenges. Then Tong’s team will verify the algorithm suite works with real-world applications in an intelligent transportation system and an online social collaboration.

Tong believes his innovative approach in moving beyond network robustness observation to intervention and its broader impact were what caught the NSF’s attention.

“Network robustness itself is pivotal to many other high-impact applications, and we hope that other domains will also benefit from our findings, tools and algorithms,” Tong said.

He said he would not have been able to fully show the innovation and broader impact of his research without the help of many different channels in the Ira A. Fulton Schools of Engineering. Sandeep Gupta, School of Computing, Informatics, and Decision Systems Engineering interim director, wrote a detailed and tailored letter of support for Tong’s research. Tirupalavanam Ganesh, associate research professor and assistant dean of Engineering Education, helped him polish a detailed education plan for the K-12 outreach requirement of a NSF CAREER Award. And the Research Advancement support team was instrumental in crafting his proposal.

“On top of that, I am very grateful to my ASU colleagues,” Tong said. “A lot of them gave me constructive advice and suggestions, read proposals despite their busy schedules, and gave very helpful reviews. Most important is the encouragement I receive from them when I feel stuck.”