• albero
• Braess's paradox
• catena di Markov
• complemento stocastico
• costante di Kemeny
• distribuzione stazionaria
• grafo
• graph
• Kemeny's constant
• Markov chain
• matrice di transizione
• mean first passage time
• network
• paradosso di Braess
• processo stocastico
• rete
• stationary distribution
• stochastic complement
• stochastic process
• tempo medio di primo passaggio
• transition matrix
• tree

La costante di Kemeny di un grafo è il tempo medio impiegato dal cammino aleatorio per raggiungere un vertice del grafo scelto casualmente, in accordo con la sua distribuzione stazionaria. Sorprendentemente, questa quantità è indipendente dalla scelta del vertice di partenza. Definita per la prima volta nel 1960 da John Kemeny, questa costante è una quantità chiave nello studio delle proprietà dei grafi. In questo lavoro presentiamo diverse proprietà e alcuni metodi per il suo calcolo. Presentiamo formule esplicite della costante di Kemeny per grafi con una struttura particolare. In seguito, analizziamo i casi in cui l’aggiunta di un arco in un grafo si traduce in un aumento della corrispondente costante di Kemeny, fenomeno contro-intuitivo noto come paradosso di Braess. Viene presentato un modello per il tracciamento del COVID-19 basato su un indicatore definito dalla costante di Kemeny, dove si sfruttano le proprietà dei grafi per identificare gli individui maggiormente responsabili della diffusione del virus. Infine, sfruttiamo la teoria dei complementi stocastici per derivare un algoritmo ricorsivo per il calcolo efficiente della costante di Kemeny, e ne confrontiamo le prestazioni con quelle di algoritmi non deterministici basati sull’approssimazione della traccia di matrice. Gli esperimenti numerici effettuati su problemi reali mostrano l’alta efficienza e affidabilità del metodo ricorsivo.

The Kemeny's constant of a graph is the expected time for a random walk to reach a randomly chosen vertex of the graph, according to its stationary distribution. Surprisingly, this quantity is independent of the choice of the starting vertex. First defined in 1960 by John Kemeny, this constant is a key quantity in the study of graph properties. In this work, we present several properties and some methods for its calculation. We present explicit formulas of Kemeny's constant for graphs with a particular structure. Subsequently, we analyze the cases where the addition of an edge in a graph increases the corresponding value of Kemeny's constant, a counter-intuitive phenomenon known as Braess's paradox. A model for tracking COVID-19 is presented, based on an indicator defined by Kemeny's constant, where the properties of graphs are exploited to identify individuals most responsible for the spread of the virus. Finally, we exploit the theory of stochastic complements to derive a recursive algorithm for the efficient calculation of the Kemeny constant, and we compare its performance with that of non-deterministic algorithms based on matrix trace approximation. Numerical experiments on real-world problems show the high efficiency and reliability of the recursive method.