  Influence maximization aims to select k most-influential vertices or seeds in
a network, where influence is defined by a given diffusion process. Although
computing optimal seed set is NP-Hard, 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 (Influence Maximization via Martingales) algorithm over large
real-world social networks. We present a memory-efficient optimization approach
(called HBMax) based on Ripples, a state-of-the-art multi-threaded parallel
influence maximization solution. Our approach, HBMax, 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 or bitmap coding, and queries on
the partially decoded data, or directly on the compressed data to preserve the
memory savings obtained through compression. Considering a NUMA architecture,
we scale up our solution on 64 CPU cores and reduce the memory footprint by up
to 82.1% with average 6.3% speedup (encoding overhead is offset by performance
gain from memory reduction) without loss of accuracy. For the largest tested
graph Twitter7 (with 1.4 billion edges), HBMax achieves 5.9X compression ratio
and 2.2X speedup.
