Rede sem escala

Ciência da Rede
Teoria
Grafo Rede complexa Contágio Redes de pequeno mundo Scale-free Estrutura comunitária Percolação Evolução Difusão de inovações (redes sociais) Controlabilidade Desenho grafo Capital social Análise de links Otimização Reciprocidade Transitividade Ligação preferencial Teoria do equilíbrio Efeito de rede Influência social
Tipos de Rede
Rede de computadores Telecomunicação Rede social Neural Artificial Interdependente Semântico Dependência Fluxo
Grafos
Caraterísticas Clique Componente Corte Ciclo Estrutura de dados Aresta Laço Vizinhança Caminho Vértice Lista de adjacência / matriz Incidência Lista / matrix Tipos Grafo bipartido Grafo completo Grafo orientado Hipergrafo Multigrafo Aleatórios Ponderado
Métricas & Algoritmos
Centralidade Grau Betweenness Proximidade PageRank Clustering Centralidades Baseadas na Dissimilaridades Distribuição de Graus Correlação de Graus Assortatividade Distância Modularidade
Modelos
Grafo Aleatório Erdös–Rényi Barabási–Albert Watts–Strogatz Exponencial Aleatório (ERGM) Epidemia Hierárquica
Categorias
Teoria dos grafos Teoria das redes complexas
v d e

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.

