Competing first passage percolation on random graphs with finite variance degrees. Issue 3 (5th March 2019)

• Record Type: Journal Article
• Authors: Ahlberg, Daniel; Deijfen, Maria; Janson, Svante
• Is Part Of: Random structures & algorithms. Volume 55:Issue 3(2019)
• Page Start: 545
• Page End: 559
• Publication Date: 2019-03-05
• Subjects: coexistence -- competing growth -- configuration model -- continuous‐time branching process -- first passage percolation -- random graphs; Random graphs -- Periodicals; Mathematical analysis -- Periodicals; 519
• DOI: 10.1002/rsa.20846
• Languages: English
• ISSNs: 1042-9832

Abstract

Abstract : 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.