Redes Livre de Escala

Origem: Wikipédia, a enciclopédia livre.
Ir para: navegação, pesquisa


As redes livres de escala são redes complexas cujo grau de distribuição segue a lei de potência, em que a maioria dos nodos(vértices) tem poucas ligações, contrastando com a existência de alguns nodos que apresentam um elevado número de ligações, ou seja um nodo com Grau(ligações) alto tende a ligar-se a outro nodo de Grau alto. A probabilidade de um nodo se ligar a outro nodo é diretamente proporcional ao seu Grau. Deste modo as redes livres de escala são dominadas por um número relativamente pequeno de nós a que designamos de hubs. Estas redes são por norma mais resistentes a falhas acidentais mas vulneráveis a ataques coordenados.
Nestas redes a probabilidade de um nó ter k ligações decai quando k aumenta, segundo a lei de potência.



P(k) \ \sim \ k^\boldsymbol{-\gamma}

em que k>0 e \gamma>0. Sendo \gamma denominado de expoente de livre escala e determina a probabilidade de P(k) da ocorrência de nodos com grau k na rede.

As redes de livre escala são bastante comuns e podem ser identificadas nos mais variados contextos tais como: World Wide Web, as redes biológicas, as redes sociais, redes metabolicas,... apesar da comunidade científica questionar estas reivindicações à medida que técnicas mais sofisticadas de análise de dados vão surgindo.[1]

História[editar | editar código-fonte]

O termo livre escala surgiu e através de um estudo[2] liderado por László Barabási na 'Universidade de Notre Dame em 1998, onde ao mapear a World Wide Web[3] pode verificar que 80% das páginas web tinham apenas 4 hiperligações e que aproximadamente 0,001% das páginas tinha mais de 1000 hiperligações. Praticamente ao mesmo tempo, uma observação semelhante foi obtida pelos irmãos Faloutsos (1999). E mais tarde Broder et al. (2000) confirmaram os dados obtidos, atravês de um mapeamento da Web numa escala maior.

Barabási e Albert propuseram um mecanismo dinâmico que designaram de ligação preferencial, para explicar o aparecimento de redes livres de escala. O mecanismo apresentado tinha como ideia base que o crescimento das redes obedecia a algumas regras, nomeadamente que os novos nodos adicionados à rede, ligam-se preferencialmente aos nodos com maior Grau. É de referir contudo que este mecanismo apenas explica a criação de um subconjunto específico das redes de escala livre, muitos outros mecanismos alternativos foram descobertos deste então. [4]

Características[editar | editar código-fonte]

rede aleatória(a) e rede de escala livre (b). Na rede aleatória verifica-se que a rede está interligada de modo aleatório. Nas redes de escala livre verifica-se a existência de nodos com mais ligações, que são são identificados como hubs.

A característica mais notável das redes livres de escala está relacionada com o número nodos (vértices) que possuem um Grau que excede em muito a média. Estes nodos são designados de "hubs" e tem um papel fundamental dentro da rede.

Outra das características das redes livres de escala diz respeito à sua capacidade de se manterem operacionais, estas redes tem uma grande capacidade de resistir à eliminação de alguns dos seus nodos ou ligações. Contudo são bastantes vulneráveis à quando perdem os nodos com Grau mais elevado ou seja, os hubs. O facto dos hubs com grau mais elevado estarem ligados a outros com menor grau e assim subsequentemente garante que a rede possui uma maior tolerância à falhas. Se uma falha aleatória acorrer na rede a probabilidade de um hub ser afetado é muito reduzido uma vez que a grande maioria dos nodos tem um grau baixo. Mesmo na eventualidade de um hub ser afetado os hubs restantes deverão conseguir manter a conectividade dos nodos da rede. Contudo se alguns dos hubs principais forem afetados, a integridade da rede fica seriamente comprometida, assim podemos considerar que os hubs são em certa medida o ponto forte e ponto fraco das redes livres de escala. Estas propriedades tem vindo a ser estudadas em maior detalhe através de percolation theory de Cohen et al.[5] [6] e por Callaway et al.[7]

