Schedule for: 16w5095 - Random Geometric Graphs and Their Applications to Complex Networks

Beginning on Sunday, November 6 and ending Friday November 11, 2016

All times in Banff, Alberta time, MDT (UTC-6).

Sunday, November 6
16:00 - 17:30 Check-in begins at 16:00 on Sunday and is open 24 hours (Front Desk - Professional Development Centre)
17:30 - 19:30 Dinner
A buffet dinner is served daily between 5:30pm and 7:30pm in the Vistas Dining Room, the top floor of the Sally Borden Building.
(Vistas Dining Room)
20:00 - 22:00 Informal gathering (Corbett Hall Lounge (CH 2110))
Monday, November 7
07:00 - 08:45 Breakfast
Breakfast is served daily between 7 and 9am in the Vistas Dining Room, the top floor of the Sally Borden Building.
(Vistas Dining Room)
08:45 - 09:00 Introduction and Welcome by BIRS Station Manager (TCPL 201)
09:00 - 10:00 Mathew Penrose: Random Bipartite geometric graphs (TCPL 201)
10:00 - 10:30 Coffee Break (TCPL Foyer)
10:30 - 11:00 Abbas Mehrabian: Rumour spreading in the spatial preferential attachment model
The Spatial Preferential Attachment model is a spatial random graph used to model social networks. Nodes live in a metric space, and edges are formed based on the metric distance and degree of the nodes. Rumour spreading is a protocol for the spread of information through a graph. In each time step nodes can pass the rumour to only one of their neighbours. The spread time is the expected time when all nodes have the rumour. We analyze rumour spreading on the SPA model, and show that the spread time differs substantially from the diameter. Joint work with Jeannette Janssen.
(TCPL 201)
11:00 - 11:30 Jane Gao: Packing edge-disjoint spanning trees in random geometric graphs (TCPL 201)
11:30 - 13:00 Lunch (Vistas Dining Room)
13:00 - 14:00 Guided Tour of The Banff Centre
Meet in the Corbett Hall Lounge for a guided tour of The Banff Centre campus.
(Corbett Hall Lounge (CH 2110))
14:00 - 14:20 Group Photo
Meet in foyer of TCPL to participate in the BIRS group photo. The photograph will be taken outdoors, so dress appropriately for the weather. Please don't be late, or you might not be in the official group photo!
(TCPL Foyer)
14:20 - 15:00 Problem Session / Progress Report (TCPL 201)
15:00 - 15:30 Coffee Break (TCPL Foyer)
15:30 - 17:30 Hard Work (TCPL 201)
17:30 - 19:30 Dinner
A buffet dinner is served daily between 5:30pm and 7:30pm in the Vistas Dining Room, the top floor of the Sally Borden Building.
(Vistas Dining Room)
Tuesday, November 8
07:00 - 09:00 Breakfast (Vistas Dining Room)
09:00 - 10:00 Dmitri Krioukov: Clustering Implies Geometry in Networks
Two common features of many large real networks are that they are sparse and that they have strong clustering, i.e., large number of triangles homogeneously distributed across all nodes. In many growing real networks for which historical data is available, the average degree and clus- tering are roughly independent of the growing network size. Recently, (soft) random geometric graphs, also known as latent-space network models, with hyperbolic and de Sitter latent geome- tries have been used successfully to model these features of real networks, to predict missing and future links in them, and to study their navigability, with applications ranging from designing optimal routing in the Internet, to identification of the information-transmission skeleton in the human brain. Yet it remains unclear if latent-space models are indeed adequate models of real networks, as random graphs in these models may have structural properties that real networks do not have, or vice versa. We show that the canonical maximum-entropy ensemble of random graphs in which the expected numbers of edges and triangles at every node are fixed to constants, are approximately soft random geometric graphs on the real line. The approximation is exact in the limit of standard random geometric graphs with a sharp connectivity threshold and strongest clustering. This result implies that a large number of triangles homogeneously distributed across all vertices is not only necessary but also a sufficient condition for the presence of a latent/effective metric space in large sparse networks. Strong clustering, ubiquitously observed in real networks, is thus a reflection of their latent geometry.
(TCPL 201)
10:00 - 10:30 Coffee Break (TCPL Foyer)
10:30 - 11:00 Nikolaos Fountoulakis: The emergence of the giant component in random graphs on the hyperbolic plane
We consider a recent model of random geometric graphs on the hyperbolic plane developed by Krioukov et al. (Phys. Rev. E 2010). This may be also viewed as a geometric version of the well- known Chung-Lu model of inhomogeneous random graphs and turns out to have basic properties that are ubiquitous in complex networks. We consider the size of the largest component of this random graph and show that a giant component emerges when the basic parameters of the model cross certain values. We also show that the fraction of vertices that are contained there converges in probability to a certain constant, which is related to a continuum percolation model on the upper-half plane. This is joint work with Tobias Müller and Michel Bode.
(TCPL 201)
11:00 - 11:30 Jeannette Janssen: Recognizing graphs with linear random structure
In many real life applications, network formation can be modelled using a spatial random graph model: vertices are embedded in a metric space S, and pairs of vertices are more likely to be connected if they are closer together in the space. A general geometric graph model that captures this concept is G(n, w), where w : S × S → [0, 1] is a symmetric “link probability” function with the property that, for fixed x ∈ S, w(x, y) decreases as y is moved further away from x. he function w can be seen as the graph limit of the sequence G(n, w) as n → ∞. We consider the question: given a large graph or sequence of graphs, how can we determine if they are likely the results of such a general geometric random graph process? Focusing on the one-dimensional (linear) case where S = [0, 1], we define a graph parameter Γ and use the theory of graph limits to show that this parameter indeed measures the compatibility of the graph with a linear model.
(TCPL 201)
11:30 - 12:00 Yuval Peres: Random Geometric Graphs beyond the Poisson process
Random Geometric graphs have traditionally been considered on the nodes of a Poisson process, but recently there has been enhanced interest in more rigid point processes. We study continuum percolation for the Ginibre ensemble and the planar Gaussian zero process, which are the primary models of translation invariant point processes in the plane exhibiting local repulsion. For the Ginibre ensemble, we establish the uniqueness of infinite cluster in the supercritical phase. For the Gaussian zero process, we establish that a non-trivial critical radius exists, and we prove the uniqueness of the infinite cluster in the supercritical regime. Finding suitable replacements for insertion and deletion tolerance is a crucial step. Joint work with Manju Krishnapur and Subhro Ghosh.
(TCPL 201)
12:00 - 13:30 Lunch (Vistas Dining Room)
13:30 - 15:00 Problem Session / Progress Report (TCPL 201)
15:00 - 15:30 Coffee Break (TCPL Foyer)
15:30 - 17:30 Hard Work (TCPL 201)
17:30 - 19:30 Dinner (Vistas Dining Room)
Wednesday, November 9
07:00 - 09:00 Breakfast (Vistas Dining Room)
09:00 - 10:00 Dieter Mitsche: On the spectral gap of random hyperbolic graphs (TCPL 201)
10:00 - 10:30 Coffee Break (TCPL Foyer)
10:30 - 11:00 Carl Dettmann: Random connection models (TCPL 201)
11:00 - 11:30 Anthony Bonato: Isomorphism results for infinite random geometric graphs (TCPL 201)
11:30 - 12:00 Problem Session / Progress Report (TCPL 201)
12:00 - 13:30 Lunch (Vistas Dining Room)
13:30 - 17:30 Free Afternoon (Banff National Park)
17:30 - 19:30 Dinner (Vistas Dining Room)
Thursday, November 10
07:00 - 09:00 Breakfast (Vistas Dining Room)
09:00 - 10:00 Joseph Yukich: Statistics of random graphs on clustering point sets (TCPL 201)
10:00 - 10:30 Coffee Break (TCPL Foyer)
10:30 - 11:00 Matthias Schulte: Limit theorems for edge length statistics of random geometric graphs (TCPL 201)
11:00 - 11:30 Guillem Perarnau: Random graphs from bridge-addable classes (TCPL 201)
11:30 - 12:00 Ewa Infeld: The Total Acquisition Number of Random Geometric Graphs (TCPL 201)
12:00 - 13:30 Lunch (Vistas Dining Room)
13:30 - 15:00 Problem Session / Progress Report (TCPL 201)
15:00 - 15:30 Coffee Break (TCPL Foyer)
15:30 - 17:30 Hard Work (TCPL 201)
17:30 - 19:30 Dinner (Vistas Dining Room)
Friday, November 11
07:00 - 09:00 Breakfast (Vistas Dining Room)
09:00 - 10:00 Laurent Menard: Percolation by cumulative merging and phase transition for the contact process on random graphs (TCPL 201)
10:00 - 10:30 Coffee Break (TCPL Foyer)
10:30 - 11:00 Guenter Last: Second order properties and asymptotic normality of cluster sizes in the random connection model (TCPL 201)
11:00 - 11:30 Kiril Solovey: Applications of Random Geometric Graphs in Robot Motion Planning (TCPL 201)
11:30 - 12:00 Checkout by Noon
5-day workshop participants are welcome to use BIRS facilities (BIRS Coffee Lounge, TCPL and Reading Room) until 3 pm on Friday, although participants are still required to checkout of the guest rooms by 12 noon.
(Front Desk - Professional Development Centre)
12:00 - 13:30 Lunch from 11:30 to 13:30 (Vistas Dining Room)