20 de agosto de 2007 Instituto de Física de São Carlos Francisco Aparecido Rodrigues Orientador:...

20 de agosto de 2007

Instituto de Física

de São Carlos

Francisco Aparecido Rodrigues

Orientador: Luciano da Fontoura Costa

Caracterização,Caracterização,

classificação e classificação e

análise análise

de redes complexasde redes complexas

SUMÁRIO

SUMÁRIO

SUMÁRIO

SUMÁRIO

Sete Pontes de Konigsberg - Leonhard Euler (1736)

É possível atravessar todas as pontes passando-se apenas uma vez por cada uma delas?

O início...O início...

INTRODUÇÃO

Leonhard Leonhard EulerEuler

INTRODUÇÃO

Redes Complexas X Teoria dos GrafosRedes Complexas X Teoria dos Grafos

1. A teoria das redes complexas está relacionada com

a modelagem de redes reais.

2. As redes não são estáticas, mas evoluem com o

tempo.

3. As redes podem ser consideradas como objetos

topológicos para simulações.

Paul Erdös Paul Erdös (1913-1996)

N vértices são conectados aleatoriamente de acordo com uma probabilidade fixa p

INTRODUÇÃO

Grafos aleatórios de Erdös-Rényi (Grafos aleatórios de Erdös-Rényi (1960)1960)

Distribuição de Poisson

Watts and Strogatz, Nature 393, 440 (1998)

Clustering: Indica a freqüência da ocorrência de ciclos de ordem 3.I

NTRODUÇÃO

Modelo de Watts-Strogatz (Modelo de Watts-Strogatz (19981998))

Vértices: documentos htmlLinks: URL links

R. Albert, H. Jeong, A-L Barabasi, Nature, 401 130 (1999)

P(k) ~ k-

Albert-Lazlo Albert-Lazlo BarabásiBarabási

INTRODUÇÃO

Teia Mundial (Teia Mundial (19991999))

M Faloutsos, P Faloutsos, C Faloutsos - Comput. Commun. Rev, 1999

Vértices: computadore,roteadores, sistemas autônomos Links: conexões físicas

INTRODUÇÃO

Internet (Internet (1999)1999)

Muitas redes reais têm uma Muitas redes reais têm uma estrutura similar:estrutura similar:

Redes livre de escalaRedes livre de escalaINTRODUÇÃO

Barabási & Albert, Science 286, 509 (1999)

1. Crescimento: um novo vértice é adicionado com m

arestas.

2. Ligação preferencial: a probabilidade da ligação entre

o novo vértice i e um vértice j na rede é dada por

INTRODUÇÃO

Modelo livre de escalaModelo livre de escala ( (19991999))

P(k) ~ k3

• Propriedades:

1. Presença de hubs (vértices altamente conectados).

2. Heterogeneidade: “rico fica mais rico”.

3. Tolerantes à falhas aleatórias.

INTRODUÇÃO

Modelo livre de escalaModelo livre de escala ( (1999)1999)

WWW (in)

Internet Atores Citações Contatos sexuais

Redes biológicas

Chamadas telefônicas

Semânticas

= 2.1 = 2. 5 = 2.3 = 3 = 3.5 = 2.1 = 2.1 = 2.8

INTRODUÇÃO

Universalidade?Universalidade?

Li, Alderson, Willinger, 2005

INTRODUÇÃO

Redes com diferentes topologias podemRedes com diferentes topologias podem

apresentar a mesma distribuição da conectividade!apresentar a mesma distribuição da conectividade!

RepresentaçãoRepresentaçãoMEDIDAS

DE

REDES

• Matriz de adjacências:

aij = 1 se i está ligado com j e 0 caso contrário.

• Grau, k

• Grau médio

• Distribuição das conexões, P(k)

k = 2

k = 2

k = 2

k = 2

k = 5 k = 2

Medidas relacionadas à conectividadeMedidas relacionadas à conectividadeMEDIDAS

DE

REDES

• Assortatividade

• r > 0: vértices com mesmo grau tendem a se ligar.

• r < 0: hubs tendem a se ligar com vértices pouco conectados.

• r = 0: não há correlação.

Medidas relacionadas à conectividadeMedidas relacionadas à conectividadeMEDIDAS

DE

REDES

Medidas relacionadas aos ciclosMedidas relacionadas aos ciclos

• Coeficiente de aglomeração

• Coeficiente de aglomeração médio

MEDIDAS

DE

REDES

• Menor caminho médio

a b c d

a nd 1 1 2

