Nós últimos meses eu tenho estudado grafo intensamente por causa do meu mestrado. O primeiro contato veio através de uma disciplina chamada Ciência das Redes onde sistemas do mundo real eram mapeados em formato de rede para que pudessem ser estudados. Agora estou revendo na disciplina de Redes Sem Fio com um enfoque completamente diferente. Nesse post eu vou descrever brevemente o que aprendi nas duas disciplinas e como grafos podem ser utilizados.

Ciência das Redes

Antes de falar de grafos precisamos falar de Redes. O que são redes? Redes são formas de se modelar sistemas complexos na forma de grafos. O exemplo mais simples são uma redes de amizades em uma rede social. Vamos supor que temos uma rede social e nela as pessoas adicionam as suas relações de amizades. Para modelar um grafo a partir das informações dessa rede devemos considerar que cada pessoa é um nó e cada relação de amizade é uma aresta. Como na nossa rede consideramos a relação de amizade como mútua o grafo não é direcionado, mas se nessa rede ao invés de relações de amizade tivéssemos apenas a opção de seguir, o grafo deveria ser direcionado.

Então na nossa rede sabemos que Alice é amiga de Carlos e Daniela e Bob é amigo de Carlos e Daniela. Na figura abaixo temos como ficaria a representação dessas relações de amizade.

Alice e Bob

Curioso do porque usei Alice e Bob? São nomes comuns na computação. Sempre que for descrever qualquer comunicação, use nomes de pessoas pela ordem das letras do alfabeto. Eu costumo alternar entre o nome de uma mulher e um homem: Alice, Bob, Carlos, Daniela. É um clássico na computação!

Agora talvez você esteja se perguntando: tá, e daí? Pra que serve isso? Modelar sistemas complexos na forma de grafo serve como meio de se estudar esses sistemas, podendo se caracterizar eles e até descobrir informações valiosas como a sugestões de arestas e até a criação de comunidades.

Quando falamos de Ciência das Redes não estamos muito interessados em algoritmos de grafos, mas na caracterização e extração de informações da redes. Essa não é uma disciplina somente de computação, mas é uma disciplina que sempre será multidisciplinar.

Enquanto cursava a disciplina eu precisei fazer uma analise de alguma rede e para isso escolhi a base de dados da Yelp e fiz uma análise de similaridade procurando relações entre revisões de usuários e relações da amizade. Um dos meus pressupostos ao começar a fazer essa análise era que amigos vão aos mesmos lugares e tem opiniões simulares sobre esses lugares, e consegui provar isso usando Correlação de Pearson. Se quiser ler o artigo eu compartilhei ele no researchgate.net: Análise de Similaridade do Dataset Yelp. Essa análise foi feita usando a biblioteca NetworkX do Python, porém se eu fosse implementar funcionalidades de redes em sistemas de produção usaria o Neo4J e Java. Durante os estudos eu consegui modelar essa rede usando Neo4J e o tempo de carga é bem mais rápido que em Python, tanto que a primeira tarefa que tive na análise foi criar um subconjunto para que pudesse fazer as análises pois era praticamente impossível carregar todo dataset em memória.

Essa disciplina me deu umas boas ideias sobre o tipo de sistemas que eu trabalho. Como você deve saber eu trabalho com um framework de processamento de dados distribuídos do Core 5G usando Kafka. Eu não trabalho com a implantação desses sistemas, mas acabo tento contato com os times que implementa pipelines de transformações de dados gerados pelos sistemas PCF e CHF. Esses sistemas geram mensagens que são transformadas, associadas a outras e geram informações de cobrança e acesso. O único sistema que vi o pipeline completo era o sistema corporativo de uma grande operadora no mundo e um dos casos de uso era calcular se os assinantes de uma determinada empresa ainda tinha acesso a um serviço. Em telefonia o gasto de banda é separado por serviço e alguns são ilimitados e outros são limitados, ao se usar toda a cota a operadora pode cortar o acesso ou reduzir a velocidade. Essa operadora em especifico implementa no sistema corporativo cotas por assinante e a empresa pode disparar um algoritmo de redistribuir a cota durante o mês. Nesse pipeline existiam muitos tópicos e muitos serviços, alguns com alto processamento e algoritmos bem complexos. A ideia que eu tive foi: e se eu modelasse esses sistemas como uma rede?

Imagina uma arquitetura distribuída usando Apache Kafka, cada tópico é um nó e cada Produtor, Consumidor e Stream é uma aresta. A informação flui de um nó para outros através dos processos em execução. Eu ainda não trabalhei nessas ideias, e talvez nem consiga trabalhar no curto prazo.

Se quiser saber mais sobre Ciência das Redes recomendo que leia o livro Network Science de Albert-Lásló Barabási (tá disponível online de graça). Nesse livro os conceitos são bem trabalhados e você consegue aplicar eles facilmente usando a biblioteca NetworkX.

Redes Sem Fio

