Pack and Measure: An Effective Approach for Influence Propagation in Social Networks

Influence Maximization has been widely used to enhance the effectiveness of online marketing campaigns. In this paper, we consider the Influence Maximization problem under the Independent Cascade model (IC). The problem asks for a minimum set of nodes in a network to serve as seed set from which a maximum influence propagation is expected. New seed-set selection methods are introduced based on the notions of a d-packing and node centrality. In particular, we focus on selecting seed-nodes that are far apart and whose estimated influence values are the highest in their local communities. Our best results are achieved via an initial computation of a d-Packing followed by selecting either nodes of high degree or high centrality in their respective closed neighborhoods. This overall “Pack and Measure” approach proves highly effective as a seed selection method. Our results have direct practical implications on conducting an online marketing campaign.