New Seeding Strategies for the Influence Maximization Problem

We present two new seeding strategies for the Influence Maximization Problem for Viral Marketing, based on graph connectivity and spectral graph theory. Specifically, the first approach CVSP uses the cut vertices and the separation pairs as the starting seeds. The second approach ER uses the vertex ranking based on the effective resistance values of the incident edges. CVSP and ER are efficient, and can be implemented in linear and near linear time, respectively. Experiments using the Independent Cascade diffusion model with real-world data sets show that our new seeding strategies perform significantly better than the existing methods, such as centrality measures, k-core and the state-of-the-art IMM, in particular for the scale-free networks with globally sparse, locally dense clusters with small diameters, in the final influence spread. Moreover, visual analysis enables more refined comparison between the methods, demonstrating that our methods have more globally wide influence spread pattern than other methods with locally dense influence spread pattern.