Competing first passage percolation on random regular graphs

DOI10.1002/RSA.20699MaRDI QIDQ4978430zbMATH OpenOpenAlexFDO

Authors Tonci Antunovic, Yael Dekel, Elchanan Mossel, Yuval Peres

Publication date 10 August 2017

Published in Random Structures \& Algorithms (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1109.2575

zbMATH Keywords

coupling methodgrowth processsocial networkssubmodularityviral marketing

Mathematics Subject Classification ID

Random graphs (graph-theoretic aspects) (05C80) Graph algorithms (graph-theoretic aspects) (05C85) Interacting random processes; statistical mechanics type models; percolation theory (60K35) Auctions, bargaining, bidding and selling, and other market models (91B26) Social networks; opinion dynamics (91D30)

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 $Theta(1)N^{a}lpha$ vertices, for some $0<alpha<1$. The value of $alpha$ 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.

Recommendations

• Competing first passage percolation on random graphs with finite variance degrees
• First-passage percolation on the random graph
• Coexistence of competing first passage percolation on hyperbolic graphs
• First passage percolation on inhomogeneous random graphs
• First passage percolation on the Erdős-Rényi random graph
• First passage percolation on random graphs with finite mean degrees
• Percolation and first-passage percolation on oriented graphs
• First passage percolation on sparse random graphs with boundary weights
• First-passage percolation on Cartesian power graphs

Cites work

• A model for spatial conflict
• A probabilistic proof of an asymptotic formula for the number of labelled regular graphs
• Absence of mutual unbounded growth for almost all parameter values in the two-type Richardson model.
• Coexistence for Richardson type competing spatial growth models
• Coexistence in two-type first-passage percolation models
• Ergodic theorems for weakly interacting infinite systems and the voter model
• Extreme value theory, Poisson-Dirichlet distributions, and first passage percolation on random networks
• Finite particle systems and infection models
• First passage percolation on locally treelike networks. I. Dense random graphs
• First passage percolation on random graphs with finite mean degrees
• First passage percolation on the Erdős-Rényi random graph
• First-passage competition with different speeds: positive density for both species is impossible
• Geodesics in first passage percolation
• scientific article; zbMATH DE number 193169 (Why is no real title available?)
• scientific article; zbMATH DE number 3463051 (Why is no real title available?)
• Limit theorems for triangular urn schemes
• Markov Chains
• Nonmonotonic coexistence regions for the two-type Richardson model on graphs
• On tail probabilities for martingales
• On the spread of viruses on the Internet
• One, Two and Three Times log n/n for Paths in a Complete Graph with Random Weights
• Some limit theorems for percolation processes with necessary and sufficient conditions
• Submodularity of influence in social networks: from local to global
• The basic contact processes
• The flooding time in random graphs
• The Initial Configuration is Irrelevant for the Possibility of Mutual Unbounded Growth in the Two-Type Richardson Model
• The two-type Richardson model with unbounded initial configurations
• Time-Dependent Statistics of the Ising Model
• Two phase transitions for the contact process on small worlds

Cited in

(12)

• Formation of large-scale random structure by competitive erosion
• Long paths in first passage percolation on the complete graph II. Global branching dynamics
• First passage percolation on the Newman-Watts small world model
• Joint distribution of distances in large random regular networks
• The winner takes it all
• First passage percolation and a model for competing spatial growth
• Competition in growth and urns
• Competing first passage percolation on random graphs with finite variance degrees
• Coexistence in preferential attachment networks
• The winner takes it all but one
• Voronoi cells in random split trees
• Universal `winner-takes-it-all' phenomenon in scale-free random graphs

This page was built for publication: Competing first passage percolation on random regular graphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4978430)