Date: 02 October 2019
Time: 12:45 - 13:35 (Lunch available from 12:35)
Room: RA 1501 (Ravelijn)
Speaker: Remco van der Hofstad
TITLE:
Competition and rumor spread on scale-free random graphs
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 typical distances 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, making these networks highly inhomogeneous. Such networks are typically modeled using random graphs with power-law degree sequences.
In this lecture, we will 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 types at these two vertices. Equip the edges with traversal times, which could be different for the two types. Then let each of the two types invade the graph, such that any other vertex can only be occupied by the types that gets there first. Let the speed of the types be the inverse of the expected traversal times of an edge by that types.
We distinguish two cases. When the traversal times are exponential, we see that one (not necessarily the faster) types will occupy almost all vertices, while the losing types 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 types 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 types occupy a positive proportion of the vertices) occurs with positive probability.
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.