Quantum Walks and Community Detection

Il processo stocastico noto come random walk può essere riproposto in versione quantistica: il quantum walk, un sistema regolato dai principi della meccanica quantistica. L'evoluzione del sistema è unitaria, l’azione di interferenze tende a privilegiare alcuni cammini piuttosto che altri e, grazie al principio di sovrapposizione, è possibile percorrere più cammini simultaneamente, finché non viene effettuata una misurazione. Nel lavoro corrente ci occupiamo del quantum walk a tempo discreto e scegliamo il formalismo del “coined quantum walk”. Questo può essere utilizzato come approccio per un algoritmo di ricerca di comunità nei grafi. Nell’algoritmo sfruttiamo la “probabilità di transizione”: fissato uno stato iniziale, per ogni nodo del grafo la probabilità di transizione è la probabilità di essere su quel nodo dopo un certo numero di passi. Si dimostra che, per ogni nodo di arrivo, la media rispetto al tempo delle probabilità di transizione converge a una distribuzione limite. L'algoritmo che applichiamo per la ricerca delle comunità inizia con l'ordinare i nodi per grado decrescente. I centri delle comunità saranno quelli con grado maggiore. Per ogni nodo calcola la distribuzione limite relativa al primo centro disponibile come stato iniziale. Se il valore ottenuto è più alto di una soglia predefinita, inserisce il nodo in analisi nella comunità del centro corrispondente. Tale processo viene ripetuto al variare dei centri, finché tutti i nodi sono stati catalogati. Per concludere, proviamo ad apportare alcune modifiche all'algoritmo. Confrontiamo i risultati che si ottengono scegliendo due diverse matrici di evoluzione del sistema: la matrice di Fourier e la matrice di Grover. Studiamo poi in quali casi sia conveniente utilizzare come criterio di selezione dei centri la misura di centralità data dal grado e in quali quella data dall'esponenziale della matrice di adiacenza.