Finding Critical Nodes for Inhibiting Diffusion of Complex Contagions in Social Networks
Abstract
We study the problem of inhibiting diffusion of complex contagions such as rumors, undesirable fads and mob behavior in social networks by removing a small number of nodes (called critical nodes ) from the network. We show that, in general, for any ρ ≥ 1, even obtaining a ρ -approximate solution to these problems is NP -hard. We develop efficient heuristics for these problems and carry out an empirical study of their performance on three well known social networks, namely epinions , wikipedia and slashdot . Our results show that the heuristics perform well on the three social networks.
Cite
Text
Kuhlman et al. "Finding Critical Nodes for Inhibiting Diffusion of Complex Contagions in Social Networks." European Conference on Machine Learning and Principles and Practice of Knowledge Discovery in Databases, 2010. doi:10.1007/978-3-642-15883-4_8Markdown
[Kuhlman et al. "Finding Critical Nodes for Inhibiting Diffusion of Complex Contagions in Social Networks." European Conference on Machine Learning and Principles and Practice of Knowledge Discovery in Databases, 2010.](https://mlanthology.org/ecmlpkdd/2010/kuhlman2010ecmlpkdd-finding/) doi:10.1007/978-3-642-15883-4_8BibTeX
@inproceedings{kuhlman2010ecmlpkdd-finding,
title = {{Finding Critical Nodes for Inhibiting Diffusion of Complex Contagions in Social Networks}},
author = {Kuhlman, Chris J. and Kumar, V. S. Anil and Marathe, Madhav V. and Ravi, S. S. and Rosenkrantz, Daniel J.},
booktitle = {European Conference on Machine Learning and Principles and Practice of Knowledge Discovery in Databases},
year = {2010},
pages = {111-127},
doi = {10.1007/978-3-642-15883-4_8},
url = {https://mlanthology.org/ecmlpkdd/2010/kuhlman2010ecmlpkdd-finding/}
}