Paper Info
Title
Complex Contagions on Configuration Model Graphs with a Power-Law Degree Distribution.
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$$α∈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 $$Ologα-23-αn. This complements the prior work which shows that for $$\\alpha > 3$$α>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$$α=3. The case where $$\\alpha \\in 2, 3$$α∈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 $$ωnα-2α-1 random seeds will infect a constant fraction of the graph within time $$O\\left \\log ^{\\frac{\\alpha -2}{3-\\alpha }}n\\right $$Ologα-23-αn with high probability. This complements prior work which shows that $$o\\left n^{\\frac{\\alpha -2}{\\alpha -1}}\\right $$onα-2α-1 random seeds will have no effect with high probability, and this also establishes a threshold at $$n^{\\frac{\\alpha -2}{\\alpha -1}}$$nα-2α-1.
Year
DOI
Venue
2016
10.1007/978-3-662-54110-4_32
WINE
Field
DocType
Citations 
Graph,Combinatorics,Exponent,Power law degree distribution,Bootstrap percolation,Omega,Degree distribution,Preferential attachment,Mathematics
Conference
0
PageRank 
References 
Authors
0.34
9
2
Name
Order
Citations
PageRank
Grant Schoenebeck150939.48
Fang-Yi Yu246.57