Anzeige
Erschienen in:
2016 | OriginalPaper | Buchkapitel
Complex Contagions on Configuration Model Graphs with a Power-Law Degree Distribution
verfasst von : Grant Schoenebeck, Fang-Yi Yu
Erschienen in: Web and Internet Economics
Verlag: Springer Berlin Heidelberg
Aktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.
Wählen Sie Textabschnitte aus um mit Künstlicher Intelligenz passenden Patente zu finden. powered by
Markieren Sie Textabschnitte, um KI-gestützt weitere passende Inhalte zu finden. powered by
Abstract
In this paper we analyze k-complex contagions (sometimes called bootstrap percolation) on configuration model graphs with a power-law distribution. Our main result is that if the power-law exponent \(\alpha \in (2, 3)\), then with high probability, the single seed of the highest degree node will infect a constant fraction of the graph within time \(O\left( \log ^{\frac{\alpha -2}{3-\alpha }}(n)\right) \). This complements the prior work which shows that for \(\alpha > 3\) boot strap percolation does not spread to a constant fraction of the graph unless a constant fraction of nodes are initially infected. This also establishes a threshold at \(\alpha = 3\).
The case where \(\alpha \in (2, 3)\) is especially interesting because it captures the exponent parameters often observed in social networks (with approximate power-law degree distribution). Thus, such networks will spread complex contagions even lacking any other structures.
We additionally show that our theorem implies that \(\omega (\left( n^{\frac{\alpha -2}{\alpha -1}}\right) \) random seeds will infect a constant fraction of the graph within time \(O\left( \log ^{\frac{\alpha -2}{3-\alpha }}(n)\right) \) with high probability. This complements prior work which shows that \(o\left( n^{\frac{\alpha -2}{\alpha -1}}\right) \) random seeds will have no effect with high probability, and this also establishes a threshold at \(n^{\frac{\alpha -2}{\alpha -1}}\).