2009 EfficientInfluenceMaximizationi

(Chen et al., 2009) ⇒ Wei Chen, Yajun Wang, and Siyu Yang. (2009). “Efficient Influence Maximization in Social Networks.” In: Proceedings of the 15th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining (KDD-2009). doi:10.1145/1557019.1557047

Subject Headings:

Notes

Categories and Subject Descriptors: F.2.2 Analysis of Algorithms and Problem Complexity: Nonnumerical Algorithms and Problems
General Terms Algorithms:, Experimentation, Performance

Cited By

Quotes

Author Keywords

Social Networks, Influence Maximization, Heuristic Algorithms

Abstract

Influence maximization is the problem of finding a small subset of nodes (seed nodes) in a social network that could maximize the spread of influence. In this paper, we study the efficient influence maximization from two complementary directions. One is to improve the original greedy algorithm of KKT03 and its improvement LKGFVG07 to further reduce its running time, and the second is to propose new degree discount heuristics that improves influence spread. We evaluate our algorithms by experiments on two large academic collaboration graphs obtained from the online archival database arXiv.org. Our experimental results show that (a) our improved greedy algorithm achieves better running time comparing with the improvement of LKGFVG07 with matching influence spread, (b) our degree discount heuristics achieve much better influence spread than classic degree and centrality-based heuristics, and when tuned for a specific influence cascade model, it achieves almost matching influence thread with the greedy algorithm, and more importantly (c) the degree discount heuristics run only in milliseconds while even the improved greedy algorithms run in hours in our experiment graphs with a few tens of thousands of nodes.
Based on our results, we believe that fine-tuned heuristics may provide truly scalable solutions to the influence maximization problem with satisfying influence spread and blazingly fast running time. Therefore, contrary to what implied by the conclusion of KKT03 that traditional heuristics are outperformed by the greedy approximation algorithm, our results shed new lights on the research of heuristic algorithms.

References

,

	Author	volume	Date Value	title	type	journal	titleUrl	doi	note	year
2009 EfficientInfluenceMaximizationi	Siyu Yang Wei Chen Yajun Wang			Efficient Influence Maximization in Social Networks				10.1145/1557019.1557047