b 1 nd 1 2

c 1 1 nd 1

d 2 2 1 nd

a

b

c

d

Medidas relacionadas à distânciaMedidas relacionadas à distância

D == 16/(4(4*3)) = 4/3l

MEDIDAS

DE

REDES

• Betweeness

(i, u,j) : número de menores caminhos entre os vértices i e j que passam pelo vértice (ou aresta) u,

(i; j) é o número total de menores caminhos entre i e j.

• Ponto de dominância central

CPD=0 CPD=1

Medidas relacionadas à distânciaMedidas relacionadas à distânciaMEDIDAS

DE

REDES

• Grau hierárquico

g = {1,15,22}

k0(g) = 12; k1(g) = 12; k2(g) = 2.

Medidas hierárquicasMedidas hierárquicasMEDIDAS

DE

REDES

• Coeficiente de aglomeração hierárquico:

• Razão de convergência:

• Razão de divergência:

dvd(g) = 1/cvd(g)

Medidas hierárquicasMedidas hierárquicasMEDIDAS

DE

REDES

Desafio: Obter um método rápido e preciso!

Detecção de comunidadesDetecção de comunidadesMEDIDAS

DE

REDES

Detecção de comunidadesDetecção de comunidadesMEDIDAS

DE

REDES

Maximização da modularidade

1. Inicia-se com a rede totalmente desconectada.

2. Vértices são conectados de forma a aumentar a modularidade

3. O processo termina quando a maior modularidade é encontrada

• Medidas fractais,

• Medidas espectrais,

• Medidas de complexidade,

• Medidas de centralidade,

• Medidas de subgrafos,

• ...

Costa, Rodrigues, Travieso, Villas Boas. Advances in Physics 2007

Outras medidasOutras medidasMEDIDAS

DE

REDES

A caracterização e classificação é feita em termo de poucas medidas!

M. E. J. Newman, SIAM, 2002

Método de classificaçãoMétodo de classificação

CLASSIFICAÇÃO

CLASSIFICAÇÃO

Método de classificaçãoMétodo de classificação

Método de classificaçãoMétodo de classificação

CLASSIFICAÇÃO

É construída uma matriz de atributos onde cada linha

representa uma rede e cada coluna uma medida.

Nessa matriz, é aplicado análise das variáveis canônicas.

No espaço de características é aplicada a classificação

bayesiana.

Procedimento:

1 - Para cada classe é construída uma matriz de dispersão e a matriz de soma dos quadrados dentro das classes,

2 – É construída a matriz de soma dos quadrados entre as classes,

3 – Diagonalize-se a matriz:

4 – Os autovalores dentro e entre são interpretados como a quantidade

de variação associada a cada autovetor ou eixo de maior variação.

CLASSIFICAÇÃO

Análise das variáveis canônicasAnálise das variáveis canônicas

Critério de decisão:

Classificação bayesianaClassificação bayesiana

CLASSIFICAÇÃO

Thomas Bayes(1702-1761)

Rede de transporte aéreo nos Estados Unidos (1997)

Medidas: { <k>, <cc>, l, st, <k2>, <C2>, <dv3>, CPD , r }

CLASSIFICAÇÃO

ResultadosResultados

Costa, Rodrigues, Travieso, Villas Boas. Advances in Physics 2007

Rede de transcrição genética (E. coli)

Medidas: { <k>, <cc>, l, st, <k2>, <C2>, <dv3>, CPD , r }

Costa, Rodrigues, Travieso, Villas Boas. Advances in Physics 2007

CLASSIFICAÇÃO

ResultadosResultados

Interação de proteínas

(Sacharomices cerevisiae)

Medidas: { <k>, <cc>, l, st, <k2>, <cc2>, <dv3>, CPD , r }

Medidas: { <k>, <cc>, l, st, r }

CLASSIFICAÇÃO

ResultadosResultados

Costa, Rodrigues, Travieso, Villas Boas. Advances in Physics 2007

MODELAGEM

DA

INTERNET

Evolução da InternetEvolução da Internet

MODELAGEM

DA

INTERNET

Modelagem da InternetModelagem da Internet

1. A cada passo um novo sistema autônomo i é adicionado à rede num posição geográfica (x,y) escolhida aleatoriamente dentro de uma caixa L X L.

2. São escolhidos m vizinhos geográficos mais próximos de i. Dentre eles, são escolhidos os r com maior grau e cada um deles é conectado a i com uma probabilidade .

