Análise de dados em instâncias do problema do corte máximo em grafos

• Jailon W. B. Oliveira da Silva UFC
• Carlos V. Dantas Araújo UFC
• Pablo L. Braga Soares UFC

DOI: https://doi.org/10.5753/ercemapi.2024.243782

Resumo

O problema do corte máximo é um dos problema centrais na otimização combinatória, com diversas aplicações práticas. Este trabalho tem como objetivo realizar uma análise exploratória de instâncias de grafos para esse problema, utilizando a Biq Mac Library. Para isso, características dos grafos foram extraídas e analisadas por meio de técnicas estatísticas e de visualização para identificar padrões e anomalias. Os resultados mostram correlações significativas entre algumas métricas e identificam outliers que podem influenciar a solução do problema. Conclui-se que a análise fornece uma base de entendimento sólida a cerca das instâncias e torna viável o desenvolvimento de modelos preditivos de aprendizado de máquina para o problema do corte máximo.

Referências

Agrawal, R., Rajagopalan, S., Srikant, R., and Xu, Y. (2003). Mining newsgroups using networks arising from social behavior. In Proceedings of the 12th international conference on World Wide Web, pages 529–535.

Almeida, A. N. and Martins, S. D. (2023). Evolução da qualidade dos planos de mitigação e monitoramento nos estudos de impacto ambiental. Revista Gestão & Sustentabilidade Ambiental, 12(1):e12355–e12355.

Barabási, A.-L. (2016). Network Science. Cambridge University Press.

Barahona, F., Grötschel, M., Jünger, M., and Reinelt, G. (1988). An application of combinatorial optimization to statistical physics and circuit layout design. Operations Research, 36(3):493–513.

Boros, E. and Hammer, P. L. (1991). The max-cut problem and quadratic 0–1 optimization; polyhedral aspects, relaxations and bounds. Annals of Operations Research, 33(3):151–180.

Diestel, R. (2017). Graph Theory. Springer.

Ferreira, M. M. C. (2022). Quimiometria iii-revisitando a análise exploratória dos dados multivariados. Química Nova, 45(10):1251–1264.

Jebb, A. T., Parrigon, S., Woo, S. E., and Loving, J. L. (2016). Exploratory data analysis and visualization: A way to extract knowledge from complex data. Journal of Computational Science, 18:3–15.

Latora, V., Nicosia, V., and Russo, G. (2017). Complex Networks: Principles, Methods and Applications. Cambridge University Press, Cambridge.

Lin, M., Xu, W., Lin, Z., and Chen, R. (2020). Determine owa operator weights using kernel density estimation. Economic research-Ekonomska istraživanja, 33(1):1441–1464.

Moore, D. S., McCabe, G. P., and Craig, B. A. (2009). Introduction to the Practice of Statistics, volume 4. WH Freeman New York.

Otterbach, J. S., Manenti, R., Alidoust, N., Bestwick, A., Block, M., Bloom, B., Caldwell, S., Didier, N., Fried, E. S., Hong, S., et al. (2017). Unsupervised machine learning on a hybrid quantum computer. arXiv preprint arXiv:1712.05771.

Shrimali, N. P. and Shah, N. H. (2020). Recent Advancements in Graph Theory. CRC Press, Boca Raton.

Sousa, S., Haxhimusa, Y., and Kropatsch, W. G. (2013). Estimation of distribution algorithm for the max-cut problem. In Graph-Based Representations in Pattern Recognition: 9th IAPR-TC-15 International Workshop, GbRPR 2013, Vienna, Austria, May 15-17, 2013. Proceedings 9, pages 244–253. Springer.

Wiegele, A. (2007). Biq mac library—a collection of max-cut and quadratic 0-1 programming instances of medium size. Preprint, 51.

Wongsuphasawat, K., Liu, Y., and Heer, J. (2019). Goals, process, and challenges of exploratory data analysis: An interview study. arXiv preprint arXiv:1911.00568.