Faça a Teoria dos Grafos trabalhar para a sua empresa

Se você é da área da Matemática ou da Computação, é provável que já tenha ouvido falar sobre a Teoria dos Grafos. Caso contrário, saiba que grafos são estruturas (matemáticas ou de dados, dependendo da área em questão) que estuda as relações entre objetos de um conjunto, formado por vértices e arestas. No esquema abaixo, temos três vértices e três arestas. Cada aresta obrigatoriamente liga dois vértices. No caso, temos que Joãozinho conhece Enzo. Já Enzo conhece tanto Sophia quanto o próprio Joãozinho. Mas Joãozinho e Sophia não se conhecem. Como as arestas possuem direção de relacionamento, dizemos que esse grafo é direcionado.

Os vértices não necessariamente precisam ser pessoas, nem as arestas, relacionamentos de amizade. Poderíamos ter lugares que se conectam por linhas de metrô, empresas envolvidas na operação Lava-Jato ou partidos políticos e suas coligações.

Gigantes de Tecnologia como Facebook e Google fazem uso da Teoria dos Grafos em suas aplicações, sendo as mais notáveis as sugestões de amigos de seus amigos na empresa do Zuckerberg e a definição da melhor rota no Google Maps. Mas o que isso tem a ver com o comércio eletrônico?

Bom, passamos recentemente pela Black Friday, um evento muito aguardado pelas lojas e por compradores atentos aos descontos promovidos na data. Por conta disso, o tráfego de potenciais compradores nos sites dessas lojas aumenta consideravelmente durante o período, assim como a preocupação com o tempo de resposta das páginas, com o sucesso das compras e com os indesejáveis fraudadores.

Banco de Dados
No início do desenvolvimento do site de vendas, a loja deve considerar de que forma ela irá armazenar os dados que trafega. Dados como cadastro do comprador, informações do produto, detalhes de pagamento, forma de entrega, entre outros. O conceito mais utilizado é o Relacional (RDBMS), que provê uma estrutura tabular como as planilhas, mas oferece o relacionamento entre as tabelas.

Modelagem de Banco de Dados Relacional

Ironicamente o modelo Relacional é péssimo para lidar com relacionamento de dados, principalmente os que são frequentemente mutáveis como um usuário “seguir” outro no Twitter. Sua estrutura não é flexível, forçando as colunas a terem valores nulos. Além disso, sua performance deixa a desejar quando há relacionamento entre várias tabelas seguidas (múltiplos JOINs). Tente imaginar a performance de uma consulta em tempo real que responda: “quais clientes compraram esse produto também compraram aquele produto e quais são similares a esse último?”. Daí a ideia de modelar um banco com grafos.

Grafos ao Resgate
Há quem diga que a tecnologia de armazenamento de dados em grafos seja o futuro, mas ela já é o presente, só não nos atentamos a isso. O mundo é interconectado, portanto, temos relacionamentos em todas as partes e, como consequência, grafos em tudo. Estudos apontam que os grafos mapeiam de forma mais realista como o cérebro humano processa o mundo que nos rodeia. Dito isso, nada mais normal que modelar esses relacionamentos em um banco de dados que use o relacionamento como parte mais importante. Temos ainda as vantagens de uma abordagem mais performática, mais flexível e adaptável a mudanças.

Abaixo segue uma consulta por um produto cujo nome é Chocolate. Mais simples de entender os relacionamentos, não acha?

Banco de Dados Orientado a Grafos

Abaixo segue um experimento apresentado no livro “Neo4j in Action”, de Aleksa Vukotic e Nicki Watt, entre um banco de dados relacional e um banco de dados orientado grafo, no caso o Neo4j. Esse experimento fez uso de uma rede social básica para encontrar conexões de amigos de amigos em uma profundidade de até 5 graus. Foram considerados 1 milhão de pessoas com aproximadamente 50 amigos cada.

Benchmarking Banco de Dados Relacional vs Neo4j

Podemos perceber pela tabela acima que ao analisar 4 graus de profundidade de amizade, temos um tempo de execução de pouco mais de 1 segundo no Neo4j e cerca de 25 minutos em um banco de dados relacional. Para 5 graus, esqueça.

Sistemas de Recomendação
Um dos grandes beneficiados com a modelagem em grafo é o sistema de recomendação de uma loja. Como você provavelmente sabe, nos últimos anos, as lojas vêm melhorando sua eficiência em vendas online graças as técnicas de recomendações personalizadas, que além de auxiliar na redução da quantidade de itens apresentados a um comprador, um sistema de recomendação também aprende com o comportamento de navegação pelas páginas e dados de compra.

Quando um site apresenta “Quem comprou esse produto, também comprou esse”, ou “Itens relacionados ao seu histórico de navegação”; os usuários e itens são vértices do grafo e os eventos de comprar ou visualizar um produto são as arestas. Assim, quando você navega em um site de uma loja que faz uso de sistemas de recomendação, muito provavelmente ela está usando a modelagem em grafos para entender o seu relacionamento com os produtos para te oferecer uma recomendação personalizada.

Logística
Outra grande aplicação dos grafos está no estudo de geolocalização. Imagine agora que você é o dono de uma loja online e que precisa entregar produtos para o Rio de Janeiro e São Paulo. Como você poderia garantir uma entrega de 48h em um período de alta demanda como a Black Friday, se seu centro de distribuição é em Minas Gerais? Bom, sua estratégia de logística tem que ser muito boa, mas também precisará de algoritmos de grafos para otimizar o caminho (aresta) de suas entregas desde os galpões de armazenamento (vértice) até o destino (outro vértice), no caso o endereço do comprador, seja no Rio ou em São Paulo.

Conclusão
Podemos perceber que essa tecnologia é extremamente interessante para o e-commerce, mas não para por aí. Diversas organizações estão utilizando grafos para modelar redes sociais, análise de fraude, campanhas eleitorais e até para evitar a proliferação de doenças. Mesmo que não haja uma solução que encaixe em todos os problemas, é indiscutível que os grafos são extremamente úteis para dados capturados na Internet.

(*) Henrique Santana é Cientista de Dados da Braspag