Two papers by GSSI researchers at AAAI 2019

The main track of AAAI 2019 will feature the presentation of two papers by CS@GSSI researchers. The two papers are

• "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 Gianlorenzo, Martin and Lorenzo (who is a CS@GSSI alumnus)  contributes to the study of one of the main tools in the analysis of social networks, viz. centrality metrics. Since central nodes are very influential in their network, increasing the centrality of a network user is a widely studies optimization problem in network analysis. Gianlorenzo, Martin and Lorenzo have studied the centrality maximization problem in undirected networks for one of the most important shortest-path-based centrality measures, namely the coverage centrality. They give several hardness results, approximation algorithms and an experimental study of their effectiveness.

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.