We will be receiving Emanuele Natale from CNRS Sophia Antipolis who will give the following talk on Wednesday, March 13 at 2pm in room Métivier.
Title: Distributed Community Detection via the 2-Choices Dynamics
Abstract: In this talk we investigate the behavior of a simple majority dynamics on networks of agents whose interaction topology exhibits a community structure. By leveraging recent advancements in the analysis of dynamics, we show that, when the states of the nodes are randomly initialized, the system rapidly and stably converges to a configuration in which the communities maintain internal consensus on different states. Our result has several implications in different contexts in which dynamics are adopted for computational and biological modeling purposes. In the context of Label Propagation Algorithms, a class of widely used heuristics for community detection, it represents the first theoretical result on the behavior of a distributed label propagation algorithm with quasi-linear message complexity. In the context of evolutionary biology, dynamics such as the Moran process have been used to model the spread of mutations in genetic populations; our result shows that, when the probability of adoption of a given mutation by a node of the evolutionary graph depends super-linearly on the frequency of the mutation in the neighborhood of the node and the underlying evolutionary graph exhibits a community structure, there is a non-negligible probability for species differentiation to occur.
This work appeared in AAAI 2019.
Bio: Emanuele Natale is a CNRS research in the I3S laboratory in Sophia Antipolis, and a member of the joint poject-team COATI between INRIA and CNRS. He got his B.Sc. in Mathematics in 2011 and M.Sc. in Computer Science in 2013, from University of Rome “Tor Vergata”, and his Ph.D. in Computer Science in 2017 from Sapienza University of Rome under the supervision of Andrea Clementi and Riccardo Silvestri. During his Ph.D. he was a visiting student at IRIF (LIAFA) in Paris, hosted by Pierre Fraigniaud, and at the Simons Institute for the Theory of Computing of U.C. Berkeley, hosted by Luca Trevisan. After his Ph.D. he joined Kurt Mehlhorn’s Algorithms and Complexity Department at the Max Planck Institute for Informatics in Saarbrücken. He joined CNRS in January 2019. He has been awarded the Best PhD Paper in CS at Sapienza 2015 (ex-aequo), the Best Student Paper at the European Symposium of Algorithms (2016), the Outstanding PhD Student of Year 2015-2016 Award of the CS PhD School of Sapienza (ex-equo), and the Best PhD Thesis Award by the Italian Chapter of EATCS (2017). He has also received a Fellowship from the Simons Institute for the Theory of Computing in 2018.
Emanuele’s webpage: https://sites.google.com/view/enatale/home
