1st Period Overview

Overview of the action's implementation for the 1st reporting period

Research in the last 18 months can be grouped into the following main directions: Dynamics on large networks, dynamical growth of physical networks, graph limits, and structural network theory.

Dynamics on large networks:  Network-based modeling of epidemics was one of the topics proposed in our application, and it was natural to focus on this. A cooperation of researchers from the Rényi Institute and CEU, but also involving mathematicians from Lausanne and Eindhoven, we studied the role of the distribution of the initial infection on the severeness of the epidemics. One of the unexpected conclusions is that the relative severeness of infections starting in the central region (core) and in the periphery depends in a non-monotone way on the infection rate: for low infection rates, epidemics starting in the central region is more dangerous, while for higher rates it I the other way around. A report will be finished and submitted in a few weeks.

A very important example of dynamics on network is the working of the nervous system. A first example studied in detail by the CEU group is the genetic blueprint of the C. elegans nervous system. More complex nervous systems, that of animals with brain, lead to the study of physical networks (see below).

Modeling dynamics on networks by continuous limit objects is an important challenge. Several notions of dynamics on finite networks, for example flows, have been extended to proposed limit objects like Markov spaces.  

Dynamical growth of physical networks: Physical networks are composed of three-dimensional physical objects embedded in space, examples of such systems include biological networks from molecular networks to nervous systems and man-made systems from electric circuits to critical infrastructure. The constraints imposed by physicality, such as the fact that objects cannot overlap and the cost of building extended connections, affect the growth and function of these networks. The study of physical networks is a nascent field of network science asking how to describe, model and predict these systems. As part of DYNASNET we initiated a collaboration between CEU and the Rényi Institute exploring these questions by leveraging results of graph combinatorics, group theory and knot theory. Recently researchers from Charles University also joined these efforts. The primary focus of our work is studying minimal models of physical networks that are simple enough to remain tractable yet capture mechanisms through which physicality affects the emergent properties of networks. We investigate two classes of such models.

The first class of models are linear physical networks, where nodes are spheres and links are cylinders with a given diameter. We define an auxiliary graph that captures constraints imposed by volume exclusion, and we show that the problem of constructing physical networks is equivalent to finding independent sets in the auxiliary graph. We study the structure of jammed physical networks, i.e., given a node set, maximal networks where no more edges can be added without violating physicality. We show, for example, that in the jammed state the top three non-trivial eigenvectors of the adjacency matrix contain information about the physical layout of the network.

The second class of models are defined on discrete lattices, where the nodes of the network are extended objects that grow via random walks. We show that the emergent network is characterized by a truncated power-law degree distribution which is universal in the sense that it does not depend on the dimension of the lattice nor the type of random walk used. This result is perhaps surprising, since power-law distributions typically require preferential attachment or optimization processes, while the growth in our model is driven by random walks. We demonstrate that two ingredients are responsible for the emergent power-law distribution: (i) network growth (the number of nodes increases over time) and (ii) externally limited node growth (nodes grow until a sufficient number of connections are formed).

Two manuscripts are under preparation summarizing our results and two contributed talks are accepted to Networks 2021, the joint Sunbelt and NetSci conference, and one paper was published, and featured on the cover of Nature Physics.

Graph Limits: Limit theories for dense and bounded-degree graph sequences had been worked out prior to this project, but their properties and applications remain important and successful research topics. Such applications have been found by researchers from Charles University and the Rényi Institute.

Substantial progress has been achieved in the case of graph sequences of intermediate density. Right-convergence of graph sequences has been defined for intermediate densities, and limit objects in the form of Markov spaces (measurable Markov chains with a stationary distribution) and double measure spaces (Markov spaces with an additional node measure). A crucial question emerged about the definition of left-convergence (or local convergence); in particular, how to define subgraph densities in Markov spaces. Here an unexpected and exciting connection with the theory of orthogonal representations of graphs has been discovered. One substantial report is posted on the ArXiv; another one is almost finished, and should be publicly available within a few weeks.

Structural network theory: The main center of this research in this area is Charles University, with active cooperation with researchers in Budapest and in Paris. The main subtopics are:

Sparsity: The hierarchy of sparse classes (bounded expansion, dense nowhere) is well established and is the subject of intensive research by many people. For monotone classes, this hierarchy mirrors a classical hierarchy in model theory (stability, NIP), with the notable exception of the dividing line delimiting polynomial expansion, which is equivalent to the existence of strongly sublinear separators. For hereditary classes, the notion of structural sparsity is more elusive and is the object of our current studies. All these sparse classes allow to obtain efficient algorithms (FPT) for pattern counting and, more generally, for model checking.

Logical limits: Among the many equivalent characterizations of nowhere denseness, which is (for monotone classes) the main dividing line between sparse and dense classes, there is a characterization in terms of the existence of particular limit objects, the modelings (i.e. totally Borel structures with a probability distribution on the domain). The underlying theory of structural limits (based on first-order property satisfaction statistics) is a general setting with applications to clustering and is particularly interesting for bounded treewidth modelings, for which a mass transport principle fully applies.

Ordered structures are studied from an algorithmic and extremal point of view.

Of particular interest is the newly defined twin-width invariant. Graphs with bounded twin-width are intuitively those that can be created by inductively splitting a vertex so that the maximum accumulated error is kept locally bounded. It is remarkable that for classes of ordered graphs, having bounded twin-width coincides with the model theoretical property of being NIP.

Universality: This classical model theoretic problems is cast into new context of EPPA problems and other group properties and homogeneity in general. Tree growing procedures with special products may have relevance to dynamics of networks. Universality reasoning also leads to new representation of planar and proper minor closed classes with many applications.

Structural Ramsey theory (particularly in relationship with Ramsey classes) has recently been revitalized both with strong finite theorems and big Ramsey degrees for countable structures.

Strong connection of this area with topological dynamics leads to many applications and interesting problems. The implications of these results for unavoidable configurations and canonical forms of motifs in networks are under investigation.