Redes Complexas- Fenomenos Estatisticos - análise do artigo de Reka, Albert e Barabasi , Albert-Laszlo de 2002

Resumo expandido seletivo do artigo ( focando mais nos conceitos e menos nas leis e formulações matematicas apresentadas) por Ricardo Borges dos Santos RA 21.000.514 Statistical mechanics of complex networks Reka Albert* and Albert-Laszlo Barabasi Department of Physics, University of Notre Dame, Notre Dame, Indiana 46556 (Publicado em 30 January 2002) Redes complexas podem ser usadas para descrever uma ampla gama de sistemas observáveis na natureza e na sociedade. Exemplos frequentemente citados incluem: célula vivas, rede de elementos químicos vinculados por meio de reações químicas , e a Internet: rede de routers e computadores ligados por meios de transmissão de dados físicas . Embora estes sistemas tradicionalmente sejam modelados como grafos aleatórios , é cada vez mais reconhecido que a topologia e evolução das redes reais são regidos por princípios de organização bastante robustos. O artigo , datado de 2002 , analisa os avanços na área de redes complexas , com foco na topologia da rede e na dinâmica de crescimento com uma visão estatística. Depois de analisar os dados empíricos que motivaram o interesse recente em redes , os autores discutem os principais modelos e ferramentas analíticas , cobrindo grafos aleatórios , redes de pequeno mundo e redes sem escala, o artigo analisa e propõe princípios teoricos quanto as leis da evolução das redes , bem como a interação entre topologia e a robustez dos diferentes tipos de rede contra falhas e ataques . O artigo afirma que estruturas em rede de natureza complexa descrevem uma vasta variedade de sistemas de alta importancia tecnológico e intelectual. Afirma ainda que nos últimos anos do século XX , assistimos a importantes avanços na direção do estudo das redes como entidades complexas que , apesar de oriundas de universos de conhecimento distintos , tais como: social, biológico, físico, de comunicação de dados ou logístico, não podem ser tratadas apenas como unidades ou sistemas estanques.

Tais avanços foram motivados por diversos desenvolvimentos paralelos. Em primeiro lugar, a informatização da aquisição de dados em todos os campos levou ao surgimento de grandes bases de dados sobre a topologia de várias redes reais . Em segundo lugar , o aumento do poder de computação nos permitiu investigar redes que contêm milhões de nós , formulando-se perguntas que não poderiam ser abordadas antes, por falta do recurso computacional. Em terceiro lugar, a lenta porém contínua quebra de fronteiras entre as disciplinas. Pesquisadores ofereceram acesso às diversas bases de dados de origens distintas, permitindo-lhes descobrir as propriedades genéricas de redes complexas, através de analogias e semelhança de comportamento sistêmico. A necessidade de se enxergar além das abordagens reducionistas específicas dos especialistas em cada area e tentar compreender o comportamento do sistema como um todo, compreendendo a topologia das interações entre os componentes , ou seja , redes , é inevitável . Caracterizou a redes de mundos pequenos,

cujo conceito descreve

o fato de que na maioria das redes desta natureza

há um caminho

relativamente curto entre quaisquer dois nós. A distância entre dois nós é definido como o número de arestas ao longo do caminho mais curto que as conecta. A manifestação mais popular desta rede de mundo pequeno é o conceito de '' seis graus de separação '' , descoberto pelo cientista social Stanley Milgram (1967), que concluiu que havia um caminho de pessoas conhecidas com um comprimento típico de cerca de seis entre a maioria dos pares de pessoas escolhidos aleatóreamente nos Estados Unidos (Kochen,1989). A propriedade de mundo pequeno parece caracterizar muitas das redes complexas: os atores de Hollywood estão em média dentro de três co-estrelas um do outro, ou o produtos químicos de uma célula são tipicamente separados por três reações. Apesar do conceito do mundo pequeno ser intrigante, não é especificamente um princípio organizador de redes . De fato, como Erdos e Re'nyi demonstraram, a típica distância entre quaisquer dois nós em um

