Random graphs with hidden variables is a wide class of network models encompassing many popular graph ensembles, such as classical random graphs, random graphs with given expected degree distributions, or random geometric graphs. In random geometric graphs, hidden variables are coordinates of nodes in a geometric space, and the probability that two nodes are linked is a function of the distance between the nodes in the space. Usually this function is a step function, meaning that a pair of nodes is connected if the distance between them is below a certain threshold. Random geometric graphs can thus be considered as discretizations of smooth geometries---nodes are atoms of spaces, and links reflect proximity between the atoms.
It was recently found that random geometric graphs in non-Euclidean spaces describe well many structural and dynamical properties of many real networks, including the Internet, brain, social networks, and the network representing the global causal structure of spacetime in the universe. Besides immediate practical applications, such as optimal routing in the Internet, this finding opens new ways to analyze networks, recasting some network problems that are intrinsically discrete as potentially more tractable problems formulated in continuous geometries. One example of such problems is network dynamics prediction.
The workshop brings together a small group of invited researchers to discuss their collaborative work-in-progress and future research directions.
Dates: July 29 (Mon) - August 2 (Fri), 2013
Times: 10am - 5pm
Place: University of California San Diego, San Diego Supercomputer Center, West Wing, Room 569
Visitor info: CAIDA, SDSC
Agenda
The general format for the workshop will be morning talks or presentations to set up the mood for the day, followed by discussions in the afternoon. Slides will not be posted online for distribution for this workshop.
July 29 (Monday)
Place: University of California San Diego, San Diego Supercomputer Center, West Wing, Room 569- 10:00 - 12:00 "The Intro Day"
- Dmitri Krioukov, Introduction: glossary of terms
- 12:00 - 14:00 working lunch
- 14:00 - 15:00 External talk
- Jordi Levy, The Nature of Industrial SAT Instances
- 15:00 - 17:00 Discussions
- Introduction part II
- Agenda bashing, summary of themes to discuss
July 30 (Tuesday)
- 10:00 - 12:00 "The Cosmic Day"
- Marian Boguna, Cosmological Networks
- Michel Buck, (Quantum) fields on causal sets
- 12:00 - 14:00 working lunch
- 14:00 - 17:00 Discussions
- David Meyer, Dimension estimation in causal sets
- Pasha Krapivsky, Cancerous spacetime models
- Marian Boguna, David Meyer, David Rideout, Growing causets without explicit geometry
July 31 (Wednesday)
- 10:00 - 12:00 "The Detective Day"
- Ginestra Bianconi, Quantum critical phenomena, multiplex networks, unfreezing hidden variables in ERGs
- David Meyer, David Rideout, Marian Boguna, Number networks
- 12:00 - 14:00 working lunch
- 15:00 - 17:00 Discussions
- Spillover discussions
- Pol Colomer de Simon, David Meyer, David Rideout, Marian Boguna, Dmitri Krioukov, Necessary and sufficient conditions for hidden geometry presence
- Pol Colomer de Simon, Tests to detect geometry in networks
- Pol Colomer de Simon, Dmitri Krioukov, 1KC-randomness conjecture
August 1 (Thursday)
- 10:00 - 12:00 "The Embedding Day"
- Fragkiskos Papadopoulos, Embedding by replaying growth
- Maksim Kitsak, Embedding in higher dimensions
- 12:00 - 14:00 working lunch
- 14:00 - 17:00 Discussions
- Spillover discussions
- Maksim Kitsak, Embedding in higher dimensions
- 19:30 Dinner reception
August 2 (Friday)
- 10:00 - 12:00 "The Dynamic Day"
- Pasha Krapivsky, Highly dispersed networks
- Massimo Ostilli, Fluctuations and ERG in hidden variable models
- Chiara Orsini, dK-series updates
- 12:30 - 14:00 working lunch
- 14:00 - 19:00 Discussions
- Dmitri Krioukov, Marian Boguna, David Meyer, David Rideout, Pol Colomer de Simon, Fragkiskos Papadoupolos, Numbers
- Ginestra Bianconi, Massimo Ostilli, Unfreezing hidden variables in ERGs
- Dmitri Krioukov, Ginestra Bianconi, 1KC-randomness
- Dmitri Krioukov, Fragkiskos Papadoupolos, Maksim Kitsaki, Embedding
- Ginestra Bianconi, Marian Boguna, Multiplexes
- Pol Colomer de Simon, Marian Boguna, Dmitri Krioukov, Pol's (gruesome) future
- Marian Boguna, David Meyer, David Rideout, Dmitri Krioukov, Distance estimation in causal sets
- Dmitri Krioukov, Marian Boguna, Maksim Kitsak, Cosmic police
- 19:00 Adjourn