3. São escolhidos aleatoriamente q sistemas autônomos, já presentes na rede, e conectados aos s sistemas autônomos de maior grau dentro de uma distância L/4, onde cada ligação é estabelecida com uma probabilidade .

4. O processo termina quando N sistemas autônomos tiverem sido adicionados à rede.

MODELAGEM

DA

INTERNET

ResultadosResultados

50 realizações do modelo

Parâmetros: m= 40, r = 3, = 0,15, q = 2, s = 2, = 0,4

MODELAGEM

DA

INTERNET

Comparação com outros modelosComparação com outros modelos

Modelos:

1. Grafos aleatórios de Erdös e Rényi

2. Small World de Watts e Strogatz

3. Livre de escala de Barabási e Albert

4. Modelo geográfico

5. Livre de escala limitado de Amaral et al.

6. Livre de escala com ligação preferencial de Dorogovtsev et al.

7. Livre de escala não linear de Krapivisky et al.

Base de dados

National Laboratory of applied Network Research (NLANR)

Rede: Topologia da Internet em 2 de abril de 1998

N = 3522 sistemas autônomos e 6324 conexões

MODELAGEM

DA

INTERNET

ResultadosResultados ER

SW

BA

GEO

LSF

DMS

Krapivsky ( = 0.5)

Krapivsky ( = 1.3)

Nosso Modelo

MODELAGEM

DA

INTERNET

ResultadosResultados ER

SW

BA

GEO

LSF

DMS

Krapivsky ( = 0.5)

Krapivsky ( = 1.3)

Nosso Modelo

MODELAGEM

DA

INTERNET

ResultadosResultados ER

SW

BA

GEO

LSF

DMS

Krapivsky ( = 0.5)

Krapivsky ( = 1.3)

Nosso Modelo

• Proteínas letais: quando removidas, causam a morte ou esterilidade de um organismo.

H. Jeong, S. P. Mason, A.-L. Barabási and Z. N. Oltvai, Nature (2001)

“Highly connected proteins are more essential (lethal) than less connected proteins.”

Letalidade em redes de interação de proteínasLetalidade em redes de interação de proteínasANÁLISE

DA

LETALIDADE

ANÁLISE

DA

LETALIDADE

Domínios protéicosDomínios protéicos

Piruvato kinasedomínio regulador

Domínio / de ligaçãode substratos

Domínio / de ligaçãode nucleotídeos

Rede de interação de domínios protéicosRede de interação de domínios protéicosANÁLISE

DA

LETALIDADE

• Domínios letais em um sentido fraco: um

domínio é letal se ele aparece em proteínas

letais.

• Domínios letais em um sentido forte: um

domínio é letal se ele aparece apenas em

proteínas letais formadas de um único

domínio.

Hipóteses sobre a letalidade em domíniosHipóteses sobre a letalidade em domínios

L. da F. Costa, F. A. Rodrigues and G. Travieso, APL (2007)

ANÁLISE

DA

LETALIDADE

Hipóteses sobre a letalidade em domíniosHipóteses sobre a letalidade em domíniosANÁLISE

DA

LETALIDADE

Letais-fraco

Letais-forte

Distribuição cumulativa das conexõesDistribuição cumulativa das conexões

L. da F. Costa, F. A. Rodrigues and G. Travieso, APL (2007)

ANÁLISE

DA

LETALIDADE

L. da F. Costa, F. A. Rodrigues and G. Travieso, APL (2007)

ResultadosResultadosANÁLISE

DA

LETALIDADE

VINHOS

DE

BORDEAUX

Dados sobre os ChateauxDados sobre os Chateaux

571 chateaux pertencentes a 8 distritos.

VINHOS

DE

BORDEAUX

Atributos da produçãoAtributos da produção

1. Castas das uvas

1. cabernet sauvignon, merlot, cabernet franc, petit verdot, semillon e

sauvignon.

2. Área de cultivo

3. Densidade da plantação

4. Idade média das vinhas

5. Produção por hectare

6. Filtragem

7. Finning

8. Quantidade de garrafas produzidas

9. Tempo de fermentação

VINHOS

DE

BORDEAUX

Construção da redeConstrução da rede

N chateaux possuem p atributos cada.N = 571 e p = 14

VINHOS

DE

BORDEAUX

ClassificaçãoClassificação

VINHOS

DE

BORDEAUX

Quais atributos influenciam na qualidade?Quais atributos influenciam na qualidade?

Conclusões e Conclusões e

trabalhos trabalhos

futurosfuturos

CONCLUSÕES

Conclusões principais

