Método Rápido de Agrupamento de Vértices para Detecção de Comunidades em Redes Complexas de Larga-escala
Resumo
Este artigo reporta resultados de uma investigação sobre o problema de detecção de comunidades em redes complexas. Na literatura dedicada a esse assunto, um algoritmo iterativo, denominado Método de Louvain (ML), se destaca como opção eficaz e rápida para o problema. Entretanto, as primeiras iterações do ML são sua parte mais custosa. Neste artigo, propõe-se um Método Rápido de Agrupamento de Vértices (MRAV) em grafos como uma opção mais rápida do que as primeiras iterações do ML. Através de experimentos envolvendo redes grandes do mundo real, demonstra-se que o sistema proposto MRAV+ML identifica comunidades com modularidade similar ao ML (redução média menor de 3%), mas com redução média de aproximadamente 42% no tempo de execução.
Referências
Adamic, L. A. e Glance, N. (2005). The political blogosphere and the 2004 US election: divided they blog. In Proc. 3rd Int. Workshop on Link Discovery, pages 36–43. ACM.
Aldecoa, R. e Marín, I. (2011). Deciphering network community structure by surprise. PloS one, 6(9):e24195.
Aldecoa, R. e Marín, I. (2013). Surprise maximization reveals the community structure of complex networks. Scientific Reports, 3:1060.
Bai, L., Cheng, X., Liang, J., e Guo, Y. (2017). Fast graph clustering with a new description model for community detection. Information Sciences, 388:37–47.
Bhowmick, S. e Srinivasan, S. (2013). A template for parallelizing the louvain method for modularity maximization. In Dynamics on and of Complex Networks, Volume 2, pages 111–124. Springer.
Blondel, V. D., Guillaume, J.-L., Lambiotte, R., e Lefebvre, E. (2008). Fast unfolding of communities in large networks. Journal of Statistical Mechanics: Theory and Experiment, 2008(10):P10008.
Boguná, M., Pastor-Satorras, R., Díaz-Guilera, A., e Arenas, A. (2004). Models of social networks based on social distance attachment. Physical Review E, 70(5):056122.
Bondy, J. A., Murty, U. S. R., et al. (1976). Graph theory with applications. Elsevier.
Chakraborty, T., Dalmia, A., Mukherjee, A., e Ganguly, N. (2017). Metrics for community analysis: A survey. ACM Computing Surveys (CSUR), 50(4):54.
Fazlali, M., Moradi, E., e Malazi, H. T. (2017). Adaptive parallel Louvain community detection on a multicore platform. Microprocessors and Microsystems, 54:26–34.
Fortunato, S. (2010). Community detection in graphs. Physics reports, 486(3-5):75–174.
Fortunato, S. e Barthelemy, M. (2007). Resolution limit in community detection. Proceedings of the National Academy of Sciences, 104(1):36–41.
Girvan, M. e Newman, M. E. (2002). Community structure in social and biological networks. Proceedings of the National Academy of Sciences, 99(12):7821–7826.
Guimera, R., Danon, L., Diaz-Guilera, A., Giralt, F., e Arenas, A. (2003). Selfsimilar community structure in a network of human interactions. Physical Review E, 68(6):065103.
Harenberg, S., Bello, G., Gjeltema, L., Ranshous, S., Harlalka, J., Seay, R., Padmanabhan, K., e Samatova, N. (2014). Community detection in large-scale networks: a survey and empirical evaluation. Wiley Interdisciplinary Reviews: Computational Statistics, 6(6):426–439.
Joshi-Tope, G., Gillespie, M., Vastrik, I., D’Eustachio, P., Schmidt, E., de Bono, B., Jassal, B., Gopinath, G., Wu, G., Matthews, L., et al. (2005). Reactome: a knowledgebase of biological pathways. Nucleic Acids Research, 33(suppl_1):D428–D432.
Khan, B. S. e Niazi, M. A. (2017). Network community detection: A review and visual survey. CoRR, abs/1708.00977.
Kwak, H., Lee, C., Park, H., e Moon, S. (2010). What is twitter, a social network or a news media? In Proc. 19th Int. Conf. on World Wide Web, pages 591–600. ACM.
Lancichinetti, A. e Fortunato, S. (2009). Community detection algorithms: a comparative analysis. Physical Review E, 80(5):056117.
Leskovec, J. e Krevl, A. (2014). SNAP Datasets: Stanford large network dataset collection. [link].
Leskovec, J., Lang, K. J., e Mahoney, M. (2010). Empirical comparison of algorithms for network community detection. In Proc. 19th Int. Conf. on World Wide Web, pages 631–640. ACM.
Mislove, A., Marcon, M., Gummadi, K. P., Druschel, P., e Bhattacharjee, B. (2007). Measurement and analysis of online social networks. In Proc. 7th ACM SIGCOMM Conf. on Internet Measurement, pages 29–42. ACM.
Newman, M. E. (2006). Modularity and community structure in networks. Proc. National Academy of Sciences, 103(23):8577–8582.
Ozaki, N., Tezuka, H., e Inaba, M. (2016). A simple acceleration method for the Louvain algorithm. Int. Journal of Computer and Electrical Engineering, 8(3):207.
Peng, C., Kolda, T. G., e Pinar, A. (2014). Accelerating community detection by using k-core subgraphs. arXiv preprint arXiv:1403.2226.
Satuluri, V., Parthasarathy, S., e Ruan, Y. (2011). Local graph sparsification for scalable clustering. In Proc. ACM SIGMOD Int. Conf. on Management of Data, pages 721–732.
Yang, J. e Leskovec, J. (2015). Defining and evaluating network communities based on ground-truth. Knowledge and Information Systems, 42(1):181–213.
Zhao, Y. (2017). A survey on theoretical advances of community detection in networks. Wiley Interdisciplinary Reviews: Computational Statistics, 9(e1403):1–13.
Aldecoa, R. e Marín, I. (2011). Deciphering network community structure by surprise. PloS one, 6(9):e24195.
Aldecoa, R. e Marín, I. (2013). Surprise maximization reveals the community structure of complex networks. Scientific Reports, 3:1060.
Bai, L., Cheng, X., Liang, J., e Guo, Y. (2017). Fast graph clustering with a new description model for community detection. Information Sciences, 388:37–47.
Bhowmick, S. e Srinivasan, S. (2013). A template for parallelizing the louvain method for modularity maximization. In Dynamics on and of Complex Networks, Volume 2, pages 111–124. Springer.
Blondel, V. D., Guillaume, J.-L., Lambiotte, R., e Lefebvre, E. (2008). Fast unfolding of communities in large networks. Journal of Statistical Mechanics: Theory and Experiment, 2008(10):P10008.
Boguná, M., Pastor-Satorras, R., Díaz-Guilera, A., e Arenas, A. (2004). Models of social networks based on social distance attachment. Physical Review E, 70(5):056122.
Bondy, J. A., Murty, U. S. R., et al. (1976). Graph theory with applications. Elsevier.
Chakraborty, T., Dalmia, A., Mukherjee, A., e Ganguly, N. (2017). Metrics for community analysis: A survey. ACM Computing Surveys (CSUR), 50(4):54.
Fazlali, M., Moradi, E., e Malazi, H. T. (2017). Adaptive parallel Louvain community detection on a multicore platform. Microprocessors and Microsystems, 54:26–34.
Fortunato, S. (2010). Community detection in graphs. Physics reports, 486(3-5):75–174.
Fortunato, S. e Barthelemy, M. (2007). Resolution limit in community detection. Proceedings of the National Academy of Sciences, 104(1):36–41.
Girvan, M. e Newman, M. E. (2002). Community structure in social and biological networks. Proceedings of the National Academy of Sciences, 99(12):7821–7826.
Guimera, R., Danon, L., Diaz-Guilera, A., Giralt, F., e Arenas, A. (2003). Selfsimilar community structure in a network of human interactions. Physical Review E, 68(6):065103.
Harenberg, S., Bello, G., Gjeltema, L., Ranshous, S., Harlalka, J., Seay, R., Padmanabhan, K., e Samatova, N. (2014). Community detection in large-scale networks: a survey and empirical evaluation. Wiley Interdisciplinary Reviews: Computational Statistics, 6(6):426–439.
Joshi-Tope, G., Gillespie, M., Vastrik, I., D’Eustachio, P., Schmidt, E., de Bono, B., Jassal, B., Gopinath, G., Wu, G., Matthews, L., et al. (2005). Reactome: a knowledgebase of biological pathways. Nucleic Acids Research, 33(suppl_1):D428–D432.
Khan, B. S. e Niazi, M. A. (2017). Network community detection: A review and visual survey. CoRR, abs/1708.00977.
Kwak, H., Lee, C., Park, H., e Moon, S. (2010). What is twitter, a social network or a news media? In Proc. 19th Int. Conf. on World Wide Web, pages 591–600. ACM.
Lancichinetti, A. e Fortunato, S. (2009). Community detection algorithms: a comparative analysis. Physical Review E, 80(5):056117.
Leskovec, J. e Krevl, A. (2014). SNAP Datasets: Stanford large network dataset collection. [link].
Leskovec, J., Lang, K. J., e Mahoney, M. (2010). Empirical comparison of algorithms for network community detection. In Proc. 19th Int. Conf. on World Wide Web, pages 631–640. ACM.
Mislove, A., Marcon, M., Gummadi, K. P., Druschel, P., e Bhattacharjee, B. (2007). Measurement and analysis of online social networks. In Proc. 7th ACM SIGCOMM Conf. on Internet Measurement, pages 29–42. ACM.
Newman, M. E. (2006). Modularity and community structure in networks. Proc. National Academy of Sciences, 103(23):8577–8582.
Ozaki, N., Tezuka, H., e Inaba, M. (2016). A simple acceleration method for the Louvain algorithm. Int. Journal of Computer and Electrical Engineering, 8(3):207.
Peng, C., Kolda, T. G., e Pinar, A. (2014). Accelerating community detection by using k-core subgraphs. arXiv preprint arXiv:1403.2226.
Satuluri, V., Parthasarathy, S., e Ruan, Y. (2011). Local graph sparsification for scalable clustering. In Proc. ACM SIGMOD Int. Conf. on Management of Data, pages 721–732.
Yang, J. e Leskovec, J. (2015). Defining and evaluating network communities based on ground-truth. Knowledge and Information Systems, 42(1):181–213.
Zhao, Y. (2017). A survey on theoretical advances of community detection in networks. Wiley Interdisciplinary Reviews: Computational Statistics, 9(e1403):1–13.
Publicado
22/07/2018
Como Citar
CARNIVALI, Gustavo S.; VIEIRA, Alex B.; ESQUEF, Paulo A. A.; ZIVIANI, Artur.
Método Rápido de Agrupamento de Vértices para Detecção de Comunidades em Redes Complexas de Larga-escala. In: WORKSHOP EM DESEMPENHO DE SISTEMAS COMPUTACIONAIS E DE COMUNICAÇÃO (WPERFORMANCE), 17. , 2018, Natal.
Anais [...].
Porto Alegre: Sociedade Brasileira de Computação,
2018
.
p. 248-261.
ISSN 2595-6167.
DOI: https://doi.org/10.5753/wperformance.2018.3332.
