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.