• A utilização de métodos de estatística multivariada permite a identificação do modelo que melhor representa uma dada rede real.

• Utilização de poucas medidas pode fornecer resultados incompletos

• O modelo de Internet sugerido se mostrou mais preciso do que os outros modelos considerados.

• O crescimento da Internet é regulado por ligação preferencial, distância geográfica entre os sistemas autônomos e adição constante de ligações

CONCLUSÕES

Conclusões principais

• A correlação entre conectividade e letalidade é mais definida para os domínios protéicos.

• Os domínios são fundamentais na definição da letalidade e função das proteínas

• As propriedades de cultivo e produção de vinhos são fortemente influenciadas pelo território

• Vinhas mais antigas e maior tempo de fermentação resultam em melhores vinhos

CONCLUSÕES

Perspectivas:

• Utilização de técnicas de mineração de dados na classificação• Mais modelos e mais medidas

• Taxonomia das redes complexas, influência das

medidas na classificação.

• Aperfeiçoamento do modelo de Internet.

• Análise das funções protéicas no nível dos

domínios.

• Consideração de outros atributos e outras regiões

na análise dos produtores de vinhos.

REFERÊNCIAS

1. Luciano da F. Costa, Francisco A. Rodrigues, Gonzalo Travieso and P. R. Villas BoasCharacterization of complex networks: A survey of Measurements Advances in Physics, Volume 56 (1), 167 - 242, 2007.

2. M. E. J. Newman,The structure and function of complex networksSIAM Review 45, 167-256 (2003).

3. S. Boccaletti, V. Latora, Y.Moreno, M. Chavez and D.-U. HwangComplex Networks: Structure and DynamicsPhysics Reports , Physics Reports, 424 (4-5 ),2006.

4. Albert-László Barabási and Zoltán N. OltvaiNetwork Biology: Understanding the Cells's Functional OrganizationNature Reviews Genetics 5, 101-113 (2004).

5. Luciano da F. Costa, Francisco A. Rodrigues and Gonzalo TraviesoProtein domain connectivity and essentialityAppl. Phys. Lett. 89, 174101 (2006) .

6. F. A. Rodrigues, P. R. Villas Boas, G. Travieso, L. da F. Costa Seeking the best Internet ModelPreprint: arXiv:0706.3225v1

7. Francisco A. Rodrigues, Gonzalo Travieso e Luciano da F. CostaF. A. The complex network of Bordeaux wines, submetido.

ARTIGOS

PUBLICADOS

1. Luciano da F. Costa, Francisco A. Rodrigues, Gonzalo Travieso and P. R. Villas BoasCharacterization of complex networks: A survey of measurementsAdvances in Physics, Volume 56, pages 167 - 242, Issue 1, January 2007.

2. Francisco A. Rodrigues, Gonzalo Travieso andLuciano da F. CostaFast Community Identification by Hierarchical GrowthInternational Journal of Modern Physics C, 18(6), June 2007.

3. Luciano da F. Costa, Francisco A. Rodrigues and G. Travieso, Analyzing Trails in Complex NetworksPhysical Review E, aceito.

4. Luciano da F. Costa, Francisco A. Rodrigues and Gonzalo TraviesoProtein domain connectivity and essentialityApplyes Physics Letters 89, 174101 (2006) .

5. Francisco A. Rodrigues and Luciano da F. CostaSurviving opinions in Sznajd models on complex networksInternational Journal of Modern Physics C, 16(11), 2005.

6. Gonzalo Travieso, Francisco A. Rodrigues, Carlos. A. Rugiero and Luciano da F. CostaComplex network modeling and simulation of distributed systems processingII TIDIA Workshop, November 7-9, 2006. São Paulo - Brazil.

ARTIGOS

SUBMETIDOS

1. Francisco A. Rodrigues, Paulino R. Villas Boas, Gonzalo Travieso and Luciano da F. Costa Seeking the best Internet ModelPreprint: arXiv:0706.3225v1

2. Francisco A. Rodrigues, Gonzalo Travieso e Luciano da F. CostaThe complex network of Bordeaux wines. Submetido.

3. Paulino R. Villas-Boas, Francisco A. Rodrigues, Gonzalo Travieso, Luciano da F. CostaChain motifs: The tails and handles of complex networksPreprint: arXiv:0706.2365

4. Paulino R. Villas Boas, Francisco A. Rodrigues, Gonzalo Travieso, Luciano da F. CostaBorder trees of complex networksPreprint: arXiv:0706.3403v1