Analisando a Escalabilidade e a Acurácia de Implementações Paralelas e Distribuídas para a Detecção de Comunidades em Grafos
Resumo
Detecção de comunidades em grafos é um tipo de análise amplamente utilizada por aplicações de diversas áreas do conhecimento. Com o crescente aumento do volume de dados surge a necessidade de implementações paralelas e distribuídas para que o tempo de processamento não aumente a ponto de limitar sua aplicabilidade. Este estudo analisa a escalabilidade e a acurácia dos métodos para detecção de comunidades mais utilizados atualmente em ambientes paralelos e distribuídos. A partir de uma análise detalhada do impacto que a comunicação entre os processos teve no tempo de execução de cada implementação são feitas recomendações em relação aos algoritmos mais promissores em relação a melhoria da escalabilidade nestes ambientes.Referências
Agreste, S., De Meo, P., Fiumara, G., Piccione, G., Piccolo, S., Rosaci, D., Sarne, G. M., and Vasilakos, A. V. (2016). An empirical comparison of algorithms to find communities in directed graphs and their application in web data analytics. IEEE transactions on big data, 3(3):289–306.
Bae, S.-H., Halperin, D., West, J., Rosvall, M., and Howe, B. (2013). Scalable flow-based community detection for large-scale network analysis. In 2013 IEEE 13th International Conference on Data Mining Workshops, pages 303–310.
Blondel, V. D., Guillaume, J.-L., Lambiotte, R., and Lefebvre, E. (2008). Fast unfolding of communities in large networks. Journal of statistical mechanics: theory and experiment, 2008(10):P10008.
Fan, W., Xu, J., Wu, Y., Yu, W., and Jiang, J. (2017). Grape: Parallelizing sequential graph computations. Proceedings of the VLDB Endowment, 10(12):1889–1892.
Faysal, M. A. M., Arifuzzaman, S., Chan, C., Bremer, M., Popovici, D., and Shalf, J. (2021). Hypc-map: A hybrid parallel community detection algorithm using information-theoretic approach. In 2021 IEEE High Performance Extreme Computing Conference (HPEC), pages 1–8. IEEE.
Fortunato, S. and Hric, D. (2016). Community detection in networks: A user guide. Physics reports, 659:1–44.
Ghosh, S., Halappanavar, M., Tumeo, A., Kalyanaraman, A., Lu, H., Chavarrià-Miranda, D., Khan, A., and Gebremedhin, A. (2018). Distributed louvain algorithm for graph community detection. In 2018 IEEE International Parallel and Distributed Processing Symposium (IPDPS), pages 885–895.
Iosup, A., Hegeman, T., Ngai, W. L., Heldens, S., Prat-Pérez, A., Manhardto, T., Chafio, H., Capotă, M., Sundaram, N., Anderson, M., et al. (2016). Ldbc graphalytics: A benchmark for large-scale graph analysis on parallel and distributed platforms. Proceedings of the VLDB Endowment, 9(13):1317–1328.
Kao, E., Gadepally, V., Hurley, M., Jones, M., Kepner, J., Mohindra, S., Monticciolo, P., Reuther, A., Samsi, S., Song, W., Staheli, D., and Smith, S. (2017). Streaming graph challenge: Stochastic block partition. In 2017 IEEE High Performance Extreme Computing Conference (HPEC), pages 1–12.
Lancichinetti, A., Fortunato, S., and Radicchi, F. (2008). Benchmark graphs for testing community detection algorithms. Physical review E, 78(4):046110.
Leskovec, J. and Krevl, A. (2014). SNAP Datasets: Stanford large network dataset collection. http://snap.stanford.edu/data.
Lu, H., Halappanavar, M., and Kalyanaraman, A. (2015). Parallel heuristics for scalable community detection. Parallel Computing, 47:19–37.
Naik, D., Ramesh, D., Gandomi, A. H., and Gorojanam, N. B. (2022). Parallel and distributed paradigms for community detection in social networks: A methodological review. Expert Systems with Applications, 187:115956.
Newman, M. E. J. and Girvan, M. (2004). Finding and evaluating community structure in networks. Phys. Rev. E, 69:026113.
Rossi, R. A. and Ahmed, N. K. (2015). The network data repository with interactive graph analytics and visualization. In AAAI.
Rosvall, M., Axelsson, D., and Bergstrom, C. T. (2009). The map equation. The European Physical Journal Special Topics, 178(1):13–23.
Sobin, C., Raychoudhury, V., and Saha, S. (2017). A survey of parallel community detection algorithms. In Handbook of Research on Applied Cybernetics and Systems Science, pages 1–26. IGI Global.
Staudt, C. L. and Meyerhenke, H. (2016). Engineering parallel algorithms for community detection in massive networks. IEEE Transactions on Parallel and Distributed Systems, 27(1):171–184.
Staudt, C. L., Sazonovs, A., and Meyerhenke, H. (2016). Networkit: A tool suite for large-scale complex network analysis. Network Science, 4(4):508–530.
Bae, S.-H., Halperin, D., West, J., Rosvall, M., and Howe, B. (2013). Scalable flow-based community detection for large-scale network analysis. In 2013 IEEE 13th International Conference on Data Mining Workshops, pages 303–310.
Blondel, V. D., Guillaume, J.-L., Lambiotte, R., and Lefebvre, E. (2008). Fast unfolding of communities in large networks. Journal of statistical mechanics: theory and experiment, 2008(10):P10008.
Fan, W., Xu, J., Wu, Y., Yu, W., and Jiang, J. (2017). Grape: Parallelizing sequential graph computations. Proceedings of the VLDB Endowment, 10(12):1889–1892.
Faysal, M. A. M., Arifuzzaman, S., Chan, C., Bremer, M., Popovici, D., and Shalf, J. (2021). Hypc-map: A hybrid parallel community detection algorithm using information-theoretic approach. In 2021 IEEE High Performance Extreme Computing Conference (HPEC), pages 1–8. IEEE.
Fortunato, S. and Hric, D. (2016). Community detection in networks: A user guide. Physics reports, 659:1–44.
Ghosh, S., Halappanavar, M., Tumeo, A., Kalyanaraman, A., Lu, H., Chavarrià-Miranda, D., Khan, A., and Gebremedhin, A. (2018). Distributed louvain algorithm for graph community detection. In 2018 IEEE International Parallel and Distributed Processing Symposium (IPDPS), pages 885–895.
Iosup, A., Hegeman, T., Ngai, W. L., Heldens, S., Prat-Pérez, A., Manhardto, T., Chafio, H., Capotă, M., Sundaram, N., Anderson, M., et al. (2016). Ldbc graphalytics: A benchmark for large-scale graph analysis on parallel and distributed platforms. Proceedings of the VLDB Endowment, 9(13):1317–1328.
Kao, E., Gadepally, V., Hurley, M., Jones, M., Kepner, J., Mohindra, S., Monticciolo, P., Reuther, A., Samsi, S., Song, W., Staheli, D., and Smith, S. (2017). Streaming graph challenge: Stochastic block partition. In 2017 IEEE High Performance Extreme Computing Conference (HPEC), pages 1–12.
Lancichinetti, A., Fortunato, S., and Radicchi, F. (2008). Benchmark graphs for testing community detection algorithms. Physical review E, 78(4):046110.
Leskovec, J. and Krevl, A. (2014). SNAP Datasets: Stanford large network dataset collection. http://snap.stanford.edu/data.
Lu, H., Halappanavar, M., and Kalyanaraman, A. (2015). Parallel heuristics for scalable community detection. Parallel Computing, 47:19–37.
Naik, D., Ramesh, D., Gandomi, A. H., and Gorojanam, N. B. (2022). Parallel and distributed paradigms for community detection in social networks: A methodological review. Expert Systems with Applications, 187:115956.
Newman, M. E. J. and Girvan, M. (2004). Finding and evaluating community structure in networks. Phys. Rev. E, 69:026113.
Rossi, R. A. and Ahmed, N. K. (2015). The network data repository with interactive graph analytics and visualization. In AAAI.
Rosvall, M., Axelsson, D., and Bergstrom, C. T. (2009). The map equation. The European Physical Journal Special Topics, 178(1):13–23.
Sobin, C., Raychoudhury, V., and Saha, S. (2017). A survey of parallel community detection algorithms. In Handbook of Research on Applied Cybernetics and Systems Science, pages 1–26. IGI Global.
Staudt, C. L. and Meyerhenke, H. (2016). Engineering parallel algorithms for community detection in massive networks. IEEE Transactions on Parallel and Distributed Systems, 27(1):171–184.
Staudt, C. L., Sazonovs, A., and Meyerhenke, H. (2016). Networkit: A tool suite for large-scale complex network analysis. Network Science, 4(4):508–530.
Publicado
17/10/2023
Como Citar
SANTOS, Gabriel G.; DE ROSE, César A. F.; LAKHOTIA, Kartik.
Analisando a Escalabilidade e a Acurácia de Implementações Paralelas e Distribuídas para a Detecção de Comunidades em Grafos. In: SIMPÓSIO EM SISTEMAS COMPUTACIONAIS DE ALTO DESEMPENHO (SSCAD), 24. , 2023, Porto Alegre/RS.
Anais [...].
Porto Alegre: Sociedade Brasileira de Computação,
2023
.
p. 157-168.
DOI: https://doi.org/10.5753/wscad.2023.235941.
