Pack and Measure: An Effective Approach for Influence Propagation in Social Networks
This work addresses the problem of optimizing influence spread in social networks for applications like marketing, though it appears incremental as it builds on existing models with a novel method.
The paper tackles the Influence Maximization problem under the Independent Cascade model by introducing a new seed-set selection method called 'Pack and Measure', which uses d-packing and vertex centrality to choose far-apart vertices with high local influence, achieving highly effective results.
The Influence Maximization problem under the Independent Cascade model (IC) is considered. The problem asks for a minimal set of vertices 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 vertex centrality. In particular, we focus on selecting seed-vertices that are far apart and whose 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 vertices 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.