PNNL

Abstract

The goal of influence maximization is to select k most-influential vertices or seeds in a network, where influence is defined by a given diffusion process. The problem has a number of important applications such as viral marketing, information spread, and epidemic control. Although computing optimal seed set is NP-Hard, due to the submodular nature of the problem efficient approximation algorithms exist. However, even state-of-the-art parallel implementations are limited by a sampling step that incurs large memory footprints. This in turn limits the problem size reach and approximation quality. In this work, we study the memory footprint of the sampling process collecting reverse reachability information in the IMM algorithm over large real-world social networks. We present an adaptive and memory-efficient optimization approach for a state-of-the-art multi-threaded parallel influence maximization algorithm. Our approach,HuffMax, uses a portion of the reverse reachable (RR) sets collected by the algorithm to learn the characteristics of the graph. Then, it compresses the intermediate reverse reachability information with Huffman coding, and queries directly on the compressed data to preserve the memory savings obtained through compression. We also propose an efficient sampling strategy based on the distribution of RR sets, which can further reduce the computation time for typical social networks with long-tail distributions. Considering a NUMA architecture, we scale up our solution on 128-core CPUs and reduce the memory footprint by up to 45.7% with negligible time overhead (or even faster) and without perceivable loss of accuracy.