Competing first passage percolation on random regular graphs1. Issue 4 (27th December 2016)

• Record Type: Journal Article
• Authors: Antunović, Tonći; Dekel, Yael; Mossel, Elchanan; Peres, Yuval
• Is Part Of: Random structures & algorithms. Volume 50:Issue 4(2017)
• Page Start: 534
• Page End: 583
• Publication Date: 2016-12-27
• Subjects: growth process -- coupling method -- submodularity -- social networks -- viral marketing; Random graphs -- Periodicals; Mathematical analysis -- Periodicals; 519
• DOI: 10.1002/rsa.20699
• Languages: English
• ISSNs: 1042-9832

Abstract

Abstract: We consider two competing first passage percolation processes started from uniformly chosen subsets of a random regular graph on N vertices. The processes are allowed to spread with different rates, start from vertex subsets of different sizes or at different times. We obtain tight results regarding the sizes of the vertex sets occupied by each process, showing that in the generic situation one process will occupy Θ ( 1 ) N α vertices, for some 0 < α < 1 . The value of α is calculated in terms of the relative rates of the processes, as well as the sizes of the initial vertex sets and the possible time advantage of one process. The motivation for this work comes from the study of viral marketing on social networks. The described processes can be viewed as two competing products spreading through a social network (random regular graph). Considering the processes which grow at different rates (corresponding to different attraction levels of the two products) or starting at different times (the first to market advantage) allows to model aspects of real competition. The results obtained can be interpreted as one of the two products taking the lion share of the market. We compare these results to the same process run on d dimensional grids where we show that in the generic situation the two products will have a linear fraction of the market each. © 2016 Wiley Periodicals, Inc. Random Struct. Alg., 50, 534–583, 2017