Redes sem fio também é uma disciplina que se usa bastante algoritmos de grafos. Mas ao contrário do que temos em Ciência das Redes aqui o ponto de vista é outro. Grafos são usados para se modelar a topologia de uma rede sem fio. Talvez você esteja pensando porque modelar sua rede Wi-Fi como um grafo, certo? Seu Wi-Fi é com certeza uma rede sem fio, mas ele não é o único exemplo que temos.

Para você entender melhor o desafio de uma rede sem fio vou falar sobre o caso de uso de uma empresa que já trabalhei. Alguns anos atrás trabalhei no desenvolvimento de uma plataforma de IIoT (IoT Industrial). A empresa tinha um produto que era um dispositivo inteligente que conectava dispositivos não tão inteligentes. Por exemplo, o leitor de energia usado pelas distribuidoras tem uma porta serial para se comunicar, mas não tem acesso a internet e nem tem a capacidade de se instalar programas. Nosso dispositivo acessava o leitor diretamente e conectava ele ao sistema da distribuidora permitindo que operações como leitura, atualização de firmware, verificação de integridade e até detecção de roubo de energia seja identificado. Esse leitor é usado nos grandes clientes como shoppings, fábricas e condomínios.

No caso de leitura de energia não há a necessidade de se usar algoritmos de grafos pois nesses clientes sempre se terá sinal de 4G/5G, e infelizmente o único caso que eu implantei. Mas a empresa tinha um outro caso de uso bem comum que é o uso para se conectar sensores de monitoramento agrícola. Nesse caso os sensores são distribuídos em uma área muito extensa e sem sinal de telefonia.

Aí jogo a pergunta: como fazer para que um dispositivo remoto consiga se conectar quando o acesso a rede é escasso? A resposta para essa pergunta é o que estudamos em Redes sem Fio!

Na disciplina estudamos como se caracteriza uma rede sem fio e uma série de algoritmos de roteamento de mensagens. Faça um exercício aí… Se eu tenho 100 dispositivos distribuídos em uma grande área com acesso restrito a conexão de internet, nem todos os dispositivos vão ter acesso a internet, mas os dispositivos vão ter acesso a se comunicar um com o outro. Como que eu garanto que todos os dispositivos estejam conectados? Eu tenho que rotear essa conexão. E era assim que resolvíamos o problema de conexão na empresa que trabalhei. Nem sempre o dispositivo tinha acesso a rede, mas se ele acessasse um dispositivo com acesso a rede ele podia enviar mensagens para a plataforma na nuvem.

Para essa disciplina eu fiz um fork de uma biblioteca do JavaFX para exibição de grafos e fiz uma série de melhorias, inclusive implementar o Dijkstra. Mas essa biblioteca é apenas para visualização, ela não poderia ser utilizada nos dispositivos remotos por 2 motivos: (i) a rede pode não ser estática mudando a sua topologia o tempo inteiro e (ii) um elemento da rede pode não conhecer a rede inteira.

E como se faz para que um dispositivo conheça a rede e saiba como rotear mensagens? A resposta vai depender do caso de uso e das características do dispositivo, mas a forma que eu implementei foi por passagem de mensagens. Um dispositivo terá que enviar uma mensagem a todos os seus vizinhos se apresentando e dizendo que ainda está acessível e quando um dispositivo recebe essa mensagem deve retornar dizendo que esse é o caminho mais rápido até o dispositivo. É óbvio que um dispositivo receberá várias mensagens, mas só a primeira deve ser respondida por esse é o caminho mais curto.

Juntando tudo…

E como vou usar isso em minha pesquisa? Eu não tenho a mínima ideia e nem me importo em não ter essa resposta. Redes sem fio são muito importantes e vão ficar cada vez mais populares. IoT virou hype uns 5 ou 6 anos atrás, mas a hype era em casos de usos forçados. Por exemplo, teve uma empresa de delivery que criou um botão que a única função era refazer o último pedido. Hoje a ideia parece ridícula, e obviamente era! Essas ideias e outras tão ridículas quanto serviram para se promover alguns pessoas e popularizar a ideia que IoT era só uma bobeira. Mas estão surgindo várias oportunidades de automatização e dispositivos conectados são o foco das implantações 5G. O 4G conseguiu entregar aquilo que era impensável 12 anos atrás, usar o celular para se ver filmes e ouvir música conectado a internet, mas o 5G não foi desenvolvido pensando em você!

Um fato interessante é que quando o CMO (Chief Marketing Office) da empresa que eu trabalho veio ao Brasil, ele não veio diretamente para São Paulo, mas para o estado de Goiás! Todos os exemplos de uso de 5G focam em carros, máquinas agrícolas, fábricas inteligentes, hospitais, etc… É bem provável que em 10 anos você não veja diferença nenhuma em como seu celular acessa a internet mas seu carro vai acessar a internet diretamente.

E pensando nesses dispositivos, como será que podemos usar algoritmos de grafos neles?

E voltando as redes? Como podemos usar o conhecimento de ciência das redes no nosso dia a dia? Eu penso em usar ele para observabilidade de sistemas orientados a mensagens. Mas esse conhecimento pode ser usado para se modelar qualquer tipo de sistema do mundo real. A minha pergunta é: como você pode usar?