PNNL

The idea that a small number of select individuals can have a disproportionately large influence on a social network is known as “influence maximization.” From viral marketing to tracking contagious viruses, or anything else that can spread through a network, influence maximization has a wide variety of applications. However, selecting a small set of key players in a social network is a hard problem of exploring all combinations of items taken at a time—a combinatorial explosion. 

Addressing this “explosion” becomes really important when costs need to be considered. The idea with influencers is that a small number of people can influence a disproportionately large number of people, so an advertiser would want to pay the top influencers to market their product on social media. With finite resources, such as sensors in an infrastructure network like the power grid, and in transportation, computer, and water/gas distribution networks, decision makers need to figure out where those resources should be allocated to make the biggest impact and benefit the most people. 

The new computing framework “DIMPLES” recently unlocked a new level of success in calculating key players in networks with greater speed and accuracy than current methods. Using 8,000 compute nodes with over 65,000 AMD GPUs and 458,000 AMD CPU cores on Frontier, the world’s first exascale supercomputer, the team was able to identify 40,000 influencers in a national scale network of about 300 million nodes in just 25 minutes—an unprecedented scale. 

“Previously, these calculations would have taken hours or days to run on even the most powerful supercomputers,” said Reece Neff, who worked on DIMPLES as part of the Department of Energy’s Distinguished Graduate Research Program. “Now, we can run the same calculations in minutes.” 

This speedup in computation time earned DIMPLES a best paper award at the Association for Computing Machinery (ACM) International Conference on Supercomputing 2025.

Taming the combinatorial explosion

Calculations of large networks can quickly become intractable as the number of parameters increases—a phenomenon known as the “combinatorial explosion." 

“Previously, our calculations were very limited in scope—up to only a few million actors in a network,” said Marco Minutoli, first author of the paper. “The underlying algorithms behind these calculations were computationally inefficient, limiting what we could do in the amount of computing time we had.” 

The team overcame the combinatorial explosion of these calculations by pairing a new algorithm, OPIM-C, with a massively parallel and distributed implementation. OPIM uses efficient sampling and submodular optimization, where the work can be composed into submodular set functions that exhibit diminishing returns. The idea behind diminishing results is that a small set of influencers can achieve the same result that a larger set would also achieve since there is diminished value in receiving the same information from multiple sources. 

The team then scaled their calculations to cover a realistic contact network roughly the size of the population of the United States—over two orders of magnitude greater than previous methods. This work builds on the pioneering work of researchers in the Biocomplexity Institute at the University of Virginia with broad implications for the use of high-performance computing for public good.

Leveraging submodularity to accelerate computations

DIMPLES brings in the latest advances in algorithms and computing to scale. The team behind DIMPLES, which includes researchers from PNNL, Oak Ridge National Laboratory, the University of Virginia, Washington State University, and North Carolina State University, combined different algorithms to make influence maximization more efficient.

For certain problems that face combinatorial explosion, the work is divided into smaller components for efficient processing. By leveraging submodularity, the solutions for these smaller subproblems can be aggregated, ensuring an approximate solution for the entire network, and thus making the problem tractable. 

“Submodularity guarantees an approximate solution—even when the exact solution is computationally infeasible” said Mahantesh Halappanavar, leader of the Data Sciences and Machine Intelligence group at PNNL. “The combination of submodularity and parallelism was crucial for DIMPLES to achieve its dramatic increase in speed and scalability.”

Submodular functions are frequently used in artificial intelligence, especially in active learning, feature selection, and clustering, where selecting a subset of representative features preserves information with diminishing returns. While most studies of submodularity are purely theoretical, DIMPLES advances the practice of incorporating submodularity into computations. 

Additional authors at PNNL are John Feo and S M Ferdous. Hao Lu and Naw Safrin Sattar from Oak Ridge National Laboratory; Anil Vullikanti, Gregor von Laszewski, Dawen Xie, Parantapa Bhattacharya, Henning Mortveit, Mandy L Wilson, and Madhav Marathe from the University of Virginia; Ananth Kalyanaraman from Washington State University, and Michela Becchi from North Carolina State University also contributed to this work. 

This research is based upon work supported by the Department of Energy (DOE) through the Exascale Computing Project and the Office of the Director of National Intelligence (ODNI), Intelligence Advanced Research Projects Activity (IARPA), through the Advanced Graphic Intelligence Logical Computing Environment (AGILE) research program. This work was also supported by Laboratory Directed Research and Development funds at PNNL. In addition, this work was supported in part by the following grants: University of Virginia Strategic Investment Fund, National Science Foundation Grants, US Centers for Disease Control and Prevention and CDC MIND cooperative.