01804nas a2200157   4500008004100000245008200041210006900123300001600192490000800208520128300216100002101499700002101520700002001541700002101561856006401582       2017                        eng d00aTiles: an online algorithm for community discovery in dynamic social networks0 aTiles an online algorithm for community discovery in dynamic soc  a1213–12410 v1063 aCommunity discovery has emerged during the last decade as one of the most challenging problems in social network analysis. Many algorithms have been proposed to find communities on static networks, i.e. networks which do not change in time. However, social networks are dynamic realities (e.g. call graphs, online social networks): in such scenarios static community discovery fails to identify a partition of the graph that is semantically consistent with the temporal information expressed by the data. In this work we propose Tiles, an algorithm that extracts overlapping communities and tracks their evolution in time following an online iterative procedure. Our algorithm operates following a domino effect strategy, dynamically recomputing nodes community memberships whenever a new interaction takes place. We compare Tiles with state-of-the-art community detection algorithms on both synthetic and real world networks having annotated community structure: our experiments show that the proposed approach is able to guarantee lower execution times and better correspondence with the ground truth communities than its competitors. Moreover, we illustrate the specifics of the proposed approach by discussing the properties of identified communities it is able to identify.1 aRossetti, Giulio1 aPappalardo, Luca1 aPedreschi, Dino1 aGiannotti, Fosca  uhttps://link.springer.com/article/10.1007/s10994-016-5582-8