Remco van der Hofstad: Competition on scale-free random graphs

Schedule

14.00-15.00 Pre-colloquium by PhD student Kristoffer Spricer (in room D41)
15:15-16:15 Colloquium lecture by Remco van der Hofstad (D1)
16:15-17:00 SMC social get together with refreshments.

Abstract

Empirical findings have shown that many real-world networks share fascinating features. Indeed, many real-world networks are small worlds, in the sense that distances between most vertices are much smaller than the size of the network. Further, many real-world networks are scale-free in the sense that there is a high variability in the number of connections of the elements of the networks. Thus, these networks are highly inhomogeneous. Such networks are typically modeled using random graphs with power-law degree sequences.

In this lecture, we investigate the behavior of competition processes on scale-free random graphs with finite-mean, but infinite-variance degrees. Take two vertices uniformly at random, or at either side of an edge chosen uniformly at random, and place an individual of two distinct species at these two vertices. Equip the edges with traversal times, which could be different for the two species. Then let each of the two species invade the graph, such that any other vertex can only be occupied by the species that gets there first. Let the speed of the species be the inverse of the expected traversal times of an edge by that species.

We distinguish two cases. When the traversal times have exponential distributions making the invasion processes Markovian, we see that one (yet not necessarily the faster) species will occupy almost all vertices, while the losing species only occupied a bounded number of vertices, i.e., the winner takes it all, the loser's standing small. In particular, no asymptotic coexistence can occur. On the other hand, for deterministic traversal times, the fastest species always gets the majority of the vertices, while the other occupies a subpolynomial number. When the speeds are the same, asymptotic coexistence (in the sense that both species occupy a positive proportion of the vertices) occurs with positive probability. These findings shed light on product innovation and viral marketing.

This lecture is based on joint work with Mia Deijfen, Julia Komjathy and Enrico Baroni, and builds on earlier work with Gerard Hooghiemstra, Shankar Bhamidi and Dmitri Znamenski.