A Science Gateway to Support Research in Spectral Graph Theory

  • Daniel Oliveira CEFET-RJ
  • Carlos Magno Abreu CEFET-RJ
  • Eduardo Ogasawara CEFET-RJ
  • Eduardo Bezerra CEFET-RJ
  • Leonardo de Lima UFPR

Resumo


Describing classes of graphs that optimize a function of the eigenvalues subject to some constraints is one of the topics addressed by Spectral Graph Theory (SGT). In this paper, we propose RioGraphX, a science gateway developed on top of Apache Spark, which aims to obtain all graphs that optimize a given mathematical function of the eigenvalues of a graph. Initial experiments involving small graphs have pointed out optimal graphs in a reasonable computational time, and also have shown that leveraging parallel processing is a promising approach to handle larger graphs.

Palavras-chave: Spectral graph theory, data processing workflow, spark, science gateway

Referências

Armbrust et al. (2015). Spark sql: Relational data processing in spark. ACM. DOI: http://dx.doi.org/10.1145/2723372.2742797.

Bomze, I. M., Budinich, M., Pardalos, P. M., and Pelillo, M. (1999). The maximum clique problem. In Handbook of combinatorial optimization, pages 1–74. Springer.

Brankov, V., Cvetkovi´c, D., Simi´c, S., and Stevanovi´c, D. (2006). Simultaneous editing and multilabelling of graphs in system newgraph. DOI: https://doi.org/10.2298/petf0617112b

Caporossi, G. and Hansen, P. (2000). Variable neighborhood search for extremal graphs: 1 the autographix system. Discrete Mathematics, 212(1-2):29–44. DOI: https://doi.org/10.1016/s0012-365x(99)00206-x

Cvetkovic, D., Rowlinson, P., and Simic, S. K. (2007). Eigenvalue bounds for the signless laplacian. Publications de l’Institut Mathématique, 81(95):11–27. DOI: https://doi.org/10.2298/pim0795011c

Cvetkovi´c, D. and Simi´c, S. (2011). Graph spectra in computer science. Linear Algebra and its Applications, 434(6):1545–1562. DOI: https://doi.org/10.1016/j.laa.2010.11.035

Cvetkovi´c, D. M. (1971). Graphs and their spectra. Publikacije Elektrotehniˇckog fakulteta. Serija Matematika i fizika, (354/356):1–50.

Dave et al. (2016). Graphframes: an integrated api for mixing graph and relational queries. In Proceedings of the Fourth International Workshop on Graph Data Management Experiences and Systems, page 2. ACM. DOI: https://doi.org/10.1145/2960414.2960416

Ghebleh, M., Kanso, A., and Stevanovi´c, D. (2019). Graph6java: A researcher–friendly java framework for testing conjectures in chemical graph theory. MATCH.

Gregor, D. and Lumsdaine, A. (2005). The parallel bgl: A generic library for distributed graph computations. Parallel Object-Oriented Scientific Computing (POOSC), 2:1–18.

Grijó, R. et al. (2019). Nordhaus–gaddum type inequalities for the two largest Laplacian eigenvalues. Discrete Applied Mathematics, 267:176–183. DOI: https://doi.org/10.1016/j.dam.2019.04.005

Hagberg, A., Swart, P., and S Chult, D. (2008). Exploring network structure, dynamics, and function using networkx. Technical report, LANL.

Mohar, B., Alavi, Y., Chartrand, G., and Oellermann, O. (1991). The laplacian spectrum of graphs. Graph theory, combinatorics, and applications, 2(871-898):12.

Vasilyev, A. and Stevanovi´c, D. (2014). Mathchem: a python package for calculating topological indices. MATCH Commun. Math. Comput. Chem, 71:657–680.

Wilf, H. S. (1967). The eigenvalues of a graph and its chromatic number. Journal of the London mathematical Society, 1(1):330–332. DOI: https://doi.org/10.1112/jlms/s1-42.1.330

Xin, R. S., Gonzalez, J. E., Franklin, M. J., and Stoica, I. (2013). Graphx: A resilient distributed graph system on spark. ACM. DOI: https://doi.org/10.1145/2484425.2484427

Zaharia et al. (2016). Apache spark: A unified engine for big data processing. Commun. ACM, 59(11):56–65. DOI: https://doi.org/10.1145/2934664
Publicado
07/10/2019
OLIVEIRA, Daniel; ABREU, Carlos Magno; OGASAWARA, Eduardo; BEZERRA, Eduardo; DE LIMA, Leonardo. A Science Gateway to Support Research in Spectral Graph Theory. In: SIMPÓSIO BRASILEIRO DE BANCO DE DADOS (SBBD), 34. , 2019, Fortaleza. Anais [...]. Porto Alegre: Sociedade Brasileira de Computação, 2019 . p. 217-222. ISSN 2763-8979. DOI: https://doi.org/10.5753/sbbd.2019.8826.