A Monte Carlo method for large deviations applied to Erdos-Rényi random graphs

L'obiettivo di questa tesi è duplice. Da un lato proponiamo una versione modificata di un noto metodo Monte Carlo, chiamato algoritmo Cloning, adattato per approssimare la funzione dei cumulanti di un'osservabile additiva, nel contesto dei grafi random di Erdӧs-Rényi (caso denso). Dall'altro lato indaghiamo la regione dove l'espressione analitica di tale funzione non è nota, quando l'osservabile considerata è il numero dei triangoli. La funzione dei cumulanti, è strettamente connessa alla teoria delle grandi deviazioni, in quanto, quando è possibile applicare il teorema di Gärtner-Ellis, essa risulta essere la trasformata di Legendre della funzione delle grandi deviazioni. Il nostro primo contributo consiste nella messa a punto di una nuova versione dell'algoritmo Cloning, progettata per lavorare nel contesto dei grafi random. La strategia utilizzata, sia dalla versione standard che da quella nuova del metodo, consiste nel simulare la dinamica di una popolazione, facendo evolvere e riprodurre una famiglia di copie del sistema, in modo tale da favorire le traiettorie atipiche. La nuova versione dell'algoritmo, pur mantenendo questo approccio, è concepita per lavorare nel contesto dei grafi random e implementa una dinamica tra spazi di dimensioni crescenti. Attraverso questo processo, possiamo scegliere di monitorare l'osservabile desiderata che, grazie a questa formulazione, può essere scritta in modo incrementale. Abbiamo testato questa versione estesa dell’algoritmo all'osservabile triangoli, dove la mancanza di indipendenza tra le quantità coinvolte, rende l'approccio analitico complesso e le simulazioni pesanti da eseguire. La funzione dei cumulanti dei triangoli, nel contesto del modello denso di Erdӧs-Rényi, coincide, a meno di una costante additiva, con la pressione di un grafo esponenziale: l'espressione analitica di quest'ultima, è nota in una regione dei parametri chiamata replica simmetrica mentre è irrisolta nella cosiddetta regione di rottura della replica. Prendendo in considerazione la prima regione, possiamo apprezzare la convergenza del metodo alla curva limite, nonostante lo sforzo computazionale richieda di contenere il numero delle iterazioni. Inoltre, sempre nel contesto di questo regime, diamo un argomento euristico riguardante la convergenza dell'algoritmo al risultato analitico, basato su un'approssimazione di campo medio che diventa esatta per grandi dimensioni del grafo. Nel nostro secondo contributo spostiamo l'indagine verso la regione di rottura della replica. Attraverso l'utilizzo di tre diversi approcci, perseguiamo l'obiettivo di scoprire il comportamento della funzione dei cumulanti in questo regime irrisolto. Due delle strategie proposte per condurre il nostro studio, si basano sul fatto che, dal punto di vista analitico, trovare l'espressione della funzione dei cumulanti coincide con risolvere un problema variazionale. Innanzitutto, applichiamo un noto algoritmo di ottimizzazione, il metodo del Gradiente Proiettato, per minimizzare il funzionale obiettivo discretizzato. In secondo luogo, utilizziamo la versione estesa dell'algoritmo Cloning precedentemente introdotta ed, infine, ottimizziamo il funzionale su una classe specifica di funzioni, con un approccio in parte analitico ed in parte numerico. Questa indagine si basa sulla congettura che gli ottimizzatori abbiano una struttura bipartita, fuori dalla regione replica simmetrica. Le simulazioni si mostrano in accordo nel rivelare un cambiamento nell'andamento della funzione dei cumulanti, rispetto a quello del regime replica simmetrico. Ciò è coerente con la teoria, poiché sappiamo che al di sotto di una soglia negativa, l'ottimizzatore del problema variazionale deve cambiare la sua struttura rispetto a quella assunta nella regione replica simmetrica e questo si riflette in modo diretto sulla funzione dei cumulanti.

The aim of this thesis is twofold. On one hand, we propose a modified version of a known Monte Carlo method, called Cloning algorithm, tailored for approximating the scaled cumulant generating function of an additive observable in the framework of random graphs. One the other hand, we investigate the region where the analytical expression of such function is not known, when the considered observable is the number of triangles of a dense Erdӧs-Rényi random graph. The scaled cumulant generating function is strictly connected with the theory of large deviations since, when it is possible to apply the Gärtner-Ellis theorem, it turns out to be the Legendre transform of the rate function. In our first contribution, we formalize a new version of the standard Cloning algorithm designed for working in the context of random graphs. The strategy used by both the standard and the new version of the method, leans on a population dynamics scheme which consists in making evolve and reproduce a family of copies of the system, in such a way that atypical trajectories are favored. The new version of the algorithm, while maintaining this approach, is devised for working on the random graphs framework and implements a dynamics over growing-size spaces. Along this process, we can choose to monitor a selected observable which, thanks to this strategy, can be written in an incremental way. We run the method on the triangle observable, where the lack of independence among the quantities involved makes computations difficult and simulations heavy to perform. It turns out that the scaled cumulant generating function of triangles of a dense Erdӧs-Rényi random graph coincides, up to an additive constant, with the pressure of another well-known model, the Exponential Random Graph one. Speaking in terms of this pressure, there exists a region of parameters (called replica symmetric) where its analytical expression is known and another one (called replica breaking) which is unresolved: this directly reflects on having information on the scaled cumulant generating function. Focusing on replica symmetric regime, we can appreciate the convergence of the Cloning method to the scaled cumulant generating function, despite the computational demand requires to keep the number of iterations low. Moreover, we give a heuristic argument concerning the convergence of the algorithm to the analytic result and based on a mean-field approximation which turns out to be exact in the graph size limit. In our second contribution, we move the investigation towards the replica breaking region and, making use of three approaches, we pursue the aim of discovering the behavior of the scaled cumulant generating function in this controversial regime. Two of the strategies proposed for leading our study, lean of the fact that, from the analytic point of view, finding the expression of the scaled cumulant generating function coincides with solving a variational problem. Firstly, we apply a well-known optimization method, called Projected Gradient algorithm for minimizing the objective functional (properly discretized). Secondly, we run the extended version of the Cloning method previously introduced and, finally, we perform an optimization of the functional over a specific class of functions. This third approach is motivated by the fact that we had an initial guess on the structure of one possible optimizer (in this region, it is not known if it is unique or not). Numerical simulations made along the three methods show agreement in revealing a change of the scaled cumulant generating function curve, compared with the shape assumed in the resolved region, crossing the same critical value of its parameter. This is coherent with the theory, since we know that below a negative threshold, the optimizer of the variational problem must change its structure with respect to the one assumed in the resolved region and this directly reflects on the scaled cumulant generating function.