A Science Gateway to Support Research in Spectral Graph Theory
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
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
Como Citar
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.
