Mostrar código-fonte de Rede sem escala

{{Ciência da Rede}}
As '''redes livres de escala''' são [[Rede_complexa|redes complexas]] cujo grau de distribuição segue a [[lei de potência]], em que a maioria dos [[Vértice_(teoria_dos_grafos)|nodos(vértices)]] tem poucas ligações, contrastando com a existência de alguns [[Vértice_(teoria_dos_grafos)|nodos]] que apresentam um elevado número de ligações, ou seja um nodo com [[Grau_(teoria_dos_grafos)|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.<br>
Nestas redes a probabilidade de um nó ter k ligações decai quando k aumenta, segundo a [[lei de potência]].
{|
|-
|


 ||
:<math>
P(k) \ \sim \ k^\boldsymbol{-\gamma}
</math>
em que k>0 e <math>\gamma</math>>0. Sendo <math>\gamma</math> 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.<ref name="Clauset">{{citar periódico
| doi = 10.1137/070710111
|último = Clauset
|primeiro = Aaron
|coautor= Cosma Rohilla Shalizi, M. E. J Newman
|título= Power-law distributions in empirical data
|periódico= 0706.1062
|data= 2007-06-07
| arxiv = 0706.1062
|bibcode = 2009SIAMR..51..661C }}</ref>

==História==

O termo livre escala surgiu e através de um estudo<ref>{{Citar periódico|titulo = Scale-Free Networks|url = http://www.nature.com/doifinder/10.1038/scientificamerican0503-60|jornal = Scientific American|paginas = 60-69|volume = 288|numero = 5|doi = 10.1038/scientificamerican0503-60|primeiro = Albert-László|ultimo = Barabási|coautores = Eric}}</ref> liderado por [http://en.wikipedia.org/wiki/Albert-L%C3%A1szl%C3%B3_Barab%C3%A1si László Barabási] na '[[University of Notre Dame|Universidade de Notre Dame]] em [[1998]], onde ao mapear a World Wide Web<ref>{{citar periódico
 |último1 =Barabási |primeiro1 =Albert-László |authorlink1=Albert-László Barabási
 |último2 =Albert |primeiro2 =Réka.
 |título=Emergence of scaling in random networks
 |periódico=[[Science (journal)|Science]]
 |volume=286 |número=5439 |páginas=509–512 |data=15 de outubro de 1999
 |arxiv=cond-mat/9910332
 |doi=10.1126/science.286.5439.509
 |mr=2091634 |pmid=10521342
|bibcode = 1999Sci...286..509B }}</ref> 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 [http://en.wikipedia.org/wiki/Preferential_attachment 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.<ref>{{Citar periódico|titulo = Evolution of networks|url = http://dx.doi.org/10.1080/00018730110112519|jornal = Advances in Physics|data = 2002-06-01|issn = 0001-8732|paginas = 1079-1187|volume = 51|numero = 4|doi = 10.1080/00018730110112519|primeiro = S. N.|ultimo = Dorogovtsev|coautores = J. F. F.}}</ref>

== Características ==

[[Imagem:Scale-free network sample.svg|thumb|Exemplo de rede aleatória and a scale-free network|400px|right|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_a_falhas_(hardware)|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 [http://en.wikipedia.org/wiki/Connectedness 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  [http://en.wikipedia.org/wiki/Percolation_theory percolation theory] de Cohen et al.<ref>{{citar periódico|título=Resilience of the Internet to Random Breakdowns|periódico=Phys. Rev. Lett.|ano=2000|primeiro =Reoven|último =Cohen|coautor=K. Erez, D. ben-Avraham and [[Shlomo Havlin|S. Havlin]]|
volume=85|páginas=4626–8|
doi= 10.1103/PhysRevLett.85.4626|
url=http://link.aps.org/doi/10.1103/PhysRevLett.85.4626
|bibcode=2000PhRvL..85.4626C|arxiv = cond-mat/0007048 }}
</ref><ref>{{citar periódico|título=Breakdown of the Internet under Intentional Attack|periódico=Phys. Rev. Lett.|ano=2001|primeiro =Reoven|último =Cohen|coautor=K. Erez, D. ben-Avraham and [[Shlomo Havlin|S. Havlin]]|
volume=86|páginas=3682–5|
doi= 10.1103/PhysRevLett.86.3682|
url=http://link.aps.org/doi/10.1103/PhysRevLett.86.3682
|bibcode=2001PhRvL..86.3682C
                            |pmid=11328053|arxiv = cond-mat/0010251 }}
</ref> e por Callaway et al.<ref>{{citar periódico|título=Network Robustness and Fragility: Percolation on Random Graphs|periódico=Phys. Rev. Lett.|ano=2000|primeiro =Duncan S.|último =Callaway|coautor=M. E. J. Newman, S. H. Strogatz and D. J. Watts|
volume=85|páginas=5468–71|
doi= 10.1103/PhysRevLett.85.5468|
url=http://link.aps.org/doi/10.1103/PhysRevLett.85.5468
|bibcode=2000PhRvL..85.5468C|arxiv = cond-mat/0007300 }}</ref>

Outra das características de grande importância das redes livre de escala é designada de [http://en.wikipedia.org/wiki/Clustering_coefficient 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 [http://en.wikipedia.org/wiki/Small-world_phenomenon 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_de_rede|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 [http://en.wikipedia.org/wiki/Small_world_network 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.<ref name="Clauset"/> Alguns exemplos que usualmente são apresentados como redes livres de escala são:

*[[Rede_social|Redes Sociais]], onde se incluem as redes colaborativas. Um dos exemplos mais estudados é a [[Teoria_dos_seis_graus_de_separação|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 [[Www|World Wide Web]].
*Algumas redes financeiras como as redes interbancarias de pagamento <ref>{{citar periódico|título=The topology of interbank payment flows|periódico=Physica A: Statistical Mechanics and its Applications|ano=2007|primeiro =Kimmo|último =Soram&auml;ki|coautor=et. al|volume=379|número=1|páginas=317–333|doi= 10.1016/j.physa.2006.11.093|url=http://www.sciencedirect.com/science/article/pii/S0378437106013124|bibcode = 2007PhyA..379..317S }}</ref>
*[[Proteinas|Proteínas]]-Rede de interação das proteínas.
*Redes semânticas.<ref>{{citar periódico|título=The Large-Scale Structure of Semantic Networks: Statistical Analyses and a Model of Semantic Growth|periódico=Cognitive Science|ano=2005|primeiro =Mark|último =Steyvers|coautor=Joshua B. Tenenbaum|volume=29|número=1|páginas=41–78|doi= 10.1207/s15516709cog2901_3|url=http://www.leaonline.com/doi/abs/10.1207/s15516709cog2901_3}}</ref>
*Redes de estradas, rotas marítimas e rotas aéreas.

== Consultar ==

* [[Grafo_assimétrico#Grafos_aleat.C3.B3rios|Grafos aleatórios]]
* [[Redes_complexas| Redes Complexas]]

== Referências==
<div class='references-small'>
{{Reflist}}
</div>
*{{citar periódico|doi=10.1103/RevModPhys.74.47 |autor =Albert R., Barabási A.-L. |título=Statistical mechanics of complex networks |periódico=Rev. Mod. Phys. |volume=74 |páginas=47–97 |ano=2002 |url=http://www.nd.edu/~networks/Publication%20Categories/publications.htm#anchor-allpub0001 |bibcode=2002RvMP...74...47A|arxiv = cond-mat/0106096 }}
*{{citar periódico|doi=10.1073/pnas.200327197 |autor =Amaral, LAN, Scala, A., Barthelemy, M., Stanley, HE. |título=Classes of behavior of small-world networks |periódico=Proc. Natl. Acad. Sci. U.S.A. |volume=97 |número=21 |páginas=11149–52 |ano=2000 |pmid=11005838 |pmc=17168 |arxiv=cond-mat/0001458|bibcode = 2000PNAS...9711149A }}
*{{citar livro|autor =Barabási, Albert-László |título=Linked: How Everything is Connected to Everything Else |ano=2004 |isbn=0-452-28439-2 }}
*{{citar periódico|doi=10.1038/scientificamerican0503-60 |autor =Barabási, Albert-László |último2 =Bonabeau |primeiro2 =Eric |título=Scale-Free Networks |periódico=Scientific American |volume=288 |páginas=60–9 |data=maio de 2003 |url=http://www.nd.edu/~networks/Publication%20Categories/01%20Review%20Articles/ScaleFree_Scientific%20Ameri%20288,%2060-69%20(2003).pdf |formato=PDF |número=5}}
*{{citar periódico|doi=10.1103/PhysRevE.69.016113 |autor =Dan Braha, Yaneer Bar-Yam |título=Topology of Large-Scale Engineering Problem-Solving Networks |periódico=Phys. Rev. E |volume=69 |páginas=016113  |ano=2004 |url=http://necsi.edu/affiliates/braha/Topology--of--Large--Scale--Design--PRE69.pdf |formato=PDF|bibcode = 2004PhRvE..69a6113B }}
* Caldarelli G. "[http://www.oup.com/us/catalog/general/subject/Physics/Mathematicalphysics/~~/dmlldz11c2EmY2k9OTc4MDE5OTIxMTUxNw==  Scale-Free Networks"] [[Oxford University Press]], Oxford (2007).
*{{citar periódico|doi=10.1103/PhysRevLett.89.258702 |autor =Caldarelli G., Capocci A., De Los Rios P., Muñoz M.A. |título=Scale-free networks from varying vertex intrinsic fitness |periódico=Physical Review Letters |volume=89 |número=25 |páginas=258702  |ano=2002 |pmid=12484927 |arxiv=cond-mat/0207366 |bibcode=2002PhRvL..89y8702C}}
*{{citar periódico|título=Resilience of the Internet to Random Breakdowns|periódico=Phys. Rev. Lett.|ano=2000|autores=R. Cohen, K. Erez, D. ben-Avraham and [[Shlomo Havlin|S. Havlin]]|volume=85|páginas=4626–8|doi= 10.1103/PhysRevLett.85.4626|url=http://link.aps.org/doi/10.1103/PhysRevLett.85.4626|bibcode=2000PhRvL..85.4626C|arxiv = cond-mat/0007048 }}
*{{citar periódico|título=Breakdown of the Internet under Intentional Attack|periódico=Phys. Rev. Lett.|ano=2001|autores=R. Cohen, K. Erez, D. ben-Avraham and [[Shlomo Havlin|S. Havlin]]|volume=86|páginas=3682–5|doi= 10.1103/PhysRevLett.86.3682|url=http://link.aps.org/doi/10.1103/PhysRevLett.86.3682|bibcode=2001PhRvL..86.3682C|pmid=11328053|arxiv = cond-mat/0010251 }}
*{{citar periódico|título=Scale-free networks on lattices|periódico=Phys. Rev. Lett.|ano=2002|autores=A.F. Rozenfeld, R. Cohen, D. ben-Avraham, [[Shlomo Havlin|S. Havlin]]|volume=89|url=http://havlin.biu.ac.il/Publications.php?keyword=Scale-free+networks+on+lattices&year=*&match=all}}
*{{citar periódico|autor =Dangalchev, Ch. |título=Generation models for scale-free networks |periódico=Physica A |volume=338 |ano=2004 }}
*{{citar periódico|autor =Dorogovtsev,  Mendes, J.F.F. , Samukhin, A.N. |título=Structure of Growing Networks: Exact Solution of the Barabási—Albert's Model |periódico=Phys. Rev. Lett. |volume=85 |número=21 |páginas=4633–6 |ano=2000 |pmid=11082614 |doi=10.1103/PhysRevLett.85.4633 |bibcode=2000PhRvL..85.4633D|arxiv = cond-mat/0004434 }}
*{{citar livro|autor =Dorogovtsev, S.N., Mendes, J.F.F. |título=Evolution of Networks: from biological networks to the Internet and WWW |publicado=Oxford University Press |ano=2003 |isbn=0-19-851590-1 }}
*{{citar periódico|autor =Dorogovtsev, S.N., Goltsev A. V.,  Mendes, J.F.F. |título= Critical phenomena in complex networks |periódico= Rev. Mod. Phys. |volume=80 |páginas=1275 |ano=2008 | doi = 10.1103/RevModPhys.80.1275 |bibcode=2008RvMP...80.1275D|arxiv = 0705.0010 }}
*{{citar periódico|doi=10.1080/00018730110112519 |autor =Dorogovtsev, S.N., Mendes, J.F.F. |título=Evolution of networks |periódico=Advances in Physics |volume=51 |páginas=1079–1187 |ano=2002 |arxiv = cond-mat/0106144 |bibcode = 2002AdPhy..51.1079D }}
*{{citar livro|último1 =Erdős |primeiro1 =P. |authorlink1=Paul Erdős |último2 =Rényi |primeiro2 =A. |authorlink2=Alfréd Rényi |título=On the Evolution of Random Graphs |publicado=Publication of the Mathematical Institute of the Hungarian Academy of Science |ano=1960 |volume=5 |páginas=17–61 |url=http://www.math-inst.hu/~p_erdos/1960-10.pdf |formato=PDF}}
*{{citar periódico|doi=10.1145/316194.316229 |autor =Faloutsos, M., Faloutsos, P., Faloutsos, C. |título=On power-law relationships of the internet topology |periódico=Comp. Comm. Rev. |volume=29 |páginas=251 |ano=1999 }}
*{{citar arXiv|autor =Li, L., Alderson, D., Tanaka, R., Doyle, J.C., Willinger, W. |eprint=cond-mat/0501169 |título=Towards a Theory of Scale-Free Graphs: Definition, Properties, and Implications (Extended Version) |ano=2005 |class=cond-mat.dis-nn }}
*{{citar conferência|url=http://www.cs.brown.edu/research/webagent/focs-2000.pdf |título=Stochastic models for the web graph |autor =Kumar, R., Raghavan, P., Rajagopalan, S., Sivakumar, D., Tomkins, A., Upfal, E. |ano=2000 |publicado=IEEE CS Press |títulolivro=Proceedings of the 41st Annual Symposium on Foundations of Computer Science (FOCS) |páginas=57–65 |local=Redondo Beach, CA }}
*{{citar periódico|autor =Manev R., Manev H. |título=The meaning of mammalian adult neurogenesis and the function of newly added neurons: the "small-world" network |periódico=Med. Hypotheses |volume=64 |número=1 |páginas=114–7 |ano=2005 |pmid=15533625 |doi=10.1016/j.mehy.2004.05.013 |url=http://linkinghub.elsevier.com/retrieve/pii/S0306987704003524}}
*{{citar jornal|autor =Matlis, Jan |título=Scale-Free Networks |url=http://www.computerworld.com/networkingtopics/networking/story/0,10801,75539,00.html |data=4 de novembro de 2002 }}
*{{citar arXiv|autor =Newman, Mark E.J. |eprint=cond-mat/0303516 |título=The structure and function of complex networks |ano=2003 |class=cond-mat.stat-mech }}
*{{citar livro|autor =Pastor-Satorras, R., Vespignani, A. |título=Evolution and Structure of the Internet: A Statistical Physics Approach |publicado=Cambridge University Press |ano=2004 |isbn=0-521-82698-5 }}
*{{citar periódico|doi=10.1073/pnas.032085699 |autor =Pennock, D.M., Flake, G.W., Lawrence, S., Glover, E.J., Giles, C.L. |título=Winners don't take all: Characterizing the competition for links on the web |periódico=Proc. Natl. Acad. Sci. U.S.A. |volume=99 |número=8 |páginas=5207–11 |ano=2002 |url=http://www.modelingtheweb.com/ |pmid=16578867 |pmc=122747|bibcode = 2002PNAS...99.5207P }}
* Robb, John.  [http://globalguerrillas.typepad.com/globalguerrillas/2004/05/scalefree_terro.html Scale-Free Networks and Terrorism], 2004.
*{{citar periódico |doi=10.1002/bies.20294 |autor=Keller, E.F. |título=Revisiting "scale-free" networks |periódico=BioEssays |volume=27 |número=10 |páginas=1060–8 |ano=2005 |url=http://www3.interscience.wiley.com/cgi-bin/abstract/112092785/ABSTRACT |pmid=16163729 }}{{Ligação inativa|1=data=maio de 2019 }}
*{{citar periódico|doi=10.1103/PhysRevE.70.037103 |autor =Onody, R.N., de Castro, P.A. |título=Complex Network Study of Brazilian Soccer Player |periódico=Phys. Rev. E |volume=70 |páginas=037103 |ano=2004 |arxiv=cond-mat/0409609|bibcode = 2004PhRvE..70c7103O }}
*{{citar periódico|doi=10.1103/PhysRevLett.90.058701 |autor =Reuven Cohen, Shlomo Havlin |título=Scale-Free Networks are Ultrasmall |periódico=Phys. Rev. Lett. |volume=90 |número=5 |páginas=058701 |ano=2003 |url=http://havlin.biu.ac.il/Publications.php?keyword=Scale-Free+Networks+are+Ultrasmall&year=*&match=all|pmid=12633404 |arxiv=cond-mat/0205476 |bibcode=2003PhRvL..90e8701C}}
*{{citar periódico|autor =Carvalho, Rodolfo |título=Rede livre de escala |periódico=Blog|url=url=http://blog.rodolfocarvalho.net/2011/08/rede-livre-de-escala.html|data=24 de Fevereiro de 2013}}