domingo, 29 de outubro de 2017

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

quarta-feira, 14 de junho de 2017

Netvizz

As ferramentas Netvizz foram desenvolvidas inicialmente por Bernhard Rieder, da Universidade de Amsterdão, no âmbito da iniciativa Digital Methods. Neste artigo, Rieder apresenta as motivações e os resultados daquele projecto, que permite explorar grupos e páginas Facebook e descobrir as redes e as dinâmicas subjacentes.
Deixo aqui o resultado duma recolha de dados muito simples que fiz hoje, e que consistiu em descobrir todas as páginas Facebook que fizeram "gosto" na página da FEUP (Faculdade de Engenharia da U.Porto), e todas as páginas que fizeram "gosto" nestas, ou entre elas, digamos que o universo social da FEUP.
Recolhi 363 páginas e 3346 interacções, que estão representadas nesta rede. Cada nó é uma página, o seu tamanho é proporcional ao número de gostos que recebeu e a côr e a posição estão associados às comunidades que uma aplicação conhecida de análise de redes - Gephi - identificou.
É possível identificar facilmente algumas destas comunidades.
Fico à espera de questões e de comentários...

quarta-feira, 29 de março de 2017

#Brexit

Gephi é uma das aplicações mais interessantes para o estudo de redes.
É opensource, tem uma arquitectura que permite o desenvolvimento de plugins por terceiros, sofreu uma evolução recente que melhorou a estrutura interna de dados, e é de uso obrigatório por quem se interesse por estes problemas.
Um plugin muito útil é o Twitter Streaming Importer, que oferece um conjunto de possibilidades muito atractivas, e que permite nomeadamente obter redes de co-ocorrências de hashtags ou redes de interacções entre utilizadores,
Enquanto escrevia este texto, iniciei uma recolha em tempo real de co-ocorrências de hashtags com a hashtag #brexit
Em 12 minutos, foram detectadas mais de 1000 hashtags diferentes, cujo estudo permite obter interpretações muito úteis dos sentimentos que neste momento percorrem a "twitosfera".
Aqui, deixo uma imagem da rede de hashtags, passados uns 15 minutos, e agora com mais de 1500 nós
Começa a notar-se uma certa organização.
Sem querer fazer um estudo aprofundado aqui, mostro agora os pares de hashtags mais frequentes ao fim de 30 minutos, no dia em que a carta de Theresa May chegou a Bruxelas
Se algum dos leitores considerar interessante esta visão e quiser explorar a análise e visualização de redes neste e noutros contextos, estou 100% disponível para ajudar.

quinta-feira, 15 de setembro de 2016

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.

terça-feira, 17 de maio de 2016

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.

segunda-feira, 18 de abril de 2016

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.

quinta-feira, 14 de janeiro de 2016

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).