Introdução ao Spark GraphX e GraphFrames
O Apache Spark é dividido em diferentes módulos, tais quais o SQL e DataFrames para trabalhar com dados estruturados, Spark Streaming que facilita a construção de aplicações com dados em streaming, a MLib destinada aos algoritmos de Machine Learning e a GraphX que é voltada para o processamento de Grafos. Todas essas bibliotecas são otimizadas para processamento paralelo, escalabilidade e tolerância a falhas.
O objetivo desse artigo é apresentar uma introdução ao módulo GraphX com Python e GraphFrames, e exemplificar possíveis aplicações que podem ser realizadas ao trabalhar com dados em Grafos.
Mas o que são Grafos?
Basicamente, um grafo é uma estrutura de dados que modela relações (chamadas de arestas) entre objetos (chamados de vértices ou nós). Dessa forma, muitos fenômenos ou estruturas podem ser modeladas com a ajuda de grafos, o exemplo mais simples são as Redes Sociais.
Em que os vértices são as pessoas e as arestas são as relações de amizade. Eventualmente um grafo pode conter pesos nas arestas, que indicam a força dessa ligação.
Outros exemplos que podem ser modelas como grafos são:
- Redes de computadores, onde os computadores são os vértices e as ligações entre eles são as arestas
- Mapas de páginas, onde as páginas são os vértices e os hiperlinks são as arestas
- Trajeto entre cidades, onde as cidades são os vértices e as estradas são as arestas
De forma geral qualquer relação entre objetos pode ser modelado como um Grafo. A parte boa é que essa estrutura de dados garante uma série de propriedades interessantes e facilita o entendimento do problema, a parte ruim é que trabalhar com grafos requer um alto custo computacional. É por esses motivos que o Spark implementa a análise de Grafos através do módulo de GraphX, para fornecer uma interface escalável e tolerante a falha dentro da estrutura de BigData.
Apache GraphX e GraphFrames
O GraphX reutiliza o conceito do Spark RDD, simplifica as tarefas de análise de gráficos, fornece a capacidade de realizar operações em Grafos direcionados e com propriedades anexadas a cada vértice e aresta. Existem muitos algoritmos em teoria de grafos que são amplamente utilizados em análise de dados e ciência da computação, desde redes de computadores até mecanismos de busca e redes sociais.
A biblioteca GraphFrames (https://graphframes.github.io/) estende a GraphX e cria uma interface de alto-nível para o Python, simplifica a API e adiciona algoritmos e otimizações para utilização da GraphX.
Exemplo de Análise em Grafos
Vamos considerar um exemplo de como usar o GraphFrames para analisar Grafos semelhantes a redes sociais. O código completo pode ser encontrado em:
Os dados de entrada para o nosso grafo de redes sociais são:
- User.csv, contendo os dados do usuário (os vértices)
- UserGraph.csv, contendo os dados das conexões entre os usuários (as arestas)
Os dados de usuário são: “ID” e “NAME”. O GraphFrames por obrigação espera uma coluna “id” como identificado do vértice.
Os dados de conexão (arestas) entre os usuários tem as colunas “USER_1” e “USER_2”. Para importação no GraphFrames o nome das colunas devem mudar para “src” que indica origem da aresta e “dst” que é o destino da aresta.
Utilizando os dois DataFrames “user_df” com os vértices e o “user_graph_df” com as arestas é possível criar um GraphFrame(vertices<DataFrame>, arestas<DataFrame>), classe responsável por representar o Grafo.
Vamos encontrar os usuários mais conectados em nossa rede social, para isso podemos utilizar três funções diferentes: GraphFrame.inDegrees, GraphFrame.outDegrees e GraphFrame.degrees.
A função “.inDegrees” retorna o total de arestas que estão conectadas ao usuário no sentido (a) -> (b), que saem dos outros usuários (a) e conectam no usuario (b), e a “.outDegrees” o inverso. A “.degress” contabiliza as duas direções.
Para nossa rede social, o usuário “Hallie” tem um total de 1933 usuários conectados a ele, o que o torna a pessoa mais influente da rede.
Motif Finding
Uma das coisas mais legais na GraphFrames é o Motif Finding, que é a busca baseada em padrões estruturais de um grafo. Por exemplo,
graph.find (“(a)-[e] -> (b); (b)-[e2] -> (a)”)
procurará pares de vértices a, b conectados por arestas em ambas as direções. Dessa forma podemos montar qualquer consulta pensando apenas na estrutura do grafo.
Vamos descobrir quais são os 1933 usuários conectados a “Hallie” usando a estrutura “(a)-[e]->(b)”. Que significa buscar um vértice qualquer “a”, que deve estar ligado por uma aresta “e” a um vértice qualquer “b” filtrando pelo “id”.
Estruturas mais complexas podem ser utilizadas para identificar “pessoas que talvez você conheça”. Afinal, um amigo de um amigo meu talvez seja meu amigo. A estrutura para essa consulta é:
graph.find (“(a)-[e]->(b); (b)-[e2]->(c); !(a)-[]->(c)”)
onde, queremos um usuário “a” que tenha conexão com “b” (a)-[e]->(b), sendo que “b” tem conexão com “c” (b)-[e2]->(c), mas “a” e “c” não tenha conexão !(a)-[]->(c).
Dessa forma podemos encontrar estruturas semelhantes a descrita abaixo, em que “Winnie” está conectado com “Edward”, “Dora” e “Josiah”, que estão conectados com “Finley”, mas “Finley” não está conectado com “Winnie”.
A busca utilizando Motif Finding permite flexibilidade e simplicidade para trabalhar com Grafos complexos, em conjunto com o Spark garante também escalabilidade nas consultas.
Conclusão
Nesse artigo foi possível abordar algumas funcionalidades da GraphFrames, desde construir Grafos a partir de dados brutos, até utilizar a Motif Finding para buscas mais complexas. A GraphFrames e GraphX são uma ótima alternativa para criar, analisar e processar estruturas em grafos usando o Spark, o que pode facilitar a abordagem em algumas categorias de problemas em Data Análises.
Todo o código utilizando nesse artigo está no meu repositório GitHub.
