Download PDF
ads:
Samyr Silva Bezerra Jácome
Aspectos Dinâmicos e Estruturais em Modelos
de Redes para Sistemas Complexos
Fortaleza – CE
Março / 2009
ads:
Livros Grátis
http://www.livrosgratis.com.br
Milhares de livros grátis para download.
Samyr Silva Bezerra Jácome
Aspectos Dinâmicos e Estruturais em Modelos
de Redes para Sistemas Complexos
Tese de Doutorado apresentada ao Departa-
mento de Física da Universidade Federal do
Ceará, como parte dos requisitos para a ob-
tenção do Título de Doutor em Física.
Orientador:
Prof. Dr. André Auto Moreira
Co-orientador:
Prof. Dr. José Soares de Andrade Junior
Doutorado em Física
Departamento de Física
Centro de Ciências
Universidade Federal do Ceará.
Fortaleza – CE
Março / 2009
ads:
Aos Meus Avós
Paternos
aos
Meus Pais
e a
Meu Amor, Celina..
Agradecimentos
• Ao Professor André Auto pela orientação, amizade e as valorosas discussões que contribui-
ram para não apenas para a realização deste trabalho como também para o enrequecimento
da minha formação científica;
• Ao Professor José Soares de Andrade Júnior pela co-orientação, discussões e suporte logí-
tico que contribuiram para a realização deste trabalho;
• Ao Professor Ascânio de Araújo pela amizade e excelentes discussões que influenciaram
diretamente nesse trabalho;
• Aos demais Professores do departamento de Física que de alguma forma contribuiram para
a realização deste trabalho;
• Aos Professores Luciano da Silva, Uriel Costa e Eric Parteli por participarem da banca de
defesa da minha tese;
• Às funcionárais Irene, Rejane, Ana Cleide, Creuza, Vera e Michele pela cordialidade e
profissionalismo;
• Aos amigos Lucas, Felipe, talita, Mariana, Baquil e Eduardo pela amizade ao longo do
período de minha formação;
• Aos amigos Erneson, Apiano, Roberto, Pablo e George pela amizade;
• Ao amigo Saulo pela amizade e discussões dos algorítmos "tampas";
• Ao Marcos pela a amizade e paciência nas correções da tese;
• Aos meus grandes amigos Oscar, Sanderson, Alexandre e Thiago Ribeiro, os quais a dis-
tância não me deixa esquecer;
• À minha querida avó, a qual chamo carinhosamente de Mãe Liquinha, pelo amor e carinho;
• Aos meus pais pelo amor, carinho, dedicação e por acreditarem no meu potencial e terem
me proporcianado uma ótima educação;
• Aos meus irmãos pelo carinho, companherísmo e principalmente pela amizade;
• Aos quase filhos Willamis, Weslley, Yolanda, David e Fernado pela estreita amizade e por
terem convivido harmoniosa e pacientemente comigo ao longo desses dois ultimos anos;
• Ao meu grande amor, Celina, por ter me dado a chance de conhecê-la e me permitir cativar
o seu amor. Vivi ao seu lado os momentos mais intensos e felizes da minha vida. Obrigado
pelo seu companherismo, sua dedicação e principalmente pela sua compreensão e paciência,
pois sei que cometi muitos erros ao longo do tempo.
Resumo
Nesta tese estudaremos sistemas onde alguma forma de desordem ou não-homogenei-
dade tem um importante papel na complexidade da formação estrutural ou da regula-
gem dinâmica do sistema. Primeiramente estudaremos a dinâmica das redes Booleanas,
onde as regras de atualização escolhidas aleatoriamente controlam o comportamento glo-
bal do sistema. Na condição crítica e próximo dela, propomos que a transição para o
regime crítico pode ser caracterizado pela divergência do tempo de relaxação t
R
. Base-
ados em simples argumentos de escalonamento, mostramos, além de outros resultados,
que a probabilidade acumulativa da distribuição de t
R
decai como uma lei de potência
P (t
R
< t) ∼ t
−β
, com o expoente β = 1, para o modelo annealed na região crítica. Em
seguida estudamos um novo método de decomposição de redes aplicado às redes livres
de escalas, onde a ampla distribuição de conectividade é um aspecto fundamental. O
método consiste basicamente na retirada simultânea e iterativa de grupos de vértices com
um determinado grau K de conectividade até que não haja mais sítios com este mesmo
grau de conectividade na rede. Deste modo, definimos algumas variáveis que caractari-
zam o processo de decomposição e obtemos uma série de expoentes e parâmetros bem
definidos. A partir do comportamento destas variáveis pudemos constatar p or meio de
algumas manipulações matemáticas que nosso método é auto-consistente, servindo como
ótima ferramenta para estudo dos aspectos estruturais de uma rede. Por fim, estudamos
os backbones, onde utilizamos um modelo de rede em que a desordem está no arranjo
aleatório de camadas fáceis e difíceis à percolação. Os resultados numéricos indicam a
quebra na classe de universalidade da geometria fractal e da distribuição de tamanhos
de massa do backbones e também um comportamento assintótico da dimensão fractal no
limite de grandes valores de massa e/ou anisotropia.
Abstract
In this thesis we study systems where some form of disorder or non-homogeneity has a
significant role at the complexity of the structural building or of the dynamics regulation
of the system. First, we study the dynamics of Boolean networks, where the rules to
update the state of the nodes are randomly chosen and control the global behavior of the
system. At the critical threshold, and near to it, we propose that the transition to the
critical regime can be characterized by the divergence of the relaxation time t
R
. Based
on simple scaling arguments, we show that the cumulative probability distribution of t
R
decays as a power-law P (t
R
< t) ∼ t
−β
, with exponent β = 1, for the annealed model at
the critical region. Then, we study a novel method for network decomposition, which we
apply to scale-free networks, that have the broad degree distribution as a fundamental
feature. This method consists in a simultaneous and iterative remotion of groups of nodes
with degree K until there are no more nodes with this degree in the network. Thus, we
define new variables that characterize the process of decomposition and we obtain a set
of well define exponents and parameters. From the behavior of these variables we can see,
through some mathematical manipulations, that our method is self-consistent, serving as
a useful tool for the study of the structural features of the network. At last, we study the
backbones of the percolation cluster, where we use a network model with layers arranged
in a disorderly way to represent some kind of anisotropy resistance to the percolation.
Our numerical results indicate a break at the universality class on the fractal dimension
and on the mass distribution of the backbones.
Sumário
Lista de Figuras
Lista de Tabelas
Introdução p. 20
1 REDES BOOLEANAS p. 23
1.1 Introdução . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . p. 23
1.2 Modelo . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . p. 25
1.3 Fluxo de informação . . . . . . . . . . . . . . . . . . . . . . . . . . . . p. 30
1.3.1 Teoria do Campo Médio . . . . . . . . . . . . . . . . . . . . . . p. 32
1.3.2 Solução Geral . . . . . . . . . . . . . . . . . . . . . . . . . . . . p. 33
1.3.3 Diagrama de fases . . . . . . . . . . . . . . . . . . . . . . . . . . p. 35
1.4 Comportamento Dinâmico no Ponto Crítico . . . . . . . . . . . . . . . p. 37
1.4.1 Teoria . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . p. 37
1.4.2 Resultado Numérico . . . . . . . . . . . . . . . . . . . . . . . . p. 39
1.5 Conclusões . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . p. 43
2 DECOMPOSIÇÃO DE REDES LIVRES DE ESCALAS p. 45
2.1 Redes Livres de Escalas . . . . . . . . . . . . . . . . . . . . . . . . . . p. 45
2.1.1 Rede de Albert-Barabási . . . . . . . . . . . . . . . . . . . . . . p. 50
2.1.1.1 Cálculo Analítico . . . . . . . . . . . . . . . . . . . . . p. 52
2.2 Método de decomposição . . . . . . . . . . . . . . . . . . . . . . . . . . p. 54
2.2.1 Modelo . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . p. 54
2.2.2 Resultados . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . p. 57
2.3 Conclusão . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . p. 62
3 PERCOLAÇÃO EM MULTI-CAMADAS p. 63
3.1 Percolação . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . p. 63
3.1.1 Modelo de Percolação . . . . . . . . . . . . . . . . . . . . . . . . p. 66
3.1.2 Backbone . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . p. 70
3.1.3 Método Self-Avoiding Random Walk . . . . . . . . . . . . . . . p. 75
3.2 Multi-camadas . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . p. 79
3.2.1 Backbone em Multi-camadas . . . . . . . . . . . . . . . . . . . . p. 81
3.3 Resultados . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . p. 84
3.4 Conclusões . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . p. 88
4 CONCLUSÕES p. 90
5 APÊNDICE p. 92
Referências p. 93
Lista de Figuras
1 Diferentes tipos de conexões. (a) Podemos observar que em uma rede
regular as conexões são escolhidas de acordo com a geometria do espaço.
No exemplo em questão, podemos observar o elemento σ
i
está conectado
aos primeiros e segundos vizinhos, ou seja, aos 4d primeiros vizinhos,
no espaço unidimensional d = 1. (b) Ao contrário do item anterior, o
elemento σ
i
pode ter suas conexões aleatoriamente escolhidas, ou seja,
qualquer elemento σ
j
do sistema tem igual chance de pertencer ao con-
junto de elementos controladores do elemento σ
i
. . . . . . . . . . . . . . p. 26
2 Ilustração exemplificando um esquema dinâmico de uma rede booleana.
a) Um diagrama de conexões contendo três elementos binários conectados
entre si. A tabela mostra a regra de cada elemento, onde o elemento 1 é
governado pela função “E“ e os elementos 2 e 3 são governados pela função
”OU”. b) A tabela mostra os 2
3
= 8 possíveis estados do sistema em um
dado tempo t no lado esquerdo e seus respectivos estados evoluídos para
o tempo t + 1 no lado direto. c) Representação da dinâmica do sistema
por gráfos de estado. Cada conjunto de algarismos representa um estado
em um dado instante e as setas indicam o sentido da evolução temporal
dos estados. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . p. 29
3 Um atrator é formado quando o estado de um sistema evolui para outro
estado já visitado, passando a repetir indefinidamente sempre a mesma
trajetória (sequências) de estados. A bacia atratora é formada por todos
os estados que evoluem naturalmente para algum estado de um atra-
tor. Na ilustração, temos uma base atratora de uma Rede Booleana com
N=13 elementos e K=3 conexões. Cada estado do sistema é representado
por um círculo e o sentido da evolução temporal acorre de fora para den-
tro da figura, onde as linhas conectam um estado ao sucessor. O atrator
é de tamanho 7 (sete estados) e o sentido de sua evolução temporal é
indicado pela seta. A tabela de bit ilustra um dos estados que compõe a
base atratora. (Fig. adaptada de [18]) . . . . . . . . . . . . . . . . . . p. 30
4 A distância de Hamming fornece a quantidade de estados diferentes dos
pares conjugados entre duas redes semelhantes. Na ilustração, temos a
representação esquemática de duas redes semelhantes com 16 elementos.
Os pares de elementos conjugados com mesma cor possuem o mesmo
estado e os que são cores diferentes (marcados por bolas pretas) possuem
estados diferentes. Neste exemplo, a distância de Hamming é H(t) = 4. p. 31
5 Diagrama de fases das redes booleanas aleatórias. A área rachurada cor-
responde a fase ordenada e a área logo acima corresponde a fase caótica.
A curva que separa ambas as regiões é a equação K
c
= [2p(1 − p)]
−1
.
Gráfico adaptado de [19]. . . . . . . . . . . . . . . . . . . . . . . . . . . p. 36
6 Distribuição cumulativa do tempo de relaxação no ponto crítico. O
tempo de relaxação é definido como a quantidade de passos necessários
para que o dano em um par de redes semelhantes chegue a zero. A linha
pontilhada é o comportamento esperado. Podemos ver que, para siste-
mas muito grandes, a distribuição segue o decaimento previsto em forma
de lei de potência, P (t
R
> t) ∼ t
−1
. Podemos observar, entretanto, um
pequeno desvio para pequenas escalas de tempo e um truncamento ex-
ponencial para tempos muito grandes, que está localizado por um tempo
de escala dado por t
×
∼ N
1/2
( ver inset). O resultado para N = 2
31
foi
obtido numericamente iterando a equação 1.26. Este resultado mostra
que até na condição crítica, o sistema tende a alcançar o estado orde-
nado. Entretanto, no limite termodinâmico o tempo de relaxação médio
diverge. O mais importante deste resultado é que na maioria dos casos
o sistema se recupera da pertubação depois de poucos passos, enquanto
que em pouquíssimos casos a resposta ao estimulo faz o sistema sofrer
uma transição global. . . . . . . . . . . . . . . . . . . . . . . . . . . . p. 39
7 Distribuição cumulativa do tempo de relaxação t
R
para a fase ordenada
próxima do ponto crítico. Estas curvas foram obtidas para uma rede de
tamanho N = 102400 e conectividade K = 3. Os resultados mostram
que a fase ordenada o tempo de escala τ
0
do truncamento exponencial
da distribuição é determinado por τ
0
∼ (I
c
− I)
−ν
para ν = 1. O gráfico
principal mostra a distribuição escalonada pelo tempo de correlação ν
0
,
enquanto os dados originais podem ser visto no inset. . . . . . . . . . . p. 40
8 Distribuição cumulativa do tempo de relaxação para a fase caótica pró-
xima do ponto crítico. Os resultados foram obtidos para uma rede de
tamanho N = 102400 e conectividade K = 3. Quando I
c
> I, o sistema
está no regime caótico e, então, esperamos que o dano nunca convirja a
zero. Esta concepção é consistente com os resultados, onde vemos que o
crossover da lei de potência decai para um comportamento plano. Isto
significa dizer que a média do tempo de relaxação diverge até para uma
rede de tamanho finito. O tempo de correlação τ
0
∼ (I − I
c
)
−ν
nos dá
o tempo de escala para diferentes probabilidades. Podemos perceber um
truncamento exponencial para valores de I se aproximando da condição
crítica. Este truncamento ocorre devido ao tamanho finito da rede. Po-
demos perceber também que o início do truncamento varia cada vez mais
rapidamente com o aumento de (I − I
c
). O gráfico principal mostra a
distribuição escalonada com o tempo de correlação τ
0
, enquanto que os
dados originais podem ser vistos no inset. . . . . . . . . . . . . . . . . . p. 41
9 Distribuição cumulativa do tempo de relaxação para o caso quenched.
Na fase ordenada próxima do ponto crítico, a distribuição torna-se res-
trita a pequenos tempos de escala. Como no modelo annealed, o inset
mostramos a superposição das curvas por um tempo de correlação dado
por τ
0
∼ (I − I
c
)
−ν
, com ν = 1. . . . . . . . . . . . . . . . . . . . . . . p. 42
10 Distribuição de Poisson feita a partir dos dados de uma simulação com-
putacional de uma rede aleatória. Os dados foram gerados de uma rede
de N = 10000 vértices e probabilidade de conexão ρ = 0.0015. No
eixo vertical temos a probabilidade haver o número X
k
vértices com co-
nectividade k (eixo horizontal) e E(X
K
)/N representa a expectativa da
destribuição de Poisson para os parâmetros N = 10000 e ρ = 0.0015(Fig.
retirada de [16]). . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . p. 46
11 Gráfico experimental da magnetização próxima do ponto crítico para
cinco tipos de materiais magnéticos diferentes, onde os eixos da magne-
tização e temperatura são multiplicados respectivamente por um fator
H
−1/δ
e H
−1/βδ
, com β ∼ 0.36 e δ ∼ 4.5. Os cinco materiais são CrBr
3
,
EuO, Ni, YIG e Pd
3
Fe e todos são ferromagnetos com estruturas dife-
rentes: o CrBr
3
é considerado uma rede anisotrópica; o EuO possui forte
interação entre os segundos vizinhos; o Ni é um ferromagneto elétron iti-
nerante; o YIG é um ferrimagneto; o Pd
3
Fe é uma liga magnética. Apesar
da diferença estrutural, todos os materiais possuem o mesmo expoente
crítico. Assim podemos colapsar o gráfico da magnetização em uma única
curva pela multiplicação de um fator de escala, fazendo com que os cinco
materiais pertençam a mesma classe de universalidade (Gráfico retirado
de [40]). . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . p. 48
12 Ilustração que mostra o processo de crescimento da rede Barabási-Albert.
A rede é iniciada com o número inicial de vértices m
0
= 3 e o coeficiente
de agregação m = 2. As bolas pretas são os vértices antigos e os cinzas
o novo vértice adicionado. . . . . . . . . . . . . . . . . . . . . . . . . . p. 50
13 Gráfico que mostra a distribuição de probabilidade do grau de conecti-
vidade P (K) em função de K, onde podemos perceber o decaimento em
lei de potência na forma P (K) ∼ K
−γ
, com γ = 3.0. A rede foi criada
com N = 10
6
vértices e diferentes coeficientes de agregação m. . . . . . p. 51
14 Ilustração que representa um processo de RI k-shells de uma rede Barabási-
Albert. A rede possui tamanho N = 10 e foi construída com um coefici-
ente de agregação m = 2. O processo de remoção foi realizado retirando
todos os vértices com K = 3 conexões. A bolas de cor cinza indicam os
vértices que serão retirados no passo seguinte. A figura a) representa a
rede inicial, t = 0, b) o processo intermediário, t = 1, com s
3
(1) = 3/10
e c) a configuração final, t = 2, com s
3
(2) = 2/10, onde não há mais
vértices com K = 3 conexões. Em todo o processo ocorreu um total de
2 iterações resultando em uma 3-shell com S
3
= 5/10. . . . . . . . . . . p. 55
15 Decomposição de uma rede de Barabási-Albert. A simulação foi reali-
zada em 200 amostras de redes com N = 2
23
vértices e diferentes valores
de coeficiente de agregação m. Dentro do inset é mostrado um gráfico
normalizado que representa o comportamento da fração média do total
de vértices retirados S
K
em função de K. Podemos perceber um de-
caimento em lei de potência com uma inclinação de aproximadamente
3.0 independente do coeficiente de agregação m. No gráfico principal é
mostrado o colapso da distribuição o da fração média S
K
por um fator
de m
−η
, onde η ≈ 1.8. . . . . . . . . . . . . . . . . . . . . . . . . . . . p. 56
16 A fração média de massa retirada s
K
(t) é definida como sendo a quan-
tidade média de vértices retirada em cada instante da iteração ao longo
de um processo de decomposição em um conjunto de 200 amostras com
redes de tamanho N = 2
25
. O gráfico mostra a distribução de s
K
(t)
em função da iteração t para m = 3 e diferentes valores de K, onde
podemos perceber um decrescimento exponencial com inclinações λ
K
.
Os símbolos representam os dados computacionais e a linha contínua o
ajuste exponencial. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . p. 57
17 A figura mostra o gráfico log-linear do tempo característico λ
K
em função
de K em redes de tamanho N = 23. Cada valor de lambda é obtido
a partir da inclinação da distribuição da média da fração de vértices
retirados s
K
(t) em função do tempo de iteração t para cada valor de
conexão K (ver Fig. 16). Podemos perceber o comportamento logaritmo
de λ
K
em função de K na forma λ
K
∼ δln(K), com δ = 0.89, e diferentes
m = 1, 3, e 7. O inset mostra a sobreposição de λ
K
por um fator escala
m
−ν
com ν = 1.25. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . p. 58
18 O gráfico acima mostra em log-log a variação C
K
em função K para
m = 3 e diferentes tamanhos de redes. A linha contínua representa
o ajuste dado pela equação 2.15. O inset é mostrado a constante C
K
multiplicado pelo seu respectivo tamanho de rede N. . . . . . . . . . . p. 59
19 O gráfico mostra o tempo total médio T (K) necessário para o término
do processo de decomposição para cada valor de K. Utilizamos diferen-
tes tamanhos N de redes para um mesmo valor de número de conexões
iniciais m = 3. A curva de linha contínua representa o ajuste da equação
2.20 com os parâmetros α = 3, δ = 0.89 e a
3
= 0.72. . . . . . . . . . . . p. 61
20 Conjunto de quatro figuras ilustrativas do modelo de percolação. a) Es-
quema de percolação por sítios de uma rede quadrada 10x10 de primeiros
vizinhos, onde os sítios azuis representam os clusters finitos, o vermelho
e o cluster percolante os brancos os sítios vazios; b), c) e d) são figuras de
simulações de uma rede quadrada 50x50 com diferentes probabilidades
de ocupação p, onde em c) e d) as cores seguem a mesma representação
de a) enquanto que em b) a cor vermelha representa o maior cluster finito
da rede e o azul os demais. . . . . . . . . . . . . . . . . . . . . . . . . . p. 67
21 Ilustração de uma rede quadrada LxL de percolação. A rede foi gerada
no ponto crítico p = p
c
= 0.59275 e com L = 500. O cluster percolante é
identificado pela cor azul claro, os maiores clusters finitos são representa-
dos na ordem decrescente pelas cores verde escuro, vermelho, rosa, verde
claro, amarelo, laranja, os demais por azul escuro e os desocupado por
preto. Através das cores, podemos perceber que no ponto crítico existem
clusters de todos os tamanhos. . . . . . . . . . . . . . . . . . . . . . . . p. 68
22 Gráfico que representa a probabilidade de haver um cluster percolante
P
∞
(p) em função da probabilidade de sítios ocupados p. As curvas foram
obtidas a partir de uma rede quadrada LxL com L = 10
2
(linha verme-
lha), L = 10
3
(linha azul), L = 10
4
(linha preta). A linha vertical serve
de referência no ponto p = p
c
= 0.59275. . . . . . . . . . . . . . . . . . p. 69
23 Gráfico que mostra o comportamento da distribuição de massa dos clus-
ters para vários níveis de tamanhos com três probabilidades p diferentes.
Em a) temos o método finity size scale que determina em função do
tamanho da rede L o comportamento da massa do maior cluster com
probabilidade de ocupação p = 0.5 (triângulos) e do cluster percolante
com probabilidades p = p
c
= 0.59275 (círculos) e p = 0.7 (quadrados).
A linha pontilhada com traços (triângulos) representa o ajuste logarít-
mico e a linha contínua (círculos) e a tracejada (quadrados) os ajustes
em lei de potência com expoentes D
f
≈ 1.89 e D ≈ 2.0, respectivamente.
Cada ponto foi obtido a partir de uma média de 1000 amostras. Em b)
temos o método do raio de giração que determina a massa do cluster
finito em função do tamanho do seu raio médio. Cada ponto foi obtido
a partir da média da massa de todos os clusters (apenas os que não to-
cam nas bordas) contidos em um intervalo logarítmico de raio médio e
a linha contínua representa um ajuste em lei de potência com o expo-
ente D
f
≈ 1.89. A simulação foi realizada utilizando uma rede quadrada
10
4
x10
4
com probabilidade de ocupação p = p
c
= 0.59275. . . . . . . . . p. 71
24 Ilustração de backbone sob cluster percolante gerado em uma rede qua-
drada. Em a) temos um exemplo esquemático onde backbone são os sítios
vermelhos e o cluster percolante os azuis. A entrada e saída de fluido são
representados pelos sítios de cor preta e os sítios verdes representam a
conexão entre regiões estagnadas ao restante do cluster. Em b) mostra-
mos uma simulação em uma rede 500×500 de um backbone de cor preta
sob um cluster percolante de cor cinza. . . . . . . . . . . . . . . . . . . p. 72
25 Gráficos que mostram os comportamentos críticos da massa do backbone
em uma rede quadrada (L × L). Em a) temos a distribuição da massa
média M
B
(para r = 2 e L = 2
11
) em função do seu raio de giração R
g
(cículos) e em função das componentes R
gx
(triângulos) e R
gy
(quadra-
dos) do raio de giração. Para uma melhor visualização, multiplicamos
por 5 e 20 as distribuições de massa das componentes R
gx
e R
gy
, respecti-
vamente. Podemos perceber os comportamentos nas formas M
B
∼ R
D
B
g
,
M
B
∼ R
D
Bx
gx
e M
B
∼ R
D
By
gy
, onde as linhas contínuas representam os
ajustes com inclinações D
B
= 1.638 ± 0.006, D
Bx
= 1.646 ± 0.007
e D
By
= 1.65 ± 0.008. Os pontos representados por diamantes mos-
tram a componente R
gy
em função de R
gx
, onde podemos perceber
uma relação em lei de potência com expoente D
Bxy
aproximadamente
igual a 1.0. Em b) temos a probabilidade de distribuição de massa do
backbone para r = 2, que decai como uma lei de potência na forma
P (M
B
) ∼ M
−τ
B
B
seguida p or um pequeno plator e depois por um cutoff
com decaimento abrupto. A linha contínua representa o ajuste com incli-
nação τ
B
= 1.237±0.02 e os símbolos representam os diferentes tamanhos
de redes (L × L). Em c) mostramos a probabilidade de distribuição de
massa P (M
B
) para diferentes tamanhos de r = 2, 4, 8, 16 e 32 e em d)
o escalonamento pelos fatores r
D
B
no eixo P (M
B
) e r
−D
B
no eixo M
B
.
Nos itens c) e d) usamos redes de tamanho L = 2
11
e em todos os itens
foram utilizados 10
5
amostras. . . . . . . . . . . . . . . . . . . . . . . . p. 73
26 Ilustração que representa a geração de um perímetro através do algoritmo
SARW. Os círculos representam os sítios desocupados, as bolas cinzas os
sítios ocupados e o X o próximo sítio com estado nulo que será visitado.
Os números fora do parênteses significam o tempo de cada passo do
caminhante e os que estão entre parentes indicam a escolha do próximo
estado, sendo 1 para ocupação e 0 para desocupado. O resultado final
do processo nos dá um perímetro externo com N
o
= 9 sítios o cupados e
N
v
= 12 sítios desocupados. . . . . . . . . . . . . . . . . . . . . . . . . p. 77
27 Exemplo ilustrativo de dois perímetros gerados a partir de um programa
computacional baseado no algoritmo SARW. Os sítios ocupados estão
em vermelho e desocupados em azul. O perímetro da esquerda é um
exemplo de perímetro interno e o da direta um perímetro externo. . . . p. 78
28 Gráfico que mostra o comportamento da fração de número de perímetro
interno n
i
(p) (bolas azuis) e externo n
e
(p) (bolas vermelhas) em fun-
ção da probabilidade p. Podemos perceber que abaixo da probabilidade
crítica (p < p
c
= 0.59275) o número de perímetros externos é máximo
enquanto os internos é praticamente nulo e quando a probabilidade está
acima (p > p
c
= 0.59275) temos o comportamento inverso. Para a proba-
bilidade p próxima do ponto crítico p
c
= 0.59275 há um comportamento
abrupto e o número de perímetros internos e externos tendem a per-
manecer iguais. As linhas contínua e tracejadas servem de referências,
indicando respectivamente o ponto crítico p
c
= 0.5927 e a igualdade do
número de perímetros internos e externos (n
i
(p) = n
e
(p)). . . . . . . . . p. 79
29 Gráficos de diagrama de fases para o modelo PM. Em a) temos o dia-
grama de fases de ˜p
c
em função do parâmetro ∆ com o cálculo compu-
tacional baseado no algoritmo SARW para os casos alternado (bolas) e
aleatório (quadrados). Em b) temos a comparação entre os algoritmos da
baseados no método da bisseção utilizando (símb olos vazios) uma rede
quadrada e no méto do SARW (símbolos preenchidos) para o cálculo do
diagrama de fases de ˜p
c
. Note que à medida que o parâmetro ∆ aumenta,
a diferença entre os métodos se tornam cada vez maior, principalmente
para o caso aleatório. No limite de ∆ = 0.5 deveremos ter ˜p
c
= 0.5, o
que não ocorre para o método da bisseção em redes quadradas. . . . . . p. 80
30 Ilustrações de backbones sob clusters percolantes em diferentes graus de
anisotropia segundo o modelo PM aleatório. Em a) temos uma rede
quadrada (250×250), ˜p
c
= 0.59725 e ∆ = 0.0, em b) uma rede retangular
(550×250), ˜p
c
= 0.588 e ∆ = 0.1 e em c) uma rede retangular (700×60),
˜p
c
= 0.57423 e ∆ = 0.2. Em ambos os casos utilizamos r = 2. . . . . . . p. 82
31 Gráficos da distribuição de massa M
B
em função da componente R
gy
do raio de giração gerados em redes de multi-camadas aleatórias. Nos
itens a) e b) mostramos o efeito de tamanho finito causados pelos limi-
tes das redes quadradas (símbolos vermelhos) e retangulares (símbolos
azuis). Podemos perceber que à medida que o parâmetro ∆ aumenta, os
efeitos de tamanho finito ficam cada vez mais acentuados na rede qua-
drada. Em ambos os itens utilizamos redes quadradas (512×512) e redes
retangulares (1800×512) e (4000×400) com ∆ = 0.1 e 0.2 e r = 2. . . . p. 83
32 Conjunto de gráficos que mostram o comportamento da distribuição de
massa do backbone M
B
em função do raio de giração R
g
(círculo) e das
componentes R
gx
(triangulo) e R
gy
(quadrado) do raio de giração e mos-
tramos também R
gy
em função de R
gx
(diamante). Em todos os ca-
sos temos o comp ortamento em lei de potência na forma M
B
∼ R
D
B
g
,
M
B
∼ R
D
Bx
gx
, M
B
∼ R
D
By
gy
e R
gy
∼ R
D
Bxy
gx
. Para facilitar a visualização
da figura, multiplicamos por 5 a distribuição de massa das componentes
R
gx
e R
gy
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . p. 85
33 Conjunto de gráficos que mostram o comportamento da densidade de
probabilidade da distribuição de massa do backbone P (M
B
) para dife-
rentes valores de ∆. Em a) e b) mostramos distribuições com massa dos
backbones que to cam nos limites da rede (vermelho) e daqueles que não
tocam (azuis) para ∆ = 0.15 e 0.30. Em c) e d) temos a distribuição
para diferentes valores de distância r entre os sítios. . . . . . . . . . . . p. 87
Lista de Tabelas
1 Ilustração do conjunto das possíveis funções booleanas com dois argu-
mentos. Nas duas primeiras colunas da esquerda para direita, o agru-
pamento de cada par de zeros e uns de cada linha forma o conjunto de
arranjos da função booleana. No restante das dezesseis colunas, cada
coluna forma um ensemble e o agrupamento dos dezesseis ensembles for-
mam o conjunto de todos os ensembles possíveis para a função booleana
com K = 2 argumentos. . . . . . . . . . . . . . . . . . . . . . . . . . . p. 27
2 Ilustração de duas funções booleanas com três argumentos. A primeira
função (quarta coluna da esquerda para a direita) é formada por uma
distribuição probabilística. A função será uniforme quando p = 0.5. Na
quinta coluna temos uma função canalizadora. Neste exemplo, sempre
que o estado do primeiro argumento σ
i
1
for igual a 0, o valor de saída
da função será sempre 1 independentemente dos estados dos outros ar-
gumentos σ
i
2
e σ
i
3
. Quando σ
i
1
for igual a 1, a distribuição seguirá uma
distribuição probabilística. . . . . . . . . . . . . . . . . . . . . . . . . . p. 28
3 A tabela mostra a probabilidade das possíveis ocorrências de configu-
rações formadas a partir de dois elementos conjugados de redes seme-
lhantes. A variável p representa a probabilidade da função booleana
ter outputs 1 e a quantidade (1 − p) a probabilidade de outputs 0.
Podemos perceber, portanto, que a probabilidade de termos configura-
ções iguais é dada por p
2
+ (1 − p)
2
= 1 + 2p(p − 1) e diferentes por
p(1 − p) + (1 − p)p = 2p(1 − p). . . . . . . . . . . . . . . . . . . . . . . p. 35
4 Tabela contendo valores de probabilidades críticas para diferente tipos
de redes [55]. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . p. 66
5 Tabela contendo os valores de probabilidades críticas para diferentes va-
lores de ∆. Na coluna do meio temos a probabilidade crítica para o mo-
delo aleatório p
cram
e na coluna da direita a probabilidade crítica para o
modelo alternado p
calt
. Os valores foram obtidos a partir de simulações
baseadas no método Self-Avoid Random Walk. . . . . . . . . . . . . . . p. 92
20
Introdução
Ao longo destes quatro anos de doutorado tive a oportunidade de conhecer e trabalhar
com vários problemas ligados aos sistemas complexos. Dentre eles três em especial pas-
saram a fazer parte de um esforço sistemático e objetivo, que culminaram nos assuntos
abordados nesta tese. Um fator em especial os unem em uma classe verdadeiramente
importante da física de sistemas complexos, ou seja, o fato de todos apresentam alguma
forma de desordem.
A identificação da desordem varia para cada tip o de sistema, porém, uma caracte-
rística comum a todos é o fato dos sistemas desordenados apresentarem algum tipo de
organização aleatória quando alguma propriedade dos seus constituintes for observada
globalmente. Esta característica corrobora, portanto, o nosso conceito intuitivo de desor-
dem, ou seja, a idéia de algo que não existe certo padrão de organização. Atualmente,
tem-se observado que a desordem é um aspecto bastante importante para a formação da
complexidade dinâmico-estrutural de uma infinidade de sistemas, como exemplo, podemos
citar: as redes Booleanas tipo annealed e quenched, onde a desordem está na aleatoriedade
das conexões e nas regras de atualizações dos estados dos sítios; as redes livre de escala,
onde a desordem está no arranjo das conexões; as redes de percolação, onde a desordem
é encontrada na disposição de poros do meio poroso etc.
Muitos sistemas físicos apresentam os regimes ordenado e caótico, entretanto, especula-
se que apenas no limite crítico entre os dois regimes há a presença de um processo de
auto-regulação eficaz, capaz de tornar um sistema dinâmico robusto e adaptável. Esta
característica está presente em diversos sistemas reais, tornando o estudo dos processos
dinâmicos em regimes críticos e quase críticos um fonte rica para a pesquisa científica.
Nesse sentido, estudamos, no capítulo 1, as redes booleanas na condição crítica e próximo
dela, onde propomos que a transição para o regime crítico pode ser caracterizado pela
divergência do tempo de relaxação t
R
, ou seja, do tempo no qual a memória do dano
aplicado na rede é completamente perdido. Com simples argumentos de escalonamento
mostramos que para o modelo annealed na região crítica, a probabilidade acumulativa da
distribuição de t
R
decai como uma lei de potência P (t
R
< t) ∼ t
−β
, com o expoente β = 1.
Nossos resultados numéricos comprovam este decaimento e mostram redes de tamanho
Introdução 21
finito com um truncamento exponencial em uma escala de tempo proporcional a N
−1/2
.
Estudamos também a distribuição t
R
partindo da condição crítica para os regimes orde-
nado e caótico. Observamos que acima da escala de tempo característico a distribuição
na fase ordenada apresenta um crossover para um decaimento exponencial. Para a fase
caótica a distribuição apresenta um crossover para um platô, que é consistente com a
divergência do tempo de relaxação médio esperado na condição caótica.
Em seguida (Cap. 2) estudamos um novo método de decomposição para redes com-
plexas. Nossa motivação se deve principalmente ao estudo do processo iterativo à medida
que a rede perde seus sítios. Este tipo de estudo pode ser bastante útil quando for asso-
ciado ou à análise de alguma propriedade que dependa das conexões da rede, como por
exemplo, o fluxo de informação e a robustez a ataques e a erros eventuais, ou ao desen-
volvimento de softwares de visualização de grandes redes. Assim, aplicamos o método de
decomposição a rede livre de escalas de Barabási-Albert. O método consiste basicamente
na retirada iterativa de grupos de vértices com o mesmo grau de conectividade, ou seja, a
cada iteração identificamos todos aqueles vértices com K conexões e, então, os retiramos
simultaneamente da rede. Esse processo é repetido até que não haja mais vértices na rede
com K conexões. Definidos as variáveis S
K
como a fração da quantidade total de vértices
retirados da rede e s
K
(t) como a fração de vértices retirados em cada iteração. Analisando
o comportamento de S
K
e s
K
(t) juntamente com outras funções que surgiram ao longo do
processo investigativo, observamos que a utilização do método de decomposição resultou
em uma série de expoentes e parâmetros relacionados entre si e invariantes para diferentes
estruturas de rede.
O terceiro tema estudado neste trabalho está ligado à percolação anisotrópica. Este
tipo de percolação está presente de diferentes maneiras em muitos sistemas reais. Um
exemplo típico são as rochas sedimentares, que podem exibir anisotropia espacial devido
à tendência das camadas morfológicas se disporem com maior probabilidade na direção
horizontal. A partir de exemplos como este, podemos concluir que entender de uma forma
mais realista o processo de escoamento em meios porosos anisotrópicos é fundamental
para o desenvolvimento de novas tecnologias. Desta forma, estudamos, no capítulo 3,
a estatística de backbones gerados em redes quadradas de percolação em multicamadas,
onde os sítios de entrada e saída de fluidos são separados por uma distância r. As camadas
possuem de diferentes densidades e são dispostas aleatoriamente ao longo de uma dada
direção. Os resultados numéricos indicam a quebra de classe de universalidade com o valor
da dimensão fractal diminuindo à medida que a anisotropia aumenta. Observamos ainda
a igualdade assintótica entra a dimensão fractal e o expoente da associado a fractalidade
Introdução 22
da direção oposta a anisotropia. Investigamos também o expoente τ
B
que caracteriza
a região de escala da densidade de probabilidade da distribuição de massa do backbone
P (M
B
) e verificamos que ele varia rapidamente com a anisotropia até um valor limite, ou
seja, τ
B
= 1.33 ± 0.01. As mudanças ocorridas na classe de universalidade dos expoentes
críticos investigados podem ser explicadas como um resultado das correlações de longo
alcance induzidas pela formação de camadas adjacentes com a mesma concentração de
probabilidade.
Na tese, todos os capítulos seguem a mesma estrutura, ou seja, seguem a ordem de
uma breve introdução, onde o foco principal é expor ao leitor idéias e propriedades básicas
necessárias ao objeto de estudo do capítulo, como conjecturas e teorias universalmente
aceitas. Na sequência é apresentado a problematização do tema seguido dos resultados,
discussões e conclusões.
23
1 REDES BOOLEANAS
Abordamos neste capítulo o estudo do comportamento dinâmico das redes boolea-
nas no ponto crítico e próximo dele através da divergência do tempo de relaxação, ou
seja, através da quantidade de tempo necessário para um pequeno dano desaparecer por
completo. Observamos além de outros resultados que com simples argumentos de es-
calonamento a probabilidade acumulativa da distribuição de t
R
decai como uma lei de
potência P (t
R
< t) ∼ t
−β
, com o expoente β = 1, indicando que o modelo annealed
pertence a mesma classe de percolação direcionada. O capítulo é iniciado com uma breve
introdução geral (1.1) e depois abordamos o aspecto teórico do fluxo de informação (1.3).
Por último apresentamos nossos resultados teóricos e numéricos (1.4) e na sequência a
conclusão (1.5).
1.1 Introdução
Nas ultimas décadas, o estudo de sistemas complexos tem sido motivo de muitos elos
interdisciplinares, tornando sua definição algo bastante abrangente. Podemos, no entanto,
particularizar o leque de possibilidades destes sistemas para as chamadas redes complexas,
as quais são definidas como sendo um sistema constituído por um grande número de
unidades relacionadas entre si em uma rede não trivial de interações [1]. Um fato marcante
que pode ser observado nas redes complexas é que elas não podem ser analisadas de
maneira reducionista, ou seja, não é possível caracterizar propriedades globais da rede
analisando apenas as suas partes constituintes. Desta forma, a análise das redes complexas
se constitui em uma quebra de paradigma, pois mesmo que as unidades individuais se
relacionem de maneira simples e conhecida, a contribuição coletiva para as propriedades
macroscópicas do sistema se manifesta de forma complexa, exigindo ferramentas de análise
global.
Uma das características mais relevantes dos sistemas complexos é sua capacidade de
evoluir espontaneamente para estados organizados [3], ou seja, um agente individual tem
1.1 Introdução 24
a habilidade de auto-regular seu comportamento até alcançar uma condição desejada para
o sistema. Todavia, esta condição não é alcançada por uma estrutura predefinida entre os
agentes, mas sim como uma condição de emergência da dinâmica do sistema. Em outras
palavras, podemos dizer que não há um controle central ou distribuição de tarefas, cada
agente responde apenas a interações locais sem conhecer o estado do sistema como um
todo. Assim, dependendo de cada tipo de estrutura dinâmica, um sistema poderá corrigir
falhas locais e responder eficazmente às mudanças do ambiente.
Os estudos ligados aos sistemas complexas mostram que ajustando apenas poucos
parâmetros que governam as interações entre os agentes individuais é possível fazer com
que um sistema sofra transições entres os estados ordenado e caótico [2]. Entretanto,
especula-se que nem a fase ordenada nem a fase caótica sejam capazes de apresentar
ao mesmo tempo a robustez e a adaptabilidade observadas em sistemas reais. Estas
características foram apenas observadas na condição crítica, a qual é definida como a
região que compreende o limite de transição entre as fases ordenada e caótica [2].
A elaboração de modelos discretos e baseados em agentes constitui um dos métodos
mais usados para a análise de redes complexas. Em particular, as redes booleanas conquis-
taram grande aceitação nos estudos científicos em virtude da sua flexibilidade em definir
tanto a estrutura de interação entre os agentes quanto as regras de evolução do sistema.
Esse modelo de rede foi inicialmente desenvolvido por Kalffman para modelar a regulação
genética [4] e atualmente tem sido aplicado em diversos tipos de problemas, que vão desde
a regulação e controle genético [5], evolução [6, 7], redes neurais [8, 9, 10] até estudos do
comportamento da estrutura da matéria [11]. Uma das suas principais características é
apresentar uma linha crítica de transição de fases no limite termodinâmico que divide os
regimes caótico do ordenado.
As redes booleanas são freqüentemente modelas com as conexões entre seus agentes
escolhidas aleatoriamente a partir de alguma classe de ensemble. São também freqüen-
temente chamadas de modelo N − K porque cada um dos N elementos que compõe o
sistema interage com outros K elementos. O modelo booleano consiste em um conjunto
de N elementos cujos os estados são descritos por variáveis booleanas, ou seja, cada ele-
mento σ
i
pode assumir apenas os estados 0 ou 1. A evolução temporal ocorre em passos
de tempo discreto, onde todos os estados são atualizados simultaneamente de acordo com
a função booleana f( σ
i
) associada a cada elemento. Os parâmetros de controle dinâmico
utilizados são a média de conectividade K e a probabilidade p, a qual fornece a pro-
babilidade com que o resultado da função booleana asso ciada ao conjunto de entradas
1.2 Modelo 25
aleatórias σ
i
= {σ
i1
, σ
i2
, ..., σ
iK
} seja igual a 1. Alguns estudos tem mostrado que apenas
estes dois parâmetros são necessários para estabelecer a rede nos regimes caótico e regular
[12, 13, 14]. Uma definição mais rigorosa do modelo será exposta na próximo seção.
1.2 Modelo
O modelo de rede booleana é constituído por um conjunto de N elementos {σ
1
, σ
2
, σ
3
,
..., σ
N
} conectados entre si, onde cada variável σ
i
é binária, ou seja, σ
i
∈ {0, 1} para
i = 1, 2, 3, ..., N. A dinâmica da rede ocorre com o estado de cada elemento booleano
sendo regido de acordo com os estados dos outros elementos aos quais está conectado.
Mais precisamente, o estado do elemento σ
i
no passo t+1 é determinado pelos estados dos
seus K
i
elementos controladores (elementos aos quais está conectado) σ
j1
, σ
j2
, σ
j3
, ..., σ
jK
no tempo t, ou seja,
σ
i
(t + 1) = f
i
(σ
1
(t), σ
2
(t), σ
3
(t), ..., σ
K
i
(t)) , (1.1)
onde f
i
é definida como a função booleana associada ao i-ésimo elemento com K
i
argu-
mentos. A estrutura do modelo estará completamente definida quando for especificado:
• A conectividade K
i
de cada elemento da rede, ou seja, definir quantas variáveis irão
determinar o estado de cada elemento σ
i
;
• As ligações de cada elemento, isto é, qual o conjunto de elementos {σ
(i)
j1
, σ
(i)
j2
, σ
(i)
j3
, ...,
σ
(i)
jK
i
} que estará associado a cada elemento σ
i
;
• As regras de evolução de cada elemento, ou seja, determinar a função booleana f
i
de cada elemento σ
i
.
A conectividade média é definida por
K =
1
N
N
i=1
K
i
. (1.2)
Assim, em um modelo mais geral, a conectividade K
i
poderá variar de um elemento para
outro, o que poderia resultar, segundo a equação (1.2), em uma conectividade média
com valores não inteiros. Nestes casos, alguns modelos ganharam muita importância, tais
como as redes de pequeno mundo [15] e as redes com a distribuição em lei de potência da
conectividade K [16]. Todavia, neste trabalho será considerado apenas o caso em que a
conectividade é a mesma para todos os elementos, ou seja, K
i
= K.
1.2 Modelo 26
Figura 1: Diferentes tipos de conexões. (a) Podemos observar que em uma rede regular as
conexões são escolhidas de acordo com a geometria do espaço. No exemplo em questão,
podemos observar o elemento σ
i
está conectado aos primeiros e segundos vizinhos, ou
seja, aos 4d primeiros vizinhos, no espaço unidimensional d = 1. (b) Ao contrário do
item anterior, o elemento σ
i
pode ter suas conexões aleatoriamente escolhidas, ou seja,
qualquer elemento σ
j
do sistema tem igual chance de pertencer ao conjunto de elementos
controladores do elemento σ
i
.
A geometria da rede booleana desempenha um importante papel na dinâmica do sis-
tema, pois o modo como as conexões estão distribuídas determina tanto o estado coletivo
do sistema quanto dos seus elementos constituintes. Como exemplos, podemos citar as
redes regulares, onde os K elementos de controle σ
j1
, σ
j2
, σ
j3
, ..., σ
jK
podem ser escolhidos
de um conjunto dos 4d vizinhos mais próximos em uma rede hiper-cúbica d dimensional
(Ver Fig. 1a). Um outro exemplo são as redes aleatórias uniformes, na qual qualquer
elemento do sistema tem igual chance de pertencer a um ou mais conjuntos de elementos
controladores (Ver Fig. 1b).
Fazendo uma análise minuciosa de um sistema booleano, temos que em uma rede com
N elementos há um espaço de estado com Ω = 2
N
possíveis configurações e que a função
booleana f
i
(σ
j
1
, σ
j
2
, σ
j
3
, ..., σ
j
K
) possui exatamente 2
K
arranjos.
Sabendo que a função booleana possui apenas dois valores de saída por arranjo, ou
seja, 0 ou 1, resulta que o número total de diferentes funções é dado por
N
f
= 2
2
K
. (1.3)
Para exemplificar, tomemos uma função booleana com K = 2. Neste caso, haverá 2
2
= 4
configurações possíveis com argumentos σ
j
1
, σ
j
2
e para cada uma destas configurações
1.2 Modelo 27
σ
i
1
σ
i
2
f
i
(σ
i
1
, σ
i
2
)
0 0 0 0 0 0 0 0 0 0 1 1 1 1 1 1 1 1
0 1 0 1 0 1 0 1 0 1 1 0 1 0 1 0 1 0
1 0 0 0 1 1 0 0 1 1 1 1 0 0 1 1 0 0
1 1 0 0 0 0 1 1 1 1 1 1 1 1 0 0 0 0
Tabela 1: Ilustração do conjunto das possíveis funções booleanas com dois argumentos.
Nas duas primeiras colunas da esquerda para direita, o agrupamento de cada par de
zeros e uns de cada linha forma o conjunto de arranjos da função booleana. No restante
das dezesseis colunas, cada coluna forma um ensemble e o agrupamento dos dezesseis
ensembles formam o conjunto de todos os ensembles possíveis para a função booleana
com K = 2 argumentos.
poderá haver dois valores de saída (0 ou 1), resultando em um total de 2
2
2
= 16 possíveis
funções booleanas (Tabela 1).
Dado um conjunto de arranjos de uma função booleana, podemos definir um ensemble
como sendo o conjunto formado por 0 e 1 associados a saída do grupo de arranjos da função
Booleana (Ver Tabela 1). A formação de um ensemble pode ser dado através da atribuição
de zeros e uns segundo uma distribuição de probabilidade. Há várias maneiras de escolha
para a distribuição, como por exemplo:
• Distribuição Uniforme: inicialmente introduzida por Kauffman, temos que todos os
ensembles tem a mesma possibilidade de ocorrer com probabilidade igual a 1/N
f
;
• Distribuição Probabilística: neste modelo, a probabilidade para que ocorra a saída
0 associado a um dado arranjo da função booleana é p e para a saída 1 é (1 − p)
(Ver Tabela 2);
• Funções Canalizadoras: neste tipo de função, o valor de saída da função booleana é
fixo para um dado valor de argumento (Ver Tabela 2);
• Funções Adaptativas: são funções capazes de se adaptar a um determinado fim. Um
exemplo de sua utilização é na simulação das sinapses de uma rede de neurônios.
Dos casos citados acima, o ensemble mais simples de ser trabalhado são os formados
pela distribuição uniforme. Entretanto, na formulação original das redes booleanas, as
conexões eram escolhidas aleatoriamente e as saídas da função f
i
eram determinadas
segundo uma tendência p. Esse modelo ficou conhecido como redes de Kauffman ou redes
booleanas aleatórias, servindo inicialmente para o estudo de regulação genética.
1.2 Modelo 28
Aleatório Canalizadora
σ
i
1
σ
i
2
σ
i
3
f(σ
i
1
, σ
i
2
, σ
i
3
) f(σ
i
1
, σ
i
2
, σ
i
3
)
0 0 0 0 1
0 0 1 1 1
0 1 0 0 1
0 1 1 0 1
1 0 0 1 0
1 0 1 0 1
1 1 0 1 1
1 1 1 1 0
Tabela 2: Ilustração de duas funções booleanas com três argumentos. A primeira função
(quarta coluna da esquerda para a direita) é formada por uma distribuição probabilística.
A função será uniforme quando p = 0.5. Na quinta coluna temos uma função canalizadora.
Neste exemplo, sempre que o estado do primeiro argumento σ
i
1
for igual a 0, o valor de
saída da função será sempre 1 independentemente dos estados dos outros argumentos σ
i
2
e σ
i
3
. Quando σ
i
1
for igual a 1, a distribuição seguirá uma distribuição probabilística.
Desde que as conexões e as funções booleanas sejam dadas, podemos, então, definir
um modelo de atualização utilizando a equação (1.1) para atualizar os estados de todos
os elementos do sistema. A forma de atualização pode ser
• Atualização sincronizada : todas as variáveis são atualizadas simultaneamente;
• Atualização serial : apenas uma variável é atualizada em cada passo de tempo.
Estas variáveis p odem ser escolhidas aleatoriamente ou por um esquema previamente
definido.
O modelo estará completamente finalizado ao determinarmos o aspecto dinâmico da es-
trutura, que pode ser:
• Modelo Quenched: em português quer dizer temperado, consiste em manter ao longo
de todo o tempo sempre as mesmas regras de atualização;
• Modelo Annealed: em português quer dizer recosido, consiste em escolher em cada
passo de tempo novas regras de atualização tais como novas conexões e funções
booleanas;
A fim de exemplificar o que foi dito nesta seção, suponhamos um pequeno sistema
formado por três elementos (N = 3) cada qual com duas conexões (K = 2). Suponhamos
1.2 Modelo 29
Figura 2: Ilustração exemplificando um esquema dinâmico de uma rede booleana. a)
Um diagrama de conexões contendo três elementos binários conectados entre si. A tabela
mostra a regra de cada elemento, onde o elemento 1 é governado pela função “E“ e os
elementos 2 e 3 são governados pela função ”OU”. b) A tabela mostra os 2
3
= 8 possíveis
estados do sistema em um dado tempo t no lado esquerdo e seus respectivos estados
evoluídos para o tempo t + 1 no lado direto. c) Representação da dinâmica do sistema
por gráfos de estado. Cada conjunto de algarismos representa um estado em um dado
instante e as setas indicam o sentido da evolução temporal dos estados.
também que a dinâmica do sistema seja quenched. Assim, fixaremos as seguintes regras:
o elemento 1 será governado pela função "E", ou seja, seu estado será sempre igual a 1
se os estados dos seus vizinhos forem 1 ao mesmo tempo e 0 caso contrário; os elementos
2 e 3 serão governados pela função "OU", onde basta apenas um dos seus vizinhos ter
estado igual a 1 para que seu estado torne-se 1 (Fig. 2a). A atualização de todos os
possíveis estados do sistema no tempo t ao t + 1 é mostrado na Fig. 2b. Em cada passo
de tempo, um estado evolui exclusivamente para outro e a sucessão da evolução destes
estados definem uma trajetória, a qual é indicada pelas setas na Fig. 2c.
Em um sistema quenched de tamanho finito há necessariamente um número finito
de estados. Com isso, temos que em algum momento do processo dinâmico o estado
do sistema deva eventualmente evoluir para outro estado já visitado. Sendo, então, o
modelo quenched um modelo determinístico (regras fixas), o sistema passará a percorrer
indefinidamente sempre a mesma trajetória, formando, assim, um ciclo de estados [17].
Na maioria casos, entretanto, o estado inicial de um sistema não faz parte de um ciclo
de estados. Assim, temos que na evolução temporal o estado inicial sempre irá alcançar
algum ponto do ciclo de estado. Definimos, então, um ciclo de estados como sendo um
atrator, pois o estado inicial de um sistema quenched de tamanho finito sempre evoluirá
para um ciclo de estado, e definimos também uma bacia atratora como o conjunto de
trajetórias que alcançam um atrator Fig. 3.
1.3 Fluxo de informação 30
Figura 3: Um atrator é formado quando o estado de um sistema evolui para outro estado
já visitado, passando a repetir indefinidamente sempre a mesma trajetória (sequências)
de estados. A bacia atratora é formada por todos os estados que evoluem naturalmente
para algum estado de um atrator. Na ilustração, temos uma base atratora de uma Rede
Booleana com N=13 elementos e K=3 conexões. Cada estado do sistema é representado
por um círculo e o sentido da evolução temporal acorre de fora para dentro da figura,
onde as linhas conectam um estado ao sucessor. O atrator é de tamanho 7 (sete estados)
e o sentido de sua evolução temporal é indicado pela seta. A tabela de bit ilustra um dos
estados que compõe a base atratora. (Fig. adaptada de [18])
Ao contrário do modelo quenchead, um sistema annealed não possui atratores. Isto
ocorre independentemente do estado do sistema ter evoluído para um estado já visitado,
pois a mudança de regras e conexões impossibilitam que o estado sucessor seja mesmo
estado sucessor da vez anterior.
1.3 Fluxo de informação
O estudo das redes complexas tem como um dos principais assuntos investigados o
processo de propagação de informação. Essa propriedade é de fundamental importância,
pois p odemos ampliar o conceito de informação e identificá-la a qualquer tipo de enti-
dade capaz de fluir em uma rede independentemente da sua formação estrutural. Assim,
podemos, por exemplo, definir a informação como sendo um vírus ou uma fofoca que se
propaga em uma rede de pessoas ou uma pequena perturbação causada em uma rede
cristalina.
1.3 Fluxo de informação 31
Figura 4: A distância de Hamming fornece a quantidade de estados diferentes dos pares
conjugados entre duas redes semelhantes. Na ilustração, temos a representação esquemá-
tica de duas redes semelhantes com 16 elementos. Os pares de elementos conjugados com
mesma cor possuem o mesmo estado e os que são cores diferentes (marcados por bolas
pretas) possuem estados diferentes. Neste exemplo, a distância de Hamming é H(t) = 4.
Investigar a resposta às mudanças constitui um dos principais focos no estudo das
redes booleanas. Esta propriedade indica o grau de robustez de uma rede, permitindo-nos
elucidar questões como: dado um dano no sistema, até quantos estados subseqüentes do
sistema ele pode perdurar? O sistema se recompõe ou diverge com um dano? Há uma
probabilidade do dano se propagar indefinidamente?
No que se refere ao estudo de fluxo de informação em redes booleanas, podemos
associar a propagação de informação à propagação de dano. Neste contexto, a simulação
computacional viabiliza o estudo da propagação considerando a evolução temporal de
sistemas idênticos, onde eles se diferenciam somente por uma pequena mudança ou na
função booleana ou nos estados iniciais dos elementos da rede.
O estudo abordado neste trabalho consiste em considerar dois sistemas semelhantes,
ou seja, dois sistemas
Σ
0
= {σ
1
(0), σ
2
(0), σ
3
(0), ..., σ
i
(0)} (1.4)
e
Σ
0
= {σ
1
(0), σ
2
(0), σ
3
(0), ..., σ
i
(0)} , (1.5)
que se diferem apenas por uma pequena fração de sítios com estados iniciais diferentes.
Desta forma, podemos analisar as configurações dos estados a partir da evolução temporal
sob a mesma dinâmica através da grandeza
H(t) =
N
i=1
(σ
i
(t) − σ
i
(t))
2
, (1.6)
que informa a quantidade de estados diferentes dos pares de elementos conjugados entre
as duas redes e é definida como sendo a distância de Hamming (Fig. 4).
Podemos concluir que se a transferência de informação no sistema for localizada, a
distância de Hamming não crescerá muito. Entretanto, se o sistema for suficientemente
1.3 Fluxo de informação 32
caótico, a informação poderá abranger todo o sistema, fazendo com que a distância de
Hamming nunca chegue a zero [19].
Outra medida bastante utilizada é a sobreposição normalizada entre configurações de
estado a(t), que é definida como
a(t) = 1 − h(t) , (1.7)
onde definimos h(t) = H(t)/N como sendo a distância de Hamming normalizada.
Analisando as equações (1.6) e (1.7) no limite do tempo tendendo ao infinito, temos
que se lim
t→∞
h(t) = 0 ou lim
t→∞
a(t) = 1 o sistema não reterá informação (dano) seja
qual for seu estado inicial. Entretanto, se lim
t→∞
h(t) > 0 ou lim
t→∞
a(t) < 1 a informação
permanecerá no sistema indefinidamente.
O modelo de rede booleana possui três tipos de fases (regimes), as quais podem ser
identificadas a partir da distância de Hamming. Desta forma, temos que na fase ordenada
a informação (quantidade de estados diferentes entre as redes) se propaga com o tempo
apenas por um número finito de elementos. Contrariamente, na fase caótica a informação
se propaga exponencialmente com o tempo, atingindo toda a rede. Por último, uma
fase intermediária, a crítica, na qual informação se propaga apenas algebricamente com o
tempo.
1.3.1 Teoria do Campo Médio
Utilizando a teoria do campo médio, na qual as interações dependem das médias glo-
bais da rede desprezando qualquer flutuação local, podemos realizar a primeira abordagem
analítica através da distância de Hamming para estudar a dinâmica da rede booleana e
determinar o limite que separa as fases ordenada e caótica [19]. Para isso, imaginemos
uma rede annealed Σ
0
formada por um número muito grande de elementos, onde todas
as conexões e estados iniciais sejam aleatoriamente escolhidos e a função booleana siga
uma distribuição uniforme. Seja a rede
Σ
0
uma rede semelhante a Σ
0
, diferenciando-se
apenas em poucos elementos com estados iniciais diferentes. A diferença inicial entre as
duas redes é quantificada pela distância de Hamming h(0), a qual fornece o número de
elementos diferentes no tempo zero. Na dinâmica do sistema, teremos que em média um
único elemento participará dos argumentos de K funções booleanas. Logo, poderemos
concluir que haverá Kh(0) funçõ es afetadas. Como a função booleana é uniformemente
distribuída, cada uma das funções alteradas terá uma probabilidade 1/2 de fornecer um
1.3 Fluxo de informação 33
valor de output diferente para cada elemento conjugado das redes. Portanto, a distância
de Hamming depois do primeiro passo será
h(1) =
1
2
Kh (0) . (1.8)
Se na evolução de cada passo de tempo o sistema mantiver a escolha das conexões e
das funções booleanas suficientemente aleatórias, o mesmo procedimento utilizado para a
equação (1.8) poderá ser mantido para passos de tempo consecutivos, logo,
h(t + 1) =
1
2
Kh( t) , (1.9)
substituindo h(t) por h(0) em cada iteração desde o tempo zero, temos que
h(t + 1) =
K
2
t
h(0)
h(t + 1) = h(0) exp [ln (0.5K) t] . (1.10)
Analisando a equação (1.10), observamos que para K > 2 o número de elementos dife-
rentes crescerá exponencialmente e para k < 2 decairá exponencialmente. Já para K = 2
não terá nem crescimento nem decaimento exponencial, haverá apenas um comporta-
mento influenciado por flutuações. Podemos, portanto, concluir que variando o valor da
conectividade, o sistema poderá apresentar uma das seguintes fases:
• Caótico (K > 2), a distância de Hamming cresce exponencialmente com o tempo;
• Ordenado (K < 2), a distância de Hamming decresce exponencialmente com o
tempo;
• Crítico (K = 2), a evolução temporal da distância de Hamming é determinada
essencialmente por flutuações.
1.3.2 Solução Geral
Pudemos obter a equação (1.10) assumindo que a função booleana do sistema adquire
os valores 1 e 0 com a mesma probabilidade p = 1/2. Entretanto, veremos que as fases
ordenada, caótica e crítica também estão presentes em casos mais gerais em que saídas 0 e 1
da função booleana são atribuídos de acordo com probabilidades p e 1−p respectivamente.
Assim, temos que para um dado valor de probabilidade p há um valor crítico K
c
(p) para
a conectividade K, onde abaixo dele o sistema apresenta a fase ordenada e acima a fase
1.3 Fluxo de informação 34
caótica. De maneira contrária, dado um valor para K, haverá um valor de probabilidade
crítica p
c
(K) que separa a fase ordenada da caótica em um sistema booleano. A solução
analítica foi obtida primeiramente por [12], fornecendo uma relação de recorrência para
distância de Hamming em função da conectividade K e da probabilidade p.
Analisando a equação (1.7), podemos perceber que a sobreposição a(t) entre os estados
dos sistemas Σ
t
e
Σ
t
em um tempo t é a probabilidade de um par de elementos conjugados
(σ
i
, σ
i
) possuírem os mesmos estados em ambas as redes. Portanto, a probabilidade de
encontrarmos os argumentos da função booleana com os mesmos estados nas duas redes
será
ρ
K
= [a(t)]
K
. (1.11)
No próximo passo de tempo a sobreposição a(t + 1) será determinada pela soma da
probabilidade dos argumentos da função booleana serem os mesmos no passo anterior
(probabilidade ρ
K
) mais a probabilidade de haver pares de elementos conjugados com
pelo menos um argumento diferente da função booleana (probabilidade 1 − ρ
K
) virem a
possuir os mesmos estados (probabilidade 1 + 2p(p − 1) (Tabela 3)), ou seja,
a(t + 1) = ρ
K
+ (1 − ρ
K
)[1 + 2p(p − 1)]
a(t + 1) = a(t)
K
+ (1 − a(t)
K
)[1 + 2p(p − 1)]
a(t + 1) = 1 − (1 − a(t)
K
)2p(p − 1)
a(t + 1) = 1 −
(1 − a(t)
K
)
/K
c
, (1.12)
onde K
c
é definido por
K
c
=
1
2p(p − 1)
. (1.13)
Substituindo a equação 1.12 na equação 1.7 podemos determinar a evolução temporal da
distância de Hamming, que é dada por [19]
h(t + 1) =
1 − [1 − h(t)]
K
/K
c
. (1.14)
Umas formas alternativas de representar a evolução temporal da Hamming foi dada
em [1]. Neste trabalho foi proposto que a dinâmica da distância de Hamming deveria ser
obtida a partir do mapa iterativo
h(t + 1) = I
1
Kh (t)[1 − h(t)]
K−1
+
1
2!
I
2
K(K − 1)h(t)
2
[1 − h(t)]
K−2
+
1
3!
I
3
K(K − 1)(K − 2)h(t)
3
[1 − h(t)]
K−3
+ ... , (1.15)
onde a influência I
i
representa a probabilidade de um elemento que tem i vizinhos danifi-
1.3 Fluxo de informação 35
σ
i
σ
i
Probabilidade
1 1 p
2
1 0 p(1 − p)
0 1 (1 − p)p
0 0 (1 − p)
2
Tabela 3: A tabela mostra a probabilidade das possíveis ocorrências de configurações for-
madas a partir de dois elementos conjugados de redes semelhantes. A variável p representa
a probabilidade da função booleana ter outputs 1 e a quantidade (1 − p) a probabilidade
de outputs 0. Podemos perceber, portanto, que a probabilidade de termos configurações
iguais é dada por p
2
+(1−p)
2
= 1+2p(p−1) e diferentes por p(1−p)+(1−p)p = 2p(1−p).
cados tornar-se danificado no passo de tempo seguinte. Em particular, foi mostrado que
para redes booleanas aleatórias que a influência média não depende do número de inputs
danificados, o que resulta na igualdade I
1
= I
2
= I
j
= I = 2p(1 − p) e conseqüentemente
na equação 1.14.
1.3.3 Diagrama de fases
Podemos fazer uma análise do comportamento da distância de Hamming a partir da
equação 1.14. Para isso imaginemos em um dado instante a propagação de uma pequena
perturbação no sistema e, então, expandimos em série de Taylor a equação 1.14, onde
teremos
h(t + 1) =
1
K
c
Kh (t) −
K(K − 1)
2
[h(t)]
2
+ ...
h(t + 1) − h(t) =
K
K
c
− 1
h(t) −
K(K − 1)
2K
c
[h(t)]
2
+ ...
∆h(t) =
K
K
c
− 1
h(t)∆t −
K(K − 1)
2K
c
[h(t)]
2
∆t + ... , (1.16)
onde ∆h(t) = h(t + 1) − h(t) e ∆t = 1. A integração do termo de primeira ordem da
equação 1.16 resulta em
h(t) ∼ exp

