Co-escolhas

As redes surgem onde menos as esperamos...
Na Faculdade de Engenharia  há dez cursos no concurso nacional de acesso, uma licenciatura e nove mestrados integrados, totalizando 893 vagas. Em 2016, houve 3276 candidatos diferentes na primeira fase que escolheram pelo menos um dos cursos da FEUP, dos quais 1843 como primeira opção.
As listas de candidatos aos cursos da Faculdade de Engenharia estão disponíveis, e este quadro resume a situação (abstenho-me de descodificar as siglas...)

Mesmo que a procura estivesse alinhada com a oferta, apenas cerca de metade dos candidatos que elegeram a FEUP em primeiro lugar teria sucesso, mas como não está, a situação é pouco simpática para um grande número de candidatos.
No sítio certo, farei brevemente uma análise desta questão e das suas vastas implicações.
Curiosamente, as (até) seis opções que cada candidato pode escolher definem relações entre os cursos, não completamente definidas nem iguais para todos, mas certamente que para cada candidato o conjunto de cursos escolhidos faz algum sentido. Daqui pode nascer uma visão dos cursos em rede!
Nesta imagem temos uma rede bimodal em que dez dos seus nós são os cursos de entrada na FEUP e os restantes 3276 são os alunos candidatos

Quando um aluno escolhe dois cursos, por exemplo, estabelece uma relação entre esses cursos. Considerando todas as relações resultantes destas co-escolhas, e usando um algoritmo de layout apropriado, os nós correspondentes a cursos mais procurados em simultâneo aproximam-se. Assim, esta imagem dá uma ideia da percepção que os candidatos têm da proximidade entre os vários cursos.
As diferentes cores correspondem a classes calculadas automaticamente pela ferramenta Gephi, que usei, e que, por alguma razão, associou dois pares de cursos: Engenharia Mecânica e Engenharia e Gestão Industrial, e Engenharia do Ambiente e Engenharia de Minas e Geoambiente.
A revisitar.

Redes direccionadas e não direccionadas

Numa rede, a relação entre dois vértices pode, ou não, ter direcção.
Se os dois vértices A e B são, por exemplo, utilizadores do Twitter e a relação é "o utilizador A segue o utilizador B", então essa relação tem uma direcção associada, de A para B.
Se os dois vértices são, noutro exemplo, personagens de um romance e a relação é "as personagens A e B contracenam numa mesma cena", então essa relação não tem uma direcção, é bidireccionada.
As relações sem direcção não pressupõem uma hierarquia entre os vértices, são afins das relações de equivalência. Os vértices distinguem-se essencialmente pela sua posição relativa na rede.
Por outro lado, as relações com direcção, são próximas das relações de ordem, havendo vértices com importâncias relativas diferentes,
As métricas das redes adequadas a cada caso concreto dependem da natureza das relações, evidentemente, e dos objectivos que se pretende atingir.
É todo um mundo a explorar.

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.

Matriz de adjacências (1)

Em Matemática, uma matriz é uma entidade constituída por um conjunto bidimensional de valores arrumados num número finito de linhas e colunas, sendo Aij o valor que se encontra na linha i e na coluna j.
Uma rede ou um grafo com N vértices podem ser representados por uma matriz quadrada com N linhas e N colunas, significando Aij = 1 que existe um lado orientado do vértice i para o vértice j e Aij = 0 que não existe.
Pegando nesta rede, por exemplo

percebe-se facilmente a sua relação com esta matriz 6x6

Esta matriz diz-se a matriz de adjacências da rede em causa. Assinala os vértices que são adjacentes. Se a matriz é simétrica relativamente à sua diagonal então os lados são simétricos (sem direcção).
Por outro lado, esta representação suporta lados múltiplos e mesmo anéis (lados que ligam um nó a ele próprio).

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.