Redes
Roberto Imbuzeiro Oliveira (IMPA)
Colóquio do IMECC/Unicamp, 2018
Rede de interação de proteínas numa levedura.
Redes = grafos
Grafos descrevem muitas coisas.
Como entender os grafos que nos interessam?
(Imagem: Barrett Lyon, Projeto OPTE, 2005)
Redes = grafos
Grafos descrevem muitas coisas.
Como entender os grafos que nos interessam?
(Imagem: Clay Reed, Allen Institute; Wei-Chung Lee, Harvard; Sam Ingersoll, artista)
Ciência de Redes
Segundo a National Academy of Sciences (EUA):
the study of network representations of physical, biological, and social phenomena leading to predictive models of these phenomena.
O estudo de representações de fenômenos físicos, biológicos e sociais por redes, levando a modelos preditivos destes fenômenos.
Assuntos de hoje
O que esperar da Ciência de Redes?
Quais seriam os problemas matemáticos importantes?
Minha trajetória: de modelagem descritiva a processos, algoritmos e inferência.
Grafos
Rede de interação de proteínas numa levedura.
Grafos orientados
Por que é útil falar de grafos?
O que é difícil? (I)
Muitos problemas naturais são
NP-difíceis. Provavelmente não
há algoritmos eficientes para
resolvê-los.
O que é difícil? (II)
Alguns grafos são muito grandes
e só são acessíveis
indiretamente.
O que é difícil? (III)
Algumas redes pequenas são “medidas” com erros.
Uma teoria “simples” para grafos aleatórios
O que veremos
Muito do que torna a teoria de grafos difícil vem dos “piores casos”, não dos típicos.
Grafos aleatórios têm comportamento mais compreensível.
Mais tarde: ligação disso com modelagem.
O modelo de Erdös-Rényi
O modelo de Erdös-Rényi
O modelo de Erdös-Rényi
Graus e números de arestas
Grau de um vértice := seu número de vizinhos.
Por que é sempre verdade que
Soma dos graus = 2 x (número de arestas)?
Conexidade
Grafo conexo
Grafo desconexo
Um teorema sobre conexidade típica
Um grafo típico logo antes de ficar conexo
A maior componente conexa
Comportamento típico
Coisas que poderiam ser complicadas ficam simples.
Características globais determinadas por propriedades locais.
Que outras coisas você conhece que são assim?
A chegada dos físicos estatísticos
Alguns fatos a serem explicados
Muitos grafos reais são esparsos (n grande, grau médio d constante)
Faloutsos (1999): distribuição de graus segue lei de potência.
Outros artigos: diâmetro da WWW é pequeno...
O que é a lei de potência
Erdös-Rényi esparso
Grafos “reais”
Abordagem de Física Estatística
Achar modelos “microscópicos” aleatórios que expliquem a lei de potência e outras propriedades observadas no mundo real.
O modelo de Barabási-Álbert
Modelo de Barabási-Álbert
Os ricos ficam mais ricos!
Reproduz a lei de potência
Erdös-Rényi esparso
Barabási-Albert
Ideia muito influente
Gerou muitos outros modelos
Resultados rigorosos de Bollobás, Riordan &c (outros grafos aleatórios!)
Não descreve bem boa parte do que se gostaria
Como anda a área ahoje
Até hoje muito esforço para modelar bem diferentes redes.
Gerou a minha tese de doutorado
Problemas com a lei de potência
Sabe-se que os métodos de medição de Faloutsos (1999) têm viés.
“On the Bias of Traceroute Sampling: or, Power-law Degree Distributions in Regular Graphs”
(Achlioptas, Clauset, Eppstein, Moore, 2008)
Qual o problema?
Medições de graus da Internet são feitas indiretamente via as rotas de pacotes (geodésicas).
O artigo mostra que este método reporta graus diferentes dos reais.
Problemas com a filosofia
“Mathematics and the Internet: A Source of Enormous Confusion and Great Potential”
(Willinger, Alderson, and Doyle - Notices of the AMS)
Pontos positivos
Criação de uma nova linguagem:
Novos exemplos para se “brincar”. Interesse na estrutura do grafo e na sua relação com o que acontece nele.
Rede de interação de proteínas numa levedura.
Lembre da meta da Ciência de Redes
the study of network representations of physical, biological, and social phenomena leading to predictive models of these phenomena.
Modelos são importante para nos ajudar a enxergar e descrever.
Também precisamos inferir e partir para a relação entre estrutura e funcionamento.
Um exemplo: o cérebro
Bullmore & Sporns, 2008
Minha agenda de pesquisa desde ~ 2012
“Uma parte é filosófica, outra parte é mais prática.”
Exemplos
Um exemplo: modelo do votante
Modelo do votante
Modelo do votante
Arrival
process
(Poisson)
time
Modelo do votante
time
Modelo do votante
time
Neighbor
chosen at
random
Modelo do votante
time
Update
opinion
O tempo até o consenso
Alguma hora, todos vão concordar.
Quanto tempo isso demora?
Dualidade
tempo
Dualidade
tempo
Dualidade
tempo
Dualidade
tempo
Conclusão
Dualidade com passeios aleatórios coalescentes.
Condutância
S
Condutância grande e pequena
Condutância constante.
Um fato e um teorema
Fato
Quanto maior a condutância, mais rápido o passeio aleatório perde memória de onde começou (ergodicidade).
Teorema
Se a condutância é pequena com relação ao tempo de encontro de dois passeios, então o tempo de consenso tem uma distribuição universal.
Redes sociais têm boa condutância
Não têm comunidades grandes, logo têm condutância média-grande (Leskovec, Lang, Dasgupta e Mahoney).
Mais exemplos no quadro!
Conclusão: algum progresso lento aqui
“Uma parte é filosófica, outra parte é mais prática.”
Obrigado!
http://w3.impa.br/~rimfo
O que é o passeio aleatório?
A cada passo, ande para um
vizinho escolhido ao acaso
com distribuição uniforme.
O que é o passeio aleatório?
A cada passo, ande para um
vizinho escolhido ao acaso
com distribuição uniforme.
O que é o passeio aleatório?
A cada passo, ande para um
vizinho escolhido ao acaso
com distribuição uniforme.
O que é o passeio aleatório?
A cada passo, ande para um
vizinho escolhido ao acaso
com distribuição uniforme.
O que é o passeio aleatório?
A cada passo, ande para um
vizinho escolhido ao acaso
com distribuição uniforme.
O que é o passeio aleatório?
A cada passo, ande para um
vizinho escolhido ao acaso
com distribuição uniforme.
Teste sua intuição
N vértices
Dois grafos bem diferentes
C = ciclo com n vértices
G = n vértices e
(quase) todas as arestas possíveis
PA “enxerga a diferença”
Muito tempo vendo amarelos, oscilação, depois muito tempo vendo pretos…
Succesão de amarelos e pretos quase equiprováveis.
Teorema de ergodicidade
Tempo de mistura
Diferenças de tempos de mistura
Tempo de mistura tem a ver com condutância
S
Mistura lenta quando condutância pequena
Redes sociais têm boa mistura
Não têm comunidades grandes, logo têm condutância média-grande e misturam em pouco tempo (Leskovec, Lang, Dasgupta e Mahoney).