ML Anthology

On Approximation of Real-World Influence Spread

Yu Yang, Enhong Chen, Qi Liu, Biao Xiang, Tong Xu, Shafqat Ali Shad
ECML-PKDD 2012 pp. 548-564
doi:10.1007/978-3-642-33486-3_35 /ecmlpkdd/2012/yang2012ecmlpkdd-approximation/

Abstract

To find the most influential nodes for viral marketing, several models have been proposed to describe the influence propagation process. Among them, the Independent Cascade (IC) Model is most widely-studied. However, under IC model, computing influence spread (i.e., the expected number of nodes that will be influenced) for each given seed set has been proved to be #P-hard. To that end, in this paper, we propose GS algorithm for quick approximation of influence spread by solving a linear system, based on the fact that propagation probabilities in real-world social networks are usually quite small. Furthermore, for better approximation, we study the structural defect problem existing in networks, and correspondingly, propose enhanced algorithms, GSbyStep and SSSbyStep , by incorporating the Maximum Influence Path heuristic. Our algorithms are evaluated by extensive experiments on four social networks. Experimental results show that our algorithms can get better approximations to the IC model than the state-of-the-arts.

PDF ECML-PKDD Semantic Scholar

Cite

Text

Yang et al. "On Approximation of Real-World Influence Spread." European Conference on Machine Learning and Principles and Practice of Knowledge Discovery in Databases, 2012. doi:10.1007/978-3-642-33486-3_35

Markdown

[Yang et al. "On Approximation of Real-World Influence Spread." European Conference on Machine Learning and Principles and Practice of Knowledge Discovery in Databases, 2012.](https://mlanthology.org/ecmlpkdd/2012/yang2012ecmlpkdd-approximation/) doi:10.1007/978-3-642-33486-3_35

BibTeX

@inproceedings{yang2012ecmlpkdd-approximation,
  title     = {{On Approximation of Real-World Influence Spread}},
  author    = {Yang, Yu and Chen, Enhong and Liu, Qi and Xiang, Biao and Xu, Tong and Shad, Shafqat Ali},
  booktitle = {European Conference on Machine Learning and Principles and Practice of Knowledge Discovery in Databases},
  year      = {2012},
  pages     = {548-564},
  doi       = {10.1007/978-3-642-33486-3_35},
  url       = {https://mlanthology.org/ecmlpkdd/2012/yang2012ecmlpkdd-approximation/}
}