Epidemias e redes [1]

As epidemias transmitem-se pelas redes de contactos físicos dos humanos. Assim, para estudar epidemias é necessário saber como os humanos se movimentam, dentro das suas comunidades homogéneas, entre comunidades geograficamente vizinhas, e entre comunidades distantes usando meios de transporte como o avião.
A difusão de epidemias não será muito diferente da difusão de ideias, ou de comportamentos, só que aqui também estes se podem movimentar entre comunidades distantes através de um simples WhatsApp ou um programa de televisão, por exemplo.
Num modelo altamente simplificado, supomos que a infecção dura um dia, e que todos ficam curados, mas não imunizados, e que só intervêm dois factores, k, o número de indivíduos que um indivíduo pode infectar, e que tem a ver com o seu isolamento pessoal, e p, a probabilidade de um indivíduo ser infectado, que depende das suas vulnerabilidades próprias e do uso de dispositivos de protecção individual.
Neste modelo simples, numa população homogénea surge um indivíduo infectado, que vai contactar com k indivíduos, que infecta com uma probabilidade p e tudo depende deste valor R0=kp.

Se R0 for menor que 1 a infecção vai eventualmente extinguir-se e se R0 for maior que 1 vai eventualmente propagar-se a toda a população, ao fim de algum tempo.
Sem esquecer que se trata de probabilidades, e que, portanto, se os números forem pequenos os resultados podem parecer inesperados, aquele factor R0 é determinante para a propagação da epidemia.
Qualquer que seja o valor de R0 > 1, o crescimento será inicialmente exponencial, mas não crescerá indefinidamente, pois à medida que se aproxima da população total começa a ser difícil encontrar indivíduos disponíveis para infectar.

Nesta figura, começamos com um único infectado no dia inicial, e vê-se que o crescimento da epidemia é muito sensível ao valor de R0.
Analisaremos em próxima publicação os efeitos da imunidade e do esgotamento da população não infectada.
Uma boa referência é este capítulo do livro Networks, Crowds, and Markets: Reasoning about a Highly Connected World, de David Easley e Jon Kleinberg, Cambridge University Press, 2010.

Redes de co-autoria

A produção científica dá diversas oportunidades de criar, observar e medir redes: os autores colaboram entre si, escolhem listas de palavras chave, citam outros autores, escolhem revistas onde publicar, etc, e todas estas actividades se podem traduzir em redes científicas e em medidas nomeadamente de clustering ou de ranking.

O CWTS - Centro de Estudos de Ciência e Tecnologia da Universidade de Leiden, Holanda, investiga nestas áreas e disponibiliza algumas ferramentas interessantes de visualização e análise de redes, nomeadamente o VOSviewer, que permite visualizar e analisar redes bibliométricas, nomeadamente a partir dos dados de Web of Science, Scopus ou Dimensions.

É um mundo muito interessante, que mostra como as pessoas colaboram e como os caminhos da ciência se vão construindo.

Neste exemplo muito simples, pesquisei a base de dados Scopus com os termos holonic manufacturing, tópico em que tive alguma produção científica.

Encontri 785 artigos científicos, e com a ferramenta VOSviewer desenhei a rede de co-autorias desses artigos, que aqui apresento com uma visualização tipo densidade.

Como seria de esperar, faço parte dessa rede, e bem próximo está o meu antigo aluno de doutoramento Paulo Leitão, que entretanto já ganhou vida própria, com o que muito me congratulo.

Actores de cinema

Descobri recentemente um ficheiro com os dados de 1000 filmes realizados entre 2006 e 2016, retirados da base de dados  IMDb.
Como numa coluna desse ficheiro estão os principais actores que contracenaram em cada um dos filmes, há aqui uma oportunidade para se visualizar a rede de todos os actores que intervieram naqueles filmes, através da relação terem contracenado em pelo menos um filme.
Um programa que escrevi (em Python) permitiu extrair os pares de relações, e a ferramenta Gephi permite obter uma panóplia de métricas, e nomeadamente a sua visualização

São 1985 actores e 5754 pares de actores, alguns dos quais ocorrem mais que uma vez.

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

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

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.

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.

Medir as redes (2)

Medir uma rede é olhar para uma rede de forma global, considerando todos os seus elementos em simultâneo.
Uma medida muito interessante é a distribuição dos graus dos nós, a frequência (o número de vezes) com que cada grau ocorre.
Na rede "reportar a"

que já apresentamos, temos 21 nós e uma distribuição curiosa dos graus in e out

n	16	0	1	1	2	0	0	1	0
Grau in	0	1	2	3	4	5	6	7	8

n	1	20	0	0	0	0	0	0	0
Grau out	0	1	2	3	4	5	6	7	8

No que respeita ao grau in, há um único nó com o grau in mais elevado, e que será em princípio o nó com maior prestígio, e no que se refere ao grau out há uma distribuição quase uniforme, com todos os nós excepto um com grau idêntico.

Em redes com um número elevado de nós, estas distribuições guardam muita informação sobre a sua natureza.

Medir as redes (1)

A ordem de uma rede é o número de vértices da rede
     N = |V|.
O tamanho de uma rede é o número de arestas da rede
     S = |E|.
A densidade de uma rede é a razão entre o número de arestas da rede e o número máximo de arestas que a rede poderia ter se todos os vértices estivessem ligados entre si
     d = S / Smax
sendo
     Smax = N (N - 1).
Numa rede não direccionada as arestas (i, j) e (j, i) aparecem muitas vezes fundidas num único lado, pelo que é preciso todo o cuidado nesta contabilidade. Ou se multiplica por dois o número de lados ou se divide por dois o número máximo de lados.
Exemplo:
Qual será a densidade desta rede?

A rede tem 5 vértices e 6 arestas
     N = 5
     S = 6
e a densidade é
     d = 6 / 20 = 0.3 = 30%

Bem vindos!

Mais um blogue? Sim!

Mas este vai ser um blogue com pouca opinião e muita interacção.
Pretendemos estudar e discutir redes, das mais simples às mais complexas, sem medo de as tratar da forma mais adequada e de usar ferramentas que ajudem nessa tarefa.
As redes são parte integrante da nossa vida e da nossa caminhada civilizacional.
Das redes marítimas aos caminhos de ferro, aos telefones, aos computadores, à Internet, cada vez mais funcionamos em rede.
O novo paradigma é a rede, não é a estrutura hierárquica tradicional, nas empresas e na sociedade.
E, em consequência, será cada vez mais difícil compreender o funcionamento destes sistemas, complexos, com muitos graus de liberdade, altamente dinâmicos e evolutivos.
É este o desafio.

Comunidades na rede dos amigos do autor no Facebook.

Olharemos para as redes, suas definições, representações, métricas, modelos de formação, comunidades, dinâmicas, e outros fenómenos que nos podem ajudar a estudar e interpretar redes.

Sigam-nos, e questionem-nos!