# Network GeomEtry

## Workshop

### Queen Mary University of London

### 16 July 2015

The rational for this workshop comes from bringing together the Complex Network Community with the Quantum Gravity Community to discuss the common mathematical questions regarding the geometrical description of networks.

Recently, in the network science community the interest in the geometrical characterization of real network datasets has been growing. This problem has indeed many applications related to routing problems in the Internet, data mining, and community detection. Moreover, complex networks like the Internet can have a non-trivial hidden hyperbolic metric that affects the navigability of the network.

In quantum gravity space-time itself is quantized. In various approaches it is described by networks, or by simplicial complexes. In the different approaches to quantum gravity, including causal dynamical triangulations, causal sets, spin networks and loop quantum gravity, space-time is an emergent property of a network. A fundamental question relates to the possibility to perform a continuous limit of these discrete metric spaces where the tools of Riemanian geometry can be applied.

At the heart of both Complex networks and Quantum Gravity are fundamental questions about the Geometry of Networks. In pure mathematics the characterization of the geometry of networks is also a very active field.

In the proposed workshop we aim to stimulate diffusion of knowledge between these different fields of physics and applied mathematics, bringing together key players in the field.

The workshop is sponsored by the School of Mathematics of Queen Mary University of London.

The registration is free and there is a call for abstracts for contributed talks with deadline the 15th June 2015.

The deadline for submission of contributed talks is the 15th June 2015.

The attendance of the workshop is free but registration is necessary.

Please send an email with your name and affiliation for the registration,

including also an abstract for the selection of contributed talks, to the

email address network.geometry (at) gmail.com

8:45-9:00 WELCOME

9:00-9:30 Marian Boguna *Toward a cosmological theory of complex networks*

9:30-10:00 Tomaso Aste *Complex hyperbolic networks from surface triangulations*

10:00-10:30 Fay Dowker * Causal Sets, Discrete Spacetime*

10:30-11:00 Tim Evans *Temporal Vertex Networks*

11:00-11:30 COFFEE BREAK

11:30-12:00 Dima Krioukov *Emergence of Geometry from Discrete Random Structures*

12:00-12:30 Mason A. Porter *Networks in Space: Granular Force Networks and Beyond*

12:30-13:00 Francesco Vaccarino *Tamarkin-Tsygan calculus and Batalin-Vilkovisky structures from weighted graph*

13:00-14:00 LUNCH

14:00-14:30 Shahn Majid * Quantum Riemannian geometry of graphs*

14:30-15:00 Carlo Trugenberger *Emergent 4D Quantum Geometry from Critical Space-Time Graphs*

15:00-15:30 Astrid Eichhorn *Probing quantum geometry*

15:30-15:50 Alessandro Codello *Random Topology*

15:50-16:10 Francesco Caravelli *Quantum graphs: lessons learned*

16:10-16:30 COFFEE BREAK

16:30-17:00 Simone Severini *On graphs and quanta*

17:00-17:30 Heather Harrington *Algebraic geometry applied to chemical reaction networks*

17:30-18:00 Ruben Sanchez-Garcia *Topology and geometry of networks via the higher-order combinatorial Laplacian *

18:00-18:20 Dane Taylor *Topological data analysis of contagion maps for examining *

* spreading processes on networks*

Marian Boguna (Universitat de Barcelona,ES)

*Toward a cosmological theory of complex networks*

Structural and dynamical similarities of different real networks suggest that some universal laws might accurately describe the dynamics of these networks, albeit the nature and common origin of such laws remain elusive. Here we show that causal network representing the large-scale structure of spacetime in our accelerating universe is a power-law graph with strong clustering, similar to many complex networks such as the Internet, social or biological networks. We prove that this strcutural similarity is a consequence of the asymptotic equivalence between the large-scale growth dynamics of complex networks and causal networks. This equivalence suggests that unexpectedly similar laws govern the dynamics of complex networks and spacetime in the universe, with implications to network science and cosmology. However, our simple frameworks is unable to explain the emergence of community structure, a property that, along with scale-free degree distributions and strong clustering, is commonly found in real complex networks. Here we show how latent network geometry coupled with preferential attachment of the nodes to this geometry fills this gap. We call this mechanism geometric preferential attachment (GPA) and validate it against the Internet. GPA gives rise to soft communities that provide a different perspective on the community structure in networks. The connections between GPA and cosmological models, including inflation, are also discussed.

