Abstracts
Elena Agliari: Complex (neural) networks for complex tasks
In the first part of this talk I will provide a gentle introduction to neural networks, focusing on two paradigmatic models, for learning and retrieving information respectively, namely the Boltzmann machine. and the Hopfield network. These systems can be represented as weighted graphs, where the architecture and the weight distribution are specifically designed according to the task that the models are assigned.
In the second part of the talk, I will discuss the interplay between model features and task complexity: simple tasks typically involve structureless, sparse datasets and require relatively simple architectures and weight distributions, but this is no longer the case for more challenging tasks, as will be shown by means of several examples.
Gabriel Berzunza: Fragmentation Process derived from $\alpha$-stable Galton-Watson trees
Aldous, Evans and Pitman (1998) studied the behaviour of the fragmentation process derived from deleting the edges of a uniform random tree on $n$ labelled vertices. In particular, they showed that, after proper rescaling, the above fragmentation process converges as $n \rightarrow \infty$ to the fragmentation process of the Brownian CRT obtained by cutting-down the Brownian CRT along its skeleton in a Poisson manner.
In this talk, we will discuss the fragmentation process obtained by deleting randomly chosen edges from a critical Galton-Watson tree $\mathbf{t}_{n}$ conditioned on having $n$ vertices, whose offspring distribution belongs to the domain of attraction of a stable law of index $\alpha \in (1,2]$. The main result establishes that, after rescaling, the fragmentation process of $\mathbf{t}_{n}$ converges, as $n \rightarrow \infty$, to the fragmentation process obtained by cutting-down proportional to the length on the skeleton of an $\alpha$-stable L\'evy tree. We will also explain how one can construct the latter by considering the partitions of the unit interval induced by the normalized $\alpha$-stable L\'evy excursion with a deterministic drift. In particular, the above extends the result of Bertoin (2000) on the fragmentation process of the Brownian CRT.
The approach uses the well-known Prim's algorithm (or Prim-Jarník algorithm) to define a consistent exploration process that encodes the fragmentation process of $\mathbf{t}_{n}$. We will discuss the key ideas of the proof.
Joint work with Cecilia Holmgren (Uppsala University)
Nic Freeman: Extensive condensation in preferential attachment with choice
I will introduce a new preferential attachment model in which each vertex has an associated fitness value. I will discuss the behaviour of the model as the number of nodes tends to infinity, including the existence of a "condensation" phase in which a small number of especially fit vertices are able to gain disproportionately large degrees. The work relies on a new connection between preferential attachment with fitnesses, and branching-coalescing particle systems; it leads to a clear and intuitive explanation for why the condensation phenomenon occurs. Moreover, we will see that in this model the condensation is "extensive", meaning that some such vertices become, each only for a limited time, connected to a positive fraction of the current graph. (Joint work with Jonathan Jordan.)
Ayalvadi Ganesh: Gossiping in random graphs
Consider a set of n agents, each of whom has a single message to convey to all other agents. The messages are all of the same length. Time is divided into rounds, and during each round, each agent may broadcast a single message. Agents are represented as nodes of a directed communication graph, and a broadcast is received error-free by all (out)-neighbours of the broadcasting node. The problem is to minimise the number of rounds until all agents have received all messages.
This is known as the gossiping problem, and various versions of it have been studied. In our version, the communication graph is a dense directed Erdos-Rényi random graph G(n,p), and we seek simple decentralised gossip algorithms. We consider two algorithms, random relaying and random linear network coding. We consider a sequence of graphs with p fixed and n tending to infinity. Our main results are that random relaying requires Theta(log n) rounds, whereas random linear network coding requires only a constant number of rounds.
Jonathan Jordan: Competing types in preferential attachment graphs with community structure
We investigate extending the results of Antunović, Mossel and Rácz on co-existence of types in preferential attachment networks to preferential attachment with community structure. We show that different types of limiting behaviour can be found depending on the choice of community structure and type assignment rule. In particular, we show that, for most choices of type assignment rule where more than one limit has positive probability in the Antunović, Mossel and Rácz results, different limits are possible in different communities if the community connections are sufficiently weak. We also give some other examples are different limits are possible in different communities, even where there is only one limit with positive probability in the Antunović, Mossel and Rácz results.
Vassili Kolokoltsov: Controlling the preferential attachment evolution in the limit of a large number of agents
We analyse the response of a complex system that includes both the capacity for growth and coalition building mechanisms to external parameters that may be set by the principal (say, by governmental regulations), that has its own agenda (may wish to influence the growth of certain economics sectors). The model is a kind of a mean-field control optimization problem with a countable state space.
Marcel Ortgiese: The contact process on a random graph adapting to the infection
The contact process is a simple model for the spread of an infection in a structured population. In this talk, we consider a variant of the contact process on an evolving random graph. Initially, the random graph has the same distribution as an Erdos-Rény random graph, but as the infection evolves the random graph reacts to the infection by resampling connections to neighbours that are infected. This model is particularly interesting, because the co-evolution of graph and infection means that we lose many of the standard techniques in this area. We prove that the model exhibits a phase transition in the infection parameter and give conditions for either phase in terms of the updating rate and the average number of neighbours. This is joint work with John Fernley and Peter Moerters.
Quasem Tawhari: Random Spatial Graphs
We study random spatial graphs constructed on the points of a Poisson point process in the unit square, in which each point is joined by an edge to its nearest neighbour in a given direction specified by a cone. The unrestricted case is the ordinary nearest-neighbour graph; the restricted case is a version of the minimal directed spanning forest (MDSF) introduced by Bhatt & Roy. For the ordinary nearest-neighbour graph, Avram & Bertsimas obtained a central limit theorem for the total edge length. For the MDSF, the limit theory is known (Penrose & Wade) in two special cases, namely the `south' and `south-west' versions.
In this talk, I will describe ongoing work to extend the limit theory to the case of general cones; depending on the parameters, the limit distribution may be normal, or the convolution of a normal distribution with a non-normal element due to boundary effects.
Andrew Wade: Random directed and on-line spatial graphs
In this talk I will give an overview of a class of random graph models constructed on random points in space, with edges added according to a rule based on proximity, including the "on-line" set-up where vertices are added sequentially and the candidate neighbour of a new vertex is chosen from among its predecessors. The examples I will focus on are the so-called minimal directed spanning tree (introduced by Bhatt and Roy) and the on-line nearest neighbour graph (which goes back at least to Steele), in both of which points are connected to nearest neighbours in Euclidean space, with some constraints. The results I will present cover the large-sample asymptotics for the total edge length of these graphs. The main feature of these results is that the limit distribution undergoes a dimension-dependent phase transition between normal (as is common under local dependence) and non-normal limits, with the non-normal component arising due to the presence of unusually long edges.