Department of Computer Science | Institute of Theoretical Computer Science | CADMO

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.

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

Previous talks by year: 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