Outra das características de grande importância das redes livre de escala é designada de coeficiente de aglomeração, que diminui à medida que o grau dos nodos aumentam. Esta distribuição também se rege pela lei de potencia. Implicando que os nodos com um grau baixo pertençam a uma sub-rede e essa sub-rede por sua vez ligada-se a outras sub-redes através dos hubs. Considere uma rede social onde os nodos correspondem a pessoas e as ligações correspondem as relações entre as pessoas da rede social. Será relativamente fácil identificar grupos de pessoas na rede que formam comunidades(pequenos grupos onde todos se conhecem) e dentro dessas comunidades existem pessoas que tem ligações com pessoas que não pertencem à comunidade. E dentro da rede existem ainda pessoas ( figuras publicas, políticos,..) que tem ligações com várias comunidades dentro da rede social, ou seja funcionam como hubs e podem ser consideradas responsáveis surgimento do fenómeno conhecido como mundo-pequeno.

Algumas das características das redes livres de escala estão associadas aos mecanismos utilizados para as gerar. Por exemplo as redes geradas através do mecanismo da ligação preferencial colocam os nodos com Grau mais elevado numa zona central da rede, interligando por forma a criar um núcleo de hubs, ou seja à medida que nos afastamos do centro da rede o Grau dos nodos vai diminuindo progressivamente. Neste tipo de rede a remoção aleatória de um grande numero de nodos não tem grande impacto, o que sugere que este tipo de mecanismo possa ser útil em situações em que a segurança é uma das principais preocupações. Outros tipo de mecanismos colocam os nodos com maior Grau na periferia da rede e consequentemente não apresentam as mesmas características.

Por mim, outra das caraterísticas diz respeito à distancia media entre dois nodos de uma rede. Tal como se verifica na maioria das redes desordenadas com o modelo de rede mundo pequeno, a distancia entre os nodos é relativamente pequena quando comparada com redes muito organizadas.

Exemplos[editar | editar código-fonte]

Apesar de serem apresentados muitos exemplos do mundo real de redes livres de escala, nem sempre é fácil provar de uma forma inequívoca que os exemplos apresentados se enquadram nesse tipo de redes, em grande parte devido ao aparecimento de técnicas mais rigorosas de analise dos dados[1] . Alguns exemplos que usualmente são apresentados como redes livres de escala são:

Consultar[editar | editar código-fonte]

Referências[editar | editar código-fonte]

  1. a b Clauset, Aaron; Cosma Rohilla Shalizi, M. E. J Newman. (2007-06-07). "Power-law distributions in empirical data". 0706.1062. DOI:10.1137/070710111. Bibcode2009SIAMR..51..661C.
  2. "". DOI:10.1038/scientificamerican0503-60.
  3. (October 15, 1999) "Emergence of scaling in random networks". Science 286 (5439): 509–512. DOI:10.1126/science.286.5439.509. PMID 10521342. Bibcode1999Sci...286..509B.
  4. doi:10.1080/00018730110112519
    Esta citação será automaticamente completada em poucos minutos. Você pode furar a fila ou completar manualmente
  5. Cohen, Reoven; K. Erez, D. ben-Avraham and S. Havlin. (2000). "Resilience of the Internet to Random Breakdowns". Phys. Rev. Lett. 85: 4626–8. DOI:10.1103/PhysRevLett.85.4626. Bibcode2000PhRvL..85.4626C.
  6. Cohen, Reoven; K. Erez, D. ben-Avraham and S. Havlin. (2001). "Breakdown of the Internet under Intentional Attack". Phys. Rev. Lett. 86: 3682–5. DOI:10.1103/PhysRevLett.86.3682. PMID 11328053. Bibcode2001PhRvL..86.3682C.
  7. Callaway, Duncan S.; M. E. J. Newman, S. H. Strogatz and D. J. Watts. (2000). "Network Robustness and Fragility: Percolation on Random Graphs". Phys. Rev. Lett. 85: 5468–71. DOI:10.1103/PhysRevLett.85.5468. Bibcode2000PhRvL..85.5468C.
  8. Soramäki, Kimmo; et. al. (2007). "The topology of interbank payment flows". Physica A: Statistical Mechanics and its Applications 379 (1): 317–333. DOI:10.1016/j.physa.2006.11.093. Bibcode2007PhyA..379..317S.
  9. Steyvers, Mark; Joshua B. Tenenbaum. (2005). "The Large-Scale Structure of Semantic Networks: Statistical Analyses and a Model of Semantic Growth". Cognitive Science 29 (1): 41–78. DOI:10.1207/s15516709cog2901_3.