${\displaystyle P(k)\ \sim \ k^{\boldsymbol {-\gamma }}}$ em que k>0 e ${\displaystyle \gamma }$>0. Sendo ${\displaystyle \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

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

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 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

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:

• Redes Sociais, onde se incluem as redes colaborativas. Um dos exemplos mais estudados é a a colaboração de atores em filmes.
• As relações sexuais humanas, que podem contribuir para a disseminação de doenças sexualmente transmissíveis.
• Vários tipos de redes de computadores, incluindo a internet e as representações gráficas da World Wide Web.
• Algumas redes financeiras como as redes interbancarias de pagamento [8]
• Proteínas-Rede de interação das proteínas.
• Redes semânticas.[9]
• Redes de estradas, rotas marítimas e rotas aéreas.

Consultar

• Grafos aleatórios
• Redes Complexas

Referências

1. Clauset, Aaron; Cosma Rohilla Shalizi, M. E. J Newman (7 de junho de 2007). «Power-law distributions in empirical data». 0706.1062. Bibcode:2009SIAMR..51..661C. arXiv:0706.1062. doi:10.1137/070710111  A referência emprega parâmetros obsoletos |coautor= (ajuda)
2. Barabási, Albert-László; Eric. «Scale-Free Networks». Scientific American. 288 (5): 60-69. doi:10.1038/scientificamerican0503-60  A referência emprega parâmetros obsoletos |coautores= (ajuda)
3. Barabási, Albert-László; Albert, Réka. (15 de outubro de 1999). «Emergence of scaling in random networks». Science. 286 (5439): 509–512. Bibcode:1999Sci...286..509B. MR 2091634. PMID 10521342. arXiv:cond-mat/9910332. doi:10.1126/science.286.5439.509 
4. Dorogovtsev, S. N.; J. F. F. (1 de junho de 2002). «Evolution of networks». Advances in Physics. 51 (4): 1079-1187. ISSN 0001-8732. doi:10.1080/00018730110112519  A referência emprega parâmetros obsoletos |coautores= (ajuda)
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. Bibcode:2000PhRvL..85.4626C. arXiv:cond-mat/0007048. doi:10.1103/PhysRevLett.85.4626  A referência emprega parâmetros obsoletos |coautor= (ajuda)
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. Bibcode:2001PhRvL..86.3682C. PMID 11328053. arXiv:cond-mat/0010251. doi:10.1103/PhysRevLett.86.3682  A referência emprega parâmetros obsoletos |coautor= (ajuda)
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. Bibcode:2000PhRvL..85.5468C. arXiv:cond-mat/0007300. doi:10.1103/PhysRevLett.85.5468  A referência emprega parâmetros obsoletos |coautor= (ajuda)
8. Soramäki, Kimmo; et. al (2007). «The topology of interbank payment flows». Physica A: Statistical Mechanics and its Applications. 379 (1): 317–333. Bibcode:2007PhyA..379..317S. doi:10.1016/j.physa.2006.11.093  A referência emprega parâmetros obsoletos |coautor= (ajuda)
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  A referência emprega parâmetros obsoletos |coautor= (ajuda)

• Albert R., Barabási A.-L. (2002). «Statistical mechanics of complex networks». Rev. Mod. Phys. 74: 47–97. Bibcode:2002RvMP...74...47A. arXiv:cond-mat/0106096. doi:10.1103/RevModPhys.74.47 
• Amaral, LAN, Scala, A., Barthelemy, M., Stanley, HE. (2000). «Classes of behavior of small-world networks». Proc. Natl. Acad. Sci. U.S.A. 97 (21): 11149–52. Bibcode:2000PNAS...9711149A. PMC 17168. PMID 11005838. arXiv:cond-mat/0001458. doi:10.1073/pnas.200327197  !CS1 manut: Nomes múltiplos: lista de autores (link)
• Barabási, Albert-László (2004). Linked: How Everything is Connected to Everything Else. [S.l.: s.n.] ISBN 0-452-28439-2 
• Barabási, Albert-László; Bonabeau, Eric (maio de 2003). «Scale-Free Networks» (PDF). Scientific American. 288 (5): 60–9. doi:10.1038/scientificamerican0503-60 
• Dan Braha, Yaneer Bar-Yam (2004). «Topology of Large-Scale Engineering Problem-Solving Networks» (PDF). Phys. Rev. E. 69. 016113 páginas. Bibcode:2004PhRvE..69a6113B. doi:10.1103/PhysRevE.69.016113 
• Caldarelli G. "Scale-Free Networks" Oxford University Press, Oxford (2007).
• Caldarelli G., Capocci A., De Los Rios P., Muñoz M.A. (2002). «Scale-free networks from varying vertex intrinsic fitness». Physical Review Letters. 89 (25). 258702 páginas. Bibcode:2002PhRvL..89y8702C. PMID 12484927. arXiv:cond-mat/0207366. doi:10.1103/PhysRevLett.89.258702  !CS1 manut: Nomes múltiplos: lista de autores (link)
• R. Cohen, K. Erez, D. ben-Avraham and S. Havlin (2000). «Resilience of the Internet to Random Breakdowns». Phys. Rev. Lett. 85: 4626–8. Bibcode:2000PhRvL..85.4626C. arXiv:cond-mat/0007048. doi:10.1103/PhysRevLett.85.4626  !CS1 manut: Usa parâmetro autores (link)
• R. Cohen, K. Erez, D. ben-Avraham and S. Havlin (2001). «Breakdown of the Internet under Intentional Attack». Phys. Rev. Lett. 86: 3682–5. Bibcode:2001PhRvL..86.3682C. PMID 11328053. arXiv:cond-mat/0010251. doi:10.1103/PhysRevLett.86.3682  !CS1 manut: Usa parâmetro autores (link)
• A.F. Rozenfeld, R. Cohen, D. ben-Avraham, S. Havlin (2002). «Scale-free networks on lattices». Phys. Rev. Lett. 89  !CS1 manut: Usa parâmetro autores (link)
• Dangalchev, Ch. (2004). «Generation models for scale-free networks». Physica A. 338 
• Dorogovtsev, Mendes, J.F.F. , Samukhin, A.N. (2000). «Structure of Growing Networks: Exact Solution of the Barabási—Albert's Model». Phys. Rev. Lett. 85 (21): 4633–6. Bibcode:2000PhRvL..85.4633D. PMID 11082614. arXiv:cond-mat/0004434. doi:10.1103/PhysRevLett.85.4633  !CS1 manut: Nomes múltiplos: lista de autores (link)
• Dorogovtsev, S.N., Mendes, J.F.F. (2003). Evolution of Networks: from biological networks to the Internet and WWW. [S.l.]: Oxford University Press. ISBN 0-19-851590-1  !CS1 manut: Nomes múltiplos: lista de autores (link)
• Dorogovtsev, S.N., Goltsev A. V., Mendes, J.F.F. (2008). «Critical phenomena in complex networks». Rev. Mod. Phys. 80. 1275 páginas. Bibcode:2008RvMP...80.1275D. arXiv:0705.0010. doi:10.1103/RevModPhys.80.1275  !CS1 manut: Nomes múltiplos: lista de autores (link)
• Dorogovtsev, S.N., Mendes, J.F.F. (2002). «Evolution of networks». Advances in Physics. 51: 1079–1187. Bibcode:2002AdPhy..51.1079D. arXiv:cond-mat/0106144. doi:10.1080/00018730110112519  !CS1 manut: Nomes múltiplos: lista de autores (link)
• Erdős, P.; Rényi, A. (1960). On the Evolution of Random Graphs (PDF). 5. [S.l.]: Publication of the Mathematical Institute of the Hungarian Academy of Science. pp. 17–61 
• Faloutsos, M., Faloutsos, P., Faloutsos, C. (1999). «On power-law relationships of the internet topology». Comp. Comm. Rev. 29. 251 páginas. doi:10.1145/316194.316229  !CS1 manut: Nomes múltiplos: lista de autores (link)
• Li, L., Alderson, D., Tanaka, R., Doyle, J.C., Willinger, W. (2005). «Towards a Theory of Scale-Free Graphs: Definition, Properties, and Implications (Extended Version)». arXiv:cond-mat/0501169 [cond-mat.dis-nn]  !CS1 manut: Nomes múltiplos: lista de autores (link)
• Kumar, R., Raghavan, P., Rajagopalan, S., Sivakumar, D., Tomkins, A., Upfal, E. (2000). «Stochastic models for the web graph» (PDF). Proceedings of the 41st Annual Symposium on Foundations of Computer Science (FOCS). Redondo Beach, CA: IEEE CS Press. pp. 57–65  !CS1 manut: Nomes múltiplos: lista de autores (link)
• Manev R., Manev H. (2005). «The meaning of mammalian adult neurogenesis and the function of newly added neurons: the "small-world" network». Med. Hypotheses. 64 (1): 114–7. PMID 15533625. doi:10.1016/j.mehy.2004.05.013 
• Matlis, Jan (4 de novembro de 2002). «Scale-Free Networks» 
• Newman, Mark E.J. (2003). «The structure and function of complex networks». arXiv:cond-mat/0303516 [cond-mat.stat-mech] 
• Pastor-Satorras, R., Vespignani, A. (2004). Evolution and Structure of the Internet: A Statistical Physics Approach. [S.l.]: Cambridge University Press. ISBN 0-521-82698-5  !CS1 manut: Nomes múltiplos: lista de autores (link)
• Pennock, D.M., Flake, G.W., Lawrence, S., Glover, E.J., Giles, C.L. (2002). «Winners don't take all: Characterizing the competition for links on the web». Proc. Natl. Acad. Sci. U.S.A. 99 (8): 5207–11. Bibcode:2002PNAS...99.5207P. PMC 122747. PMID 16578867. doi:10.1073/pnas.032085699  !CS1 manut: Nomes múltiplos: lista de autores (link)
• Robb, John. Scale-Free Networks and Terrorism, 2004.
• Keller, E.F. (2005). «Revisiting "scale-free" networks». BioEssays. 27 (10): 1060–8. PMID 16163729. doi:10.1002/bies.20294 ^[ligação inativa]
• Onody, R.N., de Castro, P.A. (2004). «Complex Network Study of Brazilian Soccer Player». Phys. Rev. E. 70. 037103 páginas. Bibcode:2004PhRvE..70c7103O. arXiv:cond-mat/0409609. doi:10.1103/PhysRevE.70.037103  !CS1 manut: Nomes múltiplos: lista de autores (link)
• Reuven Cohen, Shlomo Havlin (2003). «Scale-Free Networks are Ultrasmall». Phys. Rev. Lett. 90 (5). 058701 páginas. Bibcode:2003PhRvL..90e8701C. PMID 12633404. arXiv:cond-mat/0205476. doi:10.1103/PhysRevLett.90.058701 
• Carvalho, Rodolfo (24 de Fevereiro de 2013). [url=http://blog.rodolfocarvalho.net/2011/08/rede-livre-de-escala.html «Rede livre de escala»] Verifique valor |url= (ajuda). Blog  !CS1 manut: Falta pipe (link)