Competing first passage percolation on random regular graphs

Details Competing first passage percolation on random regular graphs Competing first passage percolation on random regular graphs

2011-09-12

arxiv.org/abs/1109.2575v1

Mathematics

Probability

42 pages, no figures

Scientific paper

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^alpha 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.

Affiliated with

Also associated with

No associations

Rating

Competing first passage percolation on random regular graphs does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with Competing first passage percolation on random regular graphs, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Competing first passage percolation on random regular graphs will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-60785