UNIVERSIDADE FEDERAL DO PIAUÍ
Centro de Ciências da Natureza
Departamento de Fı́sica
Modelagem de Redes Complexas
Gildário Dias Lima
2008
Dissertação submetida ao Corpo Docente do Departamento de Fı́sica da Universidade
Federal do Piauı́, como parte dos requisitos necessários para a obtenção do grau de
graduado em fı́sica.
Área de concentração : Fı́sica da Matéria Condensada
Avaliada por:
José Pimentel de Lima, Professor - DF/UFPI
(Orientador)
Paulo Henrique Barbosa Filho, Professor - DF/UFPI
(Co-orientador)
Francisco Ferreira Barbosa Filho, Professor - DF/UFPI
Marcondes Rodrigues Clarck, - Professor - DM/UFPI
Resumo
Atualmente os modelos mais discutidos acerca do estudo das redes complexas são:
o modelo de Barabási[4] (Escala Livre) e o modelo de e Watts e Strogatz[3] (pequeno
mundo). Destes eles, o modelo proposto por Barabási, mais abrangente, aborda questões
considerando uma nova análise que liberta as redes dos padrões regulares. Outro fator
importante do modelo, foi o fato de sua rede de escala livre, assim definida, ser uma
estrutura natural para diversos tipos de fenômenos. Apesar desses modelos terem criado
um ambiente importante para as redes complexas, existem muitas particularidades em
que os mesmos não são capazes de absorver. Uma das lacunas são as redes sociais na
Internet. Esse trabalho inicia uma análise sobre esses modelos, apresentando uma outra
abordagem capaz de contemplar a interação entre eles. Inicialmente foi apresentada uma
proposta para o tratamento geométrico dessas redes, o que facilita todo o desenvolvimento
dos estudos desses modelos e a partir dessa nova abordagem, ao tempo em que damos
continuidade, abordaremos as redes complexas agregando mais valores às informações
que estas podem conter, associando um novo papel as mesmas , semelhante ao papel da
hamiltoniana num sistema fı́sico. Aplicaremos este desenvolvimento a uma rede social
na Internet, o Orkut, que servirá como fonte de dados para contraposições dos dados.
Considerando a rede Orkut um ponto singular aos modelos, escala livre e pequeno mundo
([7]), partimos desse fato, para desenvolvermos a compreensão desse sistema.
Capı́tulo 1
Introdução
Com o avanço da informática e técnicas de simulação computacional, nas últimas
décadas o estudo de redes complexas se tornou mais evidente na comunidade cientı́fica.
Diversas estruturas organizam-se em padrões descritos por essas redes que estão presentes em nosso cotidiano, tais como: redes de distribuição elétrica, redes rodoviárias,
redes de computadores, redes sociais, redes de neurônios, etc. Inicialmente, várias tentativas de modelar fenômenos descritos por estas redes tiveram suas maiores contribuições
na matemática, entre elas destacam-se os trabalhos pioneiros do matemático Euller, que
investiu tempo para a solução do enigma das pontes para acesso à cidade prussiana de
Königsberg por volta do século XVII. O Problema consistia em atravessar todas as sete
pontes que ligavam à cidade utilizando um teorema que tratava as pontes como arestas e
os lugares que deveriam ser conectados como nós, o que ficou conhecido como teoria dos
grafos. Um grafo é uma representação de um conjunto de nós conectados por arestas a
qual a essa estrutura podemos chamar de rede.
Partindo desta primeira consideração criada por Euller, estudos consecutivos mostraram
interesse em aprofundar estas idéias. Estes estudos avançaram ainda mais com o advento
7
CAPÍTULO 1. INTRODUÇÃO
8
da informática, que tornou prático o uso da simulação para análise dos parâmetros e
aplicações sobre as redes complexas. Uma das primeiras abordagens estruturais do estudo das redes, considera a sua formação a partir de um aspecto de evolução de forma
aleatória. Este aspecto foi introduzido na literatura pelos estudos de Erdös e Rényi [1]
[2] em meados de 1960. O Modelo proposto na época consistia de nós interconectados
entre si através de uma probabilidade ρ.
Considerando esta maneira de evolução, geramos o que é conhecido como uma rede
aleatória que segue uma distribuição do tipo Poisson, onde os sı́tios tendem a si conectar
por um número igualitário de vizinhos, havendo raramente sı́tios com muitas conexões e
sı́tios com poucas conexões. As redes que apresentam este tipo de distribuição também
são denominada de redes de pequeno mundo. Estas redes de mundo pequeno tornaram-se
importante pelos resultados obtidos na prática, onde algumas estruturas respondem bem
a esta modelagem, dentre elas as redes sociais.
A partir do experimento de Milgram[4], que conduziu um experimento seminal para
testar a hipótese de que membros de uma grande rede social, no caso a população dos
Estados Unidos, estariam ligados entre si por uma pequena cadeia de conhecimentos intermediários. Milgram enviou mensagens para algumas centenas de indivı́duos selecionados
aleatoriamente para que encaminhassem a mesma mensagem para alguém próximo, com
o objetivo de alcançar um indivı́duo alvo em uma região geográfica distante. O resultado
médio de seis indivı́duos, incluindo ele, necessários para fechar uma cadeia entre ele e
o indivı́duo destino, se transformou em um dogma sociológico e uma verdade popular.
Duncam Watts e seu orientador, Steven Strogatz [3] 1999 e 2003, junto as teorias de Granovetter [8] descobriram que as redes sociais apresentavam padrões tendendo a formar
CAPÍTULO 1. INTRODUÇÃO
9
pequenas quantidades de conexões entre cada indivı́duo. Eles criaram um modelo semelhante ao de Erdös e Rényi [1] [2], considerando o estabelecimento de laços através de
uma probabilidade ρ. O primeiro problema da teoria dos mundos pequenos de Watts, foi
demonstrado por Barabási [4] 2003, pouco tempo após a publicação do trabalho. Watts,
tratava as redes sociais como redes aleatórias, ou seja, redes em que as conexões entre os
nós eram estabelecidas de modo randômico, exatamente como Erdös e Rényi, anos antes.
Entretanto, Barabási [4] (2003) demonstrou que as redes não eram formadas de modo
aleatório. Ele acreditava que, como os estudos de Watts e Strogatz [3], bem como de
Granovetter[8] tinham apontado, existia uma ordem na dinâmica de estruturação das
redes e algumas leis bem especı́ficas. Essa lei, ou padrão de estruturação, foi chamada
por Barabási de ”ricos ficam mais ricos”(rich get richer). Ou seja, quanto mais conexões
um nó possui, maiores as chances de ele ter mais novas conexões. Ele chamou essa caracterı́stica de ”conexão preferencial” (preferential attachment): um novo nó tende a se
conectar com um nó preexistente, porém mais conectado. Essa assertiva implica em outra
premissa fundamental: as redes não seriam constituı́das de nós igualitários, ou seja, com
a possibilidade de ter mais ou menos o mesmo número de conexões. Ao contrário, tais
redes possuiriam poucos nós que seriam altamente conectados (hubs ou conectores) e uma
grande maioria de nós com poucas conexões. Os hubs seriam os ”ricos”, que tenderiam
a receber sempre mais conexões. As redes com essas caracterı́sticas foram denominadas
por ele ”sem escalas” (scale free). Scharnhorst [6] 2003, discute a existência de uma
relação entre os modelos de redes sem escala e de mundos pequenos. De acordo com ela,
”algumas vezes, as duas caracterı́sticas podem ser atribuı́das às redes. Outras vezes, a
diferença radical desses dois tipos de rede é destacada”, isto implica naturalmente que
o modelo de Barabási não representa uma generalização. Este fato se torna notável em
alguns casos, dentre eles as redes sociais na Internet, que fogem ao padrão de estru-
CAPÍTULO 1. INTRODUÇÃO
10
tura absoluta de ambos os casos: mundo pequeno e scala free. O modelo de Barabási e
Albert[4], por exemplo, tem um grau de conectividade muito baixo, já que apenas alguns
nós estão altamente conectados, a maioria tem poucos links. Além disso, uma rede sem
escalas não é, necessariamente, um mundo pequeno. Já o modelo de Watts e Strogatz,
têm um grau de conectividade parecido com o de um grafo aleatório (Erdös e Rényi),
mas, tem um alto grau de conexão entre os nós.
Scharnhorst [6] explica ainda que é preciso que se atente para o fato de que os modelos
foram criados sob a forma teórica, em testes realizados em computadores. No mundo real,
as redes costumam exibir um grau de distribuição (conectividade) variado, que não necessariamente funcionam num modelo ou outro. Dependendo da definição teórica escolhida,
as propriedades dos dois tipos de rede podem ser encontradas nas redes no mundo real. O
objetivo do trabalho de Raquel da Cunha Recuero [7] 2006, foi mostrar a relação desses
dois modelos para o caso das redes sociais na Internet. Esses modelos seriam suficientes
para dar conta do estudo das redes sociais constituı́das via comunicação mediada por
computador? Os estudos de Barabási não trabalham especificamente com redes sociais,
embora ele explicite que seu modelo é aplicável a todos os tipos de rede. Já o modelo de
Watts e Strogatz é direcionado para redes sociais. No entanto, será que esses modelos
dão conta deste fenômeno na Internet? As conclusões, considerando as redes sociais na
Internet , Orkut, webblog e fotologs, apontam que:
Como se procurou demonstrar, os modelos de análise das redes propostos por Erdös e
Rényi, Watts e Strogatz e Barabási são insuficientes no sentido de perceber as complexidades de uma rede social na Internet. Isso porque esses modelos, apesar de afirmarem sua
aplicabilidade para as redes sociais, falham ao levar em conta as premissas mais básicas
CAPÍTULO 1. INTRODUÇÃO
11
da análise social.1 O modelo de Erdös e Rényi, que apresenta uma rede aleatória, tem
méritos de ter sido o primeiro a olhar para as redes sociais e sua dinâmica no tempo.
Entretanto, as relações entre os indivı́duos na comunicaçào mediada por computador não
são aleatórias. As pessoas levam em conta diversos fatores ao escolher conectar-se ou não
a alguém. Os laços sociais, portanto, são estabelecidos sob prismas muito especı́ficos de
interesses comuns de cada nó.
O modelo de Watts e Strogatz, apesar de apresentar uma construção importante, atentando para a clusterização e o valor das pequenas conexões entre grupos para gerar mundos pequenos, não observa pontos fundamentais tais como: a motivação dessas conexões,
que nem sempre são feitas de modo aleatório e podem abarcar visibilidade: no caso dos
weblogs e fotologs (Primo e Recuero, 2003 e 2004), interesses em comum, no sentido
de formar comunidades ou estabelecer relações sociais; interesses sexuais ou mesmo de
sedução e etc; o teor das interações e laços sociais estabelecidos entre os nós e sua influência na rede. O modelo de Barabási, o mais mecanicista, traz um importante insight
no sentido de prever o mecanismo de construção das redes, o de ”ricos mais ricos” e a
presença de conectores. Entretanto, o modelo falha em pontos cruciais para o estudo
das redes sociais geradas via comunicação mediada por computador. Ele não leva em
conta, por exemplo, o custo de manutenção dos laços sociais. Hubs simplesmente acumulam laços, como se a relação entre as pessoas pudesse ser meramente reduzida à uma
adição de amigos, sem qualquer custo envolvido. Conseqüentemente, não leva em conta
também o contexto social e o capital social envolvido em cada interação. Além disso, o
mecanismo de ”ricos mais ricos” falha na formação de grupos sociais na Internet, pois
as pessoas procuram conectar-se a outras por motivos especı́ficos e não simplesmente
1
Raquel da Cunha Runqueiro - TEORIA DAS REDES E REDES SOCIAIS NA INTERNET
CAPÍTULO 1. INTRODUÇÃO
12
porque possuem mais conexões. Algumas vezes, o mecanismo parece funcionar no sentido de ”fama” de alguns weblogs e fotologs, mas não necessariamente de número de
conexões. Todos os modelos, portanto, apresentam falhas na aplicação às redes sociais
na Internet, em grande parte, devido à sua natureza matemática e pouco investigativa
do teor das conexões. Para que seja possı́vel fazer uma análise do Orkut, por exemplo,
é preciso diferenciar o sistema, o software e as redes sociais que ele pode representar. O
sistema pode representar redes sociais que são estabelecidas e mantidas através de outros
sistemas de comunicação mediada por computador que não o próprio Orkut. Assim como
ele, weblogs e fotologs também demonstram algumas falhas dos modelos, notadamente,
a falta de investigação do teor, direcionamento e força das interações sociais.
Deste modo, levando-se em conta apenas os modelos para realizar a análise de redes sociais, pode-se chegar a atitudes determinı́sticas onde se assume que as relações mostradas
pelos sistemas constituem-se em laços sociais. Alguns dos resultados obtidos neste trabalho apontam para um consenso nas conclusões feitas por Raquel [7] e outros, onde
demonstraremos de forma mais precisa onde essas particularidades se formam e que
parâmetros as determinam, mostrando uma nova interpretação para o que hoje é chamado
de probabilidade de Barabási.
Capı́tulo 2
Redes Complexas
2.1
Grafos
Com o propósito de fixar notação e terminologia apresentadas neste trabalho, introduziremos a as noções necessárias para compreensão do mesmo, embora resumidas,
usaremos as definições apresentadas por Rodriguez. N. R. [22].
Um grafo é um par G = (V, E), onde V é o conjunto de vértices e E ⊂ {{u, v} : u, v ∈
V e u �= v} é o conjunto de ligaçoes de G. Consideraremos grafos que não possuem
ligações dirigidas 1 , auto-ligações
2
e nem ligações duplas 3 . Dizemos que o grafo G é
infinito se os conjuntos G e E são infinitamente enumeráveis. Se {u, v} ∈ E dizemos que
u e v são vizinhos, e representaremos u ↔ v. Chamaremos o grau de um vértice v, e
denotaremos ξv , ao número de seus vizinhos.
Um caminho χu,v em um grafo é a sequência de vértices distintos que liga u a v, onde
cada par sucessivo deles é um elo ”ligação” no grafo. Chamaremos tamanho do caminho
χu,v o número de elos deste caminho. Definimos a distância entre dois vértices u e v
Um dado vértice u ligado a um vétice v,não têm mesmo efeito de vligado a u
Um dado vétice têm arestas em si mesmo
3
Ligações duplicadas
1
2
13
CAPÍTULO 2. REDES COMPLEXAS
14
como
du,v = min(χu,v )
(2.1)
onde du,v é a geodésia.
Para as redes, o caminho médio entre dois vértices é dado pela soma da geodésica de
todos os pares de vértices e é definido como distância geodésica média, dada por:
l=
1
1
N (N
2
I=
− 1)
�
di,j
(2.2)
i�=j
∂f (x)
∂x
(2.3)
Quando um conjunto de vértices é ligado através de um certo número de ligações, e
não levando em consideração outro tipo de aspecto, estamos perante o exemplo mais
simples de uma rede (figura 2.1).
Figure 2.1: Modelo de Rede
No entanto, estas podem ser mais complicadas. Pode, por exemplo, haver mais do
que um tipo de vértice na rede, ou mais do que um tipo de ligações podendo apresentar
uma não constância em sua escala. Numa rede econômica, por exemplo, os vértices
podem representar empresas ou bancos, etc., o mesmo se passando com as ligações, que
CAPÍTULO 2. REDES COMPLEXAS
15
podem ser de diferentes tipos (banco-banco, banco-empresa), ou mesmo terem diferentes
intensidades, correspondendo estas, por exemplo, ao volume de negócio entre os vértices.
Podem ser dirigidas, ou não, consoante a troca que se faz num ou em ambos os sentidos.
Por exemplo, a WWW é uma rede dirigida, enquanto a Internet não o é. Como pode, por
exemplo, a estrutura da rede afetar o tráfego na Internet, ou o desempenho de um motor
de busca, ou a dinâmica de sistemas sociais ou biológicos? Ou podemos nós, através do
conhecimento da rede social correspondente a uma dada sociedade, por exemplo, auxiliar
a prevenção da propagação de uma epidemia, ou de um vı́rus informático na Internet?
Respostas a estas, e a muitas outras perguntas, têm sido procuradas por uma grande
comunidade de cientistas em variadas áreas. No entanto, a compreensão destes sistemas
complexos (redes) permanece ainda muito simplificada. (MENDES, J.F [9])
2.2
Redes Aleatórias
Erdös-Réyl [1] [2] propuseram um modelo para a rede aleatória que segue uma idéia
bem simples. Suponha um conjunto de n vértices onde cada vértice está conectado a outro
com uma dada probabilidade p. Isso define o que Erdös e Rényl chamaram de ensemble,
onde o grafo G para esse ensemble com m arestas possui probabilidade pm (n − 1)M −m
onde M é o número máximo de arestas possı́vel dado por M = 12 n(n − 1).
Em analogia é comum nos referirmos a essas redes, como redes em equilı́brio, a distribuição de graus é independente do tempo. Pela construção do grafo G , um dado
vértice i possui k arestas com probabilidade pk , e não está conectado com N − 1 − k
vértices com probabilidade (1 − p)N −1−k . Mas existem CNk −1 maneiras de combinar essas
conexões. Dessa forma a probabilidade de que o i-ésimo vértice possua k arestas é:
P (ξi = k) = CNk −1 pk (1 − p)N −1−k
(2.4)
CAPÍTULO 2. REDES COMPLEXAS
16
onde ξi é o número de arestas do i-ésimo vértice.
No limite N → ∞,
P (ξi = k) = CNk −1 pk (1 − p)N −1−k � e−pN
(pN )k
k!
(2.5)
No entanto, o número médio de arestas é dado por �k� = pN ou ξ¯ = pN , o que torna,
P (ξi = k) = e−ξ̄
¯k
(ξ)
k!
que é a distribuição de Poisson.
Figure 2.2: Distribuição de Poisson a partir de 2.6
(2.6)
CAPÍTULO 2. REDES COMPLEXAS
17
Para um simulação do modelo proposto por Erdös e Rényl obtivemos o gráfico:
Figure 2.3: Simulação obtida para uma rede de 5000 vértices e número médio de arestas
ξ¯ = 4
A curva que corta os pontos é o fit da função de Poisson 2.6.
2.3
Rede de Pequeno Mundo
Em 1998, Wattse-Strogatz[3] propuseram um modelo que apresenta apenas um parâmetro
de controle, ”p”, que é a probabilidade de que uma aresta u ↔ v seja reconectada u ↔ s
onde s é um vertice escolhido aleatoriamente. O algoritimo por traz do modelo é descrito
em duas etapas:
1. É construı́da uma rede unidimensional com condições de contorno de anel (rede
fechada) onde cada vértice está conectado a outros k vértices.
2. Cada vértice terá suas arestas religadas a outros vértices aleatoriamente com probabilidade p. Não é permitido auto-conexão (u ↔ u) nem conexões duplas (u ↔ v :
v ↔ u).
CAPÍTULO 2. REDES COMPLEXAS
18
Então a rede é varrida até completar um passo (uma volta). Para diferentes valores de
p ∈ [0, 1], pode-se contemplar a transição entre as ordens (p = 0) e (p = 1).
Esse modelo advém de uma abordagem de laços sociais.
Figure 2.4: Modelo de Watts-Strogatz numa rede quadrada [15]
A solução exata para o caminho geodésico médio ainda é um problema em aberto.
Barthélémy e Amaral, propuseram uma conjectura onde l ( caminho geodésico médio)
possua lei de escala. Recentemente, vários autores, por meio de argumentos analı́ticos e
simulações numéricas chegaram a uma nova lei de escala que hoje é amplamente aceita,
l∼
N 1/d
f (pKN )
K
onde f (u) obedece aos seguintes valores assintóticos


 const de u ≤ 1
