Mittagsseminar (in cooperation with J. Lengler, A. Steger, and D. Steurer)

Date and Time: Thursday, May 09, 2019, 12:15 pm

Duration: 30 minutes

Location: OAT S15/S16/S17

Speaker: Johannes Lengler

Weighted Percolation on Geometric Inhomogeneous Random Graphs

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.

Upcoming talks     |     All previous talks     |     Talks by speaker     |     Upcoming talks in iCal format (beta version!)

Previous talks by year:   2025  2024  2023  2022  2021  2020  2019  2018  2017  2016  2015  2014  2013  2012  2011  2010  2009  2008  2007  2006  2005  2004  2003  2002  2001  2000  1999  1998  1997  1996  

Information for students and suggested topics for student talks

Automatic MiSe System Software Version 1.4803M   |   admin login