Joost Jorritsma (Eindhoven University of Technology)

Typical weighted distance in preferential attachment models – Interpolating small and mini worlds

Information diffusion in networks can be modeled by first passage percolation, which can also be seen as an SI (susceptible – infected) model.

In this talk I will discuss the model for two (non-spatial) preferential attachment models where the degrees follow a power law with parameter in (2, 3):

once a preferential attachment graph on N vertices is created, we equip every edge with an i.i.d. non-negative weight from distribution L.

In this edge-weighted graph, we find for any weight distribution the precise asymptotic behavior of the weighted distance between two vertices picked uniformly at random from the graph.

We show that by tuning the weight distribution, the growth terms can match any arbitrary function that is O(log log(N)), while the network size N tends to infinity.

Surprisingly, this includes constant order for a large class of weight distributions (including e.g. exponential), in which case we identify the distributional limit.
(joint work with Julia Komjathy)