LECTURER: Andrea Clementi (Universita' degli Studi TOR VERGATA) PERIOD: 11-12/07/2017 LOCATION: GSSI, L'AQUILA, http://cs.gssi.infn.it/contacts/ SCHEDULING: http://cs.gssi.infn.it/phd-program/calendar/ TITLE: Gossip Algorithms for Information Spreading, Consensus and Community Detection ABSTRACT: The course will focus on a set of analytic tools to analyze some basic epidemic processes in networks. 1) We start giving the main concepts and results on spectral graph theory and on expander graphs. 2) We analyze the convergence time of randomized gossip algorithms in graphs having good expansion properties. 3) We analyze some simple probabilistic dynamics that achieve fast and stable consensus. 4) We consider distributed averaging processes on well-clustered graphs and look at the metastable phase in which the states of the nodes reflect the hidden clusters of the graph. Contacts: Andrea Clementi (Universita' degli Studi TOR VERGATA), clementi@mat.uniroma2.it Mattia D'Emidio (GSSI), mattia.demidio@gmail.com