Surgimento de escalas em Redes Aleatórias

Prévia do material em texto

Surgimento de escalas em Redes Aleato´rias
Raabe Melo de Oliveira
May 22, 2015
Sistemas ta˜o diversos como as redes gene´ticas ou o www sa˜o os melhores
descrito como redes com topologia complexa. A propriedade comum de muitos
grandes redes e´ que as conectividades dos ve´rtice seguem uma lei de poteˆncia sem
escala de distribuic¸a˜o. Este recurso foi encontrado para ser uma consequeˆncia
de dois mecanismos gene´ricos:
– Redes de expansa˜o continua pela adic¸a˜o de novos ve´rtices.
– E novos ve´rtices anexados preferencialmente para sites que ja´ esta˜o bem
conectados.
Um modelo com base nestes dois ingredientes reproduz o observado a esta-
ciona´ria distribuic¸o˜es livres de escala, o que indica que o desenvolvimento de
grandes redes e´ regida por fenoˆmenos de auto-organizac¸a˜o robustas que va˜o
ale´m das indicac¸o˜es dos sistemas individuais.
A incapacidade da cieˆncia contemporaˆnea para descrever sistemas compostos
de elementos na˜o ideˆnticos que teˆm diversas e na˜o-locais interac¸o˜es atualmente
limita avanc¸os em muitas disciplinas, que va˜o da biologia molecular a` cieˆncia
da computac¸a˜o. A dificuldade de descrever esses sistemas encontra-se em parte
em sua topologia: Muitos deles formam redes bastante complexas cujos ve´rtices
sa˜o os elementos do sistema e cujas arestas representam as interac¸o˜es entre eles.
Por exemplo, os sistemas vivos formam uma enorme rede gene´tica cujos
ve´rtices sa˜o prote´ınas e genes, as interac¸o˜es qu´ımicas entre eles representam
arestas. A um n´ıvel diferente organizacional, uma grande rede e´ formada pelo
sistema nervoso, cujos ve´rtices sa˜o as ce´lulas nervosas, ligados por axoˆnios. Mas
as redes igualmente complexas ocorrem em cieˆncias sociais, onde os ve´rtices sa˜o
indiv´ıduos ou organizac¸o˜es e as arestas sa˜o as interac¸o˜es sociais entre elas, ou na
World Wide Web (WWW), cujos ve´rtices sa˜o documentos HTML ligadas por
ligac¸o˜es que apontam a partir de uma pa´gina a outra. Devido ao seu grande
tamanho e a complexidade das suas interac¸o˜es, a topologia destas redes e´ em
grande parte desconhecida.
Tradicionalmente, redes de topologia complexa teˆm sido descritas com teoria
aleato´ria dos grafos de Erdos e Re nyi (ER), mas na auseˆncia de dados sobre
grandes redes, as previso˜es da teoria ER raramente foram testadas no mundo
real. No entanto, impulsionado pela informatizac¸a˜o de aquisic¸a˜o de dados, tais
informac¸o˜es topolo´gicas e´ cada vez mais dispon´ıveis, aumentando a possibilidade
de entendimento a estabilidade dinaˆmica e topolo´gica de grandes redes.
Aqui relatamos a existeˆncia de um elevado grau de auto-organizac¸a˜o car-
acterizado das propriedades de grande escala de redes complexas. Explorando
va´rios grandes bancos de dados que descrevem a topologia de grandes redes que
abrangem campos ta˜o diversos como a WWW ou citac¸a˜o padro˜es da cieˆncia,
mostramos que, independente do sistema e a identidade dos seus constituintes,
1
a probabilidade P (k) de que um ve´rtice na rede interage com outros ve´rtices
decai como uma lei de poteˆncia, seguinte P (k) ≈ K−γ . Este resultado indica
que grandes redes de auto-organizac¸a˜o em um estado livre de escala, uma car-
acter´ıstica imprevis´ıveis por todos os modelos de redes aleato´rias existentes.
Para explicar a origem dessa invariaˆncia de escala, no´s mostramos que modelos
de redes existentes na˜o incorporam o crescimento e fixac¸a˜o preferencial, duas
caracter´ısticas-chave de redes reais.
Utilizando um modelo que incorpora estes dois ingredientes, que mostram
que eles sa˜o responsa´vel pela lei de poteˆncia de escala observada em redes reais.
Finalmente, argumentamos que estes ingredientes teˆm um papel facilmente iden-
tifica´veis e importante na formac¸a˜o de muitos sistemas complexos, o que implica
que os nossos resultados sa˜o relevantes para uma grande classe de redes obser-
vado na natureza.
Embora exista muitos sistemas que formam redes complexas, topolo´gico de-
talhada dados esta˜o dispon´ıveis para apenas alguns. O gra´fico colaborac¸a˜o de
atores do filme representa uma bem documentado exemplo de um trabalho social
em rede. Cada ator e´ representado por um ve´rtice, dois atores esta˜o sendo conec-
tado se eles forem lanc¸ados juntos no mesmo filme. A probabilidade de que um
ator tenha ligac¸o˜es k (que caracterizam a sua popularidade) tem uma extremi-
dade da lei de potencia para k grande, apo´s P (k) ≈ K−γ , onde γator = 2.3±0.1
. Uma rede mais complexa com mais de 800 milho˜es de ve´rtices e´ a WWW, onde
um ve´rtice e´ um documento e as arestas sa˜o as ligac¸o˜es que aponta a partir de
um documento para outro. A topologia deste gra´fico determina a conectividade
da Web e, consequentemente, a nossa efica´cia na localizac¸a˜o de informac¸o˜es na
WWW. Informac¸a˜o sobre p(k) podem ser obtidos utilizando os roboˆs , o que
indica que a probabilidade de que os documentos k apontam para uma deter-
minada pa´gina da Web segue uma lei de poteˆncia, com γwww = 2.1± 0.1 . Uma
rede cuja topologia reflete os padro˜es histo´ricos de desenvolvimento urbano e
industrial e´ a rede de energia ele´trica do oeste dos Estados Unidos, os ve´rtices
que sa˜o geradores, transformadores e subestac¸o˜es e as arestas para as linhas de
transmissa˜o de alta tensa˜o entre eles . Por causa do tamanho relativamente
modesto da rede, contendo apenas ve´rtices 4941, a regia˜o de escalonamento e´
menos proeminente, mas e´, no entanto aproximada por uma lei de poteˆncia com
um expoente γpower = 2.3 ≈ 4 Finalmente, uma grande rede complexa e´ for-
mada pelos padro˜es de citac¸a˜o das publicac¸o˜es cient´ıficas, os ve´rtices que sa˜o
artigos publicados em revistas indexadas e as arestas links para os artigos cita-
dos em um papel. Recentemente Redner mostrou que a probabilidade de que
um artigo e´ citado vezes k (representando a conectividade de um papel dentro
da rede) segue uma lei de poteˆncia com expoente γcite = 3.
Os exemplos acima demonstram que muitas grandes redes aleato´rios com-
partilham a caracter´ıstica em comum de que a distribuic¸a˜o da sua conectividade
local e´ livre de escala, seguindo uma lei de poteˆncia para grandes k com um ex-
poente γ entre 2.1 e 4.0 , o que e´ inesperado, no quadro do atual modelos de
rede. O modelo gra´fico aleato´rio de ER assume que comec¸amos com N ve´rtices
e conectamos cada par de ve´rtices com probabilidade P . . No modelo, a prob-
abilidade de que um ve´rtice tem k arestas segue uma distribuic¸a˜o de Poisson
P (k) =
e−λλ
k!
, onde
2
λ = N(
N − 1
k
)P k(1− P )N−1−k
. N e´ o nu´mero de ve´rtices.
No modelo do mundo pequeno recentemente introduzida por Watts e Stro-
gatz, N ve´rtices formam uma rede unidimensional, cada ve´rtice sendo ligado aos
seus dois mais pro´ximos vizinhos. Com probabilidade p, cada aresta e´ reconec-
tado a um ve´rtice escolhido ao acaso. As conexo˜es de longo alcance gerado por
este processo indicam a distaˆncia entre os ve´rtices, que conduz a um fenoˆmeno
do mundo pequeno, muitas vezes referida como seis graus de separac¸a˜o. Para
p = 0, a distribuic¸a˜o de probabilidade das conectividades e´ P (k) = δ(k − Z),
em que e´ z o nu´mero de coordenac¸a˜o na rede; enquanto que para p finito, P (k)
ainde existem picos ao redor de, z mas agora tornam-se mais amplo. A carac-
ter´ıstica comum dos modelos ER e WS e´ que a probabilidade de encontrar um
ve´rtice altamente ligado (isso mesmo, um grande k) diminui exponencialmente
com k; assim, com os ve´rtices conectividade grande esta˜o praticamente ausentes.
Em contraste, a lei de poteˆncia da extremidade caracteriza P (k) para as redes
estudadas indicando que ve´rtices altamente ligado (grande k) teˆm uma grande
chance de ocorrer, dominando a conectividade.
Ha´ dois aspectos gene´ricos de redes reais que na˜o sa˜o incorporados nestes
modelos. Primeiro, ambos os modelos assumem que no´s comec¸amos com um
nu´mero fixo N de ve´rticesque sa˜o enta˜o conectadas aleatoriamente (modelo
ER), ou reconectado (modelo WS), sem modificar N . . Em contraste, a maioria
das redes do mundo real esta˜o abertas e elas s a˜o formadas pela adic¸a˜o cont´ınua
de novos ve´rtices para o sistema, portanto, o nu´mero de ve´rtices N aumenta ao
longo do tempo de vida da rede. Por exemplo, a rede ator cresce pela adic¸a˜o
de novos atores para o sistema, o WWW cresce exponencialmente ao longo do
tempo pela adic¸a˜o de novas pa´ginas da Web, e da literatura de pesquisa cresce
constantemente pela publicac¸a˜o de novos documentos. Consequentemente, uma
caracter´ıstica comum destes sistemas e´ que a rede se expande continuamente
pela adic¸a˜o de novos ve´rtices que sa˜o conectados para os ve´rtices ja´ presente no
sistema.
Em segundo lugar, os modelos de rede aleato´rias assumir que a probabilidade
de que dois ve´rtices esta˜o conectados e´ aleato´rio e uniforme. Em contraste, a
maioria das redes reais exibem preferencial conectividade. Por exemplo, um
novo ator e´ mais prova´vel de ser escalado para um papel de apoio com os atores
mais consagrados e mais conhecidos. Consequentemente, a probabilidade de
que um novo ator sera´ lanc¸ado com os ja´ estabelecidos e´ muito maior do que o
novo ator sera´ lanc¸ado com outros atores menos conhecidos. Da mesma forma,
uma pa´gina da Web rece´m-criado sera´ mais prova´vel para incluir links para
bem conhecidas documentos ja´ populares com alta conectividade, e um novo
manuscrito e´ mais propensos a citar um artigo bem conhecido e, portanto, muito
citado do que o seu menos citados e consequentemente pares menos conhecido.
A seguir mostraremos que um modelo baseado nestes dois ingredientes levam
naturalmente a` distribuic¸a˜o observada pela de escala invariante. Para incorporar
o personagem crescente da rede, comec¸amos com um pequeno nu´mero de ve´rtices
m0, a cada vez que adicionarmos um novo ve´rtice com m(≤ m0) arestas que
ligam o novo ve´rtice de m diferentes ve´rtices ja´ presente no sistema. Para
incorporar a fixac¸a˜o preferencial, assumimos que a probabilidade Π que um novo
ve´rtice sera´ conectado ao ve´rtice i depende da ki conectividade desse ve´rtice,
3
de modo que
Π(ki) =
ki∑
j kj
Depois de um tempo t passos, o modelo coduz a uma rede aleato´ria com t+m0
ve´rtices e arestas tem k arestas, segue um alei de poteˆncia com um expoente
γmode = 2.9 ± 0.1. Uma vez que a lei de poteˆncia observada para redes reais
descreve sistemas de tamanhos muito diferentes em diferentes fases do seu de-
senvolvimento, espera-se que uma correc¸a˜o do modelo deva fornecer uma dis-
tribuic¸a˜o cujas principais caracter´ısticas sa˜o independentes do tempo. De fato
demonstra, P (k) e´ independente do tempo (e, subsequentemente, independente
do tamanho do sistema m0 + t), indicando que, apesar de seu crescimento
cont´ınuo, o sistema organiza-se em um estado estaciona´rio sem escala.O de-
senvolvimento do escalonamento da lei de potencia no modelo indica que o
crescimento e fixac¸a˜o preferencial desempenham um papel importante no de-
senvolvimento da rede. Para verificar se ambos os ingredientes sa˜o necessa´rios,
no´s investigamos duas variantes do modelo. Um Modelo mante´m o cara´cter
crescente da rede, mas a fixac¸a˜o preferencial e´ eliminada pois assumindo que
um novo ve´rtice e´ ligado com uma igual probabilidade de qualquer ve´rtice no
sistema [isto e´, Π(k) = const = 1(m0+t+1) ]. Tal um modelo leva a P (K) ≈ e−βk,
indicando que na auseˆncia de uma ligac¸a˜o preferencial elimina-se o recurso livre
da escala de distribuic¸a˜o. No modelo B, comec¸amos com N ve´rtices e sem
arestas. Em cada passo de tempo, vamos selecionar aleatoriamente um ve´rtice
e conecta´-lo com probabilidade Π(ki) =
ki∑
j
kj
ao ve´rtice i no sistema. mb-
ora os primeiros tempos o modelo exibe uma lei de potencia de escala, P (k)
na˜o esta´ parado: porque N e´ constante e o nu´mero de arestas aumenta com
o tempo, apo´s as etapas t ≈ N2 fez que o sistema atinja um estado em que
todos os ve´rtices estejam ligados. A falha de sistemas A e B indica que tanto
o crescimento preferencial de fixac¸a˜o e ingredientes – e preferencial de engate
do qual sa˜o necessa´rias para o desenvolvimento da distribuic¸a˜o lei de poteˆncia
estaciona´ria observado na Fig.1.
Devido a` ligac¸a˜o preferencial, um ve´rtice que adquire mais conexo˜es do que
outro ira´ aumentar a sua conectividade numa maior taxa, assim, A diferenc¸a
inicial na conectividade entre dois ve´rtices ira´ aumentar ainda mais enquanto
a rede cresce. A taxa em que um ve´rtice adquire arestas e´ ∂ki∂t =
ki
2t , o que da´
ki = m(
t
ti
)0.5, onde t e´ o tempo em que o ve´rtice i foi adicionado a o sistema (ver
4
a Fig. 2C), uma propriedade de escala que poderia ser diretamente testada uma
vez que dados resolvidos no tempo em conectividade de rede torna-se dispon´ıvel.
Assim, os ve´rtices mais velhos (com menor ti ) aumentam a sua conectividade
a` custa dos mais jovens (com maior ti), levando ao longo do tempo para alguns
ve´rtices que sa˜o altamente conectado, um fenoˆmeno ”ricos tornam-se mais ricos”
que pode ser facilmente detectado em redes reais. Ale´m disso, esta propriedade
pode ser usada para calcular γ analiticamente. A probabilidade de que um
ve´rtice i tenha uma ligac¸a˜o menor do que k, P [ki(t) < k], pode ser escrito como
P (ti >
m2t
k2 ). Assumindo que no´s adicionermos os ve´rtices para o sistema em
intervalos de tempo iguais, iremos obter P (ti >
m2t
k2 ) = 1 − P (ti ≤ m
2t
k2 ) =
1 − m2tk2 (t + m0). A densidade de probabilidadepode P (k) ser obtido a partir
de P (k) = ∂P∂K [ki(t) < k], que ao longo de longos per´ıodos de tempo leva para a
soluc¸a˜o estaciona´ria
P (k) =
2m2
k3
dando γ = 3 independente de m. Embora reproduza uma distribuic¸a˜o gratuita
de escala observada, o modelo proposto na˜o se pode esperar para ter em conta
todos os aspectos das redes estudadas. Para isso, precisamos modelar estes
sistemas em mais detalhes. Por exemplo, no modelo assumimos fixac¸a˜o pref-
erencial linear; isto e´, Π(k) ≈ k. No entanto, embora em geral Π(k) poderia
ter uma forma arbitra´ria na˜o-linear Π(k) ≈ kα, as simulac¸o˜es indicam que a
escala esta´ presente apenas para α = 1 Ale´m disso, os expoentes obtidos para o
diferentes redes esta˜o espalhadas entre 2,1 e 4. No entanto, e´ fa´cil de modificar
o nosso modelo de conta para expoentes diferentes de α = 3 Por exemplo, se
assumirmos que uma frac¸a˜o de p as ligac¸o˜es sa˜o dirigida, obtemos α(p) = 3− p,
que e´ suportado por meio de simulac¸o˜es nume´ricas. Finalmente, algumas redes
na˜o evoluem apenas pela adic¸a˜o de novos ve´rtices mas adicionando (E a`s vezes
remover) as conexo˜es entre os ve´rtices estabelecidos. Embora estes e outras
caracter´ısticas espec´ıficas do sistema poderia modificar o expoente γ, o nosso
modelo oferece o primeiro mecanismo sucessivo para a natureza escala invariante
de redes reais.
Crescimento e fixac¸a˜o preferencial sa˜o mecanismos comuns a uma se´rie de
sistemas complexos, incluindo redes de nego´cios, redes sociais (descrevendo in-
div´ıduos ou organizac¸o˜es), as redes de transporte, e assim por diante. Conse-
quentemente, espera-se que o Estado de escala invariante observada em todos
os sistemas para os quais os dados detalhados esta´ dispon´ıvel para no´s e´ uma
propriedade gene´rica de muitas redes complexas, com aplicabilidade atingindo
muito ale´m dos exemplos citados. A melhor descric¸a˜o desses sistemas ajudaria
na compreensa˜o de outros sistemas complexos, bem como, para os quais as in-
formac¸o˜es menos topolo´gico esta´ neste momento dispon´ıvel, incluindo exemplos
importantes como as redes gene´ticas ou de sinalizac¸a˜o em sistemas biolo´gicos.
No´s muitas vezes na˜o pensamos em sistemas biolo´gicos como aberta ou crescente,
porque os seus recursos sa˜o geneticamente codificados. No entanto, as carac-
ter´ısticas das escala livresposs´ıveis de redes gene´ticas e de sinalizac¸a˜o poderiam
refletir a histo´ria evolutiva das redes, dominado pelo crescimento e agregac¸a˜o
de diferentes constituintes, conduzindo a partir de mole´culas simples para or-
ganismos complexos. Com os ra´pidos avanc¸os sendo feitos em mapeamento de
redes gene´ticas, respostas as estas perguntas pode na˜o estar muito longe.
5
Mecanismos semelhantes poderiam explicar a origem das disparidades sociais
e econoˆmicas que regem os sistemas concorrentes, porque as heterogeneidades
livre de escala sa˜o a consequeˆncia inevita´vel da auto-organizac¸a˜o devido a`s de-
ciso˜es locais feitas pelos ve´rtices individuais, com base nas informac¸o˜es que sa˜o
inclinados para os ve´rtices mais vis´ıveis (mais ricos), independentemente da
natureza e origem desta visibilidade.
6