grafo aleatório tem dimensão proporcional ao logaritmo do número de nós. Assim, grafos aleatórios são rdes do tipo mundo pequeno também. A propriedade comum das redes sociais é a de formar panelinhas, ( Agrupamento preferencial ou “Clustering” ) representando círculos de amigos ou conhecidos em que cada membro esta conectado em maior ou menor grau a todos os outros membro. Esta tendência inerente de agrupamento em torno de núcleos ,ou clusters, ou panleinhas , é quantificado pelo coeficiente de agrupamento (Watts e Strogatz, 1998), um conceito que tem suas raízes na sociologia, aparecendo sob o nome '' fração de transitivo tríplice '' (Wassermann e Faust, 1994). Grau de Distribuição : Nem todos os nós em uma rede tem o mesmo número de extremidades (nó de mesmo grau). A variação e distribuição nos graus dos nó caracteriza-se por uma função de distribuição de probabilidade P (k), que dá a probabilidade de que um nó selecionado aleatoriamente tenha exatamente k arestas. Uma vez que num grafo aleatório as arestas são colocados de forma aleatória, a maioria dos seus nós têm aproximadamente o mesmo grau: próximo ao grau médio {k} da rede. O grau de distribuição de um gráfico aleatório é bem representado por uma distribuição de Poisson com um pico em P (k ). Na opinião dos autores , um dos desenvolvimentos mais interessantes das redes complexas foi a descoberta de que, para a maioria das grandes redes, o graus de distribuição desvia significativamente da distribuição de Poisson . Em particular, para um grande número de redes, incluindo a World Wide Web (Albert, Jeong, e Baraba'si, 1999), a Internet (Faloutsos et al., 1999), ou redes metabólicas (Jeong et al.) , mostram uma “ cauda “ do tipo lei de potencia. Na forma P(k) = a * k -gama onde

a

e gama são constantes, levando o gráfico a ter uma longa cauda

inclinada quando plotado em escala log-log.

Na sessão II , os autores trazem diversos exemplos de medições de diferentes ramos da ciência e mostram que várias áreas do conhecimento tem comportamento sistêmico de rede e sua topologia e dinâmica de crescimento bem como distância entre nós tendendo a seguir regras ou leis que se repetem , apesar dos dados dos exemplos terem sido coletados em areas muito distintas REDES LIVRES DE ESCALA - Os resultados empíricos apresentados na Sec. II demonstram que muitos grandes redes tem características de redes livre de escala livre, isto é, a seu grau de distribuição segue uma lei de potência para grandes k.

Mais ainda, mesmo para as redes na qual P (k) tem

uma cauda exponencial, o grau de distribuição desvia significativamente da distribuição de Poisson. A teoria de gráfos aleatórios e o modelo de mundo pequeno geralmente não reproduzem esta característica de cauda longa. Embora seja possível e relativamnete simples construir gráfos aleatórios que apresentem grau de distribuição próximo a lei de potência (conforme o artigo mostra na Sec. V), tal discussões apenas adiam uma questão mais importante: Qual é o principal mecanismo responsável pelo surgimento de redes de livre de escala ? A resposta a esta questão vai exigir uma mudança de foco : da topologia estática da rede para modelar a dinamica de criação e crescimento da rede e sua evolução. Os autores mostraram que há uma diferença fundamental entre a abordagem de modelagem usada em grafos aleatórios e os modelos de mundo pequeno, e o necessário para reproduzir o grau de distribuição das redes livres de escala e a sua caracteristica lei de potência . Embora o objetivo dos modelos anteriores é a construção de um gráfico com características topológicas corretos, a modelagem de redes de escala livre vai colocar a ênfase em captar a dinâmica da rede. Ou seja, o princípio fundamental nas redes livres de escala é a sua evolução ou a dinâmica do surgimento destas. Se capturarmos corretamente os processos que regem o nascimento e ocaso das redes livres de escala que vemos hoje, então vamos obter a sua topologia correta também.

O modelo Barabasi-Albert - A recorrência de uma correlação do tipo lei de potencia no grau de distribuição observado em redes foi abordada pela primeira vez por Barabasi e Albert (1999), que argumentou que a natureza livre de escala de redes reais está enraizada em dois mecanismos genéricos compartilhados por muitas redes reais. Os modelos de rede discutidos até então assumiam um número fixo N de vértices que seriam,

então, ligados ou

reconectados aleatoriamente, sem modificar N. Em contraste, a maioria das redes do mundo real

descrevem sistemas

abertos que crescem pela adição contínua de novos nós. A partir de um pequeno núcleo de nós originais , o número de nós aumenta ao longo do tempo de vida da rede por meio da adição subsequente de novos nós. Por exemplo, a World Wide Web cresce exponencialmente no tempo através da adição de novas páginas web. A literatura de pesquisa cresce constantemente pela publicação de novos documentos. Em segundo lugar, os modelos de rede discutidas até agora usavam a hipótese de que a probabilidade de que dois nós estejam ligados (ou tenham sido re-conectados ) é independente do grau dos nós, ou seja, as novas arestas são colocadas aleatoriamente. A maioria das redes reais, no entanto, apresentam ligações preferenciais, de tal modo que a probabilidade de ligação a um nó depende do grau do nó. Por exemplo, uma nova página web será mais provávelmente

ligada a documentos já populares com graus mais elevados,

uma vez que tais documentos altamente conectados, são fáceis de encontrar e, portanto, bem conhecido. Um novo artigo é mais propenso a citar artigos mais conhecidos e, portanto, muito citado do que publicações menos citados e, consequentemente, menos conhecidas. Estes dois ingredientes, de crescimento e de ligação preferencial, inspiraram a introdução do modelo Barabasi-Albert, o que levou pela primeira vez a uma disciplina de rede de grau de distribuição que segue uma lei de potência.

Conclusões As mudança observadas nos poucos anos do começo do seculo XXI , tiveram impacto significativo na compreensão das redes , trazendo alguns elementos inesperados. Através de estudos empíricos, modelos e abordagens analíticas , ficou claro que as redes reais não são redes aleatória, mas exibem caracteristicas de organização comuns apesar de ter origem bastante diferentes. Esses avanços criaram um ramo prolífico da estatística, seguido com igual interesse por sociólogos, biólogos, e cientistas da computação. O objetivo do artigo era resumir, de forma coerente, o que se sabe até 2003 . Os autores descobriram que alguns princípios topológicos são menos importantes e derivam de princípios dinâmicos, de velocidade de crescimento ou decaimento do número de nós e de ligações preferenciais que muitas vezes se verificam na dinamica da rede. No entanto, os autores acreditam que estes resultados são apenas a ponta do iceberg, as evidencias apontando que tais analises estavam apenas no seu início.

> Referencias http://www.barabasilab.com/pubs/CCNR-ALB_Publications/200201-30_RevMode rnPhys-StatisticalMech/200201-30_RevModernPhys-StatisticalMech.pdf