- "Coverage Centrality Maximization in Undirected Networks" by Gianlorenzo D'Angelo (Gran Sasso Science Institute), Martin Olsen (Aarhus University) and Lorenzo Severini (ISI Foundation) and
- "Distributed Community Detection via Metastability of the 2-Choices Dynamics" by Emilio Cruciani (Gran Sasso Science Institute), Emanuele Natale (MPII) and Giacomo Scornavacca (University of L'Aquila).
The paper by Emilio, Emanuele and Giacomo analyzes the behaviour of a simple majority-based dynamics on a class of networks that present a clustered structure. By combining symmetry-breaking techniques and concentration of probability arguments with a linear algebraic approach, it provides the first symmetry-breaking analysis of dynamics for non-consensus problems on non-complete topologies. The analysis shows that, when the agents of the networks randomly initialize their states, the 2-Choices dynamics makes the network quickly converge to a configuration where the agents have a state that identifies the cluster to which they belong. The 2-Choices dynamics can be seen as a simple distributed Label Propagation Algorithm (a widely used class of heuristics for graph clustering) with quasi-linear message complexity. In this setting, the paper represents the first rigorous theoretical result. Moreover, in the context of evolutionary biology, it gives a proof of principle of sympatric/parapatric speciation, in which there is no complete geographical isolation between the species: No simple dynamics was proposed before to explain such a fundamental phenomenon.
Congratulations to Emilio, Gianlorenzo and their coauthors! It is always a pleasure to see young researchers in one's group succeed and develop their careers. Emilio Cruciani is a beginning third-year student who already has an impressive track record of high-quality publications. Keep him in mind for postdoctoral and tenure-track positions, once he finishes his studies!
The AAAI conference promotes research in artificial intelligence and is one of the premier conferences in AI, where researchers, practitioners, and scientists meet to present and discuss most recent trends and results in the field of artificial intelligence. This year it received a record number of over than 7,700 submissions of which 1,150 were accepted (with an acceptance rate of 16.2%). The list of accepted papers is at https://aaai.org/…/uplo…/2018/11/AAAI-19_Accepted_Papers.pdf.