Inhibiting diffusion of complex contagions in social networks: theoretical and experimental results

Data Mining and Knowledge Discovery
Chris J KuhlmanDaniel J Rosenkrantz

Abstract

We consider the problem of inhibiting undesirable contagions (e.g. rumors, spread of mob behavior) in social networks. Much of the work in this context has been carried out under the 1-threshold model, where diffusion occurs when a node has just one neighbor with the contagion. We study the problem of inhibiting more complex contagions in social networks where nodes may have thresholds larger than 1. The goal is to minimize the propagation of the contagion by removing a small number of nodes (called critical nodes) from the network. We study several versions of this problem and prove that, in general, they cannot even be efficiently approximated to within any factor ρ ≥ 1, unless P = NP. We develop efficient and practical heuristics for these problems and carry out an experimental study of their performance on three well known social networks, namely epinions, wikipedia and slashdot. Our results show that these heuristics perform significantly better than five other known methods. We also establish an efficiently computable upper bound on the number of nodes to which a contagion can spread and evaluate this bound on many real and synthetic networks.

References

Mar 19, 1999·Der Urologe. Ausg. A·L E MatterT Sulser
Oct 16, 1999·Science·A L Barabasi, R Albert
Aug 10, 2000·Nature·R AlbertA L Barabasi
Apr 6, 2001·Physical Review Letters·R Pastor-Satorras, A Vespignani
Jun 13, 2002·Physical Review. E, Statistical, Nonlinear, and Soft Matter Physics·Zoltán Dezso, Albert-László Barabási
Aug 9, 2003·Physical Review Letters·Mauro Mobilia
Oct 4, 2003·Physical Review. E, Statistical, Nonlinear, and Soft Matter Physics·M E J Newman, Juyong Park
Dec 14, 2004·Journal of Theoretical Biology·P S Dodds, D J Watts
Aug 5, 2005·Science·Ira M LonginiM Elizabeth Halloran
Apr 1, 2006·Proceedings of the National Academy of Sciences of the United States of America·Duncan J Watts
Apr 14, 2010·PLoS Computational Biology·Marcel Salathé, James H Jones
May 13, 2011·Nature·Yang-Yu LiuAlbert-László Barabási
Feb 23, 2012·Scientific Reports·Sandra González-BailónYamir Moreno
Apr 5, 2012·Proceedings of the National Academy of Sciences of the United States of America·Johan UganderJon Kleinberg
Jul 20, 2012·BMC Systems Biology·Gonzalo MartínJesús Carretero
Apr 6, 2013·Chaos·Sergey MelnikMason A Porter

❮ Previous
Next ❯

Citations

Oct 28, 2014·ACM Transactions on Modeling and Computer Simulation : a Publication of the Association for Computing Machinery·Keith R BissetMadhav V Marathe
Dec 7, 2018·Journal of Medical Systems·Inna Skarga-BandurovaMaksym Nesterov
Jul 22, 2021·Nature Communications·Douglas Guilbeault, Damon Centola

❮ Previous
Next ❯

Related Concepts

Trending Feeds

COVID-19

Coronaviruses encompass a large family of viruses that cause the common cold as well as more serious diseases, such as the ongoing outbreak of coronavirus disease 2019 (COVID-19; formally known as 2019-nCoV). Coronaviruses can spread from animals to humans; symptoms include fever, cough, shortness of breath, and breathing difficulties; in more severe cases, infection can lead to death. This feed covers recent research on COVID-19.

Blastomycosis

Blastomycosis fungal infections spread through inhaling Blastomyces dermatitidis spores. Discover the latest research on blastomycosis fungal infections here.

Nuclear Pore Complex in ALS/FTD

Alterations in nucleocytoplasmic transport, controlled by the nuclear pore complex, may be involved in the pathomechanism underlying multiple neurodegenerative diseases including Amyotrophic Lateral Sclerosis and Frontotemporal Dementia. Here is the latest research on the nuclear pore complex in ALS and FTD.

Applications of Molecular Barcoding

The concept of molecular barcoding is that each original DNA or RNA molecule is attached to a unique sequence barcode. Sequence reads having different barcodes represent different original molecules, while sequence reads having the same barcode are results of PCR duplication from one original molecule. Discover the latest research on molecular barcoding here.

Chronic Fatigue Syndrome

Chronic fatigue syndrome is a disease characterized by unexplained disabling fatigue; the pathology of which is incompletely understood. Discover the latest research on chronic fatigue syndrome here.

Evolution of Pluripotency

Pluripotency refers to the ability of a cell to develop into three primary germ cell layers of the embryo. This feed focuses on the mechanisms that underlie the evolution of pluripotency. Here is the latest research.

Position Effect Variegation

Position Effect Variagation occurs when a gene is inactivated due to its positioning near heterochromatic regions within a chromosome. Discover the latest research on Position Effect Variagation here.

STING Receptor Agonists

Stimulator of IFN genes (STING) are a group of transmembrane proteins that are involved in the induction of type I interferon that is important in the innate immune response. The stimulation of STING has been an active area of research in the treatment of cancer and infectious diseases. Here is the latest research on STING receptor agonists.

Microbicide

Microbicides are products that can be applied to vaginal or rectal mucosal surfaces with the goal of preventing, or at least significantly reducing, the transmission of sexually transmitted infections. Here is the latest research on microbicides.

Related Papers

Physical Review. E, Statistical, Nonlinear, and Soft Matter Physics
Osman Yağan, Virgil Gligor
Physical Review. E, Statistical, Nonlinear, and Soft Matter Physics
Emanuele CozzoYamir Moreno
Physical Review. E, Statistical, Nonlinear, and Soft Matter Physics
Javier Borge-Holthoefer, Yamir Moreno
© 2022 Meta ULC. All rights reserved