SpTheoryGraphLim · Spectral Theory of Graph Limits

Spectral Theory of Graph Limits

"Networks with a large number of interacting nodes come up in various branches of sciences. There is a rapidly growing need to understand their behavior and properties, and to work out algorithms for them. The problem is, however, that real-life networks tend to be too large to use standard graph theoretic tools and methods. Recently new areas of mathematics (such as graph convergence and parallel algorithms) have been developed in order to address this problem. This project aimed to study these areas, with particular emphasis on their spectral aspects. In parallel algorithms the idea is to distribute the algorithm among the nodes of the network and therefore have a constant running time. The project focused on certain randomized local algorithms (called factor of IID processes in probability theory). One of the key techniques that the project used and extended is entropy inequalities. They provide constraints for what can be achieved by randomized local algorithms. The Shannon entropy measures the ""uncertainty"" of a random state. One can consider the entropy of the random output of a local algorithm for different sets of nodes. It turned out that certain inequalities are satisfied between these entropies. Such inequalities played a central role in a few remarkable results recently, e.g. the Backhausz-Szegedy result on the eigenvectors of random regular graphs. The main results of this project include the analysis of how independent different parts of the output of a randomized local algorithm are. Different aspects of independence were considered: correlation, mutual information. The project also made progress in developing new entropy inequalities: an approach was found that provides a recipe for how to find and prove entropy inequalities."

Текст от CORDIS, на английски · Данни: CORDIS, © Европейски съюз