Um ranking ATP

Estabelecer o ranking dos jogadores profissionais de ténis ao logo de uma época ou de um conjunto de épocas é uma tarefa complexa.
Não jogando todos contra todos, pode pontuar-se mais os resultados em torneios mais valiosos, com os pontos crescendo de eliminatória para eliminatória, como actualmente é feito, ou pode considerar-se cada resultado como uma interacção entre dois jogadores (direccionada, do vencido para o vencedor, por exemplo) e usar uma métrica de ranking da rede de resultados (PageRank ou eigenvector) para o ranking global, valorizando mais as vitórias sobre jogadores melhor classificados.
No sítio data.world encontramos um ficheiro muito completo com todos os resultados de todos os torneios de ténis ATP desde 2000-01-31 até 2019-10-27 (54846 jogos, ao longo de quase 20 anos), do qual extraímos facilmente uma lista de pares ordenados (vencido, vencedor) que abrimos na ferramenta Gephi.
Nesta figura, onde só constam os jogadores com mais de 100 vitórias, temos os vértices da redes e etiquetas com tamanho proporcional ao PageRank e usamos o algoritmo fornecido para descobrir comunidades, que acabou por agrupar os jogadores de acordo com as gerações a que pertencem e também com os continente em que mais vezes jogam:

Sem surpresas, Federer, Nadal e Djokovic lideram este ranking.
O que fica patente é que seria possível aprofundar este estudo, ver as dinâmicas das classificações ano a ano, ver a influência dos pisos dos courts, etc.
Deixo a sugestão...

Redes, máquinas de estados e centralidade de eigenvector

Propus recentemente o seguinte problema, inspirado num desafio que encontrei em brilliant.org:
Uma máquina gera aleatoriamente as letras de A a Z, com igual probabilidade. Eventualmente, qualquer palavra que pensemos acabará por ser gerada. Considerando as palavras HEART e EARTH, qual delas, se houver, tem maior probabilidade de surgir em primeiro lugar?
Sendo do mesmo comprimento, se as palavras não tivessem letras, ou grupos de letras, em comum, a resposta seria muito simples - têm a mesma probabilidade. Mas há ali quatro letras em comum, EART, e mais um H, que numa das palavras surge em primeiro lugar e na outra em último. Dará este pormenor vantagem a uma das palavras?
Há uma solução intuitiva, e pode-se recorrer a uma simulação, como fiz neste sítio.
É interessante olhar para esta questão como uma máquina de estados, em que a entrada é o fluxo de letras e os estados memorizam a informação relevante para identificar uma ou outra palavra:

As transições (interacções) entre os estados podem ser representadas por uma matriz, em que os valores são proporcionais às probabilidades de transição entre os estados, ou o número de entradas que conduzem a essas transições:

Esta matriz, é a matriz de adjacências de um grafo (ou rede). Note-se que ao estado EART só se podem suceder dois estados, o que coloca a palavra EARTH em inferioridade em relação à palavra HEART.
A centralidade de eigenvector evidencia essa relação

Eigenvectors e campeonatos de Fórmula 1

Numa corrida, a classificação define uma rede, com arestas orientadas. É uma relação de ordem. O vencedor é o vértice de maior prestígio. Mas usar medidas de prestígio em rede, como a centralidade de eigenvector ou PageRank, não acrescenta nada.
Num campeonato, contudo, é preciso combinar os resultados de várias provas. O sistema mais usado consiste em atribuir pontos por posição e somar os pontos obtidos por cada concorrente em cada prova.
É o melhor método? Não sabemos. E na Fórmula 1 os pontos por posição têm mesmo variado ao longo dos anos. Mas é o mais simples.
Imaginemos que tomamos os resultados de todas as provas de um campeonato, construímos a rede de precedências, e calculamos as centralidades de eigenvector. Será que esta classificação é mais acertada que a simples soma de pontos? Eu diria que sim.
Aplicando a ideia ao campeonato de 2015, obtivemos uma rede com 21 vértices e 280 arestas, e um resultado interessante:

A ordem da classificação é basicamente a mesma, mas a visualização permite uma percepção muito interessante das posições relativas dos vários concorrentes.
Esmiuçaremos isto em breve.

Medir os nós (4)

O grau de um nó, ou o grau in de um nó numa rede direccionada, mede de certa forma a popularidade ou o prestígio do nó. Numa rede de artigos ou autores científicos relacionados pelas citações, seria o número de citações do artigo ou do autor.
Nem todas os lados da rede terão o mesmo valor. Uma citação de um autor com muitas citações valerá mais que uma citação de um autor não citado. Faz assim sentido considerar que cada lado vale para o nó incidente o valor do nó de onde emerge.
Este cálculo fica um pouco complicado pois como se imagina facilmente o valor de um nó passa a depender do valor de todos os outros, de uma forma iterativa.
Um método de cálculo destes valores consiste em atribuir um valor inicial a cada nó (por exemplo a sua centralidade de grau), calcular os valores corrigidos dos graus, e repetir iterativamente ou um número definido de vezes ou até se atingir uma situação de estabilidade.

Neste exemplo, para cada nó indicam-se as primeiras três iterações, a primeira correspondente ao grau in de cada nó (1, 2, 2, 3, 2, 3), a segunda em que os nós contribuem com os valores da primeira iteração (3, 4, 5, 7, 6, 6), a terceira em que os nós contribuem com os valores da segunda (6, 9, 11, 15, 13, 16), e assim sucessivamente.

Estes valores, normalizados para uma soma dos graus igual a 1, vai tender para o vector próprio (eigenvector) da matriz de adjacências do grafo correspondente ao maior eigenvalue, daí ser conhecida por centralidade de eigenvector.

Numa das próximas publicações tentaremos explicar de uma forma simples de que se trata.