Prof. Emo Welzl and Prof. Bernd Gärtner
|Mittagsseminar Talk Information|
Date and Time: Thursday, May 09, 2019, 12:15 pm
Duration: 30 minutes
Location: CAB G51
Speaker: Johannes Lengler
Geometric Inhomogeneous Random Graphs (GIRGs) are a random graph model that is supposed to capture some properties of social networks, including a power law degree distributions and community structures. These networks are ultra-small worlds, i.e., the average distance in the giant component is O(log log n). If we assign an i.i.d. cost W to each edge (think of a delay for communicating along this edge), then the average cost distance (i.e., the minimal total cost of a connecting path) drops to O(1) unless the distribution of W is doubly exponentially decaying at zero (Komjathy and Lodewijk, 2018).
However, in social networks communication along high-degree vertices is often slower, so together with Komjathy and Lapinskas we studied the scenario where large-degree vertices are penalised by a factor (deg v)^\mu, i.e., an edge u-v has cost (deg u * deg v)^\mu * W, where again all W are drawn i.i.d. In this case we get a much richer behaviour, depending on \mu, the distribution of W, and the model parameters: The number of vertices in cost-distance C may be \Omega(n) ("infinite regime"), or it may grow doubly exponentially in C, or it may grow exponentially in C, or it may grow polynomially in C.
Automatic MiSe System Software Version 1.4803M | admin login