Premium
Competing first passage percolation on random graphs with finite variance degrees
Author(s) -
Ahlberg Daniel,
Deijfen Maria,
Janson Svante
Publication year - 2019
Publication title -
random structures and algorithms
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 1.314
H-Index - 69
eISSN - 1098-2418
pISSN - 1042-9832
DOI - 10.1002/rsa.20846
Subject(s) - combinatorics , mathematics , vertex (graph theory) , random graph , distance , random regular graph , discrete mathematics , type (biology) , degree (music) , graph , chordal graph , 1 planar graph , physics , ecology , shortest path problem , acoustics , biology
We study the growth of two competing infection types on graphs generated by the configuration model with a given degree sequence. Starting from two vertices chosen uniformly at random, the infection types spread via the edges in the graph in that an uninfected vertex becomes type 1 (2) infected at rate λ 1 ( λ 2 ) times the number of nearest neighbors of type 1 (2). Assuming (essentially) that the degree of a randomly chosen vertex has finite second moment, we show that if λ 1 = λ 2 , then the fraction of vertices that are ultimately infected by type 1 converges to a continuous random variable V ∈ (0,1), as the number of vertices tends to infinity. Both infection types hence occupy a positive (random) fraction of the vertices. If λ 1 ≠ λ 2 , on the other hand, then the type with the larger intensity occupies all but a vanishing fraction of the vertices. Our results apply also to a uniformly chosen simple graph with the given degree sequence.