Glossário

Selecione uma das palavras-chave à esquerda…

Grafos e RedesGráficos na vida cotidiana

Tempo de leitura: ~20 min

Ao longo deste curso, vimos muitas aplicações da teoria dos grafos, embora algumas tenham sido de alguma forma artificial. Acontece, no entanto, que os gráficos estão no centro de muitos objetos e conceitos na vida cotidiana.

A internet, por exemplo, é um vasto gráfico virtual. Todo vértice é uma página da web individual e cada borda significa que há um hiperlink entre duas páginas. Observe que os links são apenas de uma maneira; portanto, este gráfico é , e esse gráfico é muito, muito, muito grande.

Alguns sites, como Wikipedia ou Facebook, têm muitos links de entrada, enquanto muitos sites menores podem ter muito poucos links de entrada. Esse é o conceito subjacente usado pelo Google para classificar os resultados da pesquisa.

Sites com mais links recebidos tendem a ser de qualidade superior e devem ser mostrados na parte superior dos resultados da pesquisa. Por exemplo, ao pesquisar "Londres", sites oficiais de informações turísticas são mostrados antes de pequenas lojas em Londres ou blogs de pessoas que moram em Londres. Essa idéia simples da teoria dos grafos, o algoritmo de Page Rank, tornou o Google significativamente melhor do que outros mecanismos de busca antigos.

A internet é a maior rede já criada pela humanidade. Esta imagem mostra uma proporção muito pequena de todos os servidores conectados à Internet:

© LyonLabs, LLC and Barrett Lyon, 2014

Enquanto sites e hiperlinks formam um gráfico virtual, também existe a rede física de computadores, servidores, roteadores, linhas telefônicas e cabos.

Toda vez que você faz uma ligação telefônica ou carrega um site, as operadoras de rede precisam encontrar uma maneira de conectar remetente e receptor, sem exceder a capacidade de qualquer cabo ou conexão individual. A teoria e a probabilidade dos grafos possibilitam garantir um serviço confiável, por exemplo, encontrando desvios quando uma conexão específica está ocupada.

Os gráficos também desempenham um papel importante no transporte e na navegação. Todas as redes de vôo, trem e metrô formam gráficos, que podem ser usados ao criar horários eficientes. Um dos gráficos mais reconhecíveis é o mapa do metrô de Londres:

Todas as estradas e rodovias também formam uma grande rede, usada por serviços de navegação como o Google Maps ao elaborar a rota mais curta entre dois pontos.

No futuro, os Sistemas Inteligentes de Transporte reduzirão o congestionamento e os acidentes encaminhando carros com mais eficiência, usando dados de localização coletados de smartphones e carros autônomos. Isso pode economizar milhões de horas perdidas na estrada todos os anos, reduzir significativamente a poluição e permitir que os serviços de emergência viajem mais rapidamente.

Esta imagem mostra a rede de voos de companhias aéreas comerciais no norte da Europa.

Existem inúmeros outros gráficos na ciência, engenharia ou na vida cotidiana:

As ligações entre átomos em moléculas e grades de cristal formam um gráfico.

A propagação de doenças e epidemias podem ser modeladas usando uma rede.

Na biologia, as árvores evolutivas que mostram a ascendência das espécies formam um gráfico.

Os diferentes componentes de circuitos elétricos e chips de computador formam uma rede.

A estrutura gramatical de idiomas pode ser modelada usando gráficos, por exemplo, para criar algoritmos de tradução.

Os gráficos também têm muitas aplicações em probabilidade, teoria dos jogos e matemática financeira.

Redes sociais

Finalmente, vamos pensar em um exemplo particularmente bom de gráficos que existem na vida cotidiana: as mídias sociais. Aqui, os vértices representam e as arestas representam amizades, gostos, assinaturas ou seguidores.

Quando começamos a desenhar gráficos de mídia social, podemos ver claramente alguns grupos de amigos em comum, que podem ter frequentado a mesma escola ou morado na mesma cidade. Também podemos determinar a centralidade das pessoas, que depende de quão bem conectado um vértice está e que pode ser uma medida da popularidade de uma pessoa nas mídias sociais.

Em 2014, o Facebook tinha 1,4 bilhão de usuários ativos e um total de mais de 200 bilhões de amizades. Metade de todos os usuários do Facebook tem mais de 200 amigos e, como a maioria de nossos amigos tem um número semelhante de amigos, poderíamos facilmente ter dezenas de milhares de amigos de amigos.

Uma pergunta interessante agora seria: se você escolher dois usuários aleatórios do Facebook, quantas “arestas de amizade” você precisaria seguir para passar de um para o outro? Por exemplo, a distância entre amigos é , a distância entre amigos de amigos é e assim por diante.

Com base em um estudo realizado pelo Facebook em 2016, você está, em média, conectado a qualquer outra pessoa no Facebook por mais de 3,57 pessoas: dizemos que existem 3,57 graus de separação.

Em outras palavras, se você escolher qualquer um dos bilhões de usuários do Facebook em todo o mundo, eles terão um amigo de um amigo que conhece um amigo de um de seus amigos. E isso inclui celebridades, políticos ou realeza ...

Geographic visualisation of all Facebook friendships in 2010.

Em 1929, quando o autor húngaro Frigyes Karinthy propôs pela primeira vez a idéia de “seis graus de separação”, não havia internet ou mídia social, mas o mundo já havia começado a se tornar mais interconectado.

Em 1967, Stanley Milgram conduziu um primeiro experimento empírico, onde 296 participantes que moravam em Nebraska e Kansas foram solicitados a entregar uma carta a uma pessoa em particular que morava em Boston, Massachusetts. Todos eles tiveram que escolher um amigo para enviar a carta, que escolheu outro amigo. A cada passo, a carta se aproximava de Boston. Milgram descobriu que havia, em média, apenas 5,2 amigos intermediários & # 8211; 5,2 graus de separação.

Hoje, cada um de nós faz parte de inúmeros gráficos invisíveis, subjacentes às nossas interações sociais, viagens, Internet e tecnologia, ciência e muito mais.

Archie