Tomaso Aste & Tiziana Di Matteo (University College London & King's College London UK)

*Complex hyperbolic networks from surface triangulations*

We introduce a novel way to geometrically embed networks on hyperbolic manifolds. We show that graphs embedded on surfaces are powerful and practical tools to generate, characterize, and simulate complex networks. Any network can be embedded on a surface with sufficiently high genus and therefore the study of topologically embedded graphs is non-restrictive. We show that local properties of the network are affected by the surface genus which determines the average degree, it influences the degree distribution and it controls the clustering coefficient. The global properties of the graph are also strongly affected by the surface genus which is constraining the degree of interwovenness, changing the scaling properties of the network from large-world kind (small genus) to small- and ultrasmall-world kind (large genus). Two elementary moves allow the exploration of all networks embeddable on a given surface and naturally introduce a tool to develop a statistical mechanics description for these networks. Within such a framework, we study the properties of topologically embedded graphs which dynamically tend to lower their energy towards a ground state with a given reference degree distribution. We show that the cooling dynamics between high and low “temperatures” is strongly affected by the surface genus with the manifestation of a transition to a slow dynamics toward equilibrium occurring when the distance from the reference distribution is small. We prove, with examples, that topologically embedded graphs can be built in a way to contain arbitrary complex networks as subgraphs.

References:

Tomaso Aste, Ruggero Gramatica, and T. Di Matteo. "Exploring complex networks via topological embedding on surfaces." Physical Review E 86.3 (2012): 036109.

T. Aste, T. Di Matteo, and S. T. Hyde. "Complex networks on hyperbolic surfaces." Physica A: Statistical Mechanics and its Applications 346.1 (2005): 20-26.

Fay Dowker (Imperial College, UK)

*Causal Sets, Discrete Spacetime *

Riemann anticipated that a ``discrete manifold’’ can carry its own metrical information within itself by means of the counting measure. Riemann’s insight has been given concrete expression in more recent times by the concept of a causal set — a transitive directed acyclic graph. Proposed independently by ‘tHooft, Myrheim, and by Bombelli, Lee, Meyer and Sorkin,as the deep structure of spacetime, the relationship between a causal set and an approximating continuum spacetime geometry is *statistical* in nature. I will explain this and explain why causal sets must have very high valence and why the natural causal set analogue of the Erdos-Renyi random graph is of interest for theories of discrete spacetime.

Tim Evans (Imperial College, UK)

*Temporal Vertex Networks*

How should the constraint of time change the way we analyse networks? I will look at how to take account of causality in the tools we use for network analysis. I will consider the example of temporal vertex networks such as simple Minkowskii space models, cube box space models, and citation networks.

I will consider how we can adapt measures of centrality such as degree and betweenness for such networks. I will also discuss effective measures of dimension in these cases.

Dmitri Krioukov (Northeastern University, USA)

*Emergence of Geometry from Discrete Random Structures *

In as diverse fields as network science, quantum gravity, and random graph theory, the problem of "emergent geometry" has attracted significant research attention over the last decades. In general terms, one is usually interested if a particular model or ensemble of random structures (graphs, simplicial complexes, or other discrete objects) without any "hidden geometric variables" is capable of explaining the "emergence of geometry" in some "large N" limit, the usual motivation being the belief that these discrete objects are "more fundamental", while (smooth) geometry is an artifact emerging in the continuum limit. However this high-level problem is often formulated quite differently when one attempts to put it in precise terms, so that it is often unclear what the problem really is, and what results would constitute its successful solution. The talk reviews a formulation of this problem in precise terms that is arguably exact in the sense that solving this problem in this formulation is both necessary and sufficient for proving "geometry emergence". Two simplest Riemannian and Lorentzian examples of this precise problem formulation (not solution!) are discussed for illustration purposes: random geometric graphs on the real line, and causal sets in two-dimensional de Sitter space.

Mason A. Porter (Oxford university,UK)

*Networks in Space: Granular Force Networks and Beyond*

I will describe granular force networks, which are heavily influenced by the spatial structure of granular materials. I will examine them using community structure and discuss the incorporation of spatial information into null models for community detection. I will also briefly discuss the use of random geometric graphs for the study of granular force networks, other approaches to analyzing such systems, and applications of spatial null models to other situations.

Francesco Vaccarino (Politecnico di Torino & ISI Foundation, IT)

*Tamarkin-Tsygan calculus and Batalin-Vilkovisky structures from weighted graph*

Multivector fields on a smooth manifold form a Gerstenhaber algebra with respect to wedge product and Schouten-Nijenhuis bracket. This kind of structure arise naturally within the framework of topological field theory and, in particular, of BF theories. Differential forms constitute what is called a Batalin-Vilkovisky module over this Gerstenhaber algebra. This datum form what is called a non commutative differential calculus after Nest, Tamarkin and Tsygan.

In this talk we will show, via filtrations on weighted graph, how to determine a Tamarkin-Tysgan calculus via Hochschild (co-)homology and the cohomolgy of sheaves of associative algebras as developed by Gerstenhaber. In particular we will show the key role played by quasi-symmetric algebras.

Relations with persistent cohomology will be showed too.

Shahn Majid (Queen Mary University of London, UK)

*Quantum Riemannian geometry of graphs*

We will outline a general formulation of noncommutative Riemannian geometry which on the one hand has a classical limit as ordinary Riemannian geometry and which on the other hand applies to graphs. The arrows of the graph determine the 1-forms in the geometry while a metric consists of weights attached to arrows. If time, I will give the concrete example of a square with symmetric edge weights.

Carlo Trugenberger (Swissscientific, CH)

*Emergent 4D Quantum Geometry from Critical Space-Time Graphs*

I propose a quantum gravity model in which the fundamental degrees of freedom are information bits for both discrete space-time points and links connecting them. The Hamiltonian is a very simple dynamical network model consisting of a ferromagnetic Ising model for space-time vertices and an antiferromagnetic Ising model for the links. As a result of the frustration between these two terms, the ground state self-organizes as a new type of low-clustering graph with finite Hausdorff dimension d_H= 4. I present strong evidence that the model has two quantum phase transitions, a geometrical critical point with disorder parameter (d_H-d_s) (with d_s the spectral dimension) where a continuum 4D random geometry can be defined and an UV fixed point where space-time dissolves into disordered information bits. In this model, the large-scale dimension 4 of the universe is related to the upper critical dimension 4 of the Ising model. At finite temperatures the discrete “universe graph” emerges without big bang and singularities from a ferromagnetic phase transition in which space-time itself forms out of a hot soup of information bits. When the temperature is lowered, the “universe graph” unfolds and expands by lowering its connectivity, a mechanism I have called topological expansion. The model admits also “topological black hole” excitations corresponding to graphs containing holes with no space-time inside and with ``Schwarzschild-like" horizons with a lower spectral dimension.

Astrid Eichhorn (Imperial College, UK)

*Probing quantum geometry*

Fictitious diffusion processes can be used as probes of quantum spacetimes. I will discuss candidate diffusion equations for different models of quantum spacetime, as well as numerical simulations of diffusion processes. A scale-dependent change of dimensionality emerges in this way as a universal property of quantum spacetimes.

Alessandro Codello (CP3-Origins SDU Odense DK)

*Random Topology*

Two dimensional (topological) manifolds without boundaries are classified by their Euler characteristic (number of holes) and orientation. We propose a simple model of random topology and present its numerical analysis. Finally, we comment on connections with random graphs and two dimensional quantum gravity.

Francesco Caravelli (University College London, UK)

*Quantum graphs: lessons learned*

Quantum graph models are playground for exploring the phenomenology of quantum, relational models for quantum gravity.We will discuss the framework, the pro and the cons of such an approach, the emergence of symmetries and geometry,and relate them to other models of quantum gravity based on graphs.

Simone Severini (University College London, UK)

*On graphs and quanta*

I will talk about various ways to associate a graph to a quantum mechanical state or a quantum operation. This is an old story but still a good excuse to use quantum theory to play with graphs and graphs to play with quantum theory.

Ruben Sanchez-Garcia (Southampton University, UK)

*Topology and geometry of networks via the higher-order combinatorial Laplacian *

The network modelling approach is intrinsically constrained by the fact that it can only account for pairwise (binary) interactions. A natural extension consists on using topological complexes, such as simplicial complexes. These combinatorial structures generalise networks to higher dimensions and, indeed, many of the standard analytical tools in network theory apply to complexes. One important example is the graph Laplacian, which is the 0-dimensional instance of higher-dimensional combinatorial Laplacian operators on weighted simplicial complexes. By a classical result of Hodge theory, the kernel of this linear operator is a topological invariant of the undelying complex (its real homology), while the non-zero spectrum capture the geometry in some abstract sense. In this talk I will give an overview of recent developments in the subject and possible future directions.

Heather Harrington (Oxford University, UK)

*Algebraic geometry applies to chemical reaction networks*

A key problem in evaluating mathematical models, such as those arising from chemical reaction networks, against experimental data is determining the model parameters that best fit the data. This task is central to many algorithms for model selection, but it can be extremely difficult, in general to find the "globally" best fit. We present a method to find the global optima when the models are defined by polynomials (such as those arising from biological reaction networks) using *numerical algebraic geometry*, as suite of techniques for efficiently computing the roots of polynomial systems. Our approach guarantees a solution to the global optimization problem and allows for rigorous statistical inference based on the maximum likelihood. We apply our geometric approach to chemical reaction networks arising in systems medicine and synthetic biology.

Dane Taylor (University of North Carolina, USA)

*Topological data analysis of contagion maps for examining spreading processes on networks*

Social and biological contagions are influenced by the spatial embeddedness of networks, and many historical epidemics spread as a wave across part of the Earth’s surface. In modern contagions, however, long-range edges (for example, due to airline transportation or communication media) allow clusters of a contagion to appear in distant locations. Here we study the spread of contagions on networks through a methodology grounded in topological data analysis and nonlinear dimension reduction. We construct “contagion maps” that use multiple contagions on a network to map the nodes as a point cloud. By analyzing the topology,geometry, and dimensionality of the manifold structure in such point clouds, we reveal insights to aid in the modeling, forecast, and control of spreading processes. Our approach highlights contagion maps also as a viable tool for inferring low-dimensional structure in networks.