Cammini casuali sui grafi

In my thesis I studied the theory of random walks applied to graphs. After a brief survey on the basic notions of random walks and on the properties of graphs, I started studying the main parameters, focusing on first return time, access time between two nodes, commute time (the expected number of steps in a random walk starting at i, before node j is visited and then node i is reached again) and cover time (the expected number of steps to reach every node). After analysing them on a generic graph, I studied in more detail these times on three particular graphs: a path, a cycle and a complete graph. Afterwards, in the third chapter, I studied the principal properties of these parameters. The first one concerns the access time from a node i to a node j; while it is symmetrical in theory, it is not in practice. As a second property I demonstrated the relationship between access time and cover time: the cover time from any node of a graph with n nodes is at most the maximum access time between any two nodes multiplied by the harmonic series and at least the minimum access time between two nodes multiplied by the harmonic series. The third and final property that I studied shows how the access time is not monotonic. Increasing the number of edges of a graph, I verified that the access time between two specific nodes can either increase or decrease depending on the cases. In the fourth chapter I studied the link between the theory of random walks applied to graphs and the spectral theory in fact it is possible to rewrite some equations that describe the parameters previously studied as a function of the eigenvalues of matrices. In particular I analysed the results on access time and on cover time; due to this parallelism with the spectral theory and also to the properties of the eigenvalues I easily demonstrated theorems set out in the first part of the thesis, for which a demonstration with standard techniques would have been extremely complicated. Finally, in the fifth chapter, I implemented random walks on specific graphs thanks to the use of the software R, to verify if the theoretical results could be approximated by empirical ones. In particular I simulated random walks on paths, on cycles and on complete graphs and I focused on first return time to the starting node, on access time between two generic nodes and on cover time. In almost all cases I recorded a good approximation of the theoretical value with the average of the results obtained with the single simulations.

Nella mia tesi ho studiato la teoria dei cammini casuali applicata ai grafi. Dopo un breve richiamo sui concetti basilari delle passeggiate aleatorie e delle proprietà dei grafi ho iniziato lo studio dei parametri principali concentrandomi sui tempi di primo ritorno nel nodo di partenza, di accesso tra due generici nodi, di percorrenza (il numero di passi necessari per andare dal nodo i al nodo j e poi tornare in i) e di ricoprimento (il numero di passi per visitare tutti i nodi). Dopo averli analizzati su un generico grafo, ho approfondito lo studio di questi tempi su tre particolari grafi: un percorso, un ciclo e un grafo completo. In seguito, nel terzo capitolo, mi sono concentrata sulle principali proprietà di questi parametri. La prima riguarda il tempo di accesso da un nodo i a un nodo j: esso è simmetrico dal punto di vista teorico ma non nella pratica. Come seconda proprietà ho dimostrato la relazione tra tempo di accesso e di percorrenza: il secondo infatti è limitato superiormente dal massimo tempo di accesso tra due nodi moltiplicato per la serie armonica e inferiormente dal minimo tempo di accesso moltiplicato anche in questo caso per la serie armonica. La terza e ultima proprietà che ho studiato afferma che i tempi di accesso non godono della proprietà di monotonia ho, infatti, verificato che aumentando il numero dei lati di un grafo il tempo di accesso tra due nodi fissati in alcuni casi aumenta e in altri diminuisce. Nel quarto capitolo ho studiato il legame tra la teoria dei cammini casuali applicata ai grafi e la teoria spettrale: è possibile, infatti, riscrivere le leggi che descrivono i parametri studiati in precedenza in funzione degli autovalori di matrici. In particolare ho analizzato i risultati sui tempi di accesso e di percorrenza; usando la teoria spettrale e le proprietà degli autovalori ho dimostrato facilmente teoremi enunciati nella prima parte della tesi, per i quali una dimostrazione con le tecniche standard sarebbe stata estremamente complicata. Infine, nel quinto capitolo, ho implementato, grazie all'uso del software R, cammini casuali su specifici grafi per capire se i risultati teorici siano approssimati da quelli empirici. In particolare ho simulato passeggiate aleatorie su percorsi, cicli e grafi completi e ho soffermato la mia attenzione sui tempi di primo ritorno nel nodo di partenza, di accesso tra due generici nodi e di ricoprimento. In quasi tutti i casi ho registrato una buona approssimazione del valore teorico con la media dei risultati ottenuti con le singole simulazioni.