f (u) =

 ln(u) se u ≥ 1
u
(2.7)
(2.8)
Existe na literatura um esforço para o cálculo de l de forma exata, mas isso ainda não
foi totalmente realizado. Albert e Barabási [4] em seu artigo de revisão mostram, que
dada certas circunstâncias, o cálculo de l pode ser feito exatamente. Além do pequeno
caminho médio já previsto pelo sociólogo Milgram [21] na década de 60, a rede de mundo
pequeno apresenta grande coeficiênte de aglomeração.
CAPÍTULO 2. REDES COMPLEXAS
2.4
19
Rede sem Escala
Muitas das redes reais diferem das redes aleatórias, pois apresentam uma distribuição
de graus de conectividade que segue a lei de potência equação (2.9). Como as leis de
potência são livres de qualquer escala caracterı́stica, estas redes são chamadas de redes
livres de escala, redes de escala livre ou redes sem escala [11]. Redes sem escala, são
um tipo de rede complexa que atraiu a atenção dos pesquisadores porque várias redes
reais caem nesta categoria. Diferentemente das redes aleatórias onde a distribuições de
conectividade segue a distribuição de Poisson, as de redes livres de escala, alguns poucos
elementos são muito conectados enquanto a maioria dos demais possuem baixo ı́ndice
de conectividade. Este tipo de rede é independente do número N de elementos. Sua
principal caracterı́stica, que a diferencia da rede aleatória, é a probabilidade de conexão
que é dada por [4] e citeSFFF12:
P (k) ∼ k −λ
(2.9)
onde k é o coeficiente de conectividade ou número de conexões e o expoente varia aproximadamente entre 2 e 3 para a maioria das redes reais [4].
Uma rede livre de escala pode ser construı́da adicionando-se elementos progressivamente à rede existente através de conexões com os elementos já participantes da rede
seguindo o princı́pio de conexão preferencial com a probabilidade sendo dada por
P (ki ) =
ki
N
�
(2.10)
j=1
onde ki é o número de conexões do iésimo elemento ou nó e N é o número total destes
elementos [5].
CAPÍTULO 2. REDES COMPLEXAS
20
Na natureza, estes dois principais tipos de redes (evolução aleatória e escala livre,
respectivamente, modelo de pequeno mudo e modelo de Baraási-Albert)de conexões existem, assim como existem também aquelas que são uma mistura delas. As redes aleatórias
são mais simples e foram primeiramente bem estudadas. As redes sem escala tiveram
sua natureza e propriedades conhecidas mais recentemente, principalmente nas últimas
duas décadas (extensa documentação no recente livro de Newman et al. [12]).
2.5
Modelos de Crescimento Organizado de Redes
Complexas
A Internet é baseada nas interconexões de Sistemas Autônomos que apresentam uma
aparente natureza aleatória. Porém, na realidade, são descritas por uma lei de potência,
sendo por isto considerada uma rede de topologia do tipo sem escala (scale-free network). Muitos modelos foram desenvolvidos e testados em redes de diversos tipos. De
maneira resumida podemos dividir os modelos em dois tipos: os básicos e os especı́ficos.
Os modelos básicos são aqueles utilizados para o desenvolvimento e testes de teorias e
conceitos necessários para o desenvolvimento dos modelos especı́ficos que incluem ingredientes dinâmicos existentes nas redes a que serão submetidos e avaliados. Neste capı́tulo,
são apresentados os principais modelos que caracterizam as redes livres de escala que
serviram de base para o desenvolvimento de um modelo mais abrangente e especı́fico
para Internet. Os modelos base são os modelos Barabási-Albert e a sua extensão, o
modelo Dorogovtsev-Mendes e o modelo Zhou-Mondragón. Estes modelos serviram para
o desenvolvimento de um modelo especı́fico, original e aplicado aos dados experimentais
considerados neste trabalho.
CAPÍTULO 2. REDES COMPLEXAS
2.6
21
O Modelo de Barabási-Albert
Baseado nos dois princı́pios fundamentais: crescimento contı́nuo e conexão preferencial, Barabási e Albert[4] propuseram o seguinte modelo:
• Crescimento contı́nuo: o modelo começa com um pequeno número de nós sem
conexões n0 e a cada instante é adicionado um novo nó que faz m novas conexões
a diferentes nós já presentes na rede.
• Conexão preferencial: as conexões iniciadas pelo novo nó são realizadas de acordo
com a probabilidade dada pela equação
P(ki ) =
Ki
,
N
�
kj
(2.11)
j=1
onde P(ki ) e ki são a probabilidade e o grau de conectividade do iésimo nó, respectivamente, e N é o número de nós a qualquer instante da evolução da rede.
Neste modelo, a rede resultante a cada instante terá N nós e mt conexões depois de
t passos, onde N = t + n0 . Através de simulações numéricas, é possı́vel demonstrar que
a rede resultante segue uma lei de potência cujo expoente é aproximadamente igual a 3,
independentemente do valor de m.
2.7
Modelo Barabási-Albert Estendido
Barabási e Albert observaram que algumas outras caracterı́sticas deveriam ser acrescentadas ao seu modelo básico principalmente porque em algumas redes de conexões,
o valor experimental do expoente diferia daquele obtido em sua primeira aproximação.
A primeira mudança no modelo básico está no conceito de atração inicial, que é uma
CAPÍTULO 2. REDES COMPLEXAS
22
necessidade diante dos demais mecanismos acrescentados ao modelo, novas conexões e
rearranjo. De acordo com a equação 2.11, se um nó tiver zero ligações, então a probabilidade deste nó receber uma nova ligação também será zero, e isto na maioria das
redes reais não é a realidade, pois sempre existe alguma possibilidade de, por exemplo,
na rede de citações, um artigo que ainda não foi publicado, receber citações. Para solucionar esta questão pode-se adicionar uma constante A, usualmente A = 1, garantindo a
possibilidade do nó i ter chance de receber novas ligações e assim a equação 2.11 fica:
Ki + A
P(ki ) = �
kj + A
(2.12)
j
Esta equação permite que o modelo considere a atração inicial que é intrı́nseca a
cada elemento da rede independente de estar já conectado ou ainda isolado. Uma outra
questão é que em muitas redes reais o expoente é diferente de 3, que é o valor esperado no
modelo original, sugerindo a existência de mecanismos não considerados até então. Esses
mecanismos são os chamados eventos locais, tais como: adição ou remoção de conexões
entre os nós já existentes, exclusão de nós e rearranjo de conexões.
De maneira resumida, o modelo Barabási-Albert estendido inclui os mecanismos
intrı́nseco de atração inicial e probabilı́sticos de novas conexões e de rearranjos entre
nós já existentes. A distribuição de probabilidades de conexão é descrita por uma lei de
potência dada pela equação
P (k) ∝ [k + A(p, q, m)+]−γ
2.8
(2.13)
Modelo de Dorogovtsev-Mendes
Partindo do modelo básico Barabási-Albert, Dorogovtsev e Mendes propuseram dois
novos mecanismos de crescimento:
CAPÍTULO 2. REDES COMPLEXAS
23
• Desenvolvimento de redes
• Estrutura de descaimento.
O mecanismo ”desenvolvimento de redes” considera a possibilidade do surgimento de
novas conexões entre os nós já existentes. O mecanismo ”estrutura de decaimento” , ao
contrário, admite a exclusão de conexões entre os nós já existentes. Estes mecanismos
levam à seguinte expressão para o expoente:
γ =2+
1
1 + 2c
(2.14)
onde C é o número de conexões incluı́das (> 0) ou removidas (< 0). Quando C = 0
obtemos o valor esperado do modelo original de Barabási-Albert. Em sua forma original
o modelo Dorogovtsev-Mendes considera um ou outro mecanismo.
2.9
Modelo Zhou-Mondragón
Os modelos apresentados nas seções anteriores, o modelo Barabási-Albert, sua extensão e o modelo Dorogovtsev-Mendes, são modelos gerais utilizados no desenvolvimento
de teorias e modelagem de redes complexas de uma maneira geral. São muito úteis no
entendimento dos mecanismos existentes nos estudos relacionados com o crescimento das
redes complexas em geral. Certamente servem de base para o desenvolvimento de modelos mais realistas e aplicáveis a redes complexas especı́ficas. Para a rede de conexões da
Internet, Zhou e Mondragón introduziram o conceito de conexão preferencial não-linear
onde a probabilidade de conexão agora apresenta um expoente que tem a principal caracterı́stica de amplificar o efeito de conectividade preferencial. A probabilidade de conexão
de cada nó agora é dada por:
CAPÍTULO 2. REDES COMPLEXAS
24
�
kα
(ki ) = �i
kjα
(2.15)
j
O que está por trás desta probabilidade, passaremos a chamar probabilidade alfa ou
probabilidade não-linear e é a possibilidade de aumentar a importância de grandes hubs
para a rede toda. Além deste tipo não-linear de probabilidade, este modelo considera
também a possibilidade do surgimento de novas conexões entre nós já existentes. O
modelo Zhou-Mondragón, apesar de considerar a rede de conexões entre ASs, não foi
submetido a dados retirados da tabela full routing BGP. Os autores utilizaram dados
obtidos através da utilização da ferramenta computacional traceroute. Esta ferramenta
basicamente é um programa que determina a rota por onde passam os pacotes de informação em uma rede de computadores.
Capı́tulo 3
Modelo de Cargas
O primeiro experimento quantitativo bem-sucedido para estudar a força entre cargas
elétricas foi feito por Charles Augustin de Coulomb , que mediu atrações e repulsões
elétricas e deduziu a lei que as governa. Experiências realizadas por Coulomb e seus
contemporâneos, mostraram que a força elétrica aplicada por um corpo carregado em
outro depende diretamente do produto das intensidades das duas cargas e inversamente
do quadrado de suas distancias. Isto é,
F ∼
q 1 q2
r2
(3.1)
Onde F é intensidade da força mútua que age em cada uma das cargas q1 e q2 , e r é a
distância entre seus centros.
Suponha agora uma quantidade de cargas N , distribuı́das numa região do espaço.
Consideraremos em nossa distribuição, que as cargas se manterão fixas em sua posição
após colocadas lá, se necessário, por um fator externo. As cagas, terão valores diferentes,
ou seja, q1 , q2 , q3 , ...qN com 0 < qk < qmax , onde k representa a k-ésima carga em sua
k-ésima posição. Naturalmente, também serão considerados várias distâncias r entre as
diversas cargas. Nosso propósito é construir a partir desta distribuição, uma rede espec25
CAPÍTULO 3. MODELO DE CARGAS
tral
1
26
que não guarde somente informações geométricas (localização) das cargas, mas,
informações sobre a influência de uma sobre a outra, ou seja, uma rede que nos descreva
a forma com que cada carga (sı́tio da rede) interage com as demais. Nosso parâmetro de
interação será a própria lei de Cuolomb, Eq 3.1 , para este exemplo. Considerando dois
sı́tios i e j (cada um com sua correspondente carga). Os sı́tios se ligam uns aos outros
mediante a força de interação entre eles. Considerando que todos os sı́tios da distribuição
proposta se influenciam mutuamente, podemos considerar o princı́pio da super posição
que por conseqüência teremos uma rede em que todos os sı́tios estão conectados entre-si.
O que difere de uma ligação para a outra, é apenas a intensidade da interação.
Figure 3.1: Representação de uma rede espectral de uma distribuição de 5 cargas numa
região do espaço, considerando como condição de ligação lei de Comlomb
Cada vértice representa a presença de uma carga, a condição para que os vértices
se liguem é: Dois vértices i e j, ligam-se quando Fi,j > 0, como dito acima, devido à
interação da força elétrica se estender ao infinito, por esta condição, todos os vértices se
conectaram, de forma que o número de ligações total da rede é
Nl = C2N .
1
Para este contxto, uma rede espectral é um arranjo (grafo) que contêm informações acerca das
interação do evento em questão
CAPÍTULO 3. MODELO DE CARGAS
27
Considerando que a lei da força elétrica é descrita para o espaço das configurações,a
Figura 3.1 representa a configuração e acessibilidade das cargas. No espaço euclidiano,
inicialmente sempre é possı́vel sair de um ponto e chegar a outro, nesta situação, a
geodésica representa uma linha reta (menor distância entre dois pontos no espaço euclidiano). Suponha agora, que mudemos a condição de ligação, existe agora uma força
F0 que representará um parâmetro de corte, ou seja, dois vértices i e j da rede espectral
se ligarão somente se, a força de interação Fi,j for maior que a força de corte F0 . Podemos representar esta condição matematicamente da forma: dado dois vértices da rede
espectral i e j, a probabilidade de i se conectar a j é:
Pi,j =
�
0
Fi,j
δ(F − F0 )dF
(3.2)
qi qj
e 0 < Fi,j < 1.
2
ri,j
Interpretação geométrica:
onde Fi,j = K
Se Fi,j ≥ 0, então Pi,j so poderá assumir dois valores, Pi,j = 0 ou Pi,j = 1, ou seja, os
vértices ligam-se ou não, para esta situação, Pi,j representa uma função binária.
A interpretação de (3.2) é que, devido a F0 ser uma força de corte introduzida na
dinâmica, as ligações mais fracas serão excluı́das da configuração da rede espectral. Considere que os vértices não são mais acessı́veis por qualquer caminho no espaço, esta
consideração é importante porque nesse ponto a geometria euclidiana passa a não mais
apresentar generalidade. Para tanto, imagine agora que a rede que restou, guarda as
informações das interações da nova configuração de acessibilidade. Ao vértices que não
se conectam, em tese não ”interagem” nessa nova configuração e embora exista uma
distância euclidiana e cargas diferente de zero, nessa nova abordagem espectral, esses
fatores não são suficientes para a existência de uma interação.
CAPÍTULO 3. MODELO DE CARGAS
28
Figure 3.2: Representação de uma rede espectral de uma distribuição de 5 cargas numa
região do espaço com a presença de uma força de corte F0 .
Considerando agora uma distribuição de N cargas, construiremos uma rede espectral
e avaliaremos suas propriedades em comparação com os modelos já existentes. Para uma
simulação com 1000 ”cargas”, onde 0 < qk < 10, 1 < ri,j < 50 e F0 = 0, 05. Construı́mos
o gráfico da freqüência f (ξk ) de vértices com ξk ligações.
Figure 3.3: Distribuição da frequência de vértices com k ligações.
Podemos obter uma rede semelhante, usando ao invés da distribuição de cargas, o
modelo de Erdös-Réyl [1] [2], considerando agora uma probabilidade de conexão entre os
CAPÍTULO 3. MODELO DE CARGAS
29
N vértices dada por p, onde o número de ligações média por vértice é dado por
�k� = pN.
(3.3)
Porém, para a rede espectral gerada a partir da interação entre as cargas, podemos
escrver:
N
, considerando 3.3
N
ou
N
��
1
�k� =
(N − 1) i=1 j=1
N
��
1
p=
N (N − 1) i=1 j=1
�
Fi,j
0
�
0
N
δ(F − F0 )dF
(3.4)
δ(F − F0 )dF
(3.5)
Fi,j
N
��
1
Pi,j
p=
N (N − 1) i=1 j=1
(3.6)
. Para F0 = 0, p = 1 e �k� = N Na Figura3.2, podemos perceber que a distância entre
os vértices é euclidiana.
Com este exemplos, mostramos a idéia de como as redes complexas podem conter
informações acerca de um fenômeno utilizando-se de sua propriedades para manuser
parâmetros e determinar resultados. Em (3.6, relacionamos a probabilidade do modelo
das redes complexas, com a probabilidade do modelo das redes dinâmicas.
Capı́tulo 4
O Problema da distância nas redes
sem escala
Um dos maiores problemas em manusear redes de escala livre é o fato de não haver
grandezas geométricas bem definidas para este espaço. A presença de uma anti-simetria
revela uma enorme dificuldade na elaboração de uma estrutura matemática que possa
operar no sentido de generalizar ou facilitar o estudo de muitos parâmetros posto sobre
essas redes.
A determinação desta nova noção espacial constitui um problema que é abordado
de diferentes maneiras na resolução de aplicações que envolvam as redes sem escala.
Um dos objetivos do nosso trabalho é determinar uma outra maneira de converter essa
problemática. As redes sem escala assumem agora interpretação da teoria dos grafos,
definiremos que:
Definição 4.1. O vértice i interage com o vértice j somente se i é acessı́vel a j ou j
acessı́vel a i, então graficamente dizemos que i se liga a j.
30
CAPÍTULO 4. O PROBLEMA DA DISTÂNCIA NAS REDES SEM ESCALA
31
E a partir de argumentos eurı́sticos, construimos a seguinte hipótese:
Hipotese 4.1. Para uma rede sem escala com N vértices , dados dois vértices i e j
qualquer, dizemos que i está mais próximo de j a medida que ξi aumenta, onde ξi é
número de arestas (vizinho) do vértice i.
Então é possı́vel relacionar a distância média entre dois vértices i e j a partir das
peopriedades locais pelo teorema:
Teorema 4.1. Para um grafo H convexo1 , formado por N >> 1 vértices, a distância
média entre dois vértices quaquer i e j para M caminhos tomados entre eles pode ser
escrita por
�χi,j (M )� ∼
1
,
ξi
(4.1)
onde M ≤ N .
4.1
Distância entre dois vértices; Demonstração do
Teorema 4.1
Considere agora um grafo H com 1 < k < N , onde N é o número de vértices e ξk
sendo o número de arestas (vizinhos) que o k-ésimo vértice possui.
Para um dado N , existe um número de caminhos M que liga o vértice i ao vértice j.
A função que conta o número de vértices intermediários (L) para um dado caminho de
ordem k entre os vértices i e j é definida por
(k)
χi,j = L,
1
(4.2)
Para um grafo convexo, sempre existe pelo menos um caminho possı́vel entre queisquer pares de
vértices do grafo, isso emplica que quelquer vértice possui no mı́nimo uma conexão, logo, para 1 ≤ k ≤ N
com k inteiro, ∀ ξk �= 0 e também inteiro limitado por N
CAPÍTULO 4. O PROBLEMA DA DISTÂNCIA NAS REDES SEM ESCALA
32
Figure 4.1: Modelo de grafo
onde L é o número de vértices intermediário que forma o k-ésimo caminho. Para M
caminhos diferentes, o caminho médio é dado por:
M
1 � (k)
�χi,j (M )� =
χ .
M k=1 i,j
(4.3)
Partindo de 2.1,
d(i,j) = χmin = L0
Para o grafo, tomamos dois vértices i e j quaisquer, e a partir do vértice i tomamos
M caminhos aleatórios distintos até j, de modo que a probabilidade de se obter caminhos
de tamanho L é da forma
L
1�
1
Pi,j (L) =
,
ξi k=1 (ξk − 1)
(4.4)
onde os ξk são os respectivos número de vizinhos dos vértices que formam o caminho de
tamanho L.
Para verificar o comportamento de 4.4, construimos o modelo para um dado grafo
H, que relaciona o frequência de caminhos de tamanho L (f(L)) com o tamanho dos
caminhos.
CAPÍTULO 4. O PROBLEMA DA DISTÂNCIA NAS REDES SEM ESCALA
33
Figure 4.2: Histograma dos caminhos entre dois sı́tios i e j num grafo H em relação ao
comprimento χi,j
.
Interpretando o gráfico, podemos perceber que existe uma convergência em torno da
região de menor caminho (di,j =geodésica).
˜
Considerando agora um número de ligações média para o grafo, ou seja, ξ1 ≈ ξ2 ... ≈ ξ.
Esta afirmação possui boa aproximação para as redes espectrais dos modelos de ErdösRéyl [1] [2] e de Wattse Strogatz[3] , onde ξ˜ = pN . O que torna ?? da forma:
P (L) =
1
.
ξi (ξ˜ − 1)L
(4.5)
Considerando agora um grafo com N >> 1, partindo da definição de média ponderada
podemos escrever:
∞
1 �
f (n)n,
�χi,j (M )� =
M n=d
(4.6)
onde M é o número de caminhos tomados do vértice i ao vértice j (amostra), d é a
geodésica (menor caminho) entre i e j para qual f (k) é a frequência de caminhos de
tamanho k. No entanto, P (k) = M f (k), logo
CAPÍTULO 4. O PROBLEMA DA DISTÂNCIA NAS REDES SEM ESCALA
�χi,j (M )� =
usando 4.5 temos
∞
�
P (n)n ,
34
(4.7)
n=d
∞
n
1�
,
�χi,j (M )� =
˜
ξi n=d (ξ − 1)n
(4.8)
onde n = d, d + 1, d + 2, ... + ∞
Então
�
∞ �
�
d+n
1 ˜
d
�χi,j (M )� = (ξ − 1)
ξi
(ξ˜ − 1)n
n=0
(4.9)
�
�
1
ξ˜ − 1
d+
.
�χi,j (M )� =
ξi (ξ˜ − 1)d (ξ˜ − 2)
ξ˜ − 2
(4.10)
�
�
�
∞ �
�
1
d+n
ξ˜ − 1
d+
.
=
S=
ξ˜ − 1
ξ˜ − 2
(ξ˜ − 1)n
n=0
Suponha agora que estamos interessados em medir a distância média entre dois
vértices i e j.Após cada medida de �χi,j (M )� para M caminhos, aumentamos o número
de visinhos do vértice i de modo que ξ˜ permaneça praticamente invariável, para tanto,
N >> 1. Com essas considerações, partindo de 4.10escreveremos
˜ =
f (ξ)
�
�
1
ξ˜ − 1
d+
ξ˜ − 2
(ξ˜ − 1)d (ξ˜ − 2)
que é constante para um dado N , o que torna:
�χi,j (M )� =
1 ˜
f (ξ),
ξi
(4.11)
1
ξi
(4.12)
logo,
�χi,j (M )� ∼
Para investigar 4.12, construimos um grafo aleatório com N = 5000, tomamos dois
vértices quaisquer i e j e lançamos M = 1000 caminhos aleatórios de uma a outro, para
CAPÍTULO 4. O PROBLEMA DA DISTÂNCIA NAS REDES SEM ESCALA
35
cada valor de �χi,j (M )�, aumentamos a acessibilidade do vértice i, de modo a considerar
ξi ∼
= Cte. Repetimos o processo para os mesmos dois vértices selecionados várias vezes
construindo o gráfico.
Figure 4.3: Histograma dos caminhos entre dois sı́tios i e j num grafo H
CAPÍTULO 4. O PROBLEMA DA DISTÂNCIA NAS REDES SEM ESCALA
36
É facil perceber que com o aumento do gráu de conectividade de i, o caminho médio
de i a j diminui. Quanto mais acessı́vel i estiver, mais fácil será chegar a ele considerando
a premissa de um caminho aleatório. O vértice i se ”aproxima” de J com o aumento do
grau de conectividade. Tomemos agora a transformação Log Log sobre o gráfico.
Figure 4.4: Transformaçãolog-log
CAPÍTULO 4. O PROBLEMA DA DISTÂNCIA NAS REDES SEM ESCALA
37
Partindo do gráfico acima pelo coeficiente de inclinação da reta que corta os pontos
podemos escrever
Ln(�χij (m)�
∼ λ ⇒ �χij (m)� ∼ (ξi )λ .
Ln(ξi )
(4.13)
A partir da simulação temos que λ converge para −1 tornando
−1
�χij (m)� ∼ (ξi )
⇒
� �
1
�χij (m)� ∼
ξi
(4.14)
mostrando coerência com os resultados analı́ticos.
Essa abordagem da distância entre dois vértices num grafo sem escala, permite a
análise de uma classe de aplicações fı́sicas a essas estruturas, que estão bastante presentes
em fenômenos naturais. No entanto, junto com essa nova abordagem, daremos inı́cio a
construção de um conjunto completo de propriedades matemáticas para compreensão das
mesmas.
Capı́tulo 5
Conclusão
Atualmente, é grande o número de fenômenos que apresentam comportamentos que
são bem descritos, ou em outras ocasiões, aproximadamente descritos pelas estruturas
complexas, em particular as redes complexas. Entre as mais comuns podemos citar as
redes sociais e as redes virtuais da Internet. Embora, esses fenômenos se descrevam
semelhante a essas estruturas complexas, a descrição completa de tais estruturas ainda
permanece incompreensı́vel, o que torna crescente o número de pesquisas nesta área,
isso também é facilitado por alguns fatores. Primeiro, por se tratar de questões recentes, mostrando-se como uma área que aguarda bastante descobertas. Segundo, pelo
fácil acesso a dados de pesquisas, que podem ser realizados a um baixo custo, aumentando assim, a acessibilidade dos interessados. Nossos estudos em particular, constroem
uma abordagem mais dinâmica dessas estruturas complexas, anexando às mesmas, não
somente informações estruturais, mas, uma descrição das interações do fenômeno em
questão. A redes complexas não devem ser vistas apenas como uma configuração espacial,
um aglomerado de pontos fixos conectados, devem ser capazes de guardar informações
sobre o sistema. Isso requer uma organização matemática sobre essas estruturas, que
otimize a compreensão da interação entre parâmetros, mostrando resultados com in38
CAPÍTULO 5. CONCLUSÃO
39
terpretações fı́sicas coerentes. Nosso primeiro passo, foi desenvolver matematicamente
ferramentas para que possamos desenvolver interpretações acerca da ”distância” entre os
elementos dessas estruturas, que não podem mais ser interpretados como distância euclidiana. Uma vez feita essa interpretação, podemos agregar a essas estruturas modelos
de interações fı́sicas, que de alguma forma ficam melhores descritos por estas, possibilitando a análise de parâmetros até então, emaranhados em outros contextos (estruturas
que envolvem o espaço euclidiano). A formulação do Teorema 4.1, mostra de maneira
simples, a relação da idéia de distância em termos de parâmetros locais que são facilmente acessı́veis, facilitando dessa forma a descrição de muitos fenômenos. Entre eles,
a abordagem da dinâmica das redes sociais na Internet, como por exemplo, o Orkut.
É nosso propósito dar continuidades ao estudo das propriedades dos grafos (redes) sem
escala, generalizando conceitos e demonstrando a utilidade dessa nova abordagem na resolução e simplificação de problemas que se mostrem bem descritos por essas estruturas. O
que torna essa interpretação coesiva, é a compreensão de alguns modelos pré-existentes,
apontando para uma absorção e descrição mais detalhada em interpretação matemática
e fı́sica dos modelos existentes, principalmente as Redes Aleatória [1][2] e o Modelo de
Barabási-Albert[4], que se apresentam como os mais abrangentes.
Bibliografia
[1] P. Erdös and A. Rényi. On random graphs. Publicationes Mathematicae (Debrecem),
6 : 290 − 297, 1959.
[2] P. Erdös and A. Rényi. On the evolution of random graphs. Publications of the
Mathematical Institute of the Hungarian Academy of Sciences, 5 : 17 − 61, 1960.
[3] WATTS, Duncan J. Six Degrees. The Science of a Connected Age. New York: W.
W. Norton and Company, 2003.
[4] A. L. Barabási and R. Albert. Statistical mechanics of complex networks. Reviews
of Modern Physics, 74 : 47 − 97, 2002.
[5] A. L.Barabási and R. Albert. Emergence of scaling in random networks. Science,
286 : 509 − 512, 1999.
[6] SCHARNOHORST, Andrea. Complex Networks and the Web: Insights From Nonlinear Physics. Journal od Computer Mediated Communication, V. 8, issue 4. 2003
Disponı́vel em ¡http://www.ascusc.org/jcmc/vol8/issue4/scharhorst.html¿. Acesso
em 23/03/2004.
[7] RUNQUERIRO, R. C. TEORIA DAS REDES E REDES SOCIAIS NA INTERNET:Considerações sobre o Orkut, os Weblogs e os Fotologs Universidade Federal
do Rio Grande do Sul e Universidade Católica de Pelotas - 2004.
40
BIBLIOGRAFIA
41
[8] GRANOVETTER, Mark. The Strenght of Weak Ties. American Journal of
Sociology,78, 1360 − 1380(1973).
[9] MENDES, JOSÉ FERNANDO F. Fisica de Redes Complexas, Artigo-Revista
Gazeta de Fı́sica, Departamento de Fı́sica da Universidade de Aveiro,Campus Universitário de Santiago 3810 − 193 Aveiro
[10] G. Siganos, M. Faloutsos, P. Faloutsos, and C. Faloutsos. Power-laws and the as-level
internet topology. IEEE/ACM Transactions on Networking (TON), 2003.
[11] L. A Adamic. Zipf, power-laws, and pareto - a ranking tutorial. http: // www. hpl.
hp. com/ research/ idl/ papers/ ranking/ ranking. html , acessado em março de
2007. Information Dynamics Lab, HP Labs, Palo Alto, CA 94304.
[12] M. Newman, A. L. Barabási, and D. J. Watts. The Structure and Dynamics of
Networks. Princeton University Press, 2006. ISBN-13: 978 − 0 − 691 − 11357 − 9.
[13] A. D. Araújo, T. F. Vasconcelos, A. A. Moreira, L. S. Lucena, J. S. Andrade Jr.
Phys. Rev E, 72 , 041405 (2005).
[14] A. -L. Barabási and R. Albert, Science 286,509 (1999).
[15] Ferraz. C. H. A. Dinâmica de Redes Booleanas Aleatórias na Presença de um Agente
Danificador. Tese de Doutorado. Fortaleza,06/03/2007.
[16] A. -L. Barabási and R. Albert, Science 286,509 (1999).
[17] Romeu. M. C. Percolação invasiva entre múltiplos poços. Dissertação de Mestrado.
UFC - Fortaleza, setembro de 2007.
[18] J. Feder, Fractals (Plenum Press. 1988).
BIBLIOGRAFIA
42
[19] B. Mandelbrot, The Fractal Geometry of Nature (W. H. Freeman and Company,
1982).
[20] A. -L. Barabási and R. Albert, Science 286,509 (1999).
[21] S. Milgram. Psychology Today 2, 60-67 (1967) (1999).
[22] Rodriguez. P. M Trasição de fase para um modelo de percolação de discos em grafos.
Tese de Mestrado. USP, 15 de fevereiro de 2007.