K
K
c
− 1
t
. (1.17)
Fazendo um estudo de caso, temos que para K > K
c
o sistema se comportará caoti-
camente, pois por menor que seja a perturbação, a distância crescerá exponencialmente
com o passar do tempo até que a informação (dano) alcance toda a rede. Notemos, por-
tanto, que no caso particular em que p = 1/2 e K = 2, o comportamento da distância
de Hamming está em completo acordo com o estudo feito para a aproximação de campo
1.3 Fluxo de informação 36
Figura 5: Diagrama de fases das redes booleanas aleatórias. A área rachurada corresponde
a fase ordenada e a área logo acima corresponde a fase caótica. A curva que separa ambas
as regiões é a equação K
c
= [2p(1 − p )]
−1
. Gráfico adaptado de [19].
médio. Para K ≤ K
c
, a distância de Hamming tenderá a zero para longos períodos de
tempo, o que significa dizer que o dano se propagará localmente e, então, desaparecerá.
Finalizamos este capítulo abordando um dos aspectos mais importantes da equação
1.17, o qual a partir dela podemos determinar os valores críticos que separam os regimes
ordenado e caótico. Essa situação ocorrerá quando a relação k/k
c
for igual a 1, uma vez
que de acordo com a equação 1.17 o regime não será nem ordenado nem caótico. Portanto,
K
K
c
= 1
K[2p(p − 1)] = 1
2p(p − 1) = K
−1
p
2
− p +
1
2K
= 0 ,
resolvendo a equação do segundo grau acima, temos
p
1,2
c
=
1
2
±
1
4
−
1
2K
. (1.18)
A partir da equação 1.18 temos que para um dado valor de K, o sistema poderá ser posto
1.4 Comportamento Dinâmico no Ponto Crítico 37
em uma das três diferentes fases ajustando apenas o valor da probabilidade p. A linha
crítica que separa os regimes ordenado e caótico será obtido variando ou o valor de K ou
o valor de p (Fig. 5).
1.4 Comportamento Dinâmico no Ponto Crítico
1.4.1 Teoria
Na seção anterior deduzimos a solução geral para a distância de Hamming (Eq.1.14) e
pudemos a partir dela determinar analiticamente os estados de fase ajustando apenas os
valores da conectividade K e da probabilidade p (Eq. 1.17). Entretanto, a aproximação de
primeira ordem da equação (1.14) falha (fornecendo um valor nulo) quando pretendemos
determinar o comportamento crítico (K = K
c
) do sistema. Para resolver este problema,
realizamos uma aproximação de segunda ordem (ver equação 1.16), ou seja,
∆h(t) = −
(K − 1)
2
[h(t)]
2
∆t
1
[h(t)]
2
∆h(t) = −
(K − 1)
2
∆t . (1.19)
A integração da equação acima resulta em um decaimento em lei de potência da forma
h(t) ∼ t
−β
, (1.20)
onde β = 1 é um expoente crítico. Segundo a equação (1.20), a rede booleana no ponto
crítico comporta-se como na fase ordenada, exceto pelo decaimento lento do dano em
forma de lei de potência. O expoente β está de acordo com o valor esperado para o
modelo de campo médio para percolação direcionada [20, 21], pois evidências numéricas
conjecturam que a transição do dano em sistemas annealed está na mesma classe de
universalidade da percolação direcionada [22]. Porém, uma exceção é verificada para o
modelo de percolação direcionada em duas dimensões com a dinâmica de Glauber, onde a
temperatura de transição de dano coincide com a temperatura crítica do sistema [23]. Para
dimensões maiores, essa coincidencia não ocorre mais [24], fazendo com que a conjectura
de equivalência seja válida (Uma discurção mais precisa sobre esse tema pode ser visto
em [25]).
Devido às flutuações, que são intrínsecas à dinâmica de redes booleanas, e a existência
de pontos fixos, quando a distância de Hamming se torna zero, a demonstração direta por
simulção numérica do decaimento em lei de potência dado da equação 1.20 torna-se uma
1.4 Comportamento Dinâmico no Ponto Crítico 38
tarefa muito complicada. Para contornar esta situação, propomos um novo método de
estudo que consiste em analisar estatísticamente o tempo de relaxação t
R
, que é definido
como o período de tempo necessário para que a distância de Hamming convirja para zero.
Podemos, ao invés de estudar um sistema no limite termodinâmico (redes com N →
∞), tomar um ensemble de M redes de tamanho finito e, então, definir a distância de
Hamming como a média da distância entre as duas redes semelhantes, ou seja,
¯
h(t) =
1
M
M
i=0
h
i
(t) . (1.21)
Em redes de tamanho finito há uma chance de h
i
(t) convergir para zero em passos
finitos de tempo. Quando isto ocorre, o par de redes evoluirá sempre para os mesmos
estados de sítios, fazendo com que o sistema atinja um estado de repouso dinâmico.
Nessa condição, a distância de Hamming será igual a zero idefinidamente, h
i
(t
R
< t) = 0,
e não contribuirá mais para a media definida na equação 1.21. Se definirmos M
d
como os
pares de redes não alcançaram o estado de repouso, teremos
¯
h(t) =
M
d
M
1
M
d
M
d
i=0
h
i
(t) . (1.22)
Analisando a equação (1.22), podemos observar que a fração M
d
/M dá a probabilidade
P (t
R
> t) de termos o tempo de relaxação t
r
de um dado par de redes maior que o
tempo t. Quando tomamos somente a fração M
d
/M, é razoável esperar que a função
de distribuição de probabilidade de
¯
h(t) tenha um comportamento estacionário. Neste
trabalho, assumimos que a distância média dos pares de redes não convergentes flutua em
torno de uma média, permitindo que possamos considerar o somatório da equação 1.21
constante, ou seja,
1
M
d
M
d
i=0
h
i
(t) = const . (1.23)
Assim, a equação (1.21) torna-se
¯
h(t) ∼ P (t
R
> t) . (1.24)
Substituindo, então, a equação (1.20) na (1.21), temos
P (t
R
> t) ∼ t
−β
, (1.25)
com expoente β = 1. Esse resultado nos mostra que podemos, mediante simulação numé-
1.4 Comportamento Dinâmico no Ponto Crítico 39
Figura 6: Distribuição cumulativa do tempo de relaxação no ponto crítico. O tempo de
relaxação é definido como a quantidade de passos necessários para que o dano em um
par de redes semelhantes chegue a zero. A linha pontilhada é o comportamento esp e-
rado. Podemos ver que, para sistemas muito grandes, a distribuição segue o decaimento
previsto em forma de lei de potência, P (t
R
> t) ∼ t
−1
. Podemos observar, entretanto,
um pequeno desvio para pequenas escalas de tempo e um truncamento exponencial para
tempos muito grandes, que está localizado por um tempo de escala dado por t
×
∼ N
1/2
(
ver inset). O resultado para N = 2
31
foi obtido numericamente iterando a equação 1.26.
Este resultado mostra que até na condição crítica, o sistema tende a alcançar o estado
ordenado. Entretanto, no limite termodinâmico o tempo de relaxação médio diverge. O
mais importante deste resultado é que na maioria dos casos o sistema se recupera da
pertubação dep ois de poucos passos, enquanto que em pouquíssimos casos a resposta ao
estimulo faz o sistema sofrer uma transição global.
rica, confirmar que a distribuição de probabilidade 1.25 segue a lei de potência esperada,
como será exposto na seção a seguir.
1.4.2 Resultado Numérico
A confirmação dos resultados expostos na seção anterior foi obtido a partir de dois
procedimentos numéricos diferentes, ambos corroborando a teoria proposta nesse trabalho.
O primeiro, mais intuitivo, consiste em definir duas redes semelhantes com N elementos
booleanos e, então, calcular a quantidade de pares de elementos conjugados com estados
diferentes em cada passo de tempo. O segundo procedimento é baseado no trabalho de
Derrida e Pomeau [12], onde foi mostrado que o número de elementos danificados na rede
1.4 Comportamento Dinâmico no Ponto Crítico 40
Figura 7: Distribuição cumulativa do tempo de relaxação t
R
para a fase ordenada próxima
do ponto crítico. Estas curvas foram obtidas para uma rede de tamanho N = 102400 e
conectividade K = 3. Os resultados mostram que a fase ordenada o tempo de escala
τ
0
do truncamento exponencial da distribuição é determinado por τ
0
∼ (I
c
− I)
−ν
para
ν = 1. O gráfico principal mostra a distribuição escalonada pelo tempo de correlação ν
0
,
enquanto os dados originais podem ser visto no inset.
é obtido a partir da equação de iteração estocástica
P (m, n) =
N!
m!(N − m)!
(Iq)
m
(1 − Iq)
N−m
, (1.26)
tal que I = 2p(1 − p), m e n são respectivamente o número de elementos danificados nos
passos seguinte e atual e a quantidade q = 1−(1−n/N)
K
é a probabilidade com a qual um
elemento tem de possuir uma conexão com um outro elemento danificado. Os resultados
de ambos os procedimentos foram obtidos da média de um essemble de 50.000 pares de
redes, onde mantivemos fixa a conectividade K = 3 e variamos tanto o tamanho da rede
N como a distribuição da probabilidade p. No entanto, optamos por expor neste trabalho
os resultados do segundo procedimento devido à rapidez e capacidade de obtermos redes
com o tamanho de até N = 2
31
.
A conjectura discutida na seção anterior é apoiada pelos resultados da figura (6), que
mostra a distribuição cumulativa do tempo de relaxação t
R
para uma rede de tamanho
finito no p onto crítico (K = K
c
). O tempo de relaxação é definido como o período de
tempo necessário para que a distância de Hamming convirja a zero após o sistema ter os
estados de um par de elementos conjugado danificado inicialmente.
1.4 Comportamento Dinâmico no Ponto Crítico 41
Figura 8: Distribuição cumulativa do tempo de relaxação para a fase caótica próxima do
ponto crítico. Os resultados foram obtidos para uma rede de tamanho N = 102400 e
conectividade K = 3. Quando I
c
> I, o sistema está no regime caótico e, então, espera-
mos que o dano nunca convirja a zero. Esta concepção é consistente com os resultados,
onde vemos que o crossover da lei de potência decai para um comportamento plano. Isto
significa dizer que a média do tempo de relaxação diverge até para uma rede de tamanho
finito. O tempo de correlação τ
0
∼ (I − I
c
)
−ν
nos dá o tempo de escala para diferentes
probabilidades. Podemos perceber um truncamento exponencial para valores de I se apro-
ximando da condição crítica. Este truncamento ocorre devido ao tamanho finito da rede.
Podemos perceber também que o início do truncamento varia cada vez mais rapidamente
com o aumento de (I − I
c
). O gráfico principal mostra a distribuição escalonada com o
tempo de correlação τ
0
, enquanto que os dados originais podem ser vistos no inset.
Os resultados mostram que a distribuição cumulativa possui aproximadamente o ex-
poente esperado (β = 1) acima do ponto de crossover, a partir do qual a curva segue
decaindo exponencialmente (Fig. 6). O ponto onde se inicia o decaimento exponencial é
localizado para diferentes tamanhos de redes com um tempo característico que cresce na
forma t
×
∼ N
γ
para γ = 1/2 (inset da figura 6). Este resultado é surpreendente, pois
mostra que redes booleanas tem um limite para o tempo de relaxação t
R
até mesmo na
condição crítica (K = K
c
). O valor esperado para o expoente β = 1 na equação 1.25
foi confirmado obrigatoriamente para simulações com redes de tamanhos muito grandes,
onde a curva da distribuição cumulativa coincide com a lei de potência por quase quatro
ordens de grandeza (Fig. 6).
Investigamos também o comportamento não crítico do sistema partindo do ponto
crítico. Na figura (7) mostramos resultados para redes se aproximando do ponto crítico a
partir do regime ordenado. Similarmente à condição crítica, a distribuição decai como lei
1.4 Comportamento Dinâmico no Ponto Crítico 42
Figura 9: Distribuição cumulativa do tempo de relaxação para o caso quenched. Na fase
ordenada próxima do ponto crítico, a distribuição torna-se restrita a pequenos tempos de
escala. Como no modelo annealed, o inset mostramos a superposição das curvas por um
tempo de correlação dado por τ
0
∼ (I − I
c
)
−ν
, com ν = 1.
de potência seguida por um regime exponencial. Neste caso, entretanto, a escala de tempo
para o qual o sistema vai para o regime exponencial é controlado pelo deslocamento da
condição crítica. Assim, definimos o tempo de correlação τ
0
∼ (I − I
c
)
−ν
para ν = 1. Este
resultado está de acordo com o esperado para o modelo de campo médio para percolação
direcionada [20, 21]. No caso ordenado, τ
0
é definido como o tempo de escala além do
qual o dano é removido completamente da rede.
Um comportamento complementar é observado quando o sistema vai para o ponto
crítico a partir do regime caótico, como mostra a figura (8). Neste caso, há um trun-
camento do ponto do decaimento exponencial, onde observamos um crossover para um
comportamento plano. Esta situação é consistente com o fato do tempo de relaxação
médio divergir no regime caótico. Como na fase ordenada, o tempo de escala para o
crossover na fase caótica é determinado pelo tempo de correlação τ
0
∼ (I − I
c
)
−ν
para o
mesmo expoente ν = 1. Temos, portanto, que no caso caótico τ
0
é o tempo a partir do
qual toda a memória do estado inicial é perdida e as duas redes inicialmente semelhantes
divergem para estados completamente distintos. Concluímos que assim como o expoente
β, o expoente ν está também de acordo com os resultados obtidos para o modelo de campo
médio pata percolação direcionada [20, 21].
Por último, estendemos nossos resultados para a distribuição do tempo de relaxação
1.5 Conclusões 43
para o modelo de redes booleanas quenched, onde a atualização da função booleana e a
estrutura desordenada das conexões são fixas. Construímos uma rede quenched e a dei-
xamos evoluir até que ela alcance um ciclo atrator. Subseqüentemente, provocamos uma
pertubação no atrator alterado o estado de um dos elementos da rede em um dado instante
e medimos o tempo necessário para que o sistema retorne para o mesmo ciclo atrator. Os
casos onde o sistema evolui para diferentes atratores não são considerados na estatística
e, como a forma da distribuição depende do comprimento do atrator, restringimos nosso
estudo para os casos onde o ciclo do atrator tenha pelo menos mais de 10 estados.
Observando a figura (9), temos que a distribuição do tempo de relaxação ao caso
quenched segue um comportamento inteiramente similar para o caso annealed, ou seja,
um decaimento lento seguido por um truncamento exponencial. O onset para escalas de
tempo muito grande é controlado pelo deslocamento da condição crítica τ
0
∼ (I − I
c
)
−ν
,
com ν = 1, onde podemos observar que esta relação é igual a relação de escala obtida para
o modelo annealed. Este resultado reforça a idéia que sob certas condições a rede booleana
aleatória pode ser apropriada para estudar a condição crítica de redes regulatórias.
1.5 Conclusões
Neste capítulo apresentamos resultados obtidos para a dinâmica de redes booleanas
sujeitas a uma pequena perturbação, onde observamos que dependendo do regime em
que o sistema se encontra, a distribuição cumulativa do tempo de relaxação apresenta
diferentes comportamentos.
Nesse sentido temos que no ponto crítico a distribuição cumulativa do tempo de rela-
xação segue um decaimento em lei de potência com expoente β = 1. Este comportamento
está, portanto, de acordo com a conjectura que diz que tanto a dinâmica de propaga-
ção de danos em redes annealed como o modelo de percolação direcionada pertencem à
mesma classe de universalidade [20, 21, 25]. Observamos ainda que na condição crítica
há um truncamento exponencial na região de grandes tempos de relaxação, cujo início do
truncamento escalona com o tamanho do sistema na forma τ
×
∼ N
1/2
.
Na fase ordenada próxima do ponto crítico a distribuição do tempo de relaxação tem
um crossover para um decaimento exponencial, indicando que uma pequena perturbação
é perdida depois de apenas alguns passos de tempo. Já na fase caótica próxima do ponto
crítico o crossover vai para um regime plano, indicando que o sistema poderá nunca se
recuperar de uma perturbação por menor que ela seja.
1.5 Conclusões 44
Nossos resultados podem ser interpretados dentro de uma conjectura de "vida no
limite do caos" proposto por Kauffman [2]. De acordo com esta idéia, nem o regime
ordenado nem o regime caótico podem modelar ao mesmo tempo de forma eficiente a
robustez e a adaptabilidade observadas nos sistemas auto-regulatórios reais. No contexto
dos nossos resultados, temos que apesar da distância de Hamming no regime ordenado ir
a zero com pequenos tempos de relaxação, a quantidade de estados envolvidos no processo
dinâmico é muito pequeno, impedindo a adaptabilidade. Já no regime caótico, temos um
grande número de estados envolvidos no processo dinâmico, porém o tempo de relaxação
tende a infinito, inviabilizando a auto-regulação. No ponto crítico temos o meio termo,
ou seja, temos tanto grande quantidade de estados envolvidos no processo dinâmico como
um tempo de relaxação tendendo a zero em tempos relativamente pequenos.
A distribuição em lei de potência achada no ponto crítico nos mostra que para maioria
dos eventos o sistema é robusto, recuperando-se completamente de pequenas perturbações
e erros externos. Desta forma, temos que a alteração de poucos elementos pode provocar
um processo que faça com que a maioria dos elementos não afetados do sistema responda à
pertubação, assemelhado-se a um sistema real respondendo a alguma mudança ambiental.
45
2 DECOMPOSIÇÃO DE REDES
LIVRES DE ESCALAS
Estudamos neste capítulo um novo método de decomposição de redes aplicado às redes
livres de escalas tipo Barabási-Albert. O método consiste basicamente em identificar todos
os sítios com exatamente K conexões e retirá-los simultaneamente da rede. Esse processo
é repetido iterativamente até que não haja mais sítios na rede com K conexões. Na
análise dos resultados, observamos uma série de expoentes e parâmetros bem estabelicidos
e relacionados entre si de maneira que é possível tornar o modelo auto-consistente. Na
primeira seção (2.1) apresentamos uma breve introdução às redes livres de escalas onde
propomos a rede de Barabási-Albert como um bom modelo teórico para ser trabalhado.
Na seção seguinte (2.2) definimos o novo método de decomposição e apresentamos nossos
resultados analíticos e numéricos. Na última seção (2.3) finalizamos o capítulo com a
conclusão.
2.1 Redes Livres de Escalas
O estudo topológico de redes complexas teve início com o modelo de grafos aleatórios
proposto por Erdõs e Rényi no início da década de 60 [26]. Naquela época, o estudo de
redes ficou praticamente restrito ao desenvolvimento de teorias puramente matemáticas
devido principalmente ao fato da difícil obtenção de uma grande base de dados e também
por não haver tecnologias que possibilitassem de maneira precisa sua análise. Um grande
avanço teórico se deu no início da década de 80 quando Béla Bollobás provou matematica-
mente que a distribuição de conectividade das redes aleatórias era de fato poissoniana [27],
ou seja, nesta distribuição a maioria dos vértices possuía em média a mesma quantidade
de conexões (largura do pico central da distribuição de Poisson) enquanto um pequena
minoria possuía ou poucas (lado esquerdo da distribuição de Poisson) ou muitas conexões
(lado direito da distribuição de Poisson) (Fig. 10).
2.1 Redes Livres de Escalas 46
Figura 10: Distribuição de Poisson feita a partir dos dados de uma simulação computaci-
onal de uma rede aleatória. Os dados foram gerados de uma rede de N = 10000 vértices
e probabilidade de conexão ρ = 0.0015. No eixo vertical temos a probabilidade haver o
número X
k
vértices com conectividade k (eixo horizontal) e E(X
K
)/N representa a ex-
pectativa da destribuição de Poisson para os parâmetros N = 10000 e ρ = 0.0015(Fig.
retirada de [16]).
Entretanto, ainda na década de 60 e sem conexão com o estudo de redes complexas,
dois trabalhos envolvendo redes sociais foram desenvolvidos. Primeiro em 1965, onde Price
[28] estudou o número de citações de artigos científicos e verificou que sua distribuição
seguia um decaimento em lei de potência. Depois, em 1967, o famoso estudo experimental
de Stanley Milgram [29] mostrou que entre duas pessoas desconhecidas quaisquer nos EUA
havia em média apenas uma cadeia de seis outras pessoas que as separavam, sendo este
fato conhecido posteriormente como efeito de pequeno mundo.
As redes aleatórias foram por muito tempo o único modelo teórico de redes complexas
a serem estudadas, até que em 1998 Watts e Strogatz [30] propuseram um novo modelo
que continha ao mesmo tempo tanto o efeito de pequeno mundo (característica também
presente nas redes aleatórias) quanto um alto grau de coeficiente de agrupamento (quan-
tidade de conexões próximas de um dado vértice). O modelo consistia inicialmente de
uma rede regular, onde então cada vértice era visitado e com uma probabilidade p era
reconectado aleatoriamente a outros vértices da rede. Apesar da nova característica, o
modelo de Watts e Strogatz ainda possuía uma distribuição poissoniana do seu grau de
conectividade.
2.1 Redes Livres de Escalas 47
Com o passar dos anos e com o surgimento da tecnologia computacional, o estudo dos
grafos foi convergindo cada vez mais para a aplicação em sistemas naturais, onde as redes
passaram a ser formadas por várias entidades (físicas ou idealizadas) conectadas entre
si. Assim, já no final da década de 90, dois trabalhos mudaram a concepção topológica
das redes complexas. O primeiro em 1998, onde Redner mostrou que distribuição da
quantidade de vezes com que um artigo era citado (representando a conectividade da rede)
decaia como uma lei de potência, com o expoente γ
cite
≈ 3 [31]. No ano seguinte, Barabási
et al [32] utilizaram um robô para mapear sítios da WWW (World Wide Web), onde a rede
WWW seria formada pelos sítios (vértices) e pelos hiperlinks (conexões entre os sítios).
A espectativa era que a distribuição de conectividade dos sítios corroborasse a teoria de
grafos aleatórios. Entretanto, a análise dos dados também mostrou que distribuição de
conectividade decaia em forma de lei de potência, com expoentes γ
in
≈ 2.1 (para sítios que
recebiam ligações de outros sítios) e γ
out
≈ 2.5 (para sítios que enviavam ligações de outros
sítios). A constatação deste tipo de decaimento foi um fato muito surpreendente, pois
mostrou que em alguns sistemas reais a distribuição de conectividade tanto apresentava
desvio padrão muito maior que a média de conexões como possuía uma invariância de
escala. Em um aspecto mais detalhado, temos que o grau conectividade possui todos os
níveis de tamanhos, sendo que a maioria dos vértices possui poucas conexões enquanto a
outra minoria (chamados de hubs) possui muitas conexões.
Após os trabalhos de Redner [31] e Barabási et al [32], muitos outros vieram reforçar
a idéia de que o comportamento em lei de potência de redes complexas é de certa forma
bastante comum em sistemas reais. Como exemplos podemos citar a rede da estrutura
física da internet, a qual é formada por roteadores conectados por fibra óptica ou outro tipo
de linha de transmissão [34]; rede de contato sexual entre pessoas na Suécia, que mostrou
que a maioria das pessoas em seu tempo de vida possuía apenas alguns poucos parceiros
enquanto outros poucos possuíram algumas dezenas e até centenas [35]; a rede de pessoas
conectadas por e-mail, o que poderia talvez explicar a rápida propagação de alguns tipos
de vírus; a rede de co-autorias de trabalhos científicos, a qual é formada por pesquisadores
que publicaram juntos um mesmo artigo científico [36]. Um fato curioso é que um dos
cientistas mais "conectados"é Erdõs, o qual escreveu mais de 1400 artigos com pelo menos
500 colaboradores; a rede de atores de Hollywood, os quais são considerados conectados se
dois atores atuaram juntos em algum filme [37]; a rede de metabolismo celular, onde cada
vértice representa uma molécula e cada conexão uma reação bioquímica entre elas [38]; a
rede de chamadas telefônicas, onde os vértices eram formados por números de telefones e
as conexões por chamadas completadas entre dois números [39].
2.1 Redes Livres de Escalas 48
Figura 11: Gráfico experimental da magnetização próxima do ponto crítico para cinco
tipos de materiais magnéticos diferentes, onde os eixos da magnetização e temperatura
são multiplicados respectivamente por um fator H
−1/δ
e H
−1/βδ
, com β ∼ 0.36 e δ ∼ 4.5.
Os cinco materiais são CrBr
3
, EuO, Ni, YIG e Pd
3
Fe e todos são ferromagnetos com
estruturas diferentes: o CrBr
3
é considerado uma rede anisotrópica; o EuO possui forte
interação entre os segundos vizinhos; o Ni é um ferromagneto elétron itinerante; o YIG
é um ferrimagneto; o Pd
3
Fe é uma liga magnética. Apesar da diferença estrutural, todos
os materiais possuem o mesmo expoente crítico. Assim podemos colapsar o gráfico da
magnetização em uma única curva pela multiplicação de um fator de escala, fazendo com
que os cinco materiais pertençam a mesma classe de universalidade (Gráfico retirado de
[40]).
A observação de que cada vez mais e mais fenômenos naturais apresentam grande-
zas que se comportam como uma lei de potência tem atraído boa parte da atenção da
comunidade científica. A importância deste tipo de comportamento teve seu início no es-
tudo de sistemas termodinâmicos próximos do ponto crítico, onde foram observadas duas
propriedades fundamentais. São elas (Ver [40]):
• Escalonamento: propriedade cuja validação foi verificada em diversos trabalhos ex-
perimentais, está associada à idéia de invariância de escala e se subdivide basi-
camente em duas categorias. A primeira delas é composta por um conjunto de
expoentes relacionados entre si, chamados leis de escalas. Como exemplo podemos
citar os expoentes críticos
1
α, β e γ associados respectivamente ao calor específico
C
T
, à magnetização M e à susceptibilidade magnética χ
T
, onde o vínculo é dado
por α + 2β + γ = 2. A segunda categoria consiste na possibilidade de grandezas
1
Os expoentes são matematicamente definidos p or: C
T
∼
−α
, M
2
∼
2β
e χ
T
∼
−γ
, onde é a
temperatura reduzida = (T − T
c
)/T
c
2.1 Redes Livres de Escalas 49
de n variáveis que representam os estados de um sistema passarem a representar o
mesmo estado do sistema por pelo menos n − 1 variáveis. Como exemplo, temos
a magnetização M(H, ) como função do campo magnético H e da temperatura .
Desta forma, observaremos que para cada valor do campo magnético H haverá uma
curva da magnetização M(H, ) em função da temperatura . Próximo do ponto
crítico, poderemos ter a magnetização M apenas como função da temperatura se
multiplicarmos M e por potências de H apropriadas, resultando em um colapso
de todas as curvas independentemente do valor do campo H;
• Universalidade: esta propriedade foi proposta pela primeira vez por Leo Kadanoff
nos anos 70 e ela ocorrerá quando no limite termodinâmico dois sistemas quaisquer
possuírem os mesmos expoentes, fazendo com que eles apresentem as mesmas leis
de invariância de escala independente do tipo de interação que há entre os seus
respectivos agentes. Para exemplificar, podemos citar os materiais magnéticos com
diferentes estruturas microscópicas (diferentes interações entre os agentes consti-
tuintes), que possuem aproximadamente os mesmos valores de expoentes próximo
do ponto crítico (Fig 011).
Embora as idéias de invariância de escala e universalidade tenham surgido no contexto
de transições de fase, principalmente após a comprovação empírica da teoria de grupo
de renormalização [41], sua aplicação conceitual tem alcançado uma grande diversidade
de tipos de sistemas complexos, indo desde sistemas biológicos, sociais, artificiais até o
sistema econômico. Para uma melhor compreensão sobre os conceitos acima expostos, ver
os artigos [40, 42].
Neste capítulo realizamos um estudo sobre a decomposição de redes complexas livres
de escalas baseado no modelo de crescimento preferencial proposto por Albert-Barabási
[37]. A escolha deste modelo se deveu principalmente por ele apresentar um decaimento
do grau de conectividade sob a forma de lei de potência, que como vimos está presente
em um grande número de sistemas que podem ser modelados como uma rede complexa.
Outro fator que também contribuiu para nossa escolha é o fato do modelo de rede de
Albert-Barabási ser bastante flexível na variação dos parâmetros iniciais e por possibilitar
a obtenção de uma grande quantidade de amostras, o que é crucial para uma boa descrição
estatística do nosso problema.
2.1 Redes Livres de Escalas 50
t = 1t = 0 t = 2 t = 3
Figura 12: Ilustração que mostra o processo de crescimento da rede Barabási-Albert. A
rede é iniciada com o número inicial de vértices m
0
= 3 e o coeficiente de agregação m = 2.
As bolas pretas são os vértices antigos e os cinzas o novo vértice adicionado.
2.1.1 Rede de Albert-Barabási
Apesar dos modelos de redes desenvolvidos por Erdõs e Renyi e por Watts e Stro-
gatz exibirem efeito de pequeno mundo e alto coeficiente de aglomeração (apenas Watts
e Strogatz), os mesmos falham quando tentamos utilizá-los para modelar alguns sistemas
reais, pois não apresentam o decaimento em lei de potência na distribuição de conecti-
vidade da rede. Uma solução dada para resolver esse problema foi feita por Barabási e
Albert [37] quando propuseram duas características genéricas que estariam presentes nos
sistemas reais. A primeira delas é que as redes reais crescem continuamente, ou seja, o
número de vértices N cresce com o tempo. A segunda característica foi a observação de
que havia uma preferência nas novas conexões que surgiam, isto é, era mais provável que
uma nova página da internet se conectasse com uma outra mais conhecida ou que um
novo artigo citasse um outro mais conhecido naquela área ou assunto específico. Estes e
muitos outros exemplos indicam que o surgimento das conexões não são aleatórias, mas
que há um mecanismo que governa o processo de escolha das conexões. De fato, este
processo é dado quando um novo vértice se conecta a algum dos vértices existentes com
uma probabilidade que é proporcional à quantidade de conexões de cada vértice que já
esteja na rede. Desta forma, o modelo livre de escala proposto por Barabási e Albert leva
em consideração as duas características e pode ser definido da seguinte forma:
• crescimento: a rede é iniciada com um pequeno número m
0
de vértices, estando
todos conectados entre si, e então é adicionado a cada passo de tempo t um novo
vértice que se conectará a m vértices daqueles já existentes.
• conexão preferencial: a escolha de uma nova conexão é dada por uma probabilidade
Π(K
i
), que leva em consideração a quantidade de conexões K
i
do i-ésimo vértice
existente na rede, ou seja,
2.1 Redes Livres de Escalas 51
10
0
10
1
10
2
10
3
10
4
K
10
-10
10
-8
10
-6
10
-4
10
-2
10
0
P(K)
m = 2
m =6
m = 16
P(K) ∼ K
-γ
γ
Figura 13: Gráfico que mostra a distribuição de probabilidade do grau de conectividade
P (K) em função de K, onde podemos perceber o decaimento em lei de potência na
forma P (K) ∼ K
−γ
, com γ = 3.0. A rede foi criada com N = 10
6
vértices e diferentes
coeficientes de agregação m.
Π(K
i
) =
K
i
N
j
K
j
. (2.1)
Após t passos de tempo, o tamanho da rede será N = m
0
+ t e a quantidade de
vértices m(t + m
0
). Um esquema ilustrativo do crescimento da rede poderá ser visto
na Fig. 12.
De fato poderemos constatar a partir de simulações computacionais que esse modelo
de rede irá evoluir para um estado livre de escala, onde a probabilidade de encontrarmos
um vértice com K conexões seguirá uma lei de potência P (K) = K
−γ
, com γ ∼ 3,
independentemente do valor de conexões iniciais m (único parâmetro de controle da rede)
(Fig. 13).
A distribuição em lei de potência mostra que apenas alguns vértices possuem alta
concentração de conexões, chamados de concentradores ou hubs, enquanto a grande mai-
oria possui poucas conexões. Desta forma, uma das grandes consequências da presença
dos hubs na rede é que eles possibilitam que o caminho médio d entre qualquer par de
vértices da rede sejam drasticamente diminuídos em relação ao apresentado pelas redes
aleatórias de forma que d ∼ ln(lnN) [16]. O processo de crescimento preferencial tem
também como consequência um baixo índice de coeficiente de agrupamento, C
A
∼ N
−0.75
2.1 Redes Livres de Escalas 52
[16], porém ainda maior que o apresentado pelas redes aleatórias.
O cálculo analítico do expoente da distribuição de conectividade da rede de Barabási-
Albert pode ser realizado por pelo menos três maneiras diferentes [43, 44], entretanto,
apresentaremos na subseção seguinte apenas o método da teoria contínua [16], também
conhecido como método da teoria do campo médio [45].
2.1.1.1 Cálculo Analítico
O método aproximativo escolhido aqui para o cálculo analítico do expoente da dis-
tribuição da rede de Barabási-Albert é o método da teoria contínua, que foi desenvolvido
primeiramente por Barabási et al [37, 45] em 1999. O método consiste basicamente em
calcular a dependência temporal do grau de conectividade K
i
(t) de um dado vértice i
e, então, a partir daí fazer uma mudança de variável na probabilidade cumulativa para
acharmos a distribuição de probabilidade.
No processo de crescimento da rede, temos que o grau de conectividade K
i
(t) aumen-
tará toda vez que um novo vértice for adicionado e conectado ao vértice i, acarretando
uma variação temporal da probabilidade Π(K
i
(t)). Supondo que K
i
(t) seja uma variável
contínua no tempo, a taxa em que K
i
(t) muda no tempo será proporcional a Π(K
i
(t)),
satisfazendo, consequentemente, à equação dinâmica
∂K
i
∂t
= mΠ(kKi) = m
K
i
N−1
j
K
j
. (2.2)
O somatório no denominador da equação (2.2) é realizado incluindo todos os vértices
da rede menos o novo vértice adicionado, pois para ele o tempo t = 0. Assim, teremos
que
N−1
j
k
j
= 2mt − m, porém quando o tempo é muito grande, o somatório resultará
em apenas 2mt e, portanto,
∂K
i
∂t
=
K
i
2t
. (2.3)
Sabemos que no momento da adição t
i
cada vértice i possuía apenas K
i
(t
i
) = m
conexões. Assim a solução da equação (2.3) será dada por
K
i
(t) = m
t
t
i
β
, (2.4)
2.1 Redes Livres de Escalas 53
onde β = 1/2. Podemos perceber na equação (2.4) que a distribuição de todos os vértices
evolui da mesma maneira, como uma lei de potência, de tal maneira que a única diferença
está na constante de proporcionalidade.
Usando a equação (2.4), podemos determinar a probabilidade de escolher um vértice
com o grau de conectividade K
i
(t) menor que K em função do temp o, ou seja,
P (K
i
< K) = P
t
i
>
m
1/β
t
K
1/β
. (2.5)
Suponhamos agora que cada vértice é adicionado em intervalos de tempos iguais,
temos que a densidade de probabilidade de sortear um vértice que foi adicionado em um
tempo t
i
será constante no tempo, ou seja,
P (t
i
) =
1
m
0
+ t
. (2.6)
A partir da definição de probabilidade acumulada e substituindo a equação (2.6) na
(2.5), teremos
P
t
i
>
m
1/β
t
K
1/β
= 1 − P
t
i
<
m
1/β
t
K
1/β
= 1 −
m
1/β
t
K
1/β
0
P (t
i
)dt
i
= 1 −
m
1/β
t
K
1/β
0
1
m
0
+ t
dt
i
= 1 −
1
K
1/β
m
1/β
t
m
0
+ t
. (2.7)
De acordo com a equação (2.5), podemos obter o grau de destribuição de conectividade
P (K) derivando a equação (2.7) em relação a K, portanto,
P (K) =
∂P [K
i
< K]
∂K
=
1
βK
1/β+1
m
1/β
t
m
0
+ t
. (2.8)
Assintoticamente, quando o tempo é muito grande (t → ∞), a distribuição P (K) se
comporta como uma lei de potência
P (K) ∼ 2m
2
K
3
, (2.9)
onde podemos observar a independência do expoente da destribuição P (K) com o parâ-
metro m e desta forma evidenciar a coerência com os resultados numéricos.
2.2 Método de decomposição 54
A grande maioria das redes reais apresentam uma distribuição de conectividade em
forma de lei de potência que independe do tamanho da rede. Este fato pode realmente
ser previsto analiticamente no modelo de Albert-Barabasi pela equação 2.9, indicando
que o sistema atinge seu estado estacionário para longos p eríodos de tempo. Podemos
observar ainda na equação 2.9 o termo de proporcionalidade m
2
também constatado nas
simulações numéricas (Ver em [16]).
2.2 Método de decomposição
2.2.1 Modelo
Frequentemente é observado que alguns dos sistemas reais que podem ser modelados
por redes complexas evoluem espontaneamente para estados auto-organizados após ata-
ques ou estímulos externos. Esta capacidade torna tais sistemas bastante adaptativos e
robustos a uma grande variedade de eventos naturais imprevisíveis e isso se deve prin-
cipalmente ao processo de interações locais que há entre os seus agentes constituintes.
Assim, temos, neste contexto, que os estudos ligados às conexões entre agentes tornam-se
um dos aspectos mais relevantes para se entender as propriedades dinâmico-estruturais
das redes complexas.
Muitos trabalhos foram desenvolvidos com o intuito de fornecer ferramentas mate-
máticas que nos auxiliem no entendimento de sistemas complexos. Em particular, a
observação de que algumas redes reais apresentavam um decaimento na distribuição de
conectividade sob a forma de lei de potência atraiu fortemente a atenção dos pesquisa-
dores de sistemas complexos devido principalmente ao fato das redes livres de escala não
possuírem uma conectividade média (o que torna o sistema bastante robusto a defeitos e
ataques aleatórios [16]) e por apresentarem efeito de pequeno mundo (rápida propagação
de informação). De fato, os avanços na concepção teórica da estrutura de redes complexas
indicam que estas características estão intimamente ligadas à maneira de como se dão os
arranjos das conexões entre os agentes (Ver na sequência [26, 30, 37]).
Nesse sentido, a investigação topológica torna-se um dos principais meios para se
compreender as propriedades estruturais das redes complexas. Neste trabalho, utiliza-
mos um método semelhante à decomposição k-shells para analisar o processo de retirada
iterativa de vértices de uma rede livre de escala em diferentes níveis de graus de conecti-
vidade. Comumente, uma k-shells é definida como sendo o conjunto de to dos os vértices
com conectividade menor ou igual a K [46] e está quase sempre associada à formação de
2.2 Método de decomposição 55
a) c)b)
Figura 14: Ilustração que representa um processo de RI k-shells de uma rede Barabási-
Albert. A rede possui tamanho N = 10 e foi construída com um coeficiente de agregação
m = 2. O processo de remoção foi realizado retirando todos os vértices com K = 3
conexões. A bolas de cor cinza indicam os vértices que serão retirados no passo seguinte.
A figura a) representa a rede inicial, t = 0, b) o processo intermediário, t = 1, com
s
3
(1) = 3/10 e c) a configuração final, t = 2, com s
3
(2) = 2/10, onde não há mais vértices
com K = 3 conexões. Em todo o processo ocorreu um total de 2 iterações resultando em
uma 3-shell com S
3
= 5/10.
estruturas k-core [47, 48, 49, 50].
Nosso objetivo é analisar os aspectos associados à iteração quando uma rede complexa
sofre um dado processo de remoção definido como remoção iterativa (RI) k-shells. Para
isso, utilizaremos uma rede livre de escala criada a partir do modelo de agregação prefe-
rencial de Barabási-Albert (BA) [37]. A escolha do modelo de rede BA deve-se tanto pela
sua flexibilidade nos ajustes dos parâmetros de construção da rede como por sua facilidade
de geração. O modelo BA consiste em uma rede criada a partir de um pequeno número
de vértices m
0
, cada um com m conexões iniciais. A rede é crescida acrescentando-se
um vértice por vez, onde cada um se conectará a m vértices daqueles já existentes. A
escolha das conexões é realizada seguindo uma probabilidade que é proporcional ao nú-
mero de conexões de cada vértice, ou seja, a probabilidade de um vértice já existente na
rede receber uma nova ligação é proporcional ao seu próprio número de conexões. Este
processo de crescimento será repetido até que o número máximo de vértices N seja alcan-
çado. Para facilitar o controle dos parâmetros de crescimento, usaremos neste trabalho a
relação m
0
= m + 1.
A RI k-shells é feita a partir da retirada iterativa de grupos de vértices com o mesmo
grau de conectividade, ou seja, em cada iteração identificamos todos aqueles vértices que
possuem exatamente K conexões e então os retiramos simultaneamente da rede. Como
consequência, temos a alteração da conectividade dos outros vértices da rede por causa
das conexões perdidas com os vértices retirados. Este fato faz com que alguns dos vértices
remanescentes que possuíam o número de conexões maiores que K possam vir a possuir
K conexões. Desta forma, repetimos o processo de retiradas dos vértices em sucessivas
iterações até que não haja mais vértices com K conexões na rede (Ver Fig. 14). Nesta
2.2 Método de decomposição 56
10
0
10
1
10
2
K
10
-6
10
-5
10
-4
10
-3
10
-2
10
-1
10
0
〈S
K
〉/m
η
m = 1
m = 3
m = 7
10
0
10
1
10
2
K
10
-6
10
-4
10
-2
10
0
〈S
K
〉
Figura 15: Decomposição de uma rede de Barabási-Albert. A simulação foi realizada em
200 amostras de redes com N = 2
23
vértices e diferentes valores de coeficiente de agregação
m. Dentro do inset é mostrado um gráfico normalizado que representa o comportamento
da fração média do total de vértices retirados S
K
em função de K. Podemos perceber um
decaimento em lei de potência com uma inclinação de aproximadamente 3.0 independente
do coeficiente de agregação m. No gráfico principal é mostrado o colapso da distribuição
o da fração média S
K
por um fator de m
−η
, onde η ≈ 1.8.
situação, dizemos que a rede atingiu seu ponto de saturação e calculamos a fração total
de vértices retirados S
K
somando todas as frações de vértices retirados ao longo de cada
iteração s
K
(t), ou seja,
S
K
=
T
K
t=1
s
K
(t) . (2.10)
onde t é o passo de cada iteração e T
K
é a quantidade total de iterações para o término
do processo de remoção.
Diferentemente dos estudos envolvendo a decomposição k-shells e k-core, o método RI
k-shells não é aplicado sucessivamente com diferentes valores de K em uma mesma rede
e sempre a partir do seu estado inicial, ou seja, nunca é executado em uma rede que já
tenha sofrido um processo de remoção.
A seguir apresentaremos os resultados computacionais, iniciando com a análise da
distribuição da fração média do total de vértices retirados S
K
em função do grau de
conectividade K, onde verificamos que a distribuição varia como uma lei de potência do
tipo S
K
∼ K
−α
, com α = 3. Em seguida, analisamos como a fração média de vértices
retirados s
K
(t) varia ao longo de cada iteração t, verificando um decaimento exponen-
2.2 Método de decomposição 57
Figura 16: A fração média de massa retirada s
K
(t) é definida como sendo a quantidade
média de vértices retirada em cada instante da iteração ao longo de um processo de
decomposição em um conjunto de 200 amostras com redes de tamanho N = 2
25
. O
gráfico mostra a distribução de s
K
(t) em função da iteração t para m = 3 e diferentes
valores de K, onde podemos perceber um decrescimento exponencial com inclinações λ
K
.
Os símbolos representam os dados computacionais e a linha contínua o ajuste exponencial.
cial, e então realizamos uma breve dedução teórica para explicar o processo iterativo. A
partir daí, analisamos como a constante de proporcionalidade C
K
e o tempo característico
(inclinação) λ
K
do decaimento exponencial varia com a conectividade K. Continuando
com a análise dos resultados, utilizamos as equações encontradas para descrever o com-
portamento C
K
e λ
K
juntamente com a aproximação do somatório da equação (2.10)
de uma integral da exponencial para recuperar o expoente da fração média do total de
vértices retirados S
K
. Para finalizar, deduzimos a partir das equações encontradas para
s
K
(t), C
K
e λ
K
uma equação que se ajusta muito bem à variação da quantidade total
de iterações T
K
com o grau de conectividade K.
2.2.2 Resultados
A análise estatística foi realizada com vários valores de conexões fixas K em um
conjunto de 200 amostras de redes de tamanho N . Por conveniência mostramos resultados
para diferentes tamanhos de redes com coeficientes de agregação inicial m = 1, 3 e 7, pois
o comportamento é basicamente o mesmo para qualquer valor de m.
Semelhante ao que é observado na destribuição k-shells no modelo de decomposição
2.2 Método de decomposição 58
10
0
10
1
10
2
10
3
K
0.0
1.0
2.0
3.0
4.0
5.0
λ
K
m = 1
m = 3
m = 7
10
0
10
1
10
2
K/m
µ
0
2
4
6
λ
K
Figura 17: A figura mostra o gráfico log-linear do tempo característico λ
K
em função de
K em redes de tamanho N = 23. Cada valor de lambda é obtido a partir da inclinação
da distribuição da média da fração de vértices retirados s
K
(t) em função do tempo de
iteração t para cada valor de conexão K (ver Fig. 16). Podemos perceber o comportamento
logaritmo de λ
K
em função de K na forma λ
K
∼ δln(K), com δ = 0.89, e diferentes
m = 1, 3, e 7. O inset mostra a sobreposição de λ
K
por um fator escala m
−ν
com
ν = 1.25.
k-core [46, 50, 51, 52], o inset da Fig. 15 mostra que a distribuição da média da fração
S
K
também varia sob a forma de lei de potência para diferentes valores de conexões K,
ou seja,
S
K
∼ K
−α
, (2.11)
onde o expoente α ≈ 3. Esse comportamento com o expoente α constante ocorre para
todos os valores de coeficientes de agregação m e independe do tamanho da rede N. No
gráfico principal da Fig. 15 temos um reescalonamento da fração S
K
por um fator de
m
−η
, para η ≈ 1.8, em que podemos colapsar as distribuições com os diferentes valores
de m. Notemos que apesar da inclinação α ser a mesma da distribuição de conectividade
da rede BA, o expoente do fator de reescalonamento η é ligeiramente diferente
2
[53].
O gráfico da Fig. 16 nos mostra que para m = 3 e para um dado valor de K fixo, a
média da fração de massa retirada s
K
(t) decai exponencialmente com cada iteração t
sob a forma
s
K
(t) = C
K
exp(−λ
K
t) . (2.12)
2
O fator de escalonamento da distribioção da rede livre de escala de Albert-Barabási é igual a 2.0
2.2 Método de decomposição 59
10
1
10
2
K
10
-4
10
-3
10
-2
10
-1
10
0
C
K
N = 2
13
N = 2
17
N = 2
20
N = 2
25
10
1
10
2
K
10
0
10
2
10
4
10
6
10
8
N C
K
Figura 18: O gráfico acima mostra em log-log a variação C
K
em função K para m = 3
e diferentes tamanhos de redes. A linha contínua representa o ajuste dado pela equação
2.15. O inset é mostrado a constante C
K
multiplicado pelo seu respectivo tamanho de
rede N.
Em nossas análises, o comportamento exponencial da massa retirada s
K
(t) é o mesmo
tanto para m = 1 quanto para m = 7, permitindo a generalização do decaimento expo-
nencial para qualquer valor de m. De fato é possível concluir o decaimento exponencial
para s
K
(t) raciocinando da seguinte maneira. Suponhamos que no tempo t = 1, a fração
de vértices retirados seja proporcional a uma fração inicial de vértices retirados, ou seja,
s
K
(1) =
1
b
K
C
K
, (2.13)
onde b
K
é uma constante maior que um de modo que ela represente a retirada de vértices
e C
K
é uma constante que representa a fração inicial de vértices retirados do sistema.
Supondo agora que a fração de vértices retirados em um tempo t + 1 mantenha sempre a
mesma proporcionalidade de vértices retirados em relação ao passo de tempo anterior t,
ou seja, s
K
(t + 1) = s
K
(t) /b
K
, teremos como resultado um decaimento exponencial
do tipo 2.12, onde λ
K
= ln(b
K
). Chegamos, portanto, a partir de suposições teóricas
relativamente simples, a uma expressão que se ajusta perfeitamente aos dados obtidos a
partir das simulações computacionais.
Analisando mais detalhadamente a Fig. 16, observamos que o tempo característico λ
K
(Eq. 2.12) varia para diferentes valor de conexões K. A forma dessa variação é mostrada
no gráfico principal da Fig. 17, onde podemos perceber o crescimento logarítmico de λ
K
2.2 Método de decomposição 60
em função de K na forma
λ
K
= δ ln(Ka
m
) , (2.14)
com δ = 0.89. Nesse comportamento é importante notar que o parâmetro δ é praticamente
o mesmo para os diferentes números de conexões iniciais m, onde a única mudança ocorre
no valor da constante a
m
. No inset da Fig. 17 mostramos a sobreposição das diferentes
curvas por um fator de escala m
−ν
com ν = 1.25. Ainda analisando a Fig. 16, podemos
observar que o valor da constante da fração inicial de vértices retirados C
K
(Eq. 2.12)
também muda à medida em que mudamos o valor da conexão K. No gráfico principal da
Fig. 18 é mostrada a variação da constante C
K
em função de K, onde podemos observar a
sobreposição de várias curvas com diferentes tamanhos de redes N e no inset cada variação
da constate C
K
multiplicado pelo seu respectivo tamanho de rede N. O ajuste encontrado
para C
K
é dado por
C
K
∼ K
δ−α
λ
K
. (2.15)
Sabendo como as componentes da equação exponencial (2.12) se comportam com K,
devemos agora poder de fato recuperar o expoente α = 3 da variação de S
K
com K
(Eq. 2.10). Para isso, aproximamos o somatório (Eq. 2.10) de uma integração exponencial
do tipo
S
K
=
T
1
s
K
(t) dt
S
K
=
∞
1
C
K
e
−λ
K
t
dt , (2.16)
onde podemos fazer T → ∞ uma vez que λ
K
e C
K
são independentes do tempo de iteração
t, ou seja, eles não dependem do tamanho do sistema. A integral é, portanto, facilmente
calculada, resultando em
S
K
= C
K
λ
−1
K
K
−δ
. (2.17)
Substituindo C
K
na equação acima, recuperamos a lei de potência S
K
, tornando, desta
forma, o método de decomposição aqui proposto auto-consistente.
Por último, podemos ainda utilizar o decaimento exponencial de s
K
(t) (Eq. 2.12)
para deduzir uma equação que descreva o comportamento da quantidade total de iterações
T
K
necessária para a realização de todo um processo de decomposição para um determi-
nado grau de conexão K (limite superior do somatório 2.10). Neste sentido, consideremos
que no instante T
K
(última iteração) seja retirado da rede em média apenas um vértice,
2.2 Método de decomposição 61
10
1
10
2
10
3
10
4
K
10
-1
10
0
10
1
〈T(K)〉
N = 2
13
N = 2
17
N = 2
20
N = 2
25
Figura 19: O gráfico mostra o tempo total médio T (K) necessário para o término do
processo de decomposição para cada valor de K. Utilizamos diferentes tamanhos N de
redes para um mesmo valor de número de conexões iniciais m = 3. A curva de linha
contínua representa o ajuste da equação 2.20 com os parâmetros α = 3, δ = 0.89 e
a
3
= 0.72.
com isso temos que s
K
(T
K
) será proporcional a N
−1
, ou seja,
s
K
(T
K
) = C
K
exp(−λT
K
) = DN
−1
, (2.18)
onde D é uma constante de proporcionalidade. Isolando o tempo T
K
, teremos
T
K
= λ
−1
K
ln(C
K
ND) (2.19)
Substituindo C
K
e λ
K
, temos
T
K
=
1
δ ln(Ka
m
)
ln(NDK
δ−α
ln(Ka
m
)), (2.20)
onde agora D é uma constante de proporcionalidade que engloba o termo de proporção
da constante C
K
com relação a K (Eq. 2.15) e de s
K
(T
K
) em relação ao tamanho de
rede N (Eq. 2.18) e a e δ são a constante e o coeficiente de proporção logarítmica de
λ
K
(Eq. 2.14), respectivamente. A variação da iteração total T
K
com K é mostrada na
Fig. 19, onde a linha contínua representa o ajuste dado pela Eq. 2.20. Neste ajuste
foram utilizados os parâmetros α, δ, a
3
e m = 3 fixos e um único parâmetro livre D
para diferentes valores de tamanho de rede N de modo que podemos perceber uma boa
concordância da equação 2.20 com os dados computacionais.
2.3 Conclusão 62
2.3 Conclusão
Em nossa primeira abordagem, analisamos a dependência da fração total média de
vértices retirados S
K
em relação ao grau de conectividade K e, então, constatamos que
esta dependência segue um decaimento em lei de potência com o expoente α = 3 (2.11).
Intuitivamente, este comportamento pode até ser previsto tendo em vista o conhecimento
da forma da distribuição de conectividades no modelo rede Barabási-Albert, porém, a co-
nexão matemática entre os dois tipos de decaimento não pôde ser analiticamente deduzida
neste trabalho.
Em seguida estudamos mais detalhadamente o processo iterativo da decomposição,
onde analisamos como a fração de vértices retirados s
K
(T
K
) varia a cada iteração t.
Verificamos, portanto, que a variação segue um decaimento exponencial (2.12) e dedu-
zimos teoricamente este decaimento supondo apenas que a quantidade de vértices que
serão retirados em um dado instante de tempo é proporcional à quantidade de vértices
retirados no passo de tempo anterior. Depois observamos que os parâmetros C
K
e λ
K
do
decaimento exponencial mudam para cada valor de K, sendo possível na continuação de
nossas análises estabelecer equações que descrevem com boa aceitação o comportamento
de C
K
(2.15) e λ
K
(2.14) em função de K.
Com o conhecimento detalhado do processo iterativo, foi possível verificar a auto-
consistência dos resultados de duas maneiras diferentes. Primeiramente, realizamos a
integração analítica da equação exponencial encontrada para s
K
(T
K
) (2.16), onde foi
possível recuperar o mesmo expoente α = 3 calculado computacionalmente para S
K
em
função de K (2.11). A segunda verificação foi deduzir a partir da equação encontrada
para s
K
(T
K
) uma equação que descrevesse o comportamento da quantidade total de
iterações para o término de um dado processo de decomposição (2.20).
Como resultado final de nosso trabalho, temos a constatação de que o mo delo de de-
composição proposto é auto-consistente com os seus resultados. Isto se deve basicamente
à observação de que todos os expoentes aqui encontrados tanto estão relacionados entre
si quanto são invariantes em relação à mudança dos parâmetros iniciais de construção da
rede, definindo assim uma classe de universalidade.
63
3 PERCOLAÇÃO EM
MULTI-CAMADAS
Neste capítulo apresentaremos os estudos realizados para determinar quais as mudan-
ças ocorridas nas propriedades de tranporte de fluido devido à presença da anisotropia.
Mais precisamente, utilizamos o modelo rede de percolação em multi-camadas com dife-
rentes densidades para gerar backbones
1
anisotrópicos no ponto crítico. A flexibilidade do
modelo nos permitiu observar uma forte relação entre o grau de anisotropia e os diferentes
valores da dimensão fractal e expoente da distribuição de massa. Este e outros estudos
estão contidos neste capítulo, o qual está inicialmente organizado com uma introdução ao
modelo de percolação isotrópica (3.1). Em seguida (3.2) definimos mais rigorosamente o
modelo de percolação em multi-camadas, discutimos o problema dos erros causados efeito
de tamanho finito na determinação dos expoentes críticos e propomos um novo método
para a minimização destes erros. Por fim, encerramos o capítulo com a apresentação dos
nossos resultados (3.3) e conclusões (3.4).
3.1 Percolação
Muitos sistemas físicos que envolvem fenômenos de escoamento em meios porosos
tem atraído não somente o interesse industrial como também o científico. Por parte
da industria, o interesse se dá por exemplo na busca de materiais capazes de filtrar e
selecionar partículas de diferentes tamanhos sujeitas a algum processo de escoamento, no
desenvolvimento produtos com variados índices de permeabilidade ou ainda em processos
de extração de fluidos de algum meio poroso. Já o interesse científico está na elaboração de
teorias que podem servir não apenas para o entendimento do processo de escoamento, mas
também para uma diversidade de fenômenos físicos que vão desde a mecânica estatística de
1
O backbone, cuja palavra pode ser traduzida como esqueleto condutor, são estruturas sob a qual há o
tranporte efetivo de fluidos em um meio percolante. A definição precisa do backbone está na seção 3.1.2
deste capítulo.
3.1 Percolação 64
sistemas no ponto crítico até modelos de propagação de epidemias e queimadas florestais.
Um exemplo clássico e de grande interesse econômico ligado ao escoamento em meios
porosos é o processo de extração de petróleo. Comumente temos nos método extração
petrolífera a utilização de injeção de água ou gás (geralmente dióxido de carbono ou
metano) em um ou mais poços de maneira que o petróleo seja deslocado através dos
poros das rochas até o poço de extração. Este processo continuará até que a interface de
separação dos fluidos (água ou gás e petróleo) alcance o poço de extração, onde a partir daí
a retirada do petróleo passará a diminuir. Devido à produção industrial de larga escala,
a busca por métodos mais eficazes e baratos na produção de petróleo tem atraído um
grande interesse dos pesquisadores e principalmente da própria industria. Em particular,
desenvolver um conhecimento mais aprimorado sobre a dinâmica de injeção de fluidos é de
fundamental importância, já que o tempo relacionado à injeção está intimamente ligado
à quantidade de petróleo retirado.
Uma característica que está presente no exemplo acima e em outros vários sistemas
que envolve processos de escoamento é a desordem associada ao meio poroso, que torna a
geometria espacial do sistema não trivial. Dependendo do tip o de desordem, um sistema
poderá ser classificado como homogêneo ou heterogêneo. A diferença crucial entre os dois
tipos de sistemas é que no homogêneo haverá uma escala típica na qual as proprieda-
des intensivas
2
poderão ser medidas e válidas para uma parte ou totalidade do sistema.
Já no heterogêneo a escala típica será inexistente, fazendo com que a compreensão das
propriedades físicas estejam condicionadas ao conhecimento detalhado da morfologia do
meio.
Neste contexto, a teoria da percolação tem alcançado um grande grau de aceitação
devido principalmente à simplicidade em sua definição e à presença de transição de fases
com expoentes críticos bem definidos. Foi inicialmente proposta por Broadbent e Ham-
mersley, nos anos 50, como um modelo matemático para descrever a propagação de fluidos
em meios aleatórios [54]. Para um simples exemplo deste tipo de propagação, imagine-
mos um material sólido com poros em seu interior distribuídos aleatoriamente. Temos
que se a porosidade do meio for suficientemente grande, os poros poderão se conectar ao
longo de todo material, tornando-o permeável à passagem de algum tipo fluido. Nesta
situação, um fluido poderá escoar através dos poros por todo material, ocorrendo assim
uma percolação no sistema. Vale salientar ainda que neste tipo de processo, a desordem
2
Propriedades intensivas são propriedades que não dependem do tamanho do sistema. No entanto,
devido à ocorrência de flutuações intrínsecas ao sistema estatísticos, algumas propriedades intensivas só
farão sentido a partir de uma determinada escala típica.
3.1 Percolação 65
está unicamente associada ao meio, sendo a dinâmica do fluido um processo totalmente
determinístico.
O modelo de percolação consiste em estudar processos de escoamento, propagação,
transporte etc. em uma rede formada a partir de uma rede inicial da qual as conexões são
removidas com uma probabilidade p. Neste tipo de rede podemos identificar por exemplo
os sítios com os poros, as conexões com as ligação existente entre cada par de poro e p
a porosidade do meio. O modelo de rede mais simples de ser estudado é o de uma rede
quadrada de primeiros vizinhos onde a existência de cada conexão é escolhida igual e
independentemente com probabilidade p. A questão fundamental na teoria da percolação
é, portanto, determinar a probabilidade P (p) a partir da qual é possível haver um cluster
3
infinito, ou seja, haver um sítio pertencente a um único aglomerado de sítios conectados
capaz de abranger toda a extensão de uma rede. Tal questão é de suma importância, pois
a existência de um cluster infinito é a condição necessária para a ocorrência de percolação.
Ao analisarmos os extremos da probabilidade p, podemos perceber claramente que
para p = 0 não haverá nenhuma conexão na rede, o que resultará em P (0) = 0, enquanto
para p = 1 a rede estará totalmente conectada, resultando em P (1) = 1. Também é
fácil perceber que a probabilidade P (p) é uma função crescente de p, pois quanto maior o
número de conexões na rede, maiores são as chances de haver um cluster infinito. Desta
forma, podemos concluir que probabilidade P (p) de ocorrer este tipo de cluster será dada
a partir de um certo valor de probabilidade p = p
c
, chamada de probabilidade crítica,
tal que para p < p
c
termos P (p) = 0 e para p > p
c
termos P (p) > 0. Como resultado
final desta nossa pequena análise, temos que o sistema possuirá comp ortamentos globais
completamente diferentes tanto para p < p
c
quanto para p > p
c
e, consequentemente,
apresentará uma transição de fase no limite p = p
c
.
A presença de transição de fase no modelo de percolação atraiu grande atenção dos fí-
sicos tanto pela facilidade em analisar várias propriedades importantes próximas do ponto
crítico quanto pela possibilidade destas propriedades servirem por analogia para análises
de propriedades críticas de outros sistemas mais complexos. Como exemplos, podemos
citar a magnetização dos materiais ferromagnéticos ou a resistência efetiva de uma rede
elétrica desordenada. Uma característica muito marcante na teoria da percolação é que
grande parte das propriedades analisadas se comportam como uma lei de potência, com
expoentes críticos bem estabelecidos e definindo uma classe de universalidade que depende
apenas da dimensão do modelo de rede utilizado. Na tabela 4 mostramos alguns valores
3
Um cluster é formado por um aglomerado de sítios conectados de tal forma que seja possível obter
um caminho ininterrupto entre dois pares quaisquer de sítios pertencentes ao mesmo aglomerado.
3.1 Percolação 66
Rede Sítios Ligações
Quadrada 0.59275 0.5
Triangular 0.5 0.652
Cúbica 0.3116 0.2488
Tabela 4: Tabela contendo valores de probabilidades críticas para diferente tipos de redes
[55].
de probabilidades críticas p
c
para diferentes tipos de redes [55].
Neste capítulo temos por objetivo demonstrar o efeito das multi-camadas na dis-
tribuição de massa e na dimensão fractal na distribuição dos tamanhos dos backbones.
Entretanto, faremos antes uma breve introdução ao modelo de percolação e ao método
do perímetro, que será importante para determinar a probabilidade crítica p
c
das multi-
camadas. Por último, é importante esclarecer os termos isotrópico e anisotrópico aqui
empregados. Em um modelo de percolação isotrópica a probabilidade p é a mesma em
todas a direções enquanto que no modelo anisotrópico as probabilidade p é diferente.
3.1.1 Modelo de Percolação
Desde a sua criação, o modelo de percolação tem sido adaptado para vários tipos
de sistemas diferentes. O mais comum deles é definir, sem perda de generalidade, o
modelo como uma rede formada por sítios (Fig. 20(a)). Desta forma, para obtermos uma
rede de percolação devemos alocar os sítios na rede com uma probabilidade p de eles
existirem e 1 − p de não existirem. Desde que os sítios sejam distribuídos aleatoriamente,
haverá uma possibilidade de que alguns deles sejam alocados juntos, passando a formar
clusters. Os tamanhos destes clusters aumentam à medida em que aumentamos o valor
da probabilidade p. Neste processo, ao atingimos valor crítico p = p
c
, teremos a formação
de um cluster, chamado de cluster percolante ou infinito, capaz de se ramificar e alcançar
toda a extensão da rede, tornando possível a conexão entre lados opostos.
A figura 20 mostra três simulações computacionais para o modelo de rede quadrada
de sítios com ligações entre os primeiros vizinhos (Fig. 20(a)) para diferentes valores
de probabilidades p. Quando a probabilidade de ocupação é baixa (p < p
c
) temos a
formação de pequenos clusters finitos e quando ela é alta (p > p
c
) temos a formação de
um cluster percolante que ocupa quase que a totalidade da rede. Já para o caso em que
a probabilidade é crítica (p = p
c
), temos um comportamento bastante peculiar, que é a
formação tanto do cluster percolante quanto de clusters finitos de tamanhos variados. A
3.1 Percolação 67
(a) Esquema (b) p=0.50
(c) p=0.59275 (d) p=0.70
Figura 20: Conjunto de quatro figuras ilustrativas do modelo de percolação. a) Esquema
de percolação por sítios de uma rede quadrada 10x10 de primeiros vizinhos, onde os sítios
azuis representam os clusters finitos, o vermelho e o cluster percolante os brancos os sítios
vazios; b), c) e d) são figuras de simulações de uma rede quadrada 50x50 com diferentes
probabilidades de ocupação p, onde em c) e d) as cores seguem a mesma representação de
a) enquanto que em b) a cor vermelha representa o maior cluster finito da rede e o azul
os demais.
distribuição do tamanho destes clusters finitos segue uma lei de potência cuja principal
característica é a existência de clusters de todos os tamanhos, fato que implica na falta
de uma escala típica para o sistema [56]. Na Fig. 21 é mostrado um exemplo de rede
quadrada de sítios na probabilidade crítica p = p
c
= 0.59275.
Na seção anterior definimos a probabilidade P (p) como a probabilidade de um sítio
pertencer a um aglomerado que alcance toda a extensão de uma determinada rede. Na
prática, esta probabilidade pode ser definida como sendo a fração de sítios pertencentes
ao maior cluster da rede. Definindo P (L, p) como sendo esta fração para cada tamanho
L de rede, temos que a probabilidade P (L, p) converge para um valor limite quando o
tamanho da rede for muito grande, ou seja,
P
∞
(p) = lim
L→∞
P (L, p). (3.1)
Temos que se P
∞
(p) = 0, então o cluster percolante existe e possui uma fração finita da
3.1 Percolação 68
Figura 21: Ilustração de uma rede quadrada LxL de percolação. A rede foi gerada no
ponto crítico p = p
c
= 0.59275 e com L = 500. O cluster percolante é identificado p ela cor
azul claro, os maiores clusters finitos são representados na ordem decrescente pelas cores
verde escuro, vermelho, rosa, verde claro, amarelo, laranja, os demais por azul escuro e os
desocupado por preto. Através das cores, podemos perceber que no ponto crítico existem
clusters de todos os tamanhos.
rede. Definimos, portanto, a massa M(L, p) como sendo a quantidade de sítios perten-
centes ao cluster percolante, L
d
como o tamanho da rede e d a dimensão topológica do
sistema. Desta forma, podemos definir a probabilidade P
∞
(p) como
P
∞
(p) = lim
L→∞
M(L, p)
L
d
. (3.2)
Se P
∞
(p) = 0, teremos a partir do resultado acima que
M(L, p) ∝ L
d
, para L → ∞ . (3.3)
Isto nos diz que a massa do cluster percolante e o número total possível de sítios da rede
escalonam da mesma forma, resultando numa homogeneidade na distribuição de massa
por toda a rede (a massa se distribui igualmente por toda a rede). Podemos, agora, definir
mais precisamente a probabilidade crítica p
c
como sendo o maior valor de p para o qual
P
∞
(p) = 0. Dada esta definição, temos que em torno de p
c
a probabilidade P
∞
(p) se
3.1 Percolação 69
0.6 0.8 1.0
p
0.0
0.2
0.4
0.6
0.8
1.0
P(L,p)
Figura 22: Gráfico que representa a probabilidade de haver um cluster percolante P
∞
(p)
em função da probabilidade de sítios ocupados p. As curvas foram obtidas a partir de
uma rede quadrada LxL com L = 10
2
(linha vermelha), L = 10
3
(linha azul), L = 10
4
(linha preta). A linha vertical serve de referência no ponto p = p
c
= 0.59275.
comporta como uma lei de potência, ou seja,
M(L, p) ∝ |p − p
c
|
β
, para p → p
c
, (3.4)
com o expoente β dependendo apenas da dimensão topológica d, como por exemplo β =
5/36 para d = 2 e β = 0.41 para d = 3 [55].
Os gráficos da Fig. 22 mostram o comportamento da probabilidade P
∞
(p) em função
de p para diferentes tamanhos de rede LxL. Os dados foram obtidos selcionando sempre o
maior cluster de cada realização de um total de 1000 e, então, calculando média de P
∞
(p)
a partir da Eq. (3.2) com d = 2 . Partindo de p = 0, percebemos que para baixos valores
de p a probabilidade P
∞
(p) é praticamente nula. Entretanto, à medida que p cresce e
se aproxima de p
c
= 0.59275 o comportamento de P
∞
(p) cresce de forma considerável
até que em p p
c
acontece um crescimento abrupto em P
∞
(p), mais adiante, para p
um pouco acima de p
c
, a probabilidade P
∞
(p) cresce de maneira praticamente linear até
P (p = 1) = 1. Podemos observar que no aumento do tamanho L da rede, a transição de
fase vai se tornando cada vez mais abrupta em p
c
= 0.59275, levando à conclusão de que
seu limite é atingido quando L → ∞.
Acabamos de ver como a massa do cluster percolante se comporta em função da
3.1 Percolação 70
probabilidade de ocupação p mantendo o tamanho da rede fixo. No entanto, como seria
o comportamento da massa se invertermos nossa abordagem e analisassemos a massa em
função do tamanho da rede L mantendo a probabilidade p fixa? Se considerarmos o caso
em que p > p
c
, o cluster percolante se comportará aproximadamente como a Eq. (3.3),
sendo a proporcionalidade substituída pela probabilidade P
∞
(p) de encontrarmos o cluster
percolante, ou seja, M(L, p) P
∞
(p)L
d
. Para p < p
c
, temos a inexistência do cluster
percolante, porém, analisando apenas a massa do maior cluster da rede, constatamos
um crescimento logarítmico da forma M(L, p) ∼ ln(L) . Quando p = p
c
o sistema se
encontrará no ponto crítico e o crescimento da massa se caracterizará por um crescimento
em lei de potência na forma M(p
c
) ∼ L
D
f
, sendo D
f
é a dimensão fractal do sistema.
Este expoente depende apenas da dimensão topológica do sistema, como por exemplo
D
f
= 1.89 e D
f
= 2.53 para redes em duas e três dimensões, respectivamente. A Fig.
23(a) mostra o comportamento da massa em função do tamanho da rede L para os três
regimes de probabilidade p.
Em sistemas auto-similares não é possível distinguir a totalidade das suas partes cons-
tituintes, gerando, assim, uma invariância de escala. Matematicamente essa invariância é
descrita por uma lei de potência cujo expoente é denominado de dimensão fractal. Uma
das consequências diretas da auto-similaridade para a teoria da percolação é que no ponto
crítico a distribuição de massa dos clusters será sempre a mesma (exceto por um cutoff
de tamanho finito) não importando a escala observada. Na pratica, uma das maneiras
de se constatar esta igualdade é através do cálculo da distribuição de massa pelo método
finity size scale [56] para o cluster percolante e o método do raio de giração [56] para os
clusters finitos (Fig. 23).
O estudo ligado ao modelo de percolação é realmente um campo muito vasto na física e
discutir os seus múltiplos aspectos não é, aqui, nossa intenção. Na seção seguinte faremos
apenas uma breve abordagem a respeito de backbones em redes isotrópicas como uma
introdução ao fo co principal deste capítulo, que são backbones em multi-camadas.
3.1.2 Backbone
Em sistemas físicos reais, temos que nem todo o espaço ocupado pelo meio percolante é
realmente acessível ao processo de escoamento. Como exemplo, podemos citar os processos
de infiltrações, onde há um caminho preferencial seguido pelo fluido, ou ainda a extração
de petróleo, que apesar do meio rochoso estar conectado como um todo, há regiões onde o
petróleo não poderá ser deslocado. A partir destas e de várias outras situações, podemos
3.1 Percolação 71
10
2
10
3
10
4
L
10
2
10
3
10
4
10
5
10
6
10
7
10
8
M(L)
(a) Método finity size scale
10
0
10
1
10
2
10
3
R
g
10
0
10
1
10
2
10
3
10
4
10
5
10
6
10
7
M(R
g
)
(b) Método do raio de giração
Figura 23: Gráfico que mostra o comportamento da distribuição de massa dos clusters para
vários níveis de tamanhos com três probabilidades p diferentes. Em a) temos o método
finity size scale que determina em função do tamanho da rede L o comportamento da
massa do maior cluster com probabilidade de ocupação p = 0.5 (triângulos) e do cluster
percolante com probabilidades p = p
c
= 0.59275 (círculos) e p = 0.7 (quadrados). A
linha pontilhada com traços (triângulos) representa o ajuste logarítmico e a linha contínua
(círculos) e a tracejada (quadrados) os ajustes em lei de potência com expoentes D
f
≈ 1.89
e D ≈ 2.0, respectivamente. Cada ponto foi obtido a partir de uma média de 1000
amostras. Em b) temos o método do raio de giração que determina a massa do cluster
finito em função do tamanho do seu raio médio. Cada ponto foi obtido a partir da média
da massa de todos os clusters (apenas os que não tocam nas bordas) contidos em um
intervalo logarítmico de raio médio e a linha contínua representa um ajuste em lei de
potência com o expoente D
f
≈ 1.89. A simulação foi realizada utilizando uma rede
quadrada 10
4
x10
4
com probabilidade de ocupação p = p
c
= 0.59275.
perceber o quanto é importante conhecermos quais as propriedades e características estão
associadas à propagação de fluidos em meios percolantes.
Sabemos que para que haja deslocamento de fluido em algum meio é necessária a
aplicação de uma diferença de pressão entre dois ou mais pontos. No entanto, em um
cluster percolante poderão eventualmente existir regiões em que não seja possível haver
diferença de pressão, como aquelas regiões que se conectam ao agregado percolante apenas
por uma ligação. Neste caso, a região terá o ponto de entrada, mas não o ponto de saída
(Fig. 24(a)), tornando-se, assim, uma região morta ou estagnada. A parte do cluster em
que é possível haver fluxo é chamada de backbone, podendo ser definida como a união de
todos os caminhos que não cruzam a si mesmos, chamados de self-avoding walk, capazes
de conectar os pontos de entrada e saída de fluidos. Para exemplificar, a Fig. 24(b)
mostra o resultado de uma simulação de um backbone sob um cluster percolante no ponto
3.1 Percolação 72
(a) Esquema (b) Simulação
Figura 24: Ilustração de backbone sob cluster percolante gerado em uma rede quadrada.
Em a) temos um exemplo esquemático onde backbone são os sítios vermelhos e o cluster
percolante os azuis. A entrada e saída de fluido são representados pelos sítios de cor preta
e os sítios verdes representam a conexão entre regiões estagnadas ao restante do cluster.
Em b) mostramos uma simulação em uma rede 500×500 de um backbone de cor preta
sob um cluster percolante de cor cinza.
crítico p
c
gerado em uma rede quadrada 500×500.
Vimos na seção anterior que no ponto crítico a massa do cluster percolante possui uma
dimensão fractal quando relacionada ao crescimento do tamanho do sistema. Desta forma,
é natural pensar que este comportamento fractal também se reflita nas propriedades do
backbone. No trabalho desenvolvido por Grassberger [59], pode-se constatar que a massa
do backbone M
B
cresce em função do tamanho do sistema como uma lei de potência
com o expoente D
B
= 1.6432 ± 0.0008. Na Fig. 25(a) é mostrada a distribuição de
pontos (círculos) que representa a massa média do backbone em função do seu raio de
giração R
g
, onde a inclinação nos dá com boa precisão a dimensão fractal do backbone
(D
B
= 1.638 ± 0.006). Uma importante análise é saber como a massa do backbone varia
com as componentes do raio de giração R
g
. Pela definição temos que
R
2
g
=
1
S
S
i=1
(r
i
− r
cm
)
2
= R
2
gx
+ R
2
gy
, (3.5)
3.1 Percolação 73
10
0
10
1
10
2
10
3
R
g
, R
gx
, R
gy
10
0
10
1
10
2
10
3
10
4
10
5
10
6
M
B
, R
gy
D
B
= 1.638
(a) Distribuição de Massa
10
0
10
1
10
2
10
3
10
4
10
5
10
6
M
B
10
-10
10
-8
10
-6
10
-4
10
-2
P(M
B
)
τ
B
= 1.237
L = 2
9
L = 2
10
L = 2
11
(b) Distribuição de Tamanho
10
0
10
1
10
2
10
3
10
4
10
5
M
B
10
-10
10
-8
10
-6
10
-4
10
-2
P(M
B
)
r = 16
r = 4
r = 8
r = 32
r = 2
(c) Diferentes Distâncias r
10
-1
10
0
10
1
10
2
10
3
10
4
10
5
M
B
r
- D
B
10
-10
10
-8
10
-6
10
-4
10
-2
P(M
B
) r
D
B
B
= 1.237
r = 32
r = 16
r = 8
r = 4
r = 2
τ
(d) Escalonamento
Figura 25: Gráficos que mostram os comportamentos críticos da massa do backbone em
uma rede quadrada (L × L). Em a) temos a distribuição da massa média M
B
(para r = 2
e L = 2
11
) em função do seu raio de giração R
g
(cículos) e em função das componentes R
gx
(triângulos) e R
gy
(quadrados) do raio de giração. Para uma melhor visualização, multipli-
camos por 5 e 20 as distribuições de massa das componentes R
gx
e R
gy
, respectivamente.
Podemos perceber os comportamentos nas formas M
B
∼ R
D
B
g
, M
B
∼ R
D
Bx
gx
e M
B
∼ R
D
By
gy
,
onde as linhas contínuas representam os ajustes com inclinações D
B
= 1.638 ± 0.006,
D
Bx
= 1.646 ± 0.007 e D
By
= 1.65 ± 0.008. Os pontos representados por diamantes mos-
tram a componente R
gy
em função de R
gx
, onde podemos perceber uma relação em lei de
potência com expoente D
Bxy
aproximadamente igual a 1.0. Em b) temos a probabilidade
de distribuição de massa do backbone para r = 2, que decai como uma lei de potência na
forma P (M
B
) ∼ M
−τ
B
B
seguida por um pequeno plator e depois por um cutoff com decai-
mento abrupto. A linha contínua representa o ajuste com inclinação τ
B
= 1.237 ± 0.02
e os símbolos representam os diferentes tamanhos de redes (L × L). Em c) mostramos a
probabilidade de distribuição de massa P (M
B
) para diferentes tamanhos de r = 2, 4, 8, 16
e 32 e em d) o escalonamento pelos fatores r
D
B
no eixo P (M
B
) e r
−D
B
no eixo M
B
. Nos
itens c) e d) usamos redes de tamanho L = 2
11
e em todos os itens foram utilizados 10
5
amostras.
3.1 Percolação 74
onde S é a quantidade de sítios do backbone, r
i
a posição de cada sítio na rede, r
cm
o
centro de massa do backbone e
R
2
gx
=
1
S
S
i=1
(r
x
− r
xcm
)
2
, R
2
gy
=
1
S
S
i=1
(r
y
− r
ycm
)
2
(3.6)
as componentes x e y, respectivamente. Sabendo que M
B
∼ R
D
B
g
, M
B
∼ R
D
Bx
g
e M
B
∼
R
D
By
g
, temos
M
2/D
B
B
= P M
2/D
Bx
B
+ QM
2/D
By
B
, (3.7)
onde P e Q são constantes de proporcionalidades. Rearranjando os expoentes, teremos
M
2/D
B
B
= M
1/D
Bx
+1/D
By
B
(P M
1/D
Bx
−1/D
By
B
+ QM
−1/D
Bx
+1/D
By
B
) . (3.8)
Como o meio é isotrópico, é razoável concluir que a massa do backbone não tenha uma
direção preferencial para se distribuir, ou seja, a massa cresce igualmente para ambas as
direções com o mesmo expoente crítico D
Bx
= D
By
. Devido a esta igualdade, teremos que
a subtração dos expoentes da equação 3.8 será nula, o que resultará em sua linearidade e
consequentemente na relação
2
D
B
=
1
D
Bx
+
1
D
By
. (3.9)
A equação 3.9 estabelece que D
B
= D
Bx
= D
By
, o que de fato pode ser compro-
vado numericamente. Na figura 25(a) mostramos a massa do backbone M
B
em função
das componentes x (triângulos) e y (quadrados), onde podemos perceber que ambas são
praticamente paralelas entre si (D
Bx
= 1.646 ± 0.007 e D
By
= 1.65 ± 0.008) e entre a
distribuição de massa em função do raio de giração (círculos) (D
By
= 1.638±0.006). Para
uma melhor visualização dos resultados, deslocamos a distribuição de massa na direção x
por um fator de 5M
B
e na direção y por um fator de 20M
B
. Por fim, é também interes-
sante saber como as componentes se relacionam à medida em que a massa do backbone
cresce. Na figura 25(a) (diamantes) mostramos que a componente R
gy
cresce como uma
lei de potência em relação a R
gx
, cujo expoente D
Bxy
é igual a 1.0 . Este comportamento
é coerente com o fato da distribuição do cluster não ter um direção preferencial, pois
para um dado tamanho de cluster, temos em média o mesmo comprimento na direção x
e y. A igualdade entre os expoentes D
B
= D
Bx
= D
By
mostra não apenas o aspecto da
invariância de escala do comportamento fractal do backbone crítico como também o seu
aspecto de auto-similaridade estatística, que é reflexo da característica anisotrópica do
sistema.
Outra propriedade importante é a probabilidade de distribuição de tamanhos de massa
3.1 Percolação 75
backbone P (M
B
), que se comporta como uma lei de potência do tipo P (M
B
) ∼ M
−τ
B
B
. A
partir dos estudos realizados por Herrmann e Stanley [60], é possível demonstrar por um
processo de integração simples que o expoente τ
B
está relacionado com a dimensão espacial
do meio D e a dimensão fractal do backbone D
B
sob a forma τ
B
= D/D
B
[61], onde para
o caso bidimensional (D = 2) temos τ
B
∼ 1.22. Na Fig 25(b) podemos observar que o
valor encontrado numericamente τ
B
= 1.237 ± 0.02 é coerente com a relação anterior. O
decaimento de P (M
B
) ocorre até encontrar um pequeno platô seguido de um decaimento
abrupto devido ao limite do tamanho do sistema. Temos ainda leis de escalonamento
para distribuições de P (M
B
) quando o backbone é gerado com diferentes distâncias r
muito menor que o tamanho do sistema, neste caso Barthélémy et al [61] mostram que o
fator de escala é dado por r
D
B
(Ver Figs. 25(c) e 25(d)).
O backbone crítico é uma estrutura contida dentro de outra estrutura crítica, o cluster
percolante. A partir disto, podemos esperar que as mudanças provocadas na estrutura do
cluster devido à presença de multi-camadas [62] também se reflitam nas propriedades do
backbone, como veremos na seção de multi-camadas mais adiante.
3.1.3 Método Self-Avoiding Random Walk
No modelo de percolação, o perímetro é definido como sendo um caminho contínuo
dos sítios ocupados nas fronteiras de um cluster, podendo ser externo (se for ao redor do
cluster) ou interno (contorno dos buracos dentro do cluster). Em seu trabalho, Sapoval
et al [57] estabeleceram que a dimensão fractal do tamanho de perímetro D
H
de uma
rede isotrópica (D
H
= 1.75 para redes quadradas) está relacionada com o expoente de
correlação ν por D
H
= 1 + 1/ν, tornando, assim, possível o estudo das propriedades
de percolação pela análise direta do comportamento do perímetro. Este fato é muito
importante, pois possibilita o desenvolvimento de métodos de simulação computacional
mais rápidos e precisos já que as informações associadas à massa do cluster não precisam
mais ser nem guardadas nem analisadas.
Neste contexto, Ziff et al [58] desenvolveram um algoritmo eficiente para o cálculo mais
preciso da probabilidade crítica de uma rede quadrada de primeiros vizinhos, chamado de
método Self-Avoiding Random Walk
4
(SARW). Este algoritmo permite uma considerável
redução tanto no custo de memória (possibilitando a criação de redes muito grandes)
quanto no tempo de simulação. O método simula em uma rede quadrada apenas a criação
4
Um tradução livre para o termo Self-Avoiding Random Walk seria caminhante aleatório auto-
excludente
3.1 Percolação 76
do perímetro de um cluster aleatório sem se preocupar com a sua distribuição de massa.
A idéia principal do método SARW para determinar o ponto crítico é que neste ponto a
probabilidade de haver perímetros internos e externos são iguais, ou seja, estatisticamente
teremos a mesma quantidade de perímetros internos e externos.
O algoritmo SARW pode ser definido da seguinte maneira. Primeiramente, criamos
uma rede quadrada L × L, onde os sítios poderão assumir apenas três estados, ou seja,
nulo, ocupado e desocupado. Inicialmente a rede se encontra com os sítios todos nulos e
então seguimos os seguintes passos:
(1) Escolha um par de sítios adjacentes no centro da rede e atribua os estados ocupado
para um e desocupado para o outro. Defina uma direção desenhando uma seta do
sítio desocupado para o ocupado e mova esta seta para o sítio o cupado;
(2) De acordo com a seta, olhe para o sítio da esquerda e veja se o estado do sítio é:
(a) nulo, então escolha para o sítio o estado ocupado com uma probabilidade p
e desocupado com uma probabilidade (1 − p) e vá para o item (b) ou (c) de
acordo com a escolha do estado;
(b) desocupado, então vá para o item (2) olhando para a próxima direção segundo
a ordem esquerda, em frente ou direita;
(c) ocupado, então apontamos a seta do atual sítio ocupado para o novo sítio ocu-
pado observado e em seguida movemos a seta para o novo sítio. Feito isto, vá
para o item (2) começando a olhar o sítio adjacente que fica a esquerda da seta;
(3) Continue o procedimento até que o caminhante chegue ao ponto inicial de partida
com a seta apontando na mesma direção.
O algoritmo acima gera perímetros de clusters em uma rede quadrada a partir de
um caminhante aleatório que nunca cruza o caminho o qual ele já tenha percorrido. Isto
ocorre uma vez que mantemos fixos os estados (ocupado ou desocupado) escolhidos para
cada sítio visitado até o término da simulação, onde o caminhante encontra seu ponto
de partida. Devido à independência no processo de escolha dos estados ocupado ou
desocupado, podemos perceber que a probabilidade com que um dado perímetro é gerado
pelo algoritmo SARW é a mesma probabilidade com que o acharíamos em uma rede já
preenchida. A grande vantagem do algoritmo SARW é a geração de apenas um perímetro
por cada realização, acarretando na minimização considerável dos efeitos de tamanho finito
3.1 Percolação 77
x
x
x
x
x
x
x
x
x
x
x
x
x
x
x
x
x
x
5 (0)
4 (0)
2 (0)
7 (0)
9 (0)
1 (1)
3 (1)
6 (1)
8 (1)
10 (0)
11 (1) 12 (1) 13 (0) 14 (0)
15 (1)
16 (0)
17 (1)
18 (1)
19
Figura 26: Ilustração que representa a geração de um perímetro através do algoritmo
SARW. Os círculos representam os sítios desocupados, as bolas cinzas os sítios ocupados
e o X o próximo sítio com estado nulo que será visitado. Os números fora do parênteses
significam o tempo de cada passo do caminhante e os que estão entre parentes indicam a
escolha do próximo estado, sendo 1 para ocupação e 0 para desocupado. O resultado final
do processo nos dá um perímetro externo com N
o
= 9 sítios ocupados e N
v
= 12 sítios
desocupados.
do sistema (fato que será de grande relevância na determinação do ponto crítico em multi-
camadas). No término do processo de simulação, poderemos identificar um perímetro
externo quando os sítios desocupados estiverem no lado de fora do perímetro formado
pelos sítios ocupados e o perímetro interno quando os sítios desocupados estiverem no
lado de dentro (Ver Fig. 26 e 27).
Na Fig. 26 é ilustrado um processo de formação de um perímetro a partir do método
SARW. O primeiro passo em (t = 1) é mostrado um par de sítios iniciais com uma seta
apontando do sítio desocupado para o sítio ocupado. Ainda em t = 2, o algoritmo nos diz
que devemos olhar para o sítio adjacente ao sítio ocupado que está a esquerda da seta, que
no caso se encontra com o estado nulo. Devemos então determinar aleatoriamente o novo
estado do sítio nulo, o seja, atribuiremos o valor 1 com probabilidade p na rede caso o sítio
deva ser ocupado e 0 com probabilidade (1 − p) caso deva ser desocupado. O valor entre
parênteses (igual a 1 em t = 1) indica que o novo sítio será ocupado e, portanto, devemos
desenhar a seta como mostra a Fig. 26 em t = 2. No passo de tempo seguinte (t = 2),
temos (à esquerda) um sítio nulo, entretanto, a nova escolha é desocupado. O processo é
continuado seguindo as seguintes escolhas aleatórias de estado a partir de t = 3: 1 0 0 1
0 1 0 0 1 1 0 0 0 1 0 1 1. Notemos que em t = 14 o sítio nulo passa a ser desocupado,
fazendo com que a seta mude o sentido atribuído anteriormente e o caminhante ocupe
3.1 Percolação 78
(a) Interno (b) externo
Figura 27: Exemplo ilustrativo de dois perímetros gerados a partir de um programa
computacional baseado no algoritmo SARW. Os sítios ocupados estão em vermelho e
desocupados em azul. O perímetro da esquerda é um exemplo de perímetro interno e o
da direta um perímetro externo.
automaticamente o sítio já ocupado em t = 12. No passo de tempo t = 18 o sítio nulo
passa a ser desocupado e em t = 19 o caminhante chega ao seu início, ocasionando o fim
do processo.
É importante notar que o algoritmo SARW produz um caminhante aleatório com dois
lados, um composto por sítios ocupados e o outro por sítios desocupados. Neste processo,
o caminhante nunca cruza os sítios desocupados enquanto que os sítios ocupados sempre
serão unidos ao se encontrarem. Quando p < p
c
, o caminhante tem uma forte tendência de
girar para a direita, fazendo surgir com maior frequência perímetros externos (Fig. 27(b)).
Para p > p
c
, o caminhante tenderá fortemente a dobrar para a esquerda, fazendo aumentar
a frequência de perímetros internos (Fig. 27(a)). No entanto, próximo do ponto critico
(p = p
c
), teremos a formação de grandes perímetros com igual probabilidade de girarem
tanto para a esquerda quanto para a direita. Isto nos leva a concluir estatisticamente
que no ponto crítico p
c
o número de perímetros internos e externos são iguais. A Fig.
28 mostra esse comportamento, onde o perímetro interno é praticamente inexistente e o
externo é máximo para p < p
c
e o contrário disto para p > p
c
. Próximo do ponto crítico
p = p
c
, temos uma mudança abrupta do comportamento, de forma que cada vez que p se
aproxima de p
c
, o número de perímetros tende a ficar igual. O método SARW permitiu
que determinássemos a probabilidade crítica com uma precisão de três dígitos, ou seja,
p
c
= 0.5929.
3.2 Multi-camadas 79
0.0 0.2 0.4 0.6 0.8 1.0
p
0.0
0.2
0.4
0.6
0.8
1.0
n
i
(p) , n
e
(p)
Figura 28: Gráfico que mostra o comportamento da fração de número de perímetro in-
terno n
i
(p) (bolas azuis) e externo n
e
(p) (bolas vermelhas) em função da probabilidade
p. Podemos perceber que abaixo da probabilidade crítica (p < p
c
= 0.59275) o número
de perímetros externos é máximo enquanto os internos é praticamente nulo e quando a
probabilidade está acima (p > p
c
= 0.59275) temos o comportamento inverso. Para a
probabilidade p próxima do ponto crítico p
c
= 0.59275 há um comportamento abrupto
e o número de perímetros internos e externos tendem a permanecer iguais. As linhas
contínua e tracejadas servem de referências, indicando respectivamente o ponto crítico
p
c
= 0.5927 e a igualdade do número de perímetros internos e externos (n
i
(p) = n
e
(p)).
3.2 Multi-camadas
Muitos sistemas na natureza exibem anisotropia de diferentes maneiras, podendo por
exemplo se manifestar nas propriedades geométricas, magnéticas, ópticas etc. Particular-
mente, é possível que a geometria de algumas ro chas reais exibam algum tipo de com-
portamento anisotrópico, ou seja, exibam, após o processo de formação rochoso, uma
disposição de porosidade (permeabilidade) dependendo da sua localização ou posição es-
pacial relativa. Isto pode, de fato, ser constatado se considerarmos os casos em que as
rochas ou campos geológicos são formados pelo processo de sedimentação, onde as propri-
edades geométricas e de transportes nestes meios poderão ser caracterizadas por alguma
anisotropia [63, 64, 65]. Como exemplo, temos o arenito, um tipo de rocha sedimentar,
que exibe anisotropia espacial devido à tendência das camadas morfológicas se disporem
3.2 Multi-camadas 80
0.0 0.1 0.2 0.3 0.4 0.5
∆
0.50
0.52
0.54
0.56
0.58
0.60
p
c
~
(a) Diagrama de Fases
0.0 0.1 0.2 0.3 0.4 0.5
∆
0.50
0.52
0.54
0.56
0.58
0.60
p
c
~
(b) Comparação de Métodos
Figura 29: Gráficos de diagrama de fases para o modelo PM. Em a) temos o diagrama de
fases de ˜p
c
em função do parâmetro ∆ com o cálculo computacional baseado no algoritmo
SARW para os casos alternado (bolas) e aleatório (quadrados). Em b) temos a comparação
entre os algoritmos da baseados no método da bisseção utilizando (símbolos vazios) uma
rede quadrada e no método SARW (símbolos preenchidos) para o cálculo do diagrama de
fases de ˜p
c
. Note que à medida que o parâmetro ∆ aumenta, a diferença entre os métodos
se tornam cada vez maior, principalmente para o caso aleatório. No limite de ∆ = 0.5
deveremos ter ˜p
c
= 0.5, o que não ocorre para o método da bisseção em redes quadradas.
com maior probabilidade na direção horizontal. Em casos como estes, o modelo de per-
colação em multi-camadas (PM) visa prover uma metodologia teórica mais realista para
descrever a fenomenologia dos meios porosos anisotrópicos [62], consistindo basicamente
de um modelo d-dimensional com camadas de diferentes concentrações de probabilidades.
O modelo PM [62] consiste de uma rede d-dimensional construída a partir de uma
sequência de sub-redes (camadas) com (d-1) dimensões dispostas ao longo de um eixo
arbitrário. Semelhantemente às camadas de diferentes porosidades dos sistemas geológi-
cos, atribuímos uma probabilidade de ocupação predefinida p para cada sub-rede. Como
no trabalho desenvolvido por Dayan et al. [62], restringimos nossos estudos para o caso
bidimensional (d = 2) e para dois esquemas de simulações. O primeiro é o esquema ale-
atório, onde a disposição das camadas varia ao longo do eixo y inteiro. Neste esquema
a escolha da probabilidade de ocupação p
1
e p
2
de cada camada é uma variável indepen-
dente da posição no eixo y, ou seja, P r(p(y) = p
1
) = P r(p(y) = p
2
) = 1/2. Para o caso
específico em que p
1
= p
2
, temos o modelo padrão de percolação isotrópica, no entanto,
o modelo anisotrópico surge quando temos p
1
> p
2
ou p
1
< p
2
. O segundo esquema é
o alternado, onde a probabilidade de ocupação p(y) é determinada periodicamente pela
simples escolha p(y) = p
1
se y for par ou p(y) = p
2
se y for ímpar. Em ambos os casos o
grau de anisotropia pode ser mais convenientemente representado pela reparametrização
3.2 Multi-camadas 81
˜p = (p
1
+ p
2
)/2 e ∆ = (p
2
− p
1
)/2, onde podemos notar que quanto maior o parâmetro
∆ maior será a extensão do cluster na direção x e menor na direção y. No caso limite em
que ∆ = 0.5, teremos uma rede composta por camadas com probabilidade de ocupação
nula p
1
= 0 ou máxima p
2
= 1, acarretando a impossibilidade de percolação no eixo y.
Da mesma forma que ocorre no modelo padrão de percolação isotrópica (∆ = 0. 0), o
trabalho de Dayan et al. [62] mostra que uma transição de fase de segunda ordem também
ocorre no modelo PM. Evidências numéricas indicam que a transição de fase no modelo
PM possui somente um único valor crítico de probabilidade ˜p = ˜p
c
para cada valor de
(∆). Na figura 29 (a) mostramos os diagramas de fases de p
c
em função de ∆ para ambos
os casos alternados e aleatório obtidos pelo método SARW (ver seção 3.1.3). Podemos
notar que para o mesmo valor de ∆, a probabilidade crítica ˜p
c
para o caso alternado é
ligeiramente menor do que para o caso aleatório exceto nos extremos ∆ = 0.0 e ∆ = 0.5,
onde os modelos tendem para o mesmo valor.
3.2.1 Backbone em Multi-camadas
Como discutido acima, a anisotropia afeta a maneira como a probabilidade de ocu-
pação se distribui no espaço, fazendo com que o cluster gerado seja mais alongado em
uma certa direção do que em outra. Este fato, caso não seja considerado, pode causar
uma má interpretação dos resultados obtidos por meio de alguns métodos de simulações
computacionais. Comumente utilizamos uma rede quadrada de dimensão (L
x
× L
y
), com
L
x
= L
y
= L, para simular sistemas percolantes isotrópicos de modo em que os efeitos de
tamanho finito sejam minimizados à medida que aumentamos o tamanho L da rede. Com
a presença da anisotropia surge um outro fator complicador que se não for devidamente
observado, poderá aumentar os efeitos de tamanho finito. Isto pode ser constatado, por
exemplo, nas simulações do modelo PM em redes quadradas, onde observaremos uma li-
mitação maior do crescimento de massa na direção perpendicular à anisotropia. Na figura
29 (b) mostramos uma comparação de métodos para a obtenção do diagrama de fases
da probabilidade crítica ˜p
c
em função de ∆, onde utilizamos o método da bipartição em
uma rede quadrada (símbolos vazios) e o método SARW (símbolos preenchidos). Podemos
constatar, no entanto, que o método SARW é mais preciso por gerar apenas um perímetro
por simulação em redes com limites extremamente grandes, possibilitando, assim, uma
considerável minimização dos efeitos de tamanho finito (inclusive o efeito anisotrópico).
Esta precisão pode ser de fato verificada, pois temos a probabilidade crítica ˜p
c
→ 0.5
quando tomamos o limite ∆ → 0.5. Abstraindo um pouco mais as idéias expostas an-
3.2 Multi-camadas 82
(a) ∆ = 0.0 (b) ∆ = 0.1
(c) ∆ = 0.2
Figura 30: Ilustrações de backbones sob clusters percolantes em diferentes graus de ani-
sotropia segundo o modelo PM aleatório. Em a) temos uma rede quadrada (250×250),
˜p
c
= 0.59725 e ∆ = 0.0, em b) uma rede retangular (550×250), ˜p
c
= 0.588 e ∆ = 0.1 e em
c) uma rede retangular (700×60), ˜p
c
= 0.57423 e ∆ = 0.2. Em ambos os casos utilizamos
r = 2.
teriormente, podemos concluir que os métodos que utilizam redes com d-dimensões de
comprimentos iguais não são boas opções para se determinar os expoentes críticos em
sistemas anisotrópicos.
A metodologia aqui empregada visa diminuir os efeitos de tamanho finito para poder
determinar com melhor precisão os expoentes críticos relacionados à dimensão fractal e
a probabilidade de distribuição de tamanhos de massa de backbone em multi-camadas.
Inicialmente determinamos o diagrama de fases da probabilidade crítica ˜p
c
em função
de ∆ para ambos os casos alternado e aleatório através do método SARW (seção 3.1.3).
No entanto, há neste método um grande problema que impossibilitou a determinação
de backbones: o método SARW simula apenas o perímetro do cluster sem dar qualquer
informação a respeito da sua estrutura interna.
Propomos neste trabalho um método que nos p ermite trabalhar redes retangulares
(L
x
× L
y
), com L
x
= L
y
, de modo que seja possível minimizar os efeitos de tamanho
finito provocados pela anisotropia. Para isto, observemos primeiro o modelo isotrópico no
ponto crítico. Sabemos que neste tipo de modelo não há uma preferência de direção na
distribuição de massa, consequentemente, temos que a probabilidade de ocorrer percola-
ção na direção x ou y são em média iguais se considerarmos uma rede quadrada (L × L).
Baseado nesta idéia, poderemos elaborar para o modelo anisotrópico um algoritmo que
3.2 Multi-camadas 83
10
0
10
1
10
2
R
gy
10
3
10
4
10
5
10
6
M
B
(a) ∆ = 0.1
10
0
10
1
10
2
R
gy
10
3
10
4
10
5
10
6
M
B
(b) ∆ = 0.2
Figura 31: Gráficos da distribuição de massa M
B
em função da componente R
gy
do raio
de giração gerados em redes de multi-camadas aleatórias. Nos itens a) e b) mostramos o
efeito de tamanho finito causados pelos limites das redes quadradas (símbolos vermelhos)
e retangulares (símbolos azuis). Podemos perceber que à medida que o parâmetro ∆
aumenta, os efeitos de tamanho finito ficam cada vez mais acentuados na rede quadrada.
Em ambos os itens utilizamos redes quadradas (512×512) e redes retangulares (1800×512)
e (4000×400) com ∆ = 0 .1 e 0.2 e r = 2.
ajuste as dimensões L
x
e L
y
da rede de modo que elimine o máximo possível a maior
tendência de percolação na direção oposta à anisotropia. O algoritmo consiste basica-
mente em mantermos fixos a probabilidade crítica p
c
(encontrada pelo método SARW) e
um dos comprimentos de uma rede bidimensional, a partir daí ajustamos o outro com-
primento contabilizando o número de p ercolações ocorridas em cada direção. O processo
é encerrado quando a quantidade de percolações nas direções x e y forem iguais. Na
implementação do algoritmo, observamos que à medida em que aumentamos o grau de
anisotropia, aumentamos também a diferença entre os comprimentos da rede, tornando-a
cada vez mais retangular. Estas idéias podem ser facilmente estendidas para redes com
dimensões maiores D = 2 sempre que a anisotropia ocorrer em uma dada direção, onde
passaremos a obter redes retangulares.
Uma vez que determinamos a probabilidade crítica ˜p
c
para cada valor do parâmetro
∆ e as dimensões L
x
e L
y
da rede, estaremos aptos para gerar em redes retangulares
(L
x
xL
y
) os clusters percolantes e seus respectivos backbones. Na Fig. 30 mostramos três
exemplos de backbones no ponto crítico gerados em uma rede PM aleatória para r = 2
e ∆ = 0.0, 0.1 e 0.2, onde podemos observar com mais detalhe o aspecto retangular
da rede. No apêndice 5 mostramos uma tabela com as probabilidade críticas ˜p
c
para
diferentes valores do parâmetro ∆.
3.3 Resultados 84
3.3 Resultados
Nesta seção apresentaremos a análise e discussões de resultados obtidos numerica-
mente para algumas das propriedades dos backbones gerados em redes PM no ponto crítico
com diferentes níveis de anisotropia. Mais precisamente, estudamos como se comportam
a dimensão fractal D
B
e o expoente τ
B
da probabilidade de distribuição de massa diante
das mudanças estruturais causadas pelo modelo PM para os casos alternado e aleatório.
Em nossas análises, utilizamos um total de 10
5
amostras de backbones para cada valor
específico do parâmetro ∆. As simulações numéricas foram realizadas em redes retangu-
lares (L
x
× L
y
) de modo que os comprimentos L
x
e L
y
estivessem sempre de acordo com
as idéias de ajustes discutidas na seção 3.2.1. Para facilitar a comparação entre os resul-
tados, seria necessário manter as propriedades comuns a cada tipo de sistema na mesma
ordem de grandeza. Procuramos manter a quantidade total de sítios da rede variando
sempre em torno de 2, 5 × 10
6
sítios. Desta forma usamos (2048×2048), (1800×512),
(512×3000), (4000×400), (6000×400) e (1200×400) para ∆ = 0.0, 0.10, 0.15, 0.20, 0.25
e 0.30, respectivamente.
As análises dos resultados obtidos para os backbones gerados em redes de multi-
camadas alternadas mostram que os expoentes críticos são os mesmos que os encontrados
para a rede de percolação isotrópica, indicando que ambos pertencem à mesma classe
de universalidade. Este fato pode ser facilmente explicado pela regularidade na dispo-
sição intercalada das camadas, a qual impede a formação de faixas com duas ou mais
camadas com a mesma probabilidade de ocupação. Devido à falta de anisotropia no mo-
delo de multi-camadas alternadas [62], focaremos nossas discussões apenas no modelo de
percolação de multi-camadas aleatórias.
Na seção 3.2.1 expomos nossa preocupação em minimizarmos o efeito de tamanho
finito, principalmente daquele causado pela anisotropia. Na figura 31 temos um exemplo
onde mostramos a massa do backbone M
B
em função da componente R
gy
do raio de giração
para dois tipos de redes. A reta (cor preta) é o melhor ajuste para as curvas, as quais
foram geradas em redes quadradas (símbolos vermelhos) e em rede retangulares (símbolos
azuis). O efeito de tamanho finito será maior sempre o que desvio no limite superior das
curvas em relação à reta aumentar. Desta forma, podemos constatar através dos gráficos
da figura 31 que o efeito de tamanho finito é mais acentuado na rede quadrada do que
na rede retangular, aumentando cada vez mais à medida em que aumentamos o grau
de anisotropia da rede. Mesmo sendo observado em menor proporção visual nas demais
propriedades estudadas, o efeito de tamanho finito provocado pelos limites das redes
3.3 Resultados 85
10
0
10
1
10
2
10
3
R
g
, R
gx
, R
gy
10
0
10
1
10
2
10
3
10
4
10
5
10
6
M
B
, R
gy
D
B
= 1.638
(a) ∆ = 0.0
10
0
10
1
10
2
R
g
, R
gx
, Rg
gy
10
0
10
1
10
2
10
3
10
4
10
5
10
6
M
B
, R
gy
D
B
= 1.64
(b) ∆ = 0.10
10
0
10
1
10
2
10
3
R
g
, R
gx
, R
gy
10
0
10
1
10
2
10
3
10
4
10
5
10
6
M
B
, R
gy
D
B
= 1.566
(c) ∆ = 0.15
10
0
10
1
10
2
10
3
R
g
, R
gx
, R
gy
10
0
10
1
10
2
10
3
10
4
10
5
10
6
M
B
, R
gy
D
B
= 1.50
(d) ∆ = 0.20
10
0
10
1
10
2
10
3
R
g
, R
gx
, R
gy
10
0
10
1
10
2
10
3
10
4
10
5
10
6
M
B
, R
gy
D
B
= 1.367
(e) ∆ = 0.25
10
0
10
1
10
2
10
3
R
g
, R
gx
, R
gy
10
0
10
1
10
2
10
3
10
4
10
5
10
6
M
B
, R
gy
D
B
= 1.30
(f) ∆ = 0.30
Figura 32: Conjunto de gráficos que mostram o comportamento da distribuição de massa
do backbone M
B
em função do raio de giração R
g
(círculo) e das componentes R
gx
(tri-
angulo) e R
gy
(quadrado) do raio de giração e mostramos também R
gy
em função de R
gx
(diamante). Em todos os casos temos o comportamento em lei de potência na forma
M
B
∼ R
D
B
g
, M
B
∼ R
D
Bx
gx
, M
B
∼ R
D
By
gy
e R
gy
∼ R
D
Bxy
gx
. Para facilitar a visualização da
figura, multiplicamos por 5 a distribuição de massa das componentes R
gx
e R
gy
.
3.3 Resultados 86
quadradas comprometeu a exatidão da maioria dos resultados, chegando até mesmo em
alguns casos a gerar conclusões equivocadas. Com base nessa análise, podemos concluir
que as redes retangulares são capazes de nos fornecer resultados mais coerentes e confiáveis
devido, principalmente, à melhor adequação das redes à forma resultante da distribuição
de massa dos clusters.
Assim como os sistemas isotrópicos, os clusters formados em redes de multi-camadas
aleatórias também são caracterizados por um conjunto de propriedades com expoentes
críticos bem definidos [62]. Sabemos que os backbones gerados em redes isotrópicas no
ponto crítico tem uma dimensão fractal D
B
∼ 1.64. Da mesma forma, também encon-
tramos uma dimensão fractal característica para os backbones que são gerados nas redes
de multi-camadas aleatórias. Isto pode ser verificado na figura
5
32, onde mostramos uma
série de gráficos para vários valores de ∆. Podemos, portanto, perceber que a variação
de massa M
B
em função do raio de giração R
g
(círculos) é em forma de lei de potência e
que as inclinações das curvas se tornam cada vez menores conforme aumentamos o valor
de ∆, acarretando a variação do valor da dimensão fractal do sistema.
Uma das características mais importantes no estudo de sistemas fractais anisotrópicos
é o aspecto da auto-afinidade
6
. Podemos de fato observar o aspecto auto-afim no modelo
PM aleatório através da análise da distribuição da massa do backbone nas direções x e y
do raio de giração. Na figura 32 mostramos os gráficos da massa do backbone em função
das componentes R
gx
e R
gy
(ver eq. 3.6), onde podemos perceber o comportamento em
lei de potência na forma M
B
∼ R
D
Bx
gx
e M
B
∼ R
D
By
gy
. Podemos observar na figura 32 que
as inclinações D
Bx
e D
By
começam a se tornar cada vez mais diferentes à medida em
que o valor de ∆ aumenta, onde os expoentes D
Bx
passa a diminuir e D
By
a aumentar.
Esse comportamento é coerente com a realidade do problema, pois os backbones passam
a ficar cada vez mais alongados na direção x à medida em que aumentamos o valor de
∆ (ver fig. 30). Isto nos leva, portanto, a concluir que o grau de anisotropia está não
apenas associado à desordem provocada pela aleatoriedade na disposição das camadas,
mas também ao aumento da diferença de probabilidades de ocupação que as camadas
utilizam.
5
Os valores dos expoentes da figura 32 são D
B
= 1.638 ± 0.006, D
Bx
= 1.646 ± 0.007, D
By
=
1.650 ± 0.008 e D
Bxy
= 1.001 ± 0.002 para ∆ = 0.0, D
B
= 1.640 ± 0.008, D
Bx
= 1.550 ± 0.007,
D
By
= 1.930 ± 0.010 e D
Bxy
= 0.850 ± 0.003 para ∆ = 0.10, D
B
= 1.566 ± 0.006, D
Bx
= 1.482 ± 0.005,
D
By
= 2.149 ± 0.020 e D
Bxy
= 0.734 ± 0.003 para ∆ = 0.15, D
B
= 1.500 ± 0.007, D
Bx
= 1.430 ± 0.007,
D
By
= 2.400 ± 0.020 e D
Bxy
= 0.630 ± 0.003 para ∆ = 0.20, D
B
= 1.367 ± 0.007, D
Bx
= 1.367 ± 0.007,
D
By
= 2.665 ± 0.020 e D
Bxy
= 0.550 ± 0.004 para ∆ = 0.25, D
B
= 1.300 ± 0.006, D
Bx
= 1.300 ± 0.006,
D
By
= 3.000 ± 0.020 e D
Bxy
= 0.467 ± 0.004 para ∆ = 0.30.
6
Segundo Barabási e Stanley [66], auto-afinidade é definida quando um objeto fractal deve ser reesca-
lonado de maneiras diferentes em suas direções.
3.3 Resultados 87
10
0
10
1
10
2
10
3
10
4
10
5
M
B
10
-10
10
-8
10
-6
10
-4
10
-2
P(M
B
)
τ
B
= 1.33
(a) ∆ = 0.15
10
0
10
1
10
2
10
3
10
4
10
5
10
6
M
B
10
-12
10
-10
10
-8
10
-6
10
-4
10
-2
P(M
B
)
τ
B
= 1.33
(b) ∆ = 0.30
10
0
10
1
10
2
10
3
10
4
10
5
M
B
10
-10
10
-8
10
-6
10
-4
10
-2
P(M
B
)
r = 16
r = 4
r = 8
r = 32
r = 2
(c) ∆ = 0.15
10
0
10
1
10
2
10
3
10
4
10
5
M
B
10
-10
10
-8
10
-6
10
-4
10
-2
P(M
B
)
r = 16
r = 4
r = 8
r = 32
r = 2
(d) ∆ = 0.30
Figura 33: Conjunto de gráficos que mostram o comportamento da densidade de proba-
bilidade da distribuição de massa do backbone P (M
B
) para diferentes valores de ∆. Em
a) e b) mostramos distribuições com massa dos backbones que tocam nos limites da rede
(vermelho) e daqueles que não tocam (azuis) para ∆ = 0.15 e 0.30. Em c) e d) temos a
distribuição para diferentes valores de distância r entre os sítios.
Analisando ainda a fractalidade das multi-camadas aleatórias, os resultados indicam
uma igualdade assintótica entre a dimensão fractal D
B
e o expoente D
Bx
. Isto pode ser
explicado a partir da equação 3.7, onde podemos perceber que o termo que possui o expo-
ente D
Bx
se torna mais significativo do que o termo que possui o expoente D
By
no limite
de grandes massas M
B
e/ou grandes valores de D
By
. Este comportamento assintótico dos
expoentes D
B
e D
Bx
foi comprovado numericamente, onde podemos observar nos gráficos
da figura 32 que as curvas da distribuição de massa M
B
em função do raio de giração R
g
e da componente R
gx
se tornam praticamente paralelas para ∆ = 0.25 e 0.30,
Mudando o foco da nossa análise para investigar o comportamento da densidade de
probabilidade da distribuição de massa dos backbones, observamos que o expoente τ
B
não é o mesmo que o encontrado para as redes isotrópicas. Entretanto, os resultados
3.4 Conclusões 88
indicam que independente do valor de ∆ = 0.15, 0.20, 0.25 e 0.30, o valor de τ
B
é
sempre o mesmo, ou seja, τ
B
= 1.33 ± 0.01, exceto para ∆ = 0.1, onde encontramos
τ
B
= 1.30 ± 0.005. Esse comportamento sugere que o expoente τ
B
varia rapidamente para
um limite com o aumento da anisotropia. É importante ainda observar que a relação τ
B
=
D/D
B
encontrada para as redes isotrópicas não é valida para as rede de multi-camadas
aleatórias. Nos gráficos das figuras 33(a) e 33(b) podemos observar que a probabilidade
da distribuição de massa que inclue os backbones que tocam nas bordas (cor vermelha)
possui uma saliência antes do cutoff no limite de grandes massas, tornado-se cada vez
mais pronunciada conforme o aumento da anisotropia. Essa saliência surge devido ao
efeito de tamanho finito, fato que pode ser comprova se observamos apenas a massa dos
backbones que não tocam nas bordas da rede (símbolos azuis dos gráficos das figuras 33(a)
e 33(b)). Mostramos nas figuras 33(c) e 33(d) a densidade de probabilidade P (M
B
) para
cinco valores de separação de sítios, r = 2, 4, 8, 16 e 32, para os valores de ∆ = 0.15
e 0.30. O efeito da variação de r na distribuição é simplesmente modificar o alcance da
região de escala, mantendo constante o valor do expoente τ
B
. Concluímos, portanto, que
quanto menor a distância r entre os sítios maior é o alcance da região que se comporta
como uma lei de potência.
3.4 Conclusões
Neste capítulo, expomos inicialmente uma breve introdução sobre a teoria geral da
percolação, onde buscamos introduzir as principais propriedades utilizadas no estudo de
backbones em redes de percolação em multi-camadas. Na sequência expomos também
o método Self-Avoid Random Walk (SARW), o qual nos permitiu determinar com b oa
precisão a probabilidade crítica de cada tipo de sistema. Este, no entanto, se mostrou
inviável para determinar os backbones devido à falta de qualquer informação a respeito da
distribuição de massa do cluster.
A geração dos clusters em redes PM enfrentou outra dificuldade devido ao apareci-
mento da anisotropia. Observamos que nestes tipos de sistemas os clusters passam a se
distribuir preferencialmente em uma dada direção, causando um forte efeito de tamanho
finito nos resultados. Diante desta dificuldade, propomos um algoritmo que utiliza a
probabilidade da frequência de percolação para ajustar as dimensões da rede à preferên-
cia da distribuição de massa do cluster, tendo como resultado final a formação de redes
retangulares. O uso deste algoritmo implicou numa considerável minimização do efeito
de tamanho finito, tornando os resultados mais precisos para determinar os expoentes
3.4 Conclusões 89
críticos.
As propriedades fractais dos backbones sofreram mudanças significativas devido à de-
sordem causada pela aleatoriedade na disposição das multi-camadas. Na análise dos
resultados pudemos constatar a quebra da classe de universalidade em relação ao modelo
isotrópico através da diminuição da dimensão fractal dos backbones com o aumento do pa-
râmetro ∆. Analisamos também o comportamento da massa em relação às componentes
do raio de giração e observamos a diminuição de D
Bx
e o aumento D
By
quando aumenta-
mos o valor de ∆. Constatamos que a diferença entre esses expoentes está intimamente
ligada ao grau de anisotropia do sistema, o que pode ser explicado pela preferência da
massa dos backbones em se distribuir na direção x (direção oposta à anisotropia) conforme
aumentamos o valor de ∆. Observamos ainda que assintoticamente a dimensão fractal
D
B
e o expoente D
Bx
convergem para o mesmo valor no limite de grandes massas e/ou
grandes valores de D
By
.
A densidade de probabilidade de massa também sofreu mudanças com a presença da
anisotropia. Observamos que o expoente τ
B
aumenta seu valor rapidamente até atingir um
valor limite (τ = 1.33) quando aumentos o valor de ∆. Observamos ainda uma saliência
na distribuição no limite de grandes massas, onde constatamos que esse comportamento
ocorre devido ao efeito de tamanho finito do sistema.
Apesar dos vários aspectos aqui investigados, novas perspectivas de estudos ainda
estão em aberto. Como exemplo, a determinação do expoente Hölder, também chamado
de expoente de afinidade, que caracteriza a função de afinidade de um objeto fractal
anisotrópico. Outro exemplo é o estudo das classes de multi-camadas quase-periódicas.
Esse tipo de estrutura já é bem conhecida na literatura, principalmente por sua aplicação
em super-redes magnéticas. A principal característica presente na quase-periodicidade é
a possibilidade de regular o grau de aleatoriedade da estrutura, que pode ser de grande
importância para o entendimento de alguns fenômenos naturais e desenvolvimento de
novas tecnologias. Por fim, podemos ainda utilizar o modelo de percolação em multi-
camadas como um modelo de meio poroso para estudar propriedades de transportes que
estão intimamente ligadas ao fenômeno de deslocamento de fluidos.
90
4 CONCLUSÕES
Apresentamos aqui uma conclusão geral dos estudos realizados em três sistemas di-
ferentes, cuja essência comum repousa na complexidade produzida pela desordem e não-
homogeneidade da regulação e organização das interações dos elementos constituintes.
Diante deste contexto, nossos estudos foram pautados sempre numa investigação sistema-
tizada e coerente dos fenômenos, possibilitando a formulação de novas idéias, conceitos e
relações matemáticas.
No capítulo 1 estudamos a dinâmica das redes booleanas sujeita a uma pequena
perturbação. Para isto utilizamos o tempo de relaxação, que pode ser definido como
a quantidade de tempo necessário para um pequeno dano desaparecer por completo do
sistema. Observamos que a distribuição cumulativa do tempo de relaxação no ponto
crítico segue um decaimento em lei de potência com expoente β = 1. Este fato está
de acordo com a conjectura que diz que tanto a dinâmica de propagação de danos em
redes annealed como o modelo de percolação direcionada pertencem à mesma classe de
universalidade [20, 21, 25].
Constatamos, entretanto, que na condição crítica há um truncamento para um de-
caimento exponencial do tempo de relaxação, que escalona com o tamanho do sistema a
partir do tempo característico dado por τ
×
∼ N
1/2
. Constatamos ainda que próximo do
ponto crítico o crossover do tempo de relaxação segue para dois comportamentos diferen-
tes, ou seja, na fase ordenada próxima do ponto crítico a distribuição tem um crossover
para um decaimento exponencial enquanto na fase caótica próxima do ponto crítico o
crossover vai para um regime plano, indicando que o dano se propagará indefinidamente.
Estudamos no capítulo 2 um novo método de decomposição, que consiste basicamente
de uma retirada simultânea e iterativa de grupos de vértices com um determinado grau K
de conectividade. Analisamos inicialmente a fração total média de sítios retirados S
K
em função da conectividade K e constatamos um decaimento em forma de lei de potência
com um expoente α = 3. No estudo mais detalhado do processo iterativo, analisamos
4 Conclusões 91
como a fração média de sítios retirados s
K
(t) varia a cada iteração t. Verificamos que
esta variação segue um decaimento exponencial, o qual foi possível deduzir teoricamente
a partir de suposições relativamente simples. Observamos ainda que os parâmetros C
K
e λ
K
do decaimento exponencial de s
K
(t) varia para cada valor de K, sendo possível
estabelecer uma relação direta entre esses parâmetros e a conectividade K.
A partir do conhecimento detalhado do processo iterativo, foi possível verificar a
auto-consistência dos resultados através da integração de s
K
(t) de forma que pudemos
recuperar o expoente α = 3 da fração total de sítios retirados S
K
(calculado anteri-
ormente por simulação numérica). Outra forma de verificação de auto-consistência foi
deduzir a partir da equação encontrada para s
K
(t) uma equação que descrevesse o com-
portamento da quantidade total de iterações T
K
necessária para o término de um dado
processo de decomposição.
Por fim estudamos no capítulo 3 como a anisotropia afeta as propriedades do backbone.
Para isto, analisamos primeiro os principais aspectos envolvidos na minimização de erros
provocados pelo efeito de tamanho finito, onde propomos um algoritmo que gera redes
retangulares que se adaptam melhor à distribuição de massa do backbone. Este algoritmo
foi capaz de minimizar de forma considerável o efeito de tamanho finito e permitiu uma
melhor precisão nos resultados.
Estudamos basicamente duas propriedades. A primeira delas foi a dimensão fractal
do backbone D
B
, onde pudemos constatar uma forte relação com o grau de anisotropia.
Observamos que o valor da dimensão fractal D
B
diminui com o aumento da anisotropia e
que no limite assintótico de grandes massas e/ou de grandes valores do expoente D
By
, a
dimensão fractal D
B
e o expoente D
Bx
tendem a ficar iguais. A segunda propriedade es-
tudada foi a probabilidade de distribuição de tamanhos de massa, onde pudemos observar
uma dependência do expoente τ
B
com a anisotropia. A dependência ocorre de maneira
rápida para uma convergência de um valor limite dado por τ
B
= 1.33 ± 0.01 conforme au-
mentamos a anisotropia. Observamos ainda uma saliência no limite das grandes massas,
que é causado pelos limitação do tamanho do sistema.
Finalizamos este trabalho com a grande satisfação de um dever comprido, onde bus-
camos em todos os momentos a verdade dos fatos.
92
5 APÊNDICE
∆ p
cram
p
calt
0.000 0.5929 0.5929
0.020 0.5926 0.5924
0.040 0.5922 0.5915
0.060 0.5912 0.5897
0.080 0.5899 0.5876
0.100 0.5880 0.5840
0.125 0.5855 0.5794
0.150 0.5821 0.5736
0.175 0.5784 0.5675
0.200 0.5742 0.5607
0.225 0.5692 0.5539
0.250 0.5645 0.5466
0.275 0.5593 0.5396
0.300 0.5532 0.5326
0.325 0.5472 0.5259
0.350 0.5410 0.5200
0.375 0.5340 0.5142
0.400 0.5270 0.5095
0.425 0.5200 0.5056
0.450 0.5132 0.5027
0.475 0.5061 0.5010
Tabela 5: Tabela contendo os valores de probabilidades críticas para diferentes valores de
∆. Na coluna do meio temos a probabilidade crítica para o modelo aleatório p
cram
e na
coluna da direita a probabilidade crítica para o modelo alternado p
calt
. Os valores foram
obtidos a partir de simulações baseadas no método Self-Avoid Random Walk.
93
Referências
[1] Moreira A.A. and Amaral L.A.N., Phys. Rev. Let. 94, 218702 (2005).
[2] S. A. Kalffman, The Origens of Order, Ed. Oxford University Press, Oxford (1993).
[3] L. A. N. Amaral e J. M. Otino, Eur. Phys. J. B. 38, 147 (2004).
[4] S. A. Kalffman, Jour. Of Theo. Bio. 22, 437 (1969).
[5] T. Akutsu, S. Miyano e S. Kuhara, Pac. Symp. Biocomput., 17 (1999).
[6] S. Bornholdt e K. Snepp en, Phys. Rev. Lett. 81, 36 (1998).
[7] S. Bornholdt e T. Rohlf, Phys. Rev. Lett. 84, 6114 (2000).
[8] L. Wang, E. E. Pichler e J. Ross, Proc. Nat. Acad. Sci. USA 87, 9467 (1990).
[9] K. E. Kürten, J. Phys A, L615 (1988).
[10] B. Derrida, E. Gardner and A. Zippelius, Europhysics Letters 4, 167 (1987).
[11] B. Derrida e H. flyvbjerg, J. Phys A 19, 1003 (1986).
[12] B. Derrida and Y. Pomeau, Europhy. Lett 1 (2), 45 (1986).
[13] Flyvbjerg H., J. Phys. A 21, L955 (1986).
[14] Luque B. e Solé R. V., J. Phys. A 33, 284 (2000).
[15] S. H. Strogatz, Nature 410, 268 (2001).
[16] R. Albert e A.-L. Barabási, Rev. Modern Phys. 74, 47 (2002).
[17] A. Wuensche, Genomic Regulation Modeled as a Network with Basins of Attraction,
Pacific Symposium on Biocomputing, 3:89-102 (1998).
[18] A. Wuensche, Discrete Dynamical Networks and their Attractor Basins Complexity
International 6, (1998). Also SFI Working Paper 98 -11-101.
[19] M. Aldana-Gonzalez, Susan Coppersmith and Leo P. Kadanoff. Perspectives and
Problems in Nonlinear Science. A celebratory volule in honor of Lawrence Sirovich.
Springer Applied Mathematical Sciences Series. Ehud Kaplan, Jerrold E. Marsden,
and Katepalli R. Sreenivasan Eds. (May 2003), 23-89. ISBN: 0-387-00312-6; Um link
alternativo é http://arxiv.org/abs/nlin.AO/0204062
[20] H. K. Janssen, Z. Phys. B: Condens. Matter 42, 151 (1981).
[21] G. Odor, Rev. Mod. Phys. 76, 663 (2004).
Referências 94
[22] B. Derrida and D. Stauffer, Europhys. Lett. 2, 739 (1986).
[23] H. E. Stanley, D. Stauffer, J. Kertész e H. Herrmann, Phys. Rev. Left. 59, 2326
(1987).
[24] U. M. S. Costa, J. Phys. A 20, L583 (1987).
[25] P. Grassberger, J. Stat. Phys. 79, 13 (1995).
[26] P. Erdõs e A Rényi, Publ. Math. Inst. Hung. Acad. Sci. 79, 17 (1960).
[27] B. Bollobás. Discrete Math. 33(1), 1 (1981).
[28] Derek J. De Solla Price, Science 149, 510 (1965).
[29] Stanley Milgram, Psychology Today 2,60 (1967).
[30] D. J. Watts e S. H. Strogatz, Nature 393, 440 (1998).
[31] S. Redner, Eur. Phys. J. B 4 , 131 (1998).
[32] R. Albert, H. Jeong, and A.-L. Barabási, Nature 401, 130 (1999).
[33] R. Albert e A-. L. Barabási, Rev. Mod. Phys. 74, 47 (2002).
[34] M. Faloutsos, P. faloutsos e C. faloutsos, Comput. Commun. Rev. 29,251 (1999).
[35] F. Liljeros, C. R. Edling, L. A. N. Amaral, H. E. Stanley e Y. Aberg, Nature (London)
411, 907 (2001).
[36] J. E. M. Newman, Proc. Natl. Acad. Sci. USA 98, 404 (2001), J. E. M. Newman,
Phys. Rev. E 64, 016131 (2001), J. E. M. Newman, Phys. Rev. E 64, 016132 (2001).
[37] A-. L. Barabási e R. Albert, Science 286, 509 (1999).
[38] H. Jeong, B. Tombor, R. Albert, Z. N. Oltvai, and A.-L. Barabási, Nature, 407, 651
(2000).
[39] J. Abello, P. M. Pardalos e M. G. C. Resende, DIMACS Series in Discrete Mathema-
tics and Theoretical Computer Science (American Mathematical Society, Providence)
50, 119 (1999).
[40] H. E. Stanley, Rev. of Mod. Phys. 71, S358 (1999).
[41] K. G. Wilson, Rev. Mod. Phys. 47, 773 (1975).
[42] H. E. Stanley, L. A. N. Amaral, P. Gopikrishnan, P. C. Ivanov, T. H. Keittb e V.
Pleroua, Physica A 281, 60 (2000).
[43] S. N. Dorogovtsev e J. F. F. Mendes, Phys. Rev. E 63, 056125 (2001).
[44] P. L. Krapivsky e S. Redner, Phys. Rev. Lett. 86, 5401 (2001).
[45] A.-L. Barabási, R. Albert, H. Jeong, Physica A 272, 173 (1999).
Referências 95
[46] S. Carmi, S. Havlin, S. Kirkpatrik, Y. Shavitt and E. Shir, Proc. Natl. Acad. Sci.
USA 104, 11150 (2007).
[47] V. Batagelj, M. Zaversnik, http://arxiv.org/abs/cs/0202039v1
[48] S. N. Dorogovtsev, A. V. Goltsev and J. F. F. Mendes, Phys. Rev. Lett. 96, 040601
(2006)
[49] B. Pittel, J. Spencer and N. Wormald, J. Comb. Theo., Series B 67, 111 (1996)
[50] J. I. A. Hamelin, L. Dall’Asta, A. Barrat and A. Vespignani,
http://arxiv.org/abs/cs/0511007v4.
[51] M. Baur and M. Gaertler, R. Görke, M. Krug and D. Wagner, Proc. Euro. Conf.
Comp. Sys. (ECCS’07) (2007)
[52] S. N. Dorogovtsev, A. V. Goltsev and J. F. F. Mendes, Physica D 224, 7 (2006).
[53] A.-L. Barabási, R. Albert, and H. Jeong, Phys. A 281 69 (2000).
[54] S. R. Broadbent and J.M. Hammersley, Proc. of the Camb.e Phyl. Soc. 53, 629
(1957).
[55] D. Stauffer e A. Aharony, Introduction to Percolation Theory, Taylor & Francis,
Philadelphia, 1994.
[56] J. Feder, Fractals, Plenum Press. 1998
[57] B. Sapoval, M Rosso e J. F. Gouyet, J. Physique Lett. 46, L149 (1985).
[58] R. M. Ziff, P. T. Cummings e G. Stell, J. Phys Q: Math Gen. 17, 3009 (1984).
[59] P. Grassberger, Physica A 262, 251 (1999).
[60] H. J. Herrmann e H. E. Stanley, Phys. Rev. Lett. 53, 1121 (1984).
[61] M. Barthélémy, S. V. Buldyrev, S. Havlin e H. E. Stanley, Phys. Rev. E 60, R1123
(1999).
[62] I. Dayan, J. F. Gouyet e S. Havlin, J. Phys. A 24 , L287 (1991).
[63] M. Sahimi, Applications of Percolation Theory, Taylor & Francis, London, 1994.
[64] F. A. Dullien, Porous Media - Fluid Transport and Pore Structure, Academic, New
York, 1979.
[65] H. A. Makse, G.W. Davies, S. Havlin, P. C. Ivanov, P. R. King, and H. E. Stanley,
Phys. Rev. E 54, 3129 (1996); H. A. Makse, S. Havlin, P. C. Ivanov, P. R. King, S.
Prakash, and H. E. Stanley, Physica A 233, 587 (1996); H. A. Makse, S. Havlin, P.
R. King, and H. E. Stanley, Nature 386, 379 (1997).
[66] A. -L. Barabási e H.E. Stanley, Fractal Concepts in Surface Growth, Cambridge
University Press (1995).
Livros Grátis
( http://www.livrosgratis.com.br )
Milhares de Livros para Download:
Baixar livros de Administração
Baixar livros de Agronomia
Baixar livros de Arquitetura
Baixar livros de Artes
Baixar livros de Astronomia
Baixar livros de Biologia Geral
Baixar livros de Ciência da Computação
Baixar livros de Ciência da Informação
Baixar livros de Ciência Política
Baixar livros de Ciências da Saúde
Baixar livros de Comunicação
Baixar livros do Conselho Nacional de Educação - CNE
Baixar livros de Defesa civil
Baixar livros de Direito
Baixar livros de Direitos humanos
Baixar livros de Economia
Baixar livros de Economia Doméstica
Baixar livros de Educação
Baixar livros de Educação - Trânsito
Baixar livros de Educação Física
Baixar livros de Engenharia Aeroespacial
Baixar livros de Farmácia
Baixar livros de Filosofia
Baixar livros de Física
Baixar livros de Geociências
Baixar livros de Geografia
Baixar livros de História
Baixar livros de Línguas
Baixar livros de Literatura
Baixar livros de Literatura de Cordel
Baixar livros de Literatura Infantil
Baixar livros de Matemática
Baixar livros de Medicina
Baixar livros de Medicina Veterinária
Baixar livros de Meio Ambiente
Baixar livros de Meteorologia
Baixar Monografias e TCC
Baixar livros Multidisciplinar
Baixar livros de Música
Baixar livros de Psicologia
Baixar livros de Química
Baixar livros de Saúde Coletiva
Baixar livros de Serviço Social
Baixar livros de Sociologia
Baixar livros de Teologia
Baixar livros de Trabalho
Baixar livros de Turismo