2017
Journal article
Open Access
Tiles: an online algorithm for community discovery in dynamic social networks
Rossetti G., Pappalardo L., Pedreschi D., Giannotti F.
Dynamic networks Social network analysis Artificial Intelligence Software Community discovery
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.
Source: Machine learning 106 (2017): 1213–1241. doi:10.1007/s10994-016-5582-8
Publisher: Kluwer Academic Publishers,, Boston/U.S.A. , Stati Uniti d'America
Asur, S., Parthasarathy, S., & Ucar, D. (2009). An event-based framework for characterizing the evolutionary behavior of interaction graphs. ACM Transactions on Knowledge Discovery from Data (TKDD), 3(4), 16.
Bagrow, J. P., & Lin, Y.-R. (2012). Mesoscopic structure and social aspects of human mobility. PLoS ONE, 7(5), e37676.
Barabási, A. L., & Albert, R. (1999). Emergence of scaling in random networks. Science, 286.5439, 509-512.
Bhat, S., & Abulaish, M. (Aug 2013). Overlapping social network communities and viral marketing. In International Symposium on Computational and Business Intelligence, pp. ( 243-246).
Boden, B., Günnemann, S., Hoffmann, H., & Seidl, T. (2012). Mining coherent subgraphs in multi-layer graphs with edge labels. In ACM SIGKDD.
Boldrini, C., Conti, M., & Passarella, A. (2011). From pareto inter-contact times to residuals. Communications Letters IEEE, 15(11), 1256-1258.
Buehrer, G., & Chellapilla, K. (2008). A scalable pattern mining approach to web graph compression with communities. Proceedings of the 2008 International Conference on Web Search and Data Mining, WSDM '08 (pp. 95-106). New York.
Burt, R. S. (1987). Social contagion and innovation: Cohesion versus structural equivalence. American Journal of Sociology.
Burt, R. S. (2000). Decay functions. Social Networks, 22(1), 1-28.
Cazabet, R., Amblard, F., & Hanachi, C. (2010). Detection of overlapping communities in dynamical social networks. In SocialCom, (pp. 309-314).
Chakrabarti, D., Kumar, R., & Tomkins, A. (2006). Evolutionary clustering. ACM SIGKDD.
Clauset, A., Newman, M. E. J., & Moore, C. (2004). Finding community structure in very large networks. Physical Review E, 70(6), 066111.
Coscia, M., Giannotti, F., & Pedreschi, D. (2011). A classification for community discovery methods in complex networks. Statistical Analysis and Data Mining, 4(5), 512-546.
Coscia, M., Rossetti, G., Pedreschi, D., & Giannotti, F. (2012). Demon: a local-first discovery method for overlapping communities. In ACM SIGKDD.
Dhouioui, Z., & Akaichi, J. (2014). Tracking dynamic community evolution in social networks. In ASONAM.
Folino, F., & Pizzuti, C. (2014). An evolutionary multiobjective approach for community discovery in dynamic networks. IEEE Transactions on Knowledge and Data Engineering, 26(8), 1838-1852.
Fortunato, S. (2010). Community detection in graphs. Physics Reports, 486(3), 75-174.
Goh, K.-I., & Barabási, A.-L. (2008). Burstiness and memory in complex systems. EPL (Europhysics Letters), 81(4), 48002.
Goldberg, M., Magdon-Ismail, M., Nambirajan, S., & Thompson, J. (2011). Tracking and predicting evolution of social communities. PASSAT.
Guo, C., Wang, J., & Zhang, Z. (2014). Evolutionary community structure discovery in dynamic weighted networks. Physica A: Statistical Mechanics and its Applications, 413, 565-576.
Kostakos, V. (2009). Temporal graphs. In Physica A: Statistical Mechanics and its Applications.
Lancichinetti, A., & Fortunato, S. (2009). Benchmarks for testing community detection algorithms on directed and weighted graphs with overlapping communities. Physical Review E, 80(1), 016118.
Lancichinetti, A., Fortunato, S., & Kertész, J. (2009). Detecting the overlapping and hierarchical community structure in complex networks. New Journal of Physics, 11(3), 033015.
Lee, P., Lakshmanan, L., & Milios, E. (2014). Incremental cluster evolution tracking from highly dynamic network data. In ICDE.
Leskovec, J., Kleinberg, J. M., & Faloutsos, C. (2005). Graphs over time: densification laws, shrinking diameters and possible explanations. In ACM SIGKDD.
Lin, Y., Chi, Y., & Zhu, S. (2008). Facetnet: A framework for analyzing communities and their evolutions in dynamic networks. In WWW.
Nguyen, M. V. (2012). Community evolution in a scientific collaboration network. CEC IEEE.
Nguyen, N. P., Dinh, T. N., Xuan, Y., & Thai, M. T. (2011). Adaptive algorithms for detecting community structure in dynamic social networks. In IEEE INFOCOM, (pp. 2282-2290).
Nowell, L., & Kleinberg, J. (2003). The link prediction problem for social networks. In CIKM.
Palla, G., Barabási, A. L., & Vicsek, T. (2007). Quantifying social group evolution. Nature, 446(7136), 664- 667.
Palla, G., Derényi, I., Farkas, I., & Vicsek, T. (2005). Uncovering the overlapping community structure of complex networks in nature and society. Nature, 435(7043), 814-818.
Passarella, A., Conti, M., Boldrini, C., & Dunbar, R.I. (2011). Modelling inter-contact times in social pervasive networks. In Proceedings of the 14th ACM international conference on Modeling, analysis and simulation of wireless and mobile systems, (pp. 333-340). ACM.
Qi, G., Aggarwal, C. C., & Huang, T. S. (2013). Online community detection in social sensing. WSDM.
Rinzivillo, S., Mainardi, S., Pezzoni, F., Coscia, M., Giannotti, F., & Pedreschi, D. (2012). Discovering the geographical borders of human mobility. KI - Künstliche Intelligenz, 26(3), 253-260.
Rossetti, G., Guidotti, R., Pennacchioli, D., Pedreschi, D., & Giannotti, F. (2015). Interaction prediction in dynamic networks exploiting community discovery. In Proceedings of the 2015 ACM/IEEE International Conference on Advances in Social Network Analysis and Mining.
Rossetti, G., Pappalardo, L., & Rinzivillo, S. (2016). A novel approach to evaluate community detection algorithms on ground truth. In 7th Workshop on Complex Networks, Studies in Computational Intelligence. Springer-Verlag.
Rossetti, G., Pappalardo, L., Kikas, R., Pedreschi, D., Giannotti, F., & Dumas, M. (2015). Community-centric analysis of user engagement in skype social network. In Proceedings of the 2015 ACM/IEEE International Conference on Advances in Social Network Analysis and Mining.
Rosvall, M., & Bergstrom, C. T. (2008). Maps of random walks on complex networks reveal community structure. Proceedings of the National Academy of Sciences, 105(4), 1118-1123.
Rozenshtein, P., Tatti, N., & Gionis, A. (2014). Discovering dynamic communities in interaction networks. ECML PKDD.
Shang, J., Liu, L., & Xie, F. (2012). A real-time detecting algorithm for tracking community structure of dynamic networks. 6th SNA-KDD.
Sun, Y., Tang, J., Han, J., Gupta, M., & Zhao, B. (2010). Community evolution detection in dynamic heterogeneous information networks. MLG.
Takaffoli, M., Rabbany, R., & Zaiane, O. R. (2014). Community evolution prediction in dynamic social networks. In ASONAM.
Takaffoli, M., Sangi, F., Fagnan, J., & Zaïane O. (2011). Modec-modeling and detecting evolutions of communities. ICWSM.
Viswanath, B., Mislove, A., Cha, M., & Gummadi, P. K. (2009). On the evolution of user interaction in facebook. WOSN.
Wang, P., Gonzàlez, M. C., Hidalgo, C.A., & Barabási, A. L. (2009). Understanding the spreading patterns of mobile phone viruses. Science, 324(5930), 1071-1076.
Wu, X., & Liu, Z. (2008). How community structure influences epidemic spread in social networks. Physica A Statistical Mechanics and its Applications, 387, 623-630.
Xu, H., Wang, Z., & Xiao, W. (2013). Analyzing community core evolution in mobile social networks. In SocialCom.
Zakreweska, A., & Bader, D. (2015). A dynamic algorithm for local community detection in graphs. In ASONAM.
Bagrow, J. P., & Lin, Y.-R. (2012). Mesoscopic structure and social aspects of human mobility. PLoS ONE, 7(5), e37676.
Barabási, A. L., & Albert, R. (1999). Emergence of scaling in random networks. Science, 286.5439, 509-512.
Bhat, S., & Abulaish, M. (Aug 2013). Overlapping social network communities and viral marketing. In International Symposium on Computational and Business Intelligence, pp. ( 243-246).
Boden, B., Günnemann, S., Hoffmann, H., & Seidl, T. (2012). Mining coherent subgraphs in multi-layer graphs with edge labels. In ACM SIGKDD.
Boldrini, C., Conti, M., & Passarella, A. (2011). From pareto inter-contact times to residuals. Communications Letters IEEE, 15(11), 1256-1258.
Buehrer, G., & Chellapilla, K. (2008). A scalable pattern mining approach to web graph compression with communities. Proceedings of the 2008 International Conference on Web Search and Data Mining, WSDM '08 (pp. 95-106). New York.
Burt, R. S. (1987). Social contagion and innovation: Cohesion versus structural equivalence. American Journal of Sociology.
Burt, R. S. (2000). Decay functions. Social Networks, 22(1), 1-28.
Cazabet, R., Amblard, F., & Hanachi, C. (2010). Detection of overlapping communities in dynamical social networks. In SocialCom, (pp. 309-314).
Chakrabarti, D., Kumar, R., & Tomkins, A. (2006). Evolutionary clustering. ACM SIGKDD.
Clauset, A., Newman, M. E. J., & Moore, C. (2004). Finding community structure in very large networks. Physical Review E, 70(6), 066111.
Coscia, M., Giannotti, F., & Pedreschi, D. (2011). A classification for community discovery methods in complex networks. Statistical Analysis and Data Mining, 4(5), 512-546.
Coscia, M., Rossetti, G., Pedreschi, D., & Giannotti, F. (2012). Demon: a local-first discovery method for overlapping communities. In ACM SIGKDD.
Dhouioui, Z., & Akaichi, J. (2014). Tracking dynamic community evolution in social networks. In ASONAM.
Folino, F., & Pizzuti, C. (2014). An evolutionary multiobjective approach for community discovery in dynamic networks. IEEE Transactions on Knowledge and Data Engineering, 26(8), 1838-1852.
Fortunato, S. (2010). Community detection in graphs. Physics Reports, 486(3), 75-174.
Goh, K.-I., & Barabási, A.-L. (2008). Burstiness and memory in complex systems. EPL (Europhysics Letters), 81(4), 48002.
Goldberg, M., Magdon-Ismail, M., Nambirajan, S., & Thompson, J. (2011). Tracking and predicting evolution of social communities. PASSAT.
Guo, C., Wang, J., & Zhang, Z. (2014). Evolutionary community structure discovery in dynamic weighted networks. Physica A: Statistical Mechanics and its Applications, 413, 565-576.
Kostakos, V. (2009). Temporal graphs. In Physica A: Statistical Mechanics and its Applications.
Lancichinetti, A., & Fortunato, S. (2009). Benchmarks for testing community detection algorithms on directed and weighted graphs with overlapping communities. Physical Review E, 80(1), 016118.
Lancichinetti, A., Fortunato, S., & Kertész, J. (2009). Detecting the overlapping and hierarchical community structure in complex networks. New Journal of Physics, 11(3), 033015.
Lee, P., Lakshmanan, L., & Milios, E. (2014). Incremental cluster evolution tracking from highly dynamic network data. In ICDE.
Leskovec, J., Kleinberg, J. M., & Faloutsos, C. (2005). Graphs over time: densification laws, shrinking diameters and possible explanations. In ACM SIGKDD.
Lin, Y., Chi, Y., & Zhu, S. (2008). Facetnet: A framework for analyzing communities and their evolutions in dynamic networks. In WWW.
Nguyen, M. V. (2012). Community evolution in a scientific collaboration network. CEC IEEE.
Nguyen, N. P., Dinh, T. N., Xuan, Y., & Thai, M. T. (2011). Adaptive algorithms for detecting community structure in dynamic social networks. In IEEE INFOCOM, (pp. 2282-2290).
Nowell, L., & Kleinberg, J. (2003). The link prediction problem for social networks. In CIKM.
Palla, G., Barabási, A. L., & Vicsek, T. (2007). Quantifying social group evolution. Nature, 446(7136), 664- 667.
Palla, G., Derényi, I., Farkas, I., & Vicsek, T. (2005). Uncovering the overlapping community structure of complex networks in nature and society. Nature, 435(7043), 814-818.
Passarella, A., Conti, M., Boldrini, C., & Dunbar, R.I. (2011). Modelling inter-contact times in social pervasive networks. In Proceedings of the 14th ACM international conference on Modeling, analysis and simulation of wireless and mobile systems, (pp. 333-340). ACM.
Qi, G., Aggarwal, C. C., & Huang, T. S. (2013). Online community detection in social sensing. WSDM.
Rinzivillo, S., Mainardi, S., Pezzoni, F., Coscia, M., Giannotti, F., & Pedreschi, D. (2012). Discovering the geographical borders of human mobility. KI - Künstliche Intelligenz, 26(3), 253-260.
Rossetti, G., Guidotti, R., Pennacchioli, D., Pedreschi, D., & Giannotti, F. (2015). Interaction prediction in dynamic networks exploiting community discovery. In Proceedings of the 2015 ACM/IEEE International Conference on Advances in Social Network Analysis and Mining.
Rossetti, G., Pappalardo, L., & Rinzivillo, S. (2016). A novel approach to evaluate community detection algorithms on ground truth. In 7th Workshop on Complex Networks, Studies in Computational Intelligence. Springer-Verlag.
Rossetti, G., Pappalardo, L., Kikas, R., Pedreschi, D., Giannotti, F., & Dumas, M. (2015). Community-centric analysis of user engagement in skype social network. In Proceedings of the 2015 ACM/IEEE International Conference on Advances in Social Network Analysis and Mining.
Rosvall, M., & Bergstrom, C. T. (2008). Maps of random walks on complex networks reveal community structure. Proceedings of the National Academy of Sciences, 105(4), 1118-1123.
Rozenshtein, P., Tatti, N., & Gionis, A. (2014). Discovering dynamic communities in interaction networks. ECML PKDD.
Shang, J., Liu, L., & Xie, F. (2012). A real-time detecting algorithm for tracking community structure of dynamic networks. 6th SNA-KDD.
Sun, Y., Tang, J., Han, J., Gupta, M., & Zhao, B. (2010). Community evolution detection in dynamic heterogeneous information networks. MLG.
Takaffoli, M., Rabbany, R., & Zaiane, O. R. (2014). Community evolution prediction in dynamic social networks. In ASONAM.
Takaffoli, M., Sangi, F., Fagnan, J., & Zaïane O. (2011). Modec-modeling and detecting evolutions of communities. ICWSM.
Viswanath, B., Mislove, A., Cha, M., & Gummadi, P. K. (2009). On the evolution of user interaction in facebook. WOSN.
Wang, P., Gonzàlez, M. C., Hidalgo, C.A., & Barabási, A. L. (2009). Understanding the spreading patterns of mobile phone viruses. Science, 324(5930), 1071-1076.
Wu, X., & Liu, Z. (2008). How community structure influences epidemic spread in social networks. Physica A Statistical Mechanics and its Applications, 387, 623-630.
Xu, H., Wang, Z., & Xiao, W. (2013). Analyzing community core evolution in mobile social networks. In SocialCom.
Zakreweska, A., & Bader, D. (2015). A dynamic algorithm for local community detection in graphs. In ASONAM.
Metrics
Back to previous page
BibTeX entry
@article{oai:it.cnr:prodotti:366889,
title = {Tiles: an online algorithm for community discovery in dynamic social networks},
author = {Rossetti G. and Pappalardo L. and Pedreschi D. and Giannotti F.},
publisher = {Kluwer Academic Publishers,, Boston/U.S.A. , Stati Uniti d'America},
doi = {10.1007/s10994-016-5582-8},
journal = {Machine learning},
volume = {106},
pages = {1213–1241},
year = {2017}
}
0000-0003-3099-3835CNR ExploRA
ISTI Repository
DOIAlso available from
ISTI Repository
DOIAlso available from
