A day on Random Graphs

ATTENTION! Registration before May 15th is free but compulsory for organizational purposes: here.

The workshop is organised by the Rome Center on Mathematics for Modeling and Data ScienceS (RoMaDS) of Tor Vergata University and funded by the excellence program Math@TOV. The aim of the workshop is to bring together experts form probability theory and computer science to share our viewpoints on random graphs.


Luca Avena (Leiden University)
A randomized k-centrality measure & applications to networks node immunization

In recent works, Avena and Gaudilliere proposed a randomized flexible method to identify sets of k "central" nodes in a network based on so-called Kirchhoff's forest: a spanning rooted forest measure which generalizes the well-known uniform spanning tree. We recall the main mathematical results behind this method which we then apply in the context of "multiple-node immunization" for complex networks under attack of a viral agent. The latter is a hot topic in network science and it consists in identifying and removing a set of nodes of a given size in a graph to maximally impede the virus spread. Several approaches have been proposed in the literature in relation to numerical and theoretical insights on how classical models for virus spread (so-called compartmental models) evolve on graphs. Based on the stability analysis of these compartmental models, the maximal eigenvalue of the adjacency matrix of the graph has been proposed as a measure for how much resilient the network is. Thus, one of the most common approaches for immunization consists in identifying the set of nodes of a given cardinality, for which the reduced network (obtained by removing these nodes and their incident edges) has smallest maximal eigenvalue. This optimization problem turns out to be a computationally hard problem in the well-known NP-class and the available exact or proxy algorithms offer good solutions and performances only under certain conditions. As we will argue both theoretically and via experimental results on classical synthetic and real-world benchmarks, by using the random k-central nodes associated to the Kirchhoff's forest, one can build a valuable efficient method to improve the state of the art within this multiple-node immunization problem.
Joint work with Michael Emmerich, Alex Gaudilliere and Irina Gurewitsch.


Afonso S. Bandeira (ETH Zürich)
Statistical-to-Computational Gaps: The Low-Degree method and Free-Energy Barriers

When faced with a data analysis, learning, or statistical inference problem, the amount and quality of data available fundamentally determines whether such tasks can be performed with certain levels of accuracy. With the growing size of datasets however, it is crucial not only that the underlying statistical task is possible, but also that is doable by means of efficient algorithms. In this talk we will discuss methods aiming to establish limits of when statistical tasks are possible with computationally efficient methods or when there is a fundamental "Statistical-to-Computational gap" in which an inference task is statistically possible but inherently computationally hard. We will describe recent rigorous correspondences between two different approaches to argue computational hardness of high dimensional inference, the low degree method and methods based on free energy potentials. Based on joint work with Ahmed El Alaoui, Samuel B. Hopkins, Tselil Schramm, Alexander S. Wein, and Ilias Zadik.


Luca Becchetti (Università La Sapienza)
Dynamic Random Networks with Node Churn

We study expansion and flooding in evolving graphs, when nodes and edges are continuously created and removed. We consider a model with Poisson node inter-arrival and exponential node survival times. Upon joining the network, a node connects to d = O(1) random nodes, while an edge disappears whenever one of its endpoints leaves the network. For this model, we show that, although at any point in time the graph has a constant (depending on d) fraction of isolated nodes with large, constant probability, flooding still informs a fraction 1-\exp(-Omega(d)) of the nodes in time O(log n). Moreover, at any given time, the graph exhibits a "large-set expansion" property. We further consider a model in which each edge leaving the network is replaced by a fresh, random one. For this second model, we prove that, with high probability i) flooding informs all nodes in time O(log n) and ii) the graph is a vertex expander.


Júlia Komjáthy (TU Delft)
Distance evolution in scale-free preferential attachment models

We study the evolution of the graph distance between two fixed vertices in dynamically growing random graph models. More precisely, we consider preferential attachment models with power-law exponent τ∈(2,3), sample two vertices u_t, v_t uniformly at random when the graph has t vertices, and study the evolution of the graph distance between these two fixed vertices as the surrounding graph grows. This yields a discrete-time stochastic process in t′≥t, called the distance evolution. We show that there is a tight strip around a deterministic function that the distance evolution never leaves with high probability as t tends to infinity. Joint work with Joost Jorritsma.


Luca Trevisan (Università Bocconi)
A Ihara-Bass Formula for Non-Boolean Matrices and Strong Refutations of Random CSPs

We define a notion of non-backtracking operator for general weighted graphs, including graphs with negative weights, and prove a Ihara-Bass formula for it. Previously these notions were known only for unweighted graphs.
We use this theory to prove new results on strong refutations of random instances of 3SAT and of other constraint satisfaction problems with an odd number of variables per constraint.



09h30 - 10h30 Luca Avena
10h30 - 11h00 Coffee break
11h00 - 12h00 Luca Trevisan
12h00 - 13h00 Afonso S. Bandeira
13h00 - 14h30 Now is the time of lunch (cit.)
14h30 - 15h30 Júlia Komjáthy
15h30 - 16h30 Luca Becchetti


The conference will take place in Aula Gismondi (aka Aula Magna) at Università Tor Vergata, Via della Ricerca Scientifica 1, 00133, Roma.
When you arrive, facing the main building, head towards your left. At the left-end of the building, before entering, take the stairs on your left. Walk a few meters under the 'bridges' and you are there.


Andrea Clementi
Domenico Marinucci
Michele Salvi
Stefano Vigogna


Should you have further questions, please write to salvi@mat.uniroma2.it .

Here the poster with artwork of Valeria Petrone.