O número de Bacon, e o algoritmo da distância mínima

O prolífico ator Kevin Bacon fez, um dia, uma declaração de que já trabalhou com todo mundo em Hollywood. Realmente, ele está na ativa desde os anos 80, trabalhando em dúzias de filmes como JFK, Apollo 13 e até X-Men First Class.

Baseado nesta afirmação e na Teoria dos Seis Graus de Separação, cientistas de dados criaram o “Número de Bacon”: qual a distância mínima entre Bacon e cada ator que já atuou em filmes.

Este site mostra o número de Bacon: https://oracleofbacon.org/movielinks.php

Exemplos:

O grande Tarcísio Meira tem número de Bacon 3. Trabalhou com Luc Merenda em “OSS 117 takes a vacation”, que por sua vez trabalhou com Tomas Milian em “Silent Action”, que trabalhou com Bacon em “JFK”.

O habilidoso Bruce Lee tem número de Bacon 3.

Note que pode haver mais de um caminho mínimo possível, por isso o botão “Find a different link”.

A “Mulher Maravilha” Gal Gadot tem número de Bacon 2.

E o “Capitão Nascimento” Wagner Moura, número de Bacon 2.

Há vários atores brasileiros que não constam na lista, quando mexemos no site. Neste caso, eles têm número de Bacon infinito.

Mundo Pequeno

É bem difícil encontrar algum ator que tenha uma distância de Bacon grande (a maior distância que encontrei foi 3 – mas eu também não tenho lá grande conhecimento de nomes de atores). O mundo de Hollywood é muito menor que o mundo real.

Porém, mesmo no mundo real, existe a teoria do “Mundo Pequeno”. Na média, 6 conexões separam quaisquer duas pessoas no mundo. Entre eu e o presidente dos EUA, eu conheço alguém que conhece alguém que conhece alguém que conhece alguém que conhece alguém que conhece o presidente.

Esta teoria é utilizada para entender a topologia de uma rede. Exemplo. O Facebook reportou distância média de 4,57, em 2016, baseado em 1,6 bilhão de usuários.

Outra reflexão é a dos superconectores. Há pessoas que são super elos, aqueles que conhecem muita gente, e que devem ser atingidos para que uma mensagem passe adiante.

Note que é a distância mínima que vale, o que nos leva à seguinte pergunta.

Como funciona o algoritmo do caminho mínimo?

O algoritmo consiste em encontrar o menor caminho num grafo. A ideia básica é simples, vamos tentar exemplificar com um hipotético “Número de Romário”.

Digamos que eu tenha as seguintes listas (resumidas, a bem da simplicidade):

Seleção Brasileira de 1994:

  • Taffarel
  • Dunga
  • Cafu
  • Bebeto
  • Romário

Seleção Brasileira de 1998:

  • Taffarel
  • Dunga
  • Cafu
  • Rivaldo
  • Ronaldo

Seleção Brasileira de 2002:

  • Dida
  • Cafu
  • Ronaldinho Gaúcho
  • Rivaldo
  • Ronaldo

Seleção Brasileira de 2006 (quadrado mágico):

  • Ronaldinho Gaúcho
  • Ronaldo
  • Adriano
  • Kaká

Quero calcular o “Número de Romário”, para todos os envolvidos.

Começo com a seleção de 1994. Todo mundo que jogou junto com Romário tem conexão 1:

Na seleção de 1998, Romário não jogou (porque o Zagallo não gostava dele, uma injustiça, diga-se de passagem!).
Primeiro, faço uma varredura se os nomes de 1998 já foram contabilizados.

Taffarel, Dunga e Cafu já estão na lista, então não entram.

Já Rivaldo e Ronaldo, podem ser ligados via qualquer um dos três, vamos mostrar só a conexão com Cafu, por simplicidade. Eles terão distância 2.

Em 2002, dois novos nomes: Dida e Ronaldinho Gaúcho.

Eles podem ser ligados via Rivaldo ou Ronaldo – mas aí a distância vai ser 3.

Ou eles podem ser ligados via Cafu (um superconector), e a distância vai ser 2. Como queremos a menor distância, vale esta conexão.

Em 2006, dois novos nomes: Adriano e Kaká.
Eles podem ser ligados por Ronaldo, e aí vão ter distância 3.

Este não é o único algoritmo possível, existem diversas outras alternativas, com seus prós e contras. Encontrar distâncias em grafos pode ser utilizada em roteirização (como o Waze).

Note também que Romário e Ronaldo já jogaram juntos, na vida real. Aqui, é só ilustrativo.

Exercício

A seleção de 2010 era muito ruim, nem vale muita consideração, mas suponha que foi essa a convocação simplificada:

  • Daniel Alves
  • Robinho
  • Kaká
  • Luis Fabiano

Qual o “Número de Romário” do Robinho e do Luis Fabiano?

Veja também:

Um comentário sobre “O número de Bacon, e o algoritmo da distância mínima

  1. Pingback: Como desenhar organogramas no Excel | Ferramentas em Excel-Vba

Deixe um comentário

Faça o login usando um destes métodos para comentar:

Logotipo do WordPress.com

Você está comentando utilizando sua conta WordPress.com. Sair /  Alterar )

Imagem do Twitter

Você está comentando utilizando sua conta Twitter. Sair /  Alterar )

Foto do Facebook

Você está comentando utilizando sua conta Facebook. Sair /  Alterar )

Conectando a %s