A tensão entre soldados britânicos e colonialistas americanos aumentava vertiginosamente na primavera de 1775. Na manhã de 19 de abril, algumas centenas de soldados britânicos marcharam para Boston para capturar armas escondidas e alguns líderes rebeldes. Marchando para o norte, passando por pequenas vilas de Lexington e Concord, os britânicos ficaram surpresos ao encontrar uma resistência feroz e organizada. Massacrados, eles bateram em retirada rumo a Boston sob uma importunação constante da milicia colonial.
Essa emergente rebelião foi um grande estímulo na confiança dos colonialistas e deu início à guerra pela independência americana contra os britânicos.
Mas como a milícia colonial foi avisada em tempo hábil para se juntar antes do avanço britânico? Na tarde de 18 de abril, um rapaz que trabalhava num estábulo em Boston ouviu um soldado britânico falar ao outro que haveria sérios problemas no dia seguinte. O rapaz correu com a notícia para a casa de um ourives chamado Paul Revere, que a recebeu com muita preocupação, já que não era o primeiro rumor sobre isso naquele dia. Mais cedo, ele havia escutado sobre uma movimentação estranha de muitos oficiais britânicos no píer de Boston. Tripulantes foram vistos se movimentando rapidamente nos navios atracados no píer. Muitos outros marinheiros foram vistos, naquela manhã, correndo como se fosse uma missão repentina. Revere ficou cada vez mais convencido de que os britânicos estavam preparando uma grande investida contra a cidade de Lexington, a noroeste de Boston, para prender os líderes colonialistas John Hancock e Samuel Adams, e depois para a cidade de Concord, para apoderar-se das armas e munições armazenadas pelas milicias locais.
Revere, então, decidiu que ele precisava avisar as comunidades no entorno de Boston de que os britânicos estavam a caminho, de forma que a milícia local pudesse se preparar. Ele montou em seu cavalo e iniciou sua jornada rumo a Lexington, que ficou conhecida como o “percurso da meia-noite”. Em duas horas ele cobriu 13 milhas. Ao longo do caminho, em cada vila, ele batia na porta dos moradores e espalhava a notícia aos líderes coloniais locais de que os britânicos estavam vindo e pedia que eles espalhassem o recado a outros. A notícia se espalhou como um vírus, já que todos aqueles informados por Revere enviavam seus próprios mensageiros até que toda a região estivesse informada. A notícia já estava em Lincoln à 1 hora da manhã, em Sudbury às 3 horas, em Andover, 40 milhas a noroeste de Boston, às 5 horas, e perto das 9 da manhã, em Ashby, a quase 60 milhas de Boston. Quando o exército britânico finalmente marchou em direção à Lexington, na manhã de 19 de abril de 1775, seu ataque encontrou uma resistência feroz e organizada. Naquele dia em Concord, os britânicos foram confrontados e derrotados pela milícia colonial e, a partir daí, veio a guerra revolucionária americana.
Um fato interessante, porém, é que na mesma noite um homem chamado William Dawes também cavalgou de Boston até outras vilas, ainda mais populosas, com a mesma notícia, saindo até antes de Revere. Poderia-se esperar uma resposta ainda mais contundente dos rebeldes neste caso. Mas isso não aconteceu. Uns poucos milicianos responderam à Dawes, e chegando muito depois de que pudessem ser efetivamente úteis à causa.
Revere é uma figura importante na história americana, enquanto Dawes encontra-se apenas nos rodapés dos livros. Revere tornou a mensagem viral, enquanto Dawes foi ignorado. Por quê?
Malcolm Gladwell propôs uma resposta para essa pergunta em seu livro “The Tipping Point, How Little Things Can Make a Big Difference”. Paul Revere era uma pessoa especial, um conector. William Dawes era um sapateiro de 26 anos. Ele cavalgou pelas vilas batendo aleatoriamente nas portas das pessoas e gritando que os britânicos estavam vindo. Mas as pessoas nessas vilas não o conheciam, então não tinham confiança de que a mensagem representava realmente uma ameaça. Paul Revere, por outro lado, era bem conhecido. Ele era um bem-sucedido homem de negócios que, aos 40 anos, estava no centro de importantes eventos dentro e fora de Boston. Quando Revere cavalgou pelas vilas, ele não bateu nas portas das pessoas de forma aleatória. Ele foi diretamente aos comandantes das milícias locais. Ao abrirem as portas de suas casas no meio da noite, reconhecendo Paul Revere, eles agiram rapidamente para alertar a vizinhança e espalhar a mensagem.
Paul Revere era um conector. Conectou-se com as pessoas certas para espelhar sua mensagem rapidamente e de forma muito mais abrangente. Os conectores, ou influenciadores, estão mais vivos do que nunca nos nossos dias. São pessoas especiais que possuem não apenas muitas conexões, mas conexões importantes, capaz de disseminar uma palavra ou ideia amplamente e de forma extremamente rápida. O impacto desses conectores ou influenciadores pode ser realmente avassalador na sociedade e nos negócios. O importante é identificá-los. Como? Análise de redes sociais, que está inserido no conceito de ciência de redes.
Seis graus de separação e o nosso “mundo pequeno”
Você provavelmente já ouviu falar no conceito de seis graus de separação. Esse conceito está relacionado com as distâncias médias em redes sociais. Não as atuais, digitais, mas as antigas. É a ideia de que existem seis pessoas ou menos entre você e qualquer outra pessoa no planeta. Isso significa que você conhece alguém, que conhece alguém, que conhece alguém, que conhece alguém, que conhece alguém, que conhece alguém que me conhece. Claro, talvez você me conheça diretamente. Se não, agora conhece. É basicamente quando conhecemos uma pessoa que possui alguma história ou origem com alguém que a gente conhece. É o famoso “que mundo pequeno!”. E, na verdade, esse tema está muito relacionado com um estudo intitulado small-world experiment, um conjunto de experimentos conduzido por Stanley Milgram e outros pesquisadores examinando o comprimento médio dos caminhos entre pessoas dentro de estruturas sociais nos Estados Unidos. O conceito se baseia na ideia de que a sociedade está inserida numa rede denominada mundo pequeno, caracterizada, de modo geral, por caminhos curtos entre os indivíduos.
A maneira mais direta de provar esse conceito de mundo pequeno é por meio da ciência de redes e suas proposições matemáticas. É o estudo das “coisas conectadas”. “Coisas” podem ser representadas por pessoas, dispositivos eletrônicos, empresas, governos, agências, bancos, contas bancárias etc. Na prática, qualquer entidade que se possa imaginar. “Conectadas” representam qualquer evento que possa ligar duas entidades ou coisas referidas anteriormente. Por exemplo, chamadas telefônicas, mensagens de texto, e-mails, likes, transferências de fundos, pagamentos, referências em publicações, localizações geográficas semelhantes ou iguais, contratos, e assim por diante.
Ciência de rede e suas aplicações
O estudo de redes emerge a partir de diversas disciplinas como uma forma de analisar dados relacionais complexos. Uma das principais disciplinas em questão é a teoria de grafos. Virtualmente, qualquer indústria, em qualquer domínio, possui informações que podem ser analisadas em termos de dados conectados. A ciência de rede, então, pode ser aplicada como forma de compreender desde eventos espaço-temporais, como, por exemplo, a propagação de doenças virais, até eventos de negócios bem tradicionais como o churn, a aquisição de produtos ou o consumo de serviços em indústrias de telecomunicações, mídia e entretenimento, passando por lavagem de dinheiro, fraude bancária, evasão de impostos, além de diversas outras aplicações de negócio no nosso dia a dia.
Os métodos por trás da ciência de redes
Análise de redes inclui algoritmos baseados na teoria de grafos que podem aumentar consideravelmente o desempenho dos modelos estatísticos e de aprendizado de máquina tradicionais. Em muitas aplicações analíticas, interações entre entidades de interesse podem ter um valor inestimável para revelar um conhecimento escondido nos dados, um conhecimento dificilmente encontrado em modelos tradicionais que avaliam os comportamentos das entidades de maneira individual, sem observar os seus relacionamentos. Esse conhecimento pode ser utilizado como uma variável de entrada em uma modelo supervisionado tradicional, incorporando informação discriminante no treinamento desses algoritmos estatísticos e de aprendizado de máquina, ou mesmo de forma independente, como pura e simples análise da topologia da rede e de seus principais atores e relacionamentos.
Frequentemente, essas variáveis de rede descritas no primeiro caso se revelam como as mais importantes ou com mais poder preditor. Ou seja, a análise de rede vai além das tradicionais modelagens supervisionadas e não supervisionadas como, por exemplo, modelos de estimação e classificação ou modelos de agrupamento. Ambas as abordagens supervisionadas e não supervisionadas são utilizadas para encontrar padrões existentes nos dados. Contudo, esses modelos são frequentemente baseados em atributos individuais das entidades em estudo, descrevendo as características principais das observações. A análise de redes, por sua vez, revela padrões existentes nos relacionamentos entre essas entidades, o que por vezes identifica características individuais impossíveis de serem descobertas analisando-se apenas as observações individualmente.
Algoritmos de análise e otimização de redes
Uma linha extremamente relevante em ciência de redes se concentra em algoritmos de análise e otimização. Tanto em análise quanto em otimização, as redes são normalmente representadas de forma muito simples, por meio de um conjunto de nós e um conjuntos de links (às vezes chamados de vértices e arcos). Os nós são as “coisas” descritas acima, pessoas, telefones, computadores, contas, lojas, cidades etc. Os links são as “conectadas” acima, as ligações entre os nós ou “coisas”, relações (pessoas), chamadas (telefones), cabos (computadores), transferências (contas), entregas (lojas), ruas (cidades) etc.
A análise das redes de relacionamento, por exemplo, pode ser diretamente utilizada para identificar o comportamento dos clientes, não do ponto de vista individual, mas sim de relacionamento, reconhecendo possíveis influenciadores, tanto no âmbito de promoção quanto de detração. Esse conhecimento pode ser usado em eventos de negócios tradicionais, como evitar e reduzir o churn, ou aumentar o consumo e a adoção de produtos e serviços, quanto em eventos menos tradicionais, como identificação de anomalias, reconhecimento de fraude e estimação de risco. Na verdade, é difícil imaginar uma indústria que não obtenha benefícios por meio da aplicação de análise e otimização de redes. Muito se discute aplicações de negócio em bancos, seguradoras, empresas de telecomunicações, mas setores como varejo, serviços, governo, hospitalidade e entretenimento, transporte, educação e, sobretudo, ciências sociais e de saúde, são em suma grandes beneficiárias da aplicação da ciência de rede.
Otimização de redes como melhoria em processos operacionais
Na linha de otimização de redes, muitas aplicações práticas dependem de como os dados determinam as redes a serem analisadas. Redes podem existir implícita e explicitamente em diferentes contextos. As redes são construídas com base em uma recorrência natural de distintos relacionamentos como, por exemplo, autores que se referenciam em artigos acadêmicos, atores que contracenam juntos, palavras ou tópicos que aparecem nos mesmos documentos, itens ou produtos que aparecem nos mesmos carrinhos de compra, suspeitos de atos ilícitos que frequentam os mesmos locais ao mesmo tempo, além de uma infinidade de outras situações. Nesses tipos de rede, o peso dos links é modelado como a frequência ou a importância das relações, ou uma combinação de ambas.
Alguns algoritmos de redes focam particularmente em características dos nós e dos links. Por exemplo, no caso de cadeia de suprimentos onde caminhões devem entregar produtos para múltiplas lojas. As lojas representam os nós. As ruas em que os caminhões trafegam representam os links. As lojas possuem características como, por exemplo, a quantidade de produtos demandada, o horário de funcionamento, o horário de entrega etc. O peso dos links pode ser modelado como a distância percorrida pelos caminhões, ou tempo de viajem necessário para cumprir o trajeto, ou um possível custo associado a pedágios, ou mesmo uma combinação considerando todas essas características. Os próprios caminhões, que não representam necessariamente nem os nós, nem os links, podem ter suas próprias características e influenciar a solução, como a capacidade de carga que podem transportar, por exemplo.
Um ponto muito interessante em otimização de redes e mesmo em análise de redes é que o mesmo conjunto de dados pode ser utilizado para construir diferentes redes, servindo de base para algoritmos de otimização distintos. E as aplicações são inúmeras.
Algoritmos de identificação de sub redes ou grupos de nós, como k-Core Decomposition, Connected Components ou Community Detection facilitam uma análise mais pontual e focada das redes e auxiliam na identificação de anomalias, revelando, por exemplo, grupos de nós mais coesos, comunidades especificas baseadas nos seus relacionamentos ou nós que funcionam como pontes, conectando grupos de relacionamentos apartados. Identificação de grupos fraudulentos, clientes que funcionam como promotores e detratores ou entidades que criam pontes únicas entre outras entidades em mercados específicos são exemplos de aplicações práticas.
O algoritmo Node Similarity identifica possíveis nós similares com base nas topologias a sua volta ou na configuração dos seus vizinhos. Esse é muito utilizado para encontrar entidades semelhantes, por exemplo, empresas ou pessoas associadas a transações suspeitas de acordo com suas vizinhanças e relacionamentos.
Os algoritmos que computam as métricas de centralidade, como Degree, Closeness, Betweenness, Hub, Authority, Pagerank, Eigenvector e Influence são muito utilizados para caracterizar os principais atores nas redes de relacionamento, sejam indivíduos, empresas ou mesmo países. Quais entidades são mais centrais, controlam o fluxo da informação, são mais importantes ou influenciadoras?
Algoritmos como Cycle, Clique, Path e Shortest Path revelam padrões em redes de relacionamentos que não podem ser comumente identificados por métodos tradicionais de análise de dados. Cliques possuem diversas aplicações na indústria de bioinformática, ciências sociais, engenharia elétrica, química, apenas para citar algumas. Cycles podem ser utilizados também em química e biologia, sobretudo em problemas de agendamento. Existe um conjunto de aplicações práticas para Shortest Path como, por exemplo, avaliação da capilaridade das malhas rodoviárias, planejamento de transporte público, planejamento de tráfego urbano, robótica, redução de tempo em redes de comunicações, sequências em processos de tomadas de decisões e mesmo em definição de layout de instalações industriais.
Pattern Match é um algoritmo que pode buscar padrões específicos de relacionamentos com base em características dos nós e links, normalmente considerando uma rede extremamente grande. É como buscar um padrão de relacionamento reconhecido em uma rede específica, bem pequena, dentro de uma rede extremamente grande. Casos conhecidos de aplicação focam na identificação das fraudes carrossel, onde imposto e bens são passados entre empresas e jurisdições diferentes ao longo do tempo.
O algoritmo Minimum Spanning Tree busca o conjunto de links necessários para, com o menor custo possível, se manter o alcance e acessibilidade da rede original. Isso permite uma redução no custo de redundância em diversas redes reais, como de energia, computadores e transporte.
Topological Sort busca o caminho necessário na rede considerando-se um conjunto de interdependências. Por exemplo, imagine um conjunto de atividades que devem ser cumpridas, mas que possuem outras atividades como pré-requisitos. Esse algoritmo em particular busca o melhor caminho de execução, considerando todas as dependências existentes, de forma a minimizar ou maximizar uma função objetivo, seja reduzir o tempo ou custo de execução ou aumentar o lucro ao fim da operação. A solução é dada na forma de uma rede de conexões.
No exemplo anterior onde as lojas são nós e as ruas onde os caminhões trafegam entregando os produtos são os links, algoritmos de otimização de rede podem calcular rotas e sequências ótimas para minimizar o tempo ou a distância das viagens. Por exemplo, o algoritmo Traveling Salesman Problem (TSP) identifica a sequência de visitas para minimizar o tempo ou a distância da viagem total. A este problema, adicione-se um depósito para distribuir os produtos e capacidades específicas dos veículos que irão entregar esses produtos a lojas. O algoritmo Vehicle Routing Problem (VRP) calcula as rotas necessárias e a quantidade de viagens para suprir a demanda das lojas desde o depósito considerando as capacidades dos veículos envolvidos nas entregas. Some-se a isso os horários que as entregas podem ser feitas nas lojas e temos o Vehicle Routing Problem with Time Windows (VRPTW). Essas restrições aumentam a complexidade do problema, provavelmente adicionando mais viagens à solução final. Existem outras variantes do VRP, incluindo, por exemplo, coletas e entregas nas viagens (VRPPD), ou a necessidade de se maximizar o lucro total da operação (VRPP), além de outras restrições considerando múltiplos depósitos, inventário disponível, possíveis transferências entre lojas, dentre outras. O algoritmo Maximum Network Flow considera as características dos links ou das ruas e caminhões para calcular a carga máxima a ser distribuída entre depósitos e lojas considerando demanda, suprimento e capacidade de transferência da rede. O algoritmo Minimum-Cost Network Flow considera restrições similares, mas tenta equilibrar demanda e suprimento com o menor custo possível.
Por fim, algoritmos como Minimum Cut podem ser usados em segmentação de imagens, assim como em identificação de pontos vulneráveis em redes de computadores e telecomunicações. Transitive Closure pode ser aplicado em problemas de acessibilidade de redes, alcance de conexões e é comumente aplicado em linguagens estruturadas de banco de dados com o objetivo de reduzir o tempo de processamento de consultas em sistemas gerenciados de banco de dados.
Redes bipartidas
Redes bipartidas ou bigraphs são redes onde os nós podem ser divididos em dois grupos separados e independentes. Os nós dentro de cada grupo podem se conectar, mas não entre grupos. Não existe conexão entre nós dos diferentes grupos. Por exemplo, um conjunto de nós formado por trabalhadores que não se comunicam e um conjunto de nós formado por tarefas que também não se comunicam. Trabalhadores se comunicam com as tarefas por meio de características nas relações como, por exemplo, o tempo que cada trabalhador leva para executar uma tarefa, o custo associado a cada um deles para executar cada tarefa ou mesmo o horário que eles podem executar cada uma dessas tarefas.
O algoritmo Linear Assignment busca a melhor combinação desses dois grupos bipartidos no sentido de minimizar ou maximizar uma função objetivo como, por exemplo, reduzir o custo total de execução de todas as tarefas, aumentar a quantidade de tarefas executadas em um intervalo de tempo particular, ou maximizar o lucro considerando os valores das tarefas (produtos por exemplo) e os custos inerentes a cada uma delas com base em cada um dos trabalhadores.
Para encerrar
Os conceitos de análise e otimização de redes servem não apenas para analisar as estruturas sociais, sobretudo em áreas como sociologia e psicologia, mas também para solucionar problemas de negócios bastante complexos, como cadeia de suprimentos, agendamento de força de trabalho, planejamento urbano, entendimento de efeitos virais e até mesmo sequenciamento genético. Realmente difícil de imaginar uma área, indústria ou contexto que não possa se beneficiar dos conceitos de ciência de redes, de forma isolada ou combinada com outras abordagens analíticas.
Carlos Pinheiro
