PUMA
Istituto di Scienza e Tecnologie dell'Informazione     
Rossetti G., Pappalardo L., Pedreschi D., Giannotti F. Tiles: an online algorithm for community discovery in dynamic social networks. In: Machine Learning, vol. 1 Springer, [Online First 08 September 2016]
 
 
Abstract
(English)
Community 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.
URL: http://link.springer.com/article/10.1007/s10994-016-5582-8
DOI: 10.1007/s10994-016-5582-8
Subject Dynamic Networks
Community Discovery
G.2.2 DISCRETE MATHEMATICS. Graph Theory


Icona documento 1) Download Document PDF


Icona documento Open access Icona documento Restricted Icona documento Private

 


Per ulteriori informazioni, contattare: Librarian http://puma.isti.cnr.it

Valid HTML 4.0 Transitional