LarissaDeFariasRibeiro-DISSERT

Prévia do material em texto

Universidade Federal do Rio Grande do Norte
Centro de Ciências Exatas e da Terra
Departamento de F́ısica Teórica e Experimental
Programa de Pós-Graduação em F́ısica
Redes sem Escala T́ıpica: Visão Geral,
Modelos Alternativos e Técnicas Computacionais
Larissa de Farias Ribeiro
Natal–RN
Janeiro de 2017
Larissa de Farias Ribeiro
Redes sem Escala T́ıpica: Visão Geral,
Modelos Alternativos e Técnicas Computacionais
Dissertação de mestrado apresentada ao Pro-
grama de Pós-Graduação em F́ısica da Universi-
dade Federal do Rio Grande do Norte como requi-
sito parcial para a obtenção do grau de Mestre em
F́ısica.
Orientador: Prof. Dr. Luciano Rodrigues da Silva
Coorientador: Prof. Dr. Tiago Medeiros de Vieira
Natal–RN
Janeiro de 2017
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
Universidade Federal do Rio Grande do Norte – UFRN 
Sistema de Bibliotecas – SISBI 
Catalogação da Publicação na Fonte - Biblioteca Central Zila Mamede 
 
Ribeiro, Larissa de Farias. 
 Redes sem escala típica: visão geral, modelos alternativos e técnicas 
computacionais / Larissa de Farias Ribeiro. - 2017. 
 107 f. : il. 
 
 Dissertação (mestrado) - Universidade Federal do Rio Grande do 
Norte, Centro de Ciências Exatas e da Terra, Programa de Pós-
Graduação em Física. Natal, RN, 2017. 
 Orientador: Prof. Dr. Luciano Rodrigues da Silva. 
 Coorientador: Prof. Dr. Tiago Medeiros de Viera. 
 
 1. Redes complexas - Dissertação. 2. Redes sem escala típica - 
Dissertação. 3. Redes aleatórias - Dissertação. 4. Distribuição de 
conectividade - Dissertação. 5. Lei de potência - Dissertação. I. Silva, 
Luciano Rodrigues da. II. Viera, Tiago Medeiros de. III. Título. 
 
RN /UF/BCZM CDU 
530.1 
Larissa de Farias Ribeiro
Redes sem Escala T́ıpica: Visão Geral,
Modelos Alternativos e Técnicas Computacionais
Dissertação de Mestrado apresentada ao Programa de Pós-Graduação em F́ısica da Univer-
sidade Federal do Rio Grande do Norte como requisito parcial para a obtenção do grau de
Mestre em F́ısica.
Aprovada em 13 de janeiro de 2017 pelos membros da banca examinadora.
Banca Examinadora
Prof. Dr. Luciano Rodrigues da Silva (Presidente – Orientador)
Universidade Federal do Rio Grande do Norte (UFRN)
Prof. Dr. Tiago Medeiros de Vieira (Examinador Externo – Coorientador)
Universidade Federal de Lavras (UFLA)
Prof. Dr. Raimundo Silva Junior (Examinador Interno)
Universidade Federal do Rio Grande do Norte (UFRN)
Prof. Dr. Mauŕıcio Lopes de Almeida (Examinador Interno)
Universidade Federal do Rio Grande do Norte (UFRN)
i
Aos meus pais.
ii
Agradecimentos
Aos meus pais, por toda dedicação e apoio. À minha querida irmã Camila Ribeiro,
pela amizade incondicional. Ao meu companheiro de vida e de sonhos Jadson Tadeu, por todo
amor e parceria. À Benjamin, meu companheiro de quatro patas, que com sua forma pura de
amar torna minha vida mais leve e feliz.
Ao professor Luciano Rodrigues da Silva, por ter me concedido a oportunidade de
adquirir novos conhecimentos, por todo apoio e incentivo constante. Em especial, ao professor
coorientador Tiago Medeiros, por todo ensinamento, paciência e generosidade ao longo desses
últimos anos. Muito obrigada por todo seu empenho e dedicação para a conclusão deste
trabalho.
À Capes, pelo apoio financeiro que proporcionou o desenvolvimento deste trabalho. Aos
professores do DFTE que contribúıram para minha formação profissional e aos funcionários.
iii
“Um jovem cientista precisa se dedicar
a um projeto pelo qual ele se interesse,
com o qual ele tenha prazer. Divirtam-se!
Quem faz ciência com o objetivo de
ganhar prêmios corre um grande risco de
ter uma vida miserável. ”
(Kurt Wüthrich, Nobel de Qúımica.)
iv
Resumo
Estamos inseridos num mundo formado por redes e nos últimos anos estudos sobre
redes e suas propriedades têm se expandido consideravelmente. A principal razão é que di-
versos sistemas podem ser modelados através das chamadas Redes Complexas. Exemplos de
sistemas facilmente modelados como redes são: a sociedade, a Web, o cérebro, dentre outros.
Para compreender o comportamento desses sistemas, vários modelos na área de Redes Com-
plexas foram propostos. Barabási e Albert propuseram um modelo que inclúıa dois mecanismos
básicos (crescimento e ligação preferencial), reproduzindo um comportamento caracteŕıstico de
alguns sistemas reais: a distribuição de conectividade em lei de potência. Como consequência
do modelo de Barabási e Albert, foram surgindo outros modelos de redes, considerando dife-
rentes tipos de fatores inclúıdos no mecanismo de ligação preferencial. Modelos que utilizam
este mecanismo explicam satisfatoriamente o aparecimento das distribuições que seguem lei de
potência em redes reais. Entretanto, a ligação preferencial não é o único mecanismo através
do qual uma rede pode crescer e gerar este tipo de distribuição de conectividade. Por isso,
neste trabalho analisamos dois outros modelos que utilizam mecanismos diferentes da ligação
preferencial e que são capazes de gerar redes sem escala t́ıpica: o modelo de cópia de vértices e
o modelo de transformação de redes Poissonianas. Comparamos os resultados com as redes de-
correntes do modelo de Barabási e Albert, pois acreditamos que estudar modelos distintos que
geram resultados similares nos permite ampliar nossos conhecimentos referentes à aplicação
de redes complexas e sobre os mecanismos capazes de gerar essas redes. Devido à necessidade
de produção e divulgação de materiais introdutórios às técnicas computacionais fundamentais
para a simulação de redes, também apresentamos neste trabalho algumas técnicas utilizadas
para implementar as redes dos modelos apresentados.
Palavras-chave: Redes complexas; Redes sem escala t́ıpica; Redes aleatórias; Distribuição de
conectividade em lei de potência.
v
Abstract
We are part of a world formed by networks and in recent years studies on networks and
their properties have expanded considerably. The main reason is that several systems can be
modeled through so called Complex Networks. Examples of systems easily modeled as networks
are: society, the Web, the brain, among others. To understand the behavior of these systems,
several models in the field of Complex Networks have been proposed. Barabási and Albert
proposed a model that included two basic mechanisms (growth and preferential attachment),
reproducing a characteristic behavior of some real systems: power-law connectivity distribution.
As a consequence of the Barabási and Albert model, other network models have appeared,
considering different types of factors included in the preferential attachment mechanism. Mo-
dels that use this mechanism satisfactorily explain the emergence of distributions that follow
power-law in real networks. However, preferential attachment is not the unique mechanism
through which a network can grow and generate this type of connectivity distribution. There-
fore, in this work we analyze two other models that use different mechanisms of preferential
attachment and that are able to generate scale-free networks: the vertex copy model and the
Poissonian networks transformation model. We compare the results with the networks deri-
ved from the Barabási and Albert model, because we believe that studying different models
that lead to similar results allow us to expand our knowledge concerning applications area of
complex networks and the mechanisms able to generating such networks. Due to the need of
production and dissemination of introductory materials to the fundamental computational te-
chniques for network simulation, we also present in this dissertation some techniques employed
to implement the networks of the presented models.
Keywords: Complex Networks; Scale-Free Networks; Random Networks;Power-law Connec-
tivity Distribution.
vi
Lista de Figuras
2.1 (a) Representação das pontes de Königsberg. (b) Grafo das pontes de Königsberg. 4
2.2 Representação esquemática de uma rede. . . . . . . . . . . . . . . . . . . . . 4
2.3 Gráficos ilustrativos mostrando a diferença entre a distribuição de Poisson e a
distribuição em lei de potência. . . . . . . . . . . . . . . . . . . . . . . . . . 8
2.4 Exemplo do conceito de coeficiente de agregação local. . . . . . . . . . . . . . 9
2.5 Exemplo do conceito de distância média. . . . . . . . . . . . . . . . . . . . . 10
2.6 Ilustração de redes constrúıdas a partir do modelo de Erdös e Rényi. . . . . . . 11
2.7 Representação da estrutura de uma rede gerada pelo modelo de Erdös e Rényi. 13
2.8 Mapa dos Estados Unidos. . . . . . . . . . . . . . . . . . . . . . . . . . . . . 16
2.9 Processo de reconexão dos vértices proposto pelo modelo de Watts e Strogatz. 18
2.10 Comparação entre a distância média e o coeficiente de agregação para o modelo
de Watts e Strogatz. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 18
3.1 Ilustração do mecanismo de ligação preferencial para o modelo de Barabási e
Albert. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 21
3.2 Distribuição de conectividade em lei de potência para o modelo de Barabási e
Albert. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 24
3.3 Representação da estrutura de uma rede para o modelo de Barabási e Albert. . 25
3.4 Coeficiente de agregação versus o tamanho da rede para o modelo de Barabási
e Albert. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 26
3.5 Distância média versus o tamanho da rede para o modelo de Barabási e Albert. 27
3.6 Ilustração da dinâmica de crescimento de uma rede seguindo o modelo de
Bianconi. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 29
3.7 Gráfico das funções f(C) = exp(−2/C) e q(C) = 1− 1/C em função de C. . 32
3.8 Distribuição de conectividade em lei de potência para o modelo de Bianconi-
Barabási. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 33
3.9 Comportamento da evolução temporal da conectividade dos vértices para dife-
rentes parâmetros de qualidade η. . . . . . . . . . . . . . . . . . . . . . . . . 34
vii
3.10 Dependência do expoente dinâmico β(η) com o parâmetro de qualidade η para
uma distribuição de qualidade uniforme. . . . . . . . . . . . . . . . . . . . . . 34
3.11 Representação da estrutura de uma rede para o modelo de Bianconi-Barabási. 35
3.12 Comportamento de um vértice ao variarmos o valor do expoente α. . . . . . . 36
3.13 Dependência do expoente dinâmico β(η) com o parâmetro de qualidade η e α
para a distribuição de qualidade ρ(η) = ηα. . . . . . . . . . . . . . . . . . . . 37
3.14 Evolução temporal da conectividade dos vértices para diferentes parâmetros de
qualidade η para o modelo de extensão de Bianconi-Barabási. . . . . . . . . . 37
3.15 Distribuição de conectividade cumulativa para a extensão do modelo de
Bianconi-Barabási. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 38
3.16 Distância média e coeficiente de agregação para a extensão do modelo de
Bianconi-Barabási. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 39
3.17 Ilustração da dinâmica de crescimento da rede para o modelo de afinidade. . . 41
3.18 Distribuição de conectividade para o modelo de afinidade. . . . . . . . . . . . 42
3.19 (a) Comportamento da evolução temporal da conectividade dos vértices para
diferentes parâmetros de qualidade η para o modelo de afinidade. (b) De-
pendência do expoente dinâmico β(η) com o parâmetro de qualidade η para o
modelo de afinidade. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 43
3.20 Distância média e coeficiente de agregação para o modelo de afinidade. . . . . 43
3.21 Ilustração da dinâmica de crescimento da rede gerada pelo modelo de Natal. . 45
3.22 (a) Análise da distribuição de conectividade para αA = 2 fixo e diferentes
valores de αG. (b) Comportamento da rede ao variar αA e manter αG = 2 fixo. 46
3.23 Representação da estrutura de uma rede gerada variando os valores de vértices
distribúıdos no plano para αG e αA para o modelo de Natal. . . . . . . . . . . 47
3.24 Comportamento da evolução temporal da conectividade dos vértices para o
modelo de Natal. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 48
3.25 Comportamento do expoente dinâmico β com relação ao expoente αA para o
modelo de Natal. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 48
3.26 Ilustração da dinâmica de crescimento da rede para o modelo de afinidade com
métrica. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 51
3.27 Distribuição de conectividade para αA = 2 fixo e diferentes valores de αG para
o modelo de afinidade com métrica. . . . . . . . . . . . . . . . . . . . . . . . 52
3.28 Distribuição de conectividade para αG = 2 fixo e diferentes valores de αA para
o modelo de afinidade com métrica. . . . . . . . . . . . . . . . . . . . . . . . 52
3.29 Comparação entre o modelo de Natal (MN) e o modelo de afinidade com
métrica (AM). . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 53
3.30 Representação da estrutura de uma rede gerada variando os valores de αG e
αA para o modelo de afinidade com métrica. . . . . . . . . . . . . . . . . . . 53
viii
3.31 Comportamento da evolução temporal da conectividade de um vértice para o
modelo de afinidade com métrica. . . . . . . . . . . . . . . . . . . . . . . . . 54
3.32 Comportamento de β(η, αA) com η e com αA. . . . . . . . . . . . . . . . . 55
4.1 Representação de uma rede com N = 6 vértices. . . . . . . . . . . . . . . . . 57
4.2 Matriz de adjacência da rede de interação protéına-protéına. . . . . . . . . . . 59
4.3 Exemplificação do vetor de apoio utilizado na construção do código rápido para
o modelo de Barabási e Albert. . . . . . . . . . . . . . . . . . . . . . . . . . 66
5.1 Ilustração do mecanismo de cópia de vértices. . . . . . . . . . . . . . . . . . 74
5.2 Distribuição de conectividade em lei de potência para o modelo de cópia de
vértices. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 76
5.3 Representação da estrutura de uma rede para o modelo de cópia de vértices. . 77
5.4 Coeficiente de agregação versus o tamanho da rede para o modelo de cópia de
vértices. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 78
5.5 Distância média versus o tamanho da rede para o modelo de cópia de vértices. 79
5.6 Comparação entre as propriedades do modelo de Barabási e Albert e o modelo
de cópia de vértices. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 79
5.7 Ilustração do crescimento de uma rede seguindo o modelo de transformação
de redes Poissonianas. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 81
5.8 Distribuição de conectividade em lei de potência para o modelo de trans-
formação de redes Poissonianas. . . . . . . . . . . . . . . . . . . . . . . . . . 82
5.9 Representação da estrutura de uma rede para o modelo de transformação de
redes Poissonianas . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 83
5.10 Coeficiente de agregação versus o tamanho da rede para o modelo de trans-
formação de redes Poissonianas. . . . . . . . . . . . . . . . . . . . . . . . . . 84
5.11 Distância média versus o tamanho da rede para o modelo de transformação de
redes Poissonianas. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 84
ix
Lista de Tabelas
4.1 Complexidade de tempo das quatro operações para representações de uma rede
de N vértices e Marestas utilizando matrizes e listas de adjacência. . . . . . 61
x
Sumário
Resumo iv
Abstract v
1 Introdução 1
2 Revisão Histórica 3
2.1 Definição de Redes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3
2.2 Conceitos Básicos . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 6
2.2.1 Distribuição de Conectividade . . . . . . . . . . . . . . . . . . . . . . 6
2.2.2 Coeficiente de Agregação . . . . . . . . . . . . . . . . . . . . . . . . 7
2.2.3 Distância Média . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 9
2.3 Modelos Clássicos de Redes . . . . . . . . . . . . . . . . . . . . . . . . . . . 10
2.3.1 Modelo de Erdös e Rényi . . . . . . . . . . . . . . . . . . . . . . . . 10
2.3.1.1 Propriedades Estruturais do Modelo de Erdös e Rényi . . . . 12
2.3.2 Experimento de Milgram: o fenômeno de mundo pequeno . . . . . . . 14
2.3.3 Modelo de Watts e Strogatz . . . . . . . . . . . . . . . . . . . . . . . 16
3 Redes sem Escala T́ıpica 19
3.1 Modelo de Barabási e Albert . . . . . . . . . . . . . . . . . . . . . . . . . . . 20
3.1.1 Propriedades do modelo de Barabási e Albert . . . . . . . . . . . . . . 24
3.2 Modelo de Bianconi-Barabási . . . . . . . . . . . . . . . . . . . . . . . . . . 27
3.3 Extensão do Modelo de Bianconi-Barabási . . . . . . . . . . . . . . . . . . . 33
3.4 Modelo de Afinidade . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 39
3.5 Modelo de Natal . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 44
3.6 Modelo de Afinidade com Métrica . . . . . . . . . . . . . . . . . . . . . . . . 49
4 Técnicas Computacionais 56
4.1 Matrizes e Listas de Adjacência . . . . . . . . . . . . . . . . . . . . . . . . . 56
4.2 Análise de Algoritmos de Redes Fundamentais . . . . . . . . . . . . . . . . . 61
xi
4.2.1 Rede Aleatória . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 61
4.2.2 Rede de Barabási e Albert . . . . . . . . . . . . . . . . . . . . . . . . 63
4.2.2.1 Código Padrão . . . . . . . . . . . . . . . . . . . . . . . . . 63
4.2.2.2 Código Rápido . . . . . . . . . . . . . . . . . . . . . . . . . 66
4.2.3 Rede de Bianconi-Barabási . . . . . . . . . . . . . . . . . . . . . . . . 67
4.2.3.1 Código Padrão . . . . . . . . . . . . . . . . . . . . . . . . . 67
4.2.3.2 Código Rápido . . . . . . . . . . . . . . . . . . . . . . . . . 68
5 Redes sem Escala T́ıpica: Modelos Alternativos 71
5.1 Modelo de Cópia de Vértices . . . . . . . . . . . . . . . . . . . . . . . . . . 72
5.1.1 Propriedades do modelo de Cópia de Vértices . . . . . . . . . . . . . . 77
5.2 Modelo de Transformação de Redes Poissonianas . . . . . . . . . . . . . . . . 80
5.2.1 Propriedades do modelo de Transformação de Redes Poissonianas . . . 82
5.3 Análise dos Resultados . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 85
6 Considerações finais 87
Referências bibliográficas 90
1
Caṕıtulo 1
Introdução
Nos últimos anos, os estudos sobre redes e suas propriedades têm se expandido con-
sideravelmente. A principal razão é que diversos sistemas podem ser modelados através das
chamadas Redes Complexas. Por exemplo, as sociedades são redes constitúıdas por diferentes
tipos de relacionamentos entre indiv́ıduos, as células são redes de moléculas ligadas por reações
qúımicas e, a internet é uma rede de roteadores e computadores ligados através de conexões
ópticas e f́ısicas.
Pode-se considerar que o estudo das redes teve sua origem na Teoria dos Grafos, ramo
da matemática que iniciou por volta de 1736, quando Euler solucionou o famoso problema das
sete pontes de Königsberg. Ao resolver este problema, ele apresentou ao mundo o que seria o
primeiro grafo e hoje a ideia de grafo é a representação mais simples de uma rede do ponto de
vista matemático. As redes podem ser basicamente definidas como um conjunto de elementos
conectados entre si. Torna-se fácil, então, perceber que as redes estão em toda parte, sendo
uma preciosa ferramenta usada para descrever vários sistemas reais. Mas apesar da importância
e alcance das redes, durante um bom tempo os pesquisadores dedicaram poucos esforços na
tentativa de compreender completamente suas estruturas e propriedades. No entanto, nas
últimas décadas a comunidade cient́ıfica passou a investigar os mecanismos que determinam
as caracteŕısticas estruturais e topológicas das redes complexas.
Os primeiros estudos rigorosos sobre redes foram realizados por Erdös e Rényi em 1959.
Eles propuseram um modelo onde a construção de uma rede iniciava-se com N vértices e cada
um dos posśıveis pares de vértices era conectado com uma probabilidade p, produzindo assim
uma rede aleatória que apresentava uma distribuição de conectividade do tipo Poissoniana.
Este modelo foi a base da teoria das redes por muitas décadas. Porém, nos últimos anos, com
os avanços tecnológicos e o aumento do poder computacional, pesquisas nesta área puderam
se desenvolver e possibilitaram o estudo das estruturas e propriedades de muitas redes reais,
as quais demonstraram que o modelo de rede aleatória não era suficiente para descrevê-las. Os
resultados obtidos a partir destas novas redes mostraram que sua distribuição de conectividade
segue uma lei de potência do tipo P (k) ∝ k−γ e que, portanto, desvia significativamente da
distribuição de Poisson. Este comportamento, indica a ausência de uma escala t́ıpica, fazendo
2
com que redes como estas sejam chamadas de Redes sem Escala T́ıpica ou Redes Complexas.
No âmbito da f́ısica, redes desse tipo foram inicialmente estudadas por Barabási e
Albert, os quais propuseram um modelo que gerasse redes com distribuição de conectividade
em lei de potência a partir de um algoritmo simples que inclúıa apenas duas regras básicas:
crescimento e ligação preferencial [17]. Como consequência do modelo de Barabási e Albert,
foram surgindo outros modelos de redes, considerando diferentes tipos de fatores inclúıdos
no mecanismo de ligação preferencial, dentre os quais apresentaremos com mais detalhes
no decorrer deste trabalho: o modelo de Bianconi [22], o modelo de extensão do modelo
de Bianconi [12], o modelo de afinidade [23], o modelo de Natal [26, 27] e o modelo de
afinidade com métrica [29]. Modelos que utilizam o mecanismo de ligação preferencial explicam
satisfatoriamente o aparecimento das distribuições que seguem lei de potência em redes reais.
Entretanto, este não é o único mecanismo através do qual uma rede pode crescer e gerar este
tipo de distribuição de conectividade. Outros modelos que utilizam mecanismos diferentes e
que são capazes de resultar em redes sem escala t́ıpica são: o modelo de cópia de vértices e o
modelo de transformação de redes Poissonianas.
Esta dissertação concentra-se no estudo das redes sem escala t́ıpica e tem como obje-
tivo apresentar uma visão geral dos modelos fundamentais desta área, técnicas computacionais
para implementar essas redes e modelos alternativos. O conteúdo apresentado organiza-se da
seguinte forma. No caṕıtulo 2, apresentaremos os principais conceitos para a compreensão
da área e os modelos clássicos de redes: modelo de Erdös e Rényi e o modelo de Watts e
Strogatz. Esses são modelos que apresentam uma distribuição de conectividade com escala
t́ıpica. O caṕıtulo 3 é dedicado ao estudo das redes sem escala t́ıpica. Neste caṕıtulo apresen-
taremos modelos que utilizam o mecanismo de ligação preferencial e que geram distribuição
de conectividade em lei de potência: o modelo de Barabási-Albert e modelos derivados deste.
No caṕıtulo 4, apresentaremos técnicas básicas para modelar redes e algoritmos de alguns mo-
delos fundamentais. No caṕıtulo 5, discutiremos modelos que utilizam mecanismos diferentes
da ligação preferencial e que geram redes sem escala t́ıpica: o modelo de cópia de vértices
e o modelode transformação de redes Poissonianas. Por fim vêm as considerações finais e
perspectivas para trabalhos futuros.
3
Caṕıtulo 2
Revisão Histórica
Estamos inseridos num mundo formado por redes e nos últimos anos estudos sobre
redes e suas propriedades têm se expandido consideravelmente. A principal razão é que diversos
sistemas podem ser modelados através das chamadas redes complexas. Exemplos de sistemas
facilmente modelados como redes são: (i) a sociedade, que é uma rede formada por pessoas
conectadas através de algum tipo de relação entre elas; (ii) a Web, que é a rede virtual
formada por “páginas da internet”; (iii) o cérebro, que é uma rede de neurônios interconectados
através de sinapses; etc. Para facilitar a discussão dos modelos de redes complexas apresentada
nos caṕıtulos seguintes, no presente caṕıtulo são revisados os conceitos básicos de redes e
apresentados os principais modelos clássicos.
2.1 Definição de Redes
O que são redes? De uma forma bastante simples, uma rede é um conjunto de elementos
conectados entre si. O estudo das redes teve sua origem na Teoria de Grafos, a qual surgiu
em 1736 quando o matemático súıço Leonard Euler apresentou uma solução para o problema
das pontes de Königsberg. A cidade de Königsberg, capital da Prússia Oriental, era banhada
pelo rio Pregel, que ao cruzá-la se ramificava de tal maneira a formar quatro faixas de terra.
Estas eram conectadas umas às outras através de sete pontes, as famosas sete pontes de
Königsberg (ver figura 2.1). Durante muito tempo os habitantes da cidade se perguntaram
se seria posśıvel encontrar um caminho cont́ınuo que cruzasse as sete pontes, passando sobre
cada uma apenas uma única vez. Euler considerou a situação e para solucionar o problema
utilizou um diagrama onde as faixas de terra eram representadas por vértices (A a D) e as
pontes por arestas (1 a 7), criando possivelmente o primeiro grafo da história. A partir do grafo
de Königsberg, ele provou que era imposśıvel existir um caminho que não cruzasse a mesma
ponte duas vezes. Esta prova baseou-se na observação de que vértices que apresentam um
número ı́mpar de arestas devem ser o ponto de partida ou de chegada. Além disso, para existir
um caminho cont́ınuo que atravessasse as sete pontes era necessário ter um único vértice deste
tipo. Logo esse caminho não poderia existir caso o grafo tivesse mais de dois vértices com o
número ı́mpar de arestas. Como o grafo de Königsberg continha quatro destes vértices, era
4
Figura 2.1: (a) Representação das pontes de Königsberg. (b) Grafo das pontes de Königsberg.
As faixas de terra são representadas pelos vértices e as pontes pelas arestas. Figura adaptada
de [1].
imposśıvel encontrar o caminho desejado [2].
Encontramos então na teoria de grafos, o formalismo matemático para podermos re-
presentar e descrever redes. Na literatura cient́ıfica os termos rede e grafo são usados fre-
quentemente como sinônimos, entretanto existe uma diferença conceitual entre essas duas
terminologias que deve ser evidenciada. As redes na maioria das vezes referem-se a sistemas
reais onde os seus elementos possuem propriedades espećıficas do sistema que desejam des-
crever, enquanto que os grafos são representações puramente matemáticas de redes, tratando
estas como conjuntos de vértices e arestas. Os cientistas da área das redes complexas, em ge-
ral, utilizam a seguinte nomenclatura: os vértices são denominados de nós ou śıtios e as arestas
são chamadas de conexões ou ligações [3]. Deve-se ressaltar que a distinção entre vértices e
nós ou śıtios raramente é obrigatória. Do mesmo modo, geralmente as nomenclaturas aresta,
conexão e ligação são intercambiáveis. Assim, uma rede pode ser definida como um conjunto
de elementos (śıtios ou nós) conectados entre si por linhas (ligações ou conexões), conforme
esquematizado na figura (2.2).
Figura 2.2: Representação esquemática de uma rede.
5
Uma caracteŕıstica importante de um vértice é o número total de conexões que este
realiza, ou seja, o número de arestas que possui. Essa grandeza é chamada de conectividade
(k) ou grau do vértice. Quando dois vértices estão conectados diretamente, dizemos que
estes são vizinhos ou adjacentes. Vértices muito conectados são chamados de polos (hubs).
As redes podem ser direcionadas ou não direcionadas. Elas são direcionadas quando há uma
direção associada a cada conexão, isto é, quando está expĺıcito a origem da conexão e seu
destino. No caso das redes direcionadas, pode-se definir duas conectividades para cada vértice:
a conectividade de entrada ki
1 se refere ao número de arestas que chegam até ele (o vértice
é o destino delas) e a conectividade de sáıda ko
2 se refere ao número de arestas que partem
dele (o vértice é a origem delas). Com isso, a conectividade total de um vértice em uma
rede direcionada é k = ki + ko. Quando as redes são não direcionadas falamos apenas em
conectividade k do vértice, pois não há as noções de origem e destino associadas a cada
conexão. Neste trabalho focaremos exclusivamente em redes não direcionadas. É interessante
notar que a quantidade máxima de arestas Mmax que uma rede deste tipo composta por N
vértices pode ter é apenas um problema de análise combinatória. Cada vértice pode se ligar a
no máximo outros N − 1 vértices. Se cada vértice realizar todas essas conexões, então a rede
terá um total de N(N−1) arestas. Nota-se, porém, que nesse caso cada par de vértices estará
conectado por duas arestas, por isso se torna necessário dividir essa quantidade de arestas por
2. Isso é a combinação de N elementos 2 a 2:
Mmax =
(
N
2
)
=
N !
(N − 2)!2!
=
N(N − 1)
2
(2.1)
De certa forma, definimos o termo rede de uma maneira bem simples e formal. Mas
sabemos que definir este conceito não envolve somente explicar “o que é uma rede”, mas
também apresentar os diferentes tipos de redes existentes e suas caracteŕısticas. É interes-
sante notarmos que não devemos nos restringir somente à estrutura bruta que uma rede nos
apresenta, mas que também devemos procurar entendê-la de uma maneira universal, isto é, um
conjunto de vértices e arestas podem nos fornecer informações úteis quando usados para mo-
delar sistemas adequados e quando são analisados corretamente. Exemplos dessas informações
são previsões sobre o fluxo de dados na internet ou sobre como uma doença se espalhará em
uma comunidade. Sabemos que procurar ter esta visão mais universal é uma tarefa dif́ıcil, mas
que pode trazer recompensas relevantes para nossa percepção da dimensão desta área. Por
isso, no próximo tópico, apresentamos algumas caracteŕısticas fundamentais para a compre-
ensão das redes complexas: a distribuição de conectividade, o coeficiente de agregação médio
e a distância média.
1O ı́ndice i faz referência à palavra em inglês input.
2O ı́ndice o faz referência à palavra em inglês output.
6
2.2 Conceitos Básicos
2.2.1 Distribuição de Conectividade
Uma importante propriedade estrutural de qualquer rede é a distribuição de conectivi-
dade P (k). Ela é a caracterização mais básica de uma rede e representa somente o passo inicial
para sua descrição e compreensão. A distribuição de conectividade nos fornece a probabilidade
de que um vértice, escolhido de forma aleatória, possua k ligações. De forma equivalente, po-
demos dizer que esta nos mostra a fração de vértices de uma rede que apresenta conectividade
k. A forma como a conectividade k está distribúıda entre os vértices de uma rede é visualizada
através do gráfico P (k) versus k. Mais informações podem ser extráıdas através do cálculo
dos momentos da distribuição, sendo que a equação para o momento de ordem n é
〈kn〉 =
∑
k
knP (k) (2.2)
Dessa equação vemos que, o primeiro momento〈k〉 é a conectividade média da rede, enquanto
que o segundo momento, 〈k2〉, determina as flutuações existentes na distribuição de conecti-
vidade. Note que 〈k〉 pode ser calculado diretamente a partir do número N de vértices e M
de arestas:
〈k〉 = 1
N
N∑
i=1
ki =
2M
N
(2.3)
Para auxiliar no entendimento do conceito de distribuição de conectividade, listamos abaixo
alguns exemplos comuns de distribuições presentes nas redes complexas.
A. Distribuição de Poisson: A distribuição de Poisson é uma distribuição de proba-
bilidade discreta que expressa a probabilidade que um certo número de eventos ocorra em um
intervalo cont́ınuo (tempo ou espaço). Esta nos proporciona descrever situações nas quais são
observadas duas caracteŕısticas principais: (i) o número N de elementos (objetos) envolvidos
é grande (N → ∞); e (ii) os eventos ocorrem com probabilidade p pequena (p → 0). Ela é
definida por:
P (k) =
e−〈k〉〈k〉k
k!
(2.4)
Podemos citar como exemplo de uma rede que segue essa distribuição, a rede aleatória.
Observa-se o comportamento poissoniano quando seu número de vértices tende ao infinito
e sua conectividade média 〈k〉 é fixa (ver figura 2.3). Em razão dessa propriedade, dizemos
que esse sistema possui uma distribuição com escala t́ıpica.
7
B. Distribuição em Lei de Potência: A distribuição de conectividade é dita ser
do tipo lei de potência quando sua função de probabilidade tem a forma:
P (k) = Ak−γ (2.5)
onde A é apenas uma constante de normalização, k 6= 0 e γ é o expoente padrão da dis-
tribuição. Deve-se notar que embora a distribuição em lei de potência decaia rapidamente
quando o valor de k cresce, o decaimento ainda é mais lento do que o de qualquer outra
distribuição, o que implica numa probabilidade muito maior de existir eventos extremos. Uma
maneira conveniente de apresentar a distribuição em lei de potência é no gráfico log-log, onde
é fácil medir o expoente da distribuição γ (ver figura 2.3).
Ao contrário da distribuição de Poisson, a distribuição em lei de potência não possui
um valor caracteŕıstico para sua conectividade. Essa propriedade faz com que redes descritas
por essas distribuições sejam chamadas de redes sem escala t́ıpica ou redes livre de escala. Ou
seja, como não existe um único elemento que seja representativo das conexões de todos os
outros elementos, essa rede não possui uma escala t́ıpica de conectividade – dáı o termo “livre
de escala”.
2.2.2 Coeficiente de Agregação
O coeficiente de agregação é um parâmetro que nos informa sobre a presença de
conexões entre os vizinhos de um dado vértice. Considere, por exemplo, um vértice que possua
dois vizinhos. Qual é a probabilidade de que estes dois vizinhos estejam conectados entre
si? É o coeficiente de agregação que nos fornece este resultado. Formalmente, seja um dado
vértice i que possui ki vizinhos, o valor do coeficiente de agregação (local) de i é dado pelo
quociente entre o número de arestas mi que os vizinhos de i possuem entre si e o número
total ki(ki − 1)/2 de arestas posśıveis que eles poderiam possuir:
ci =
mi
ki(ki − 1)/2
(2.6)
onde ci assume valores dentro do intervalo 0 ≤ ci ≤ 1. Logo, quando ci = 0, temos que os
vizinhos do vértice i não se conectam entre si e quando ci = 1, todos os vizinhos do vértice i
também são vizinhos entre si (ver figura 2.4). Observe que a definição acima somente é válida
para vértices que tenham pelo menos dois vizinhos. Podemos também obter o coeficiente de
agregação de toda a rede, isto é, o coeficiente de agregação médio. Este é definido como a
média dos ci pelo número total de vértices:
C̄ =
1
N
∑
i
mi
ki(ki − 1)/2
(2.7)
8
Figura 2.3: Gráficos ilustrativos, gerados a partir da simulação de redes, mostrando a diferença
entre a distribuição de Poisson e a distribuição em lei de potência. (a) Distribuição de Poisson:
vemos que existe um valor t́ıpico para k, o valor médio, e que os demais valores de k não se
distanciam muito desse valor médio. (b) Distribuição em lei de potência em um gráfico com
eixos em escala linear: é posśıvel observar valores de k muito altos, correspondendo aos casos
extremos que são menos raros do que na distribuição de Poisson. (c) Distribuição em lei de
potência em um gráfico cujos eixos têm escala semi-logaŕıtmica: comportamento linear com
inclinação aproximadamente igual ao expoente da equação (2.5).
Depois da distribuição de conectividade, o coeficiente de agregação é um dos
parâmetros mais utilizados na descrição de redes complexas. Nas redes sociais, por exem-
plo, essa propriedade fica expĺıcita na ideia de que “os meus amigos são provavelmente amigos
entre si”.
É interessante ressaltar que existem outras definições para o coeficiente de agregação
de uma rede, por exemplo, a definição relacionada com a contagem de ciclos de comprimento
três, ou seja, triângulos, a qual também é conhecida como transitividade da rede. Contudo,
as menções feitas ao coeficiente de agregação neste texto se referem à definição apresentada
anteriormente.
9
Figura 2.4: Exemplo do conceito de coeficiente de agregação local. Veja que para o vértice i,
temos ki = 6 e mi = 5, resultando em um coeficiente de agregação local ci = 1/3.
2.2.3 Distância Média
A distância média é outra propriedade importante que nos ajuda a compreender o
comportamento de uma rede. Porém, antes de definirmos o que é distância e distância média,
precisamos conhecer o que é um caminho. É dito que existe um caminho entre dois vértices
i e j quando existe uma sequência de vértices, vizinhos aos pares, que permite sair de i e
chegar a j ou vice-versa. Portanto, caminho é a sequência dos vértices ou das arestas que
devem ser atravessadas no percurso entre os vértices i e j. O comprimento de um caminho é
definido como o número de arestas que o formam. Já no caso de o caminho ser especificado
pela sequência de vértices atravessados, o comprimento é definido como o número de vértices
menos 1, desde que sejam inclúıdos no caminho os vértices inicial e final. Como exemplo,
podemos usar a rede da figura (2.5). Um dos vários caminhos entre os vértices 1 e 7 é a
sequência de vértices (1, 3, 7), cujo comprimento é 2. A distância entre dois vértices, por
sua vez, é definida como o comprimento do caminho mais curto. Quando os dois vértices
estão desconectados, define-se a distância entre eles como infinita. A distância média entre os
vértices de uma rede é definida como a média da distância entre todos os pares de vértices
da rede. Formalmente, seja dij a distância entre os vértices i e j de uma rede arbitrária, a
distância média entre os vértices da rede é dada pela equação:
l̄ =
2
N(N − 1)
∑
i<j
dij (2.8)
A distância média possui uma função central no estudo da estrutura de redes, pois
informa quão próximos os vértices estão uns dos outros. No transporte de informações, onde
podemos citar como exemplo o envio de pacotes de dados de um computador para o outro
10
Figura 2.5: Exemplo do conceito de distância média. A distância média entre os vértices da
rede é 1,6 e o diâmetro é 3.
através da Internet, a menor distância fornece a melhor alternativa de tráfego desses pacotes
de dados, fazendo que com estes sejam transferidos da maneira mais eficiente posśıvel. Dito
isto, vemos que esta propriedade é muito relevante para a comunicação e propagação de
informações em uma rede.
Ao falarmos da distância média é interessante termos noção de um conceito relacio-
nado: o diâmetro de uma rede, o qual também é frequentemente usado. O diâmetro de uma
rede é definido como a maior das distâncias entre todos os pares de vértices que formam a
rede.
2.3 Modelos Clássicos de Redes
Nesta seção, iremos apresentar e discutir alguns modelos clássicosde redes, abordando
suas fundamentações, procedimentos de construção e propriedades. Começaremos fazendo a
descrição de um dos modelos que formam a base da teoria de redes complexas, o modelo de
Erdös e Rényi. Em seguida, apresentaremos o experimento de Stanley Milgram, o qual teve
um papel importante para o estudo das redes sociais e que foi fundamental para o surgimento
do modelo de Watts e Strogatz, que também discutiremos ao final desta seção.
2.3.1 Modelo de Erdös e Rényi
Entre 1959 e 1968, Paul Erdös e Alfred Rényi desenvolveram a teoria dos grafos
aleatórios, a qual era uma combinação da teoria da probabilidade e da análise combinatória
com a teoria dos grafos, estabelecendo assim um novo ramo da matemática. Baseado nesta
teoria, eles propuseram um dos primeiros modelos de redes, o qual ficou conhecido por vários
nomes, como modelo binomial, modelo de rede aleatória, modelo de rede Poissoniana e até
mesmo modelo de Erdös e Rényi, devido ao impacto e importância do trabalho deles na
compreensão das propriedades dessas redes [4, 5]. O modelo de rede aleatória foi também
introduzido, de forma independente, por Edgar Gilbert no mesmo ano em que Erdös e Rényi
11
publicaram seu trabalho sobre este assunto [6]. Entretanto, as contribuições de Erdös e Rényi
foram tão fundamentais para o desenvolvimento dessa área que eles são considerados os
fundadores da teoria dos grafos aleatórios.
O modelo de rede aleatória é relativamente simples e não possui um critério que
privilegie certas ligações em relação a outras. Existem duas definições desde modelo, ambas
baseadas apenas em dois parâmetros. A primeira definição assume como fixo o número N
de vértices e o número M de arestas, ficando por isso conhecida como modelo G(N,M). De
acordo com esta definição, ao construirmos uma rede, os N vértices da rede são conectados por
M arestas escolhidas aleatoriamente dentre as N(N − 1)/2 posśıveis. Erdos e Rényi usaram
esta definição em seus trabalhos sobre redes aleatórias. A segunda definição deste modelo
foi introduzida por Gilbert e segue diretamente a ideia por trás da distribuição binomial, a
qual é caracterizada pelos parâmetros N e p fixos, e por isso ficando conhecida como modelo
G(N, p). Seguindo esta segunda definição, a construção de uma rede inicia-se com N vértices
e cada par de vértices é conectado com probabilidade p, a mesma probabilidade para todos os
pares (ver figura 2.6). Deste modo, é feita a tentativa de adicionar cada uma das N(N −1)/2
arestas que podem estar presentes na rede. Cada uma tem probabilidade p de ser adicionada
e essa probabilidade é independente das demais. Note que é como se tentássemos adicionar
todas as arestas posśıveis, uma por uma, mas somente a adição de uma fração p delas fosse
efetivamente realizada, de modo que o valor esperado de arestas é dado por pN(N − 1)/2.
Portanto, a conectividade média (equação 2.3) relaciona-se com p da seguinte forma:
〈k〉 = 2pN(N − 1)/2
N
= p(N − 1) ∼= pN (2.9)
assumindo que N � 1.
Figura 2.6: Ilustração de redes constrúıdas a partir modelo de Erdös e Rényi. Consideramos
três redes, cada uma com N = 10 vértices e com uma determinada probabilidade p. (a) Rede
com p = 0, onde evidentemente obtemos vértices isolados. (b) e (c) Redes onde conectamos
cada par de vértices com probabilidade p = 0.1 e p = 0.2, respectivamente.
12
Neste trabalho, vamos explorar a segunda definição apresentada, o modelo G(N, p),
pois além dele nos permitir calcular as principais caracteŕısticas da rede com maior facilidade,
também representa as redes reais com maior veracidade, devido ao fato que em redes reais
o número de ligações dificilmente é conhecido com antecedência. Percebe-se que esse mo-
delo segue duas regras básicas: tamanho constante e ligações completamente aleatórias. O
algoritmo para a construção de uma rede aleatória é o seguinte:
(1) Inicie a rede com N vértices.
(2) Faça uma listagem de todos os N(N − 1)/2 pares de vértices distintos.
(3) Selecione um par de vértices e gere um número aleatório entre 0 e 1, considerando uma
distribuição de probabilidade uniforme.
(3.1) Se o número gerado for menor ou igual a probabilidade predeterminada p, estabeleça
uma ligação entre o par de vértices selecionado.
(3.2) Se o número gerado for maior que p, não estabeleça nenhuma ligação entre o par
de vértices selecionado.
(4) Repita o passo (3) para cada um dos N(N − 1)/2 pares de vértices da rede, garantindo
que cada par de vértice só seja visitado uma única vez.
Baseado neste algoritmo, constrúımos uma representação de uma rede gerada pelo
modelo de Erdös e Rényi (ver figura 2.7). Esta representação nos permite observar que vários
vértices não possuem nenhuma ligação (k = 0), sendo representados por vértices isolados (na
cor azul), enquanto a maioria realiza várias ligações.
Erdös e Rényi estudaram propriedades associadas a redes aleatórias quando N →∞.
Um dos resultados mais importantes que eles obtiveram foi que as redes aleatórias possuem
uma transição de fase, ou seja, eles mostraram que existe uma probabilidade p a partir da
qual observamos uma mudança abrupta na rede, onde esta deixa de ser formada por pequenos
conjuntos de vértices conectados entre si, passando a ser um grande aglomerado formado pela
fusão da maioria dos pequenos grupos. Esta caracteŕıstica está diretamente relacionada ao
processo conhecido como percolação. Para mais informações sobre percolação veja [7].
A seguir faremos uma análise das principais caracteŕısticas das redes aleatórias.
2.3.1.1 Propriedades Estruturais do Modelo de Erdös e Rényi
A) Distribuição de conectividade
Em uma rede aleatória com probabilidade de conexão p, a conectividade ki de um
vértice i, segue uma distribuição binomial:
13
Figura 2.7: Representação da estrutura de uma rede gerada com N = 80 e p = 0.03 pelo
modelo de Erdös e Rényi.
P (k = ki) = C
k
N−1p
k(1− p)N−1−k (2.10)
onde o primeiro termo, CkN−1, é o número de maneiras equivalentes de selecionar k vértices
dentre os N−1 diferentes de i, com a intenção de se realizarem k conexões. O segundo termo,
pk, representa a probabilidade de que o vértice escolhido esteja conectado a k outros, enquanto
o terceiro termo, (1 − p)N−1−k, representa a probabilidade de que tal vértice não esteja co-
nectado aos (N − 1 − k) vértices restantes. Como todos os vértices em uma rede aleatória
são equivalentes estatisticamente, a probabilidade de um vértice selecionado aleatoriamente
possuir k ligações é a mesma para todos. Para N suficientemente grande e p suficientemente
pequeno, essa distribuição tende a uma distribuição de Poisson:
P (k) ≈ e
−pN(pN)k
k!
=
e−〈k〉〈k〉k
k!
(2.11)
onde 〈k〉 é a conectividade média que é dada por 〈k〉 = p(N−1). Podemos observar então que
as redes constrúıdas segundo essas regras apresentam uma distribuição de conectividade onde
a maioria dos vértices possui uma quantidade ligações em torno de um valor médio, enquanto
poucos vértices possuem uma quantidade de ligações que difere muito da média (ver figura
2.3).
14
B) Coeficiente de Agregação
Considerando um vértice qualquer em uma rede aleatória, a probabilidade de que dois
vértices vizinhos dele estejam ligados entre si é igual à probabilidade de que dois vértices
aleatoriamente selecionados estejam conectados, pois já sabemos que todas as arestas têm
igual probabilidade de existirem. Logo, o coeficiente de agregação médio é dado por:
C̄ = p =
〈k〉
N
(2.12)
C) Distância Média
Considere uma rede aleatória onde os vértices tenham em média k ligações, 〈k〉. Isto
significa que de um vértice qualquer, pode-se visitar, em média, outros k vértices afastados
com uma distância unitária, ou seja, l = 1. De cada um desses k vértices, podemos visitar, em
média, outrosk vértices, os quais são vizinhos com l = 2 em relação ao vértice considerado
inicialmente e, portanto, o número médio de vértices visitados é 〈k〉2. De forma geral, para
a distância l dizemos que o número médio de vizinhos é aproximadamente 〈k〉l, ou melhor,
podemos visitar 〈k〉l vértices com l passos. Se a rede contém N vértices 〈k〉l não pode
ultrapassar o tamanho N , ou seja, N = 〈k〉l. Portanto, para atingir os N vértices da rede são
necessários em média
l̄ =
lnN
ln 〈k〉
(2.13)
passos. Isso sugere que a distância média entre os vértices é pequena em comparação com o
tamanho da rede. Esta caracteŕıstica dá origem ao fenômeno conhecido como mundo pequeno
(small-world), o qual serviu de base para explicar o resultado do experimento de Stanley
Milgram que discutiremos no próximo tópico.
2.3.2 Experimento de Milgram: o fenômeno de mundo pequeno
O estudo da distância média ganhou destaque em 1967, quando o psicólogo e sociólogo
norte-americano Stanley Milgram realizou um experimento com a intenção de saber se duas
pessoas desconhecidas e escolhidas aleatoriamente nos Estados Unidos, poderiam ser conecta-
das através de pessoas que se conheciam. Se isso fosse posśıvel, quantas pessoas formariam a
corrente de conhecidos que ligaria as duas pessoas aleatórias? Desta forma, a questão central
desse experimento focava em medir a “distância social”3 entre duas pessoas quaisquer nos
EUA, o que nos forneceria uma ideia geral sobre a rede de contatos sociais deste páıs.
3Usamos a expressão “distância social” para enfatizar que o experimento teve a intenção de medir a
distância topológica dentro da rede social na qual cada indiv́ıduo está imerso e não a distância espacial.
15
Para dar ińıcio a este experimento, Milgran selecionou pessoas aleatoriamente nos
estados de Nebraska e Kansas, e as pediu para participarem de um estudo relacionado à
sociedade americana, onde deveriam entregar uma carta para duas pessoas escolhidas como
alvos no estado de Massachusetts (ver figura 2.8). A primeira pessoa alvo era a esposa de
um estudante de graduação e a segunda um corretor da bolsa de valores de Boston. A carta
continha o objetivo do estudo, uma fotografia, o nome, o endereço, alguns dados pessoais da
pessoa alvo e as seguintes instruções:
(1) Cada pessoa que receber a carta deve se identificar colocando seu nome na mesma. Isto
serve para rastrear a origem da carta, evitando que esta retorne para a mesma pessoa.
(2) Se você conhece a pessoa alvo, envie este documento diretamente para ele(a).
(3) Se você não conhece diretamente a pessoa alvo, repasse este documento para algum
conhecido que você acredite que tenha maior probabilidade de conhecer o destinatário.
(4) Ao enviar a carta, cada pessoa deve remeter ao cientista uma confirmação de sua par-
ticipação. Esta etapa é muito importante para o desenvolvimento do estudo, pois pro-
porciona ao pesquisador o acompanhamento do trajeto da experiência. Quando a carta
chegar à pessoa alvo, esta deverá enviar a mesma para o pesquisador para completar a
experiência.
O resultado da experiência foi surpreendente, pois esperava-se que o número de cartas
para chegar à pessoa alvo fosse muito grande. Entretanto, o número de intermediários dessas
cartas variou entre 1 e 10, com média 6. Este trabalho foi publicado em 1967, na revista
“Psychology Today” intitulado como “Problema de Mundo Pequeno” e mostrou que dois
indiv́ıduos quaisquer nos EUA estão conectados por, em média, seis intermediários [8]. Dáı
surgiu a famosa expressão “Seis Graus de Separação”, a qual já inspirou peças de teatro, filmes
e livros [9]. Apesar deste experimento ter se restringido apenas aos Estados Unidos, admite-se
que seu resultado seja universal.
O advento de novas tecnologias de comunicação aguçou a curiosidade dos estudiosos
da área, de modo que novos experimentos desse tipo foram realizados utilizando a outrora
famosa plataforma de mensagens instantâneas da Microsoft, o MSN Messenger. Esse estudo
data de 2006 e analisou cerca de 30 bilhões de mensagens de 240 milhões de usuários da
plataforma espalhado por todo o globo. Os resultados encontrados confirmaram a tese dos
seis graus de separação [10, 11]. Empresas como o Facebook têm repetido o experimento mais
recentemente e têm encontrado um padrâo que indica que essa distância média vem caindo
com o tempo, o que indica que as pessoas estão se tornando cada vez mais conectadas umas
às outras. No entanto, deve-se tomar o cuidado de perceber que a ligações sociais em meios
virtuais não refletem necessariamente as relações interpessoais do mundo real. Apesar disso,
todas essas novas iniciativas de medir o grau de separação entre as pessoas reforçam o conceito
de mundo pequeno.
16
Figura 2.8: Mapa dos Estados Unidos. Os estados de Nebraska e Kansas, em vermelho, repre-
sentam os pontos de sáıda das cartas e o estado de Massachusetts, em verde, representa o
ponto de chegada. Figura adaptada de [13].
É importante ressaltar, que a contribuição de Milgram foi além de medir a distância
entre pessoas e mostrar o quanto estamos conectados, pois com este estudo ele nos forneceu
uma das primeiras demonstrações do fenômeno de mundo pequeno e motivou estudos teóricos
mais aprofundados, que resultaram em modelos de redes mais próximos das redes reais.
2.3.3 Modelo de Watts e Strogatz
Em 1998, Duncan Watts e Steven Strogatz ao estudarem a estrutura de diferentes redes
reais em diversos doḿınios, verificaram que algumas destas redes possuiam caracteŕısticas em
comum, como o coeficiente de agregação médio ser superior ao das redes aleatórias, enquanto
a distância média possúıa valores pequenos [14]. Isso indicou que apesar do modelo de Erdös e
Rényi ser um dos mais estudados para representar redes, este não era suficiente para capturar
aspectos fundamentais das estruturas presentes em muitas redes reais. Então, para modelar
muitas dessas redes, era necessário um modelo que conseguisse unir caracteŕısticas de mundo
pequeno e alto coeficiente de agregação. Assim, Watts e Strogatz foram os primeiros a propor
um algoritmo para gerar redes de mundo pequeno, com o propósito de explicar os valores
elevados de C̄ encontrados em seus estudos.
O modelo de Watts e Strogatz pode ser constrúıdo a partir de uma rede de N vértices
com a forma de um anel e com topologia de conexão regular. As conexões são estabelecidas
de modo que cada vértice se liga aos seus k vizinhos mais próximos, sendo m vizinhos à sua
esquerda e m à sua direita, logo k = 2m. Este modelo propõe que uma fração das ligações dessa
rede seja reconectada. O processo de reconexão consiste em percorrer cada ligação da rede e,
com probabilidade p, reconectar uma das extremidades da ligação a um novo vértice escolhido
17
aleatoriamente nesta rede. Nesse procedimento não se permite autoconexões e nem conexões
múltiplas entre um mesmo par de vértices. Deve-se ressaltar que, embora as ligações iniciais
sejam limitadas aos m primeiros vizinhos, após o processo de reconexão algumas ligações de
longo alcance são estabelecidas, conectando muitas vezes vértices diametralmente opostos.
Esse processo está ilustrado na figura (2.9). O algoritmo para a construção de uma rede de
Watts e Strogatz é o seguinte:
(1) Inicie construindo uma rede com N vértices em forma de um anel.
(2) Estabeleça ligações de cada vértice da rede com seus k vizinhos mais próximos, metade à
esquerda e metade à direita.
(3) Selecione uma ligação e com probabilidade p, reconecte-a a um novo vértice escolhido
aleatoriamente, evitando autoconexões e conexões duplicadas.
(4) Repita o passo (3) para todas as ligações da rede.
O processo de reconexão possibilita, ao modelo de Watts e Strogatz, transformar uma
rede com caracteŕısticas de rede regular em uma rede aleatória. Vejamos:quando p = 0 e
k = 4, temos uma rede regular, a qual possui um coeficiente de agregação médio dado por:
C̄ =
3(m− 1)
2(2m− 1)
=
1
2
(2.14)
e a distância média dada por:
l̄ =
N
4
(2.15)
Como esperado, neste caso temos um coeficiente de agregação alto e uma distância média
proporcional a N/k. Já quando p = 1, obtemos uma rede aleatória, pois cada ligação é re-
conectada a um novo vértice, transformando uma rede regular em uma rede completamente
aleatória. Já sabemos que a rede aleatória tem C̄ = 〈k〉
N
e l̄ ∼= lnNln 〈K〉 , o que significa um coe-
ficiente de agregação baixo, inversamente proporcional a N , e uma distância média pequena,
proporcional a lnN .
Através da variação de p, Watts e Strogatz mostraram que existe um intervalo con-
siderável de valores para a probabilidade p, no qual o modelo apresenta paralelamente um
coeficiente de agregação médio alto e uma distância média baixa, como podemos observar na
figura (2.10). Com isso, vemos que a rede de mundo pequeno pode ser considerada um caso
intermediário entre a rede regular e a rede completamente aleatória.
A distribuição de conectividade P (k) de uma rede desse tipo é baseada no fato de
que para p = 0, a distribuição segue a função P (k) = δ(k − k̄), pois todos os vértices têm a
mesma conectividade k̄. Enquanto isso, à medida que p cresce, os vértices passam a ter outros
valores de k. Consequentemente, quando chegarmos em p = 1, recuperamos a distribuição
binomial esperada para uma rede aleatória, com o máximo em torno do valor médio k = k̄.
18
Figura 2.9: Processo de reconexão dos vértices proposto pelo modelo de Watts e Strogatz
capaz de tornar uma rede regular em aleatória. A ilustração da esquerda (p = 0) mostra uma
rede regular, na qual cada vértice se liga aos 4 vizinhos mais próximos. A distância entre os dois
vértices nas cores azul e vermelho é 5. A ilustração do centro (0 < p < 1) mostra a mesma
rede depois que 3 vértices tiveram suas conexões iniciais alteradas. Pode-se notar claramente
que foram inclúıdas ligações de longo alcance, pois a distância entre os vértices azul e vermelho
agora passou a ser 3. Isto mostra que a inclusão de ligações aleatórias, geradas neste modelo
pelo processo de reconexão, é fundamental para que a rede tenha a caracteŕıstica de mundo
pequeno. Por outro lado, a ilustração da direita (p = 1) mostra uma rede na qual todas as
conexões foram redirecionadas aleatoriamente, logo o que temos é uma rede aleatória. Figura
adaptada de [15].
Figura 2.10: Comparação entre a distancia média e o coeficiente de agregação para o modelo
de Watts e Strogatz. Note a rápida queda da distancia média, enquanto o coeficiente de
agregação permanece constante durante boa parte do intervalo, demonstrando que a rede
apresenta o efeito mundo pequeno. Figura retirada de [13].
19
Caṕıtulo 3
Redes sem Escala T́ıpica
O estudo da maioria das redes complexas têm sido motivado pelo desejo de compreen-
der os sistemas reais, por exemplo, as redes sociais ou as redes biológicas. Com o avanço da
tecnologia e a disponibilidade de computadores que permitem a análise de dados em grandes
quantidades, houve uma mudança significativa nesta área. Por causa disso, as pesquisas atu-
ais podem considerar redes envolvendo uma enorme quantidade de vértices e arestas, o que
tem revelado várias caracteŕısticas que diferenciam substancialmente as redes reais das redes
aleatórias.
Assim, desde o final da última década, os estudos das redes reais têm levado pes-
quisadores de diversas áreas a descobrirem a presença de estruturas sem escala caracteŕıstica
em uma quantidade cada vez maior de sistemas. Devido a isto, pesquisas sobre redes sem
escala t́ıpica estão sendo amplamente difundidas. Estes sistemas apresentam uma distribuição
de conectividade seguindo uma lei de potência e é este tipo de comportamento que indica a
ausência de uma escala t́ıpica. Por isso, como já vimos, estas redes são chamadas de redes
sem escala t́ıpica ou redes livres de escala.
As redes sem escala t́ıpica são bastante distintas das redes aleatórias clássicas. Nos
modelos discutidos no caṕıtulo anterior, vimos que o número N de vértices permanece fixo,
que as ligações são realizadas de forma completamente aleatória e que estes apresentam
uma distribuição de conectividade P (k) do tipo Poissoniana, com um valor caracteŕıstico
〈k〉. Mas, apesar de serem modelos bastante estudados para descrever a estrutura de redes,
estes falham em reproduzir caracteŕısticas presentes em muitas redes reais. Por exemplo, em
redes reais o número de vértices cresce continuamente devido à adição de novos vértices.
Portanto se queremos modelar essas redes não podemos recorrer a um modelo estático. Além
disso, na maioria das redes reais novos vértices preferem realizar ligações com os vértices mais
conectados, fazendo com que estas apresentem alguns poucos vértices com uma conectividade
muito alta, enquanto que a maioria dos vértices apresentam baixa conectividade. Redes com
essas caracteŕısticas têm topologia heterogênea, a qual se traduz em uma distribuição de
conectividade que decai em lei de potência.
20
A existência desse tipo de distribuição em várias redes reais levou os pequisadores a
questionar quais tipos de mecanismos seriam responsáveis por gerar tal comportamento [17]. A
resposta surgiu a partir dos trabalhos de Barabási e Albert ao mostrarem que o comportamento
de redes reais pode ser reproduzido através da imposição de algumas regras para o crescimento
das redes, resultando no famoso modelo de Barabási e Albert capaz de gerar redes sem escala
t́ıpica [16, 17, 18].
Neste caṕıtulo, apresentaremos modelos de redes sem escala t́ıpica. Começaremos apre-
sentando o modelo de Barabási e Albert, o qual nos fornece a fundamentação inicial para cons-
truir redes com distribuição de conectividade em lei de potência. Em seguida, apresentaremos
modelos derivados do modelo de Barabási e Albert: Modelo de Bianconi, Modelo de extensão
do modelo de Bianconi, Modelo de Afinidade, Modelo de Natal e o Modelo de Afinidade com
Métrica.
3.1 Modelo de Barabási e Albert
Sabemos que leis de potência regulam várias distribuições de probabilidade utilizadas
para descrever caracteŕısticas de diversos sistemas f́ısicos. Nas redes complexas, a distribuição
de conectividade em lei de potência foi inicialmente estudada por Albert-László Barabási e
Réka Albert em 1999 [17]. Estudos sobre propriedades de sistemas reais associados a leis de
potência já existiam nas ciências sociais [39], por exemplo, no entanto dentro da área das
redes complexas o crédito pela atenção que se dá atualmente a este tópico vem da análise
de Barabási e Albert sobre a estrutura da Web. Eles analisaram como as páginas da Web
estavam conectadas umas às outras e perceberam que a distribuição de conectividade ocorria
seguindo uma lei de potência. Buscando explicar este fenômeno, eles propuseram um modelo
baseado em duas regras básicas, as quais tinham relação com as regras de formação de redes
reais. A primeira regra mencionada por Barabási e Albert é o crescimento da rede, partindo
da observação de que as redes reais não são estáticas, ou seja, a quantidade de vértices que
as compõem está em constante alteração e tende a aumentar com o tempo. A segunda regra
é a ligação preferencial (preferential attachment)1, a qual expressa o fato de que os vértices
mais conectados tendem a ficar ainda mais conectados, pois os vértices recém adicionados à
rede tendem a se ligar àqueles que são mais conectados (os polos). Vale salientar que os polos
representam a diferença estrutural mais marcante entre uma rede aleatória e uma rede sem
escala t́ıpica. Portanto, a ideia fundamental do modelo consiste no crescimento da rede via
ligação preferencial.Essas duas regras formam a base do modelo de Barabási e Albert, também conhecido
como modelo BA ou modelo livre de escala, que é um dos primeiros modelos teóricos a gerar
1Também conhecido por efeito Mateus, devido ao verśıculo deste evangelho que diz “Porque todos aqueles
que têm, mais lhes será dado e terão em abundância.” ou pelo chamado fenômeno “Ricos ficam cada vez mais
ricos”.
21
uma distribuição de conectividade em lei de potência. O algoritmo para a construção de uma
rede de Barabási e Albert é o seguinte:
(1) Inicia-se a rede com N0 vértices conectados entre si.
(2) A cada passo de tempo adiciona-se um novo vértice à rede. Este vértice possui um número
ḿınimo M0(< N0) de arestas, que conectam o novo vértice a M0 vértices diferentes pré-
existentes na rede. A probabilidade de um vértice i pré-existente receber a ligação do
vértice recém adicionado é proporcional à conectividade ki do vértice i e é dada por:∏
(ki) =
ki∑
j kj
(3.1)
(3) Repete-se o passo anterior até o tamanho desejado do sistema. Depois de t passos de
tempo este procedimento resulta em uma rede com N = N0+t vértices e M0(M0 + 1)/2+
M0t ligações.
Note que embora o processo de construção da rede contenha ingredientes aleatórios, a
ligação preferencial tem um efeito dominante, de modo que ela privilegia os vértices que têm
maior conectividade fazendo com que possuam maior probabilidade de adquirir novas conexões
(ver figura 3.1).
Figura 3.1: Ilustração do mecanismo de ligação preferencial com N0 = 3 e M0 = 2, ressaltando
a preferência dos novos vértices em estabelecer conexões com vértices mais conectados.
A combinação desses dois mecanismos, crescimento e ligação preferencial, produz re-
sultados interessantes sobre a conectividade individual dos vértices. Podemos observar que os
vértices que foram adicionados à rede no ińıcio do seu processo de formação, possuem maiores
probabilidades de se tornarem polos e uma vez que isto tenha ocorrido, dificilmente os novos
vértices adicionados conseguirão se tornar polos também.
Barabási e Albert mostraram através de uma abordagem anaĺıtica que para este modelo
proposto, a distribuição de conectividade P (k) ∼ k−γ possui um expoente γ = 3, considerando
o limite termodinâmico. Pode-se explicar este resultado analisando o constante crescimento da
rede a partir de um tratamento cont́ınuo, pois a conectividade dos vértices varia com o tempo,
o que torna posśıvel calcular a evolução temporal da conectividade de um vértice qualquer da
rede. Este tratamento cont́ınuo foi introduzido por Barabási e Albert [3, 17] e está descrito
abaixo.
22
Tratamento cont́ınuo: Considerando um vértice i qualquer da rede, a conectividade
ki deste vértice aumenta quando novos vértices que passam a fazer parte da rede se conectam
a ele. Desse modo, a taxa com que ki varia é proporcional a Π(ki) e satisfaz a seguinte
equação:
dki
dt
= M0
∏
(ki) = M0
ki∑N−1
j kj
(3.2)
Note que a soma no denominador é feita sobre todos os vértices já existentes na rede, ou seja,
não consideramos o vértice que está sendo introduzido. Além disso, cada ligação realizada é
simétrica, logo esta é contabilizada duas vezes:
N−1∑
j
kj = 2M0t−M0 = M0(2t− 1) (3.3)
Observe que o termo M0 é subtráıdo porque corresponde às ligações que o vértice que está
sendo introduzido realiza ao entrar na rede e só desejamos contabilizar as ligações que ele
ganha dos vértices que são adicionados posteriormente. Com isso, a equação (3.2) torna-se:
dki
dt
=
ki
2t− 1
(3.4)
No limite t→∞, o denominador se torna 2t, logo:
dki
ki
=
1
2
dt
t
(3.5)
Sabendo que o vértice i é adicionado à rede no tempo ti com o número inicial de
conexões ki = M0, ou seja, considerando a condição ki(ti) = M0 e integrando, temos que a
solução da equação (3.5) é dada por:
ki(t) = M0
(
t
ti
)β
(3.6)
onde β = 1/2. A partir desta equação vemos que a conectividade de todos os vértices evolui
da mesma maneira independentemente do instante em que foi adicionado à rede e segue uma
lei de potência, com o expoente caracteŕıstico. Isto explica o fato de que os polos observados
são sempre vértices adicionados nos instantes iniciais da rede.
Para calcularmos o grau de distribuição do modelo BA, devemos primeiro escrever a
probabilidade de que um vértice tenha conectividade ki(ti) menor que k, ou seja, a partir da
equação (3.6):
P [ki(ti) < k] = P
[
M0
tβ
ti
β
< k
]
= P
[
ti
β >
M0t
β
k
]
= P
[
ti > t
M0
1
β
k
1
β
]
(3.7)
23
Como neste modelo os vértices são adicionados à rede em intervalos iguais de tempo, os valores
de ti obedecem uma densidade de probabilidade constante, dada por:
P (ti) =
1
N0 + t
(3.8)
Substituindo esta equação na equação (3.7), obtemos:
P
[
ti >
M0
1
β t
k
1
β
]
= 1− M0
1
β t
k
1
β (N0 + t)
(3.9)
A partir disto, podemos obter a distribuição de conectividade P (k):
P (k) =
∂P [ki(ti) < k]
∂k
=
2M0
1
β t
(N0 + t)
1
k
1
β
+1
(3.10)
No limite t→∞, obtemos:
P (k) ∼ 2M0
1
β k−γ (3.11)
onde o expoente da lei de potência é dado por
γ =
1
β
+ 1 = 3 (3.12)
com β = 1
2
. Este valor concorda corretamente com os resultados numéricos (ver figura 3.2).
Note que a variação de P (k) com k independe de M0, pois este parâmetro contribui apenas
para a constante de normalização da distribuição.
Sabemos que distribuições de conectividade descritas por leis de potência (pelo menos
em parte) 2 são frequentemente encontradas em diversos sistemas reais. Essa caracteŕıstica tem
sido verificada em sistemas com várias escalas de tamanho, sendo mais acentuada em sistemas
maiores. Também tem sido verificado que essas leis de potência não dependem do tempo, assim
como indica o modelo de Barabási e Albert. Isso significa que essas redes rapidamente devem
atingir um regime estacionário no que diz respeito à distribuição de conectividade.
Em geral, as estruturas das redes podem ser analisadas e visualizadas fazendo uso de
ferramentas baseadas em grafos. O uso desse tipo de técnica nos proporciona construir uma
representação das estruturas de redes e propor interpretações para estas, como por exem-
plo, sobre as interações existentes entre seus vértices. Com este objetivo, constrúımos uma
representação de uma rede gerada pelo modelo de Barabási e Albert (ver figura 3.3). Esta
representação nos permite identificar os polos (em vermelho), que são os vértices que pos-
suem uma maior quantidade de conexões, e suas interações com os demais vértices. Também
2A grande maioria das redes reais não tem distribuições de conectividade como leis de potência pura. Na
grande maioria dos casos, as leis de potência são truncadas (power-laws with cutoff). Esses truncamentos
se devem ao tamanho finito dos sistemas reais. Acredita-se que se pudéssemos aproximar mais do limite
termodinâmico (N →∞), os truncamentos não seriam observados.
24
Figura 3.2: Distribuição de conectividade em lei de potência para o modelo de Barabási e
Albert obtida a partir de simulações computacionais. Deve-se notar a proximidade entre o
valor do coeficiente encontrado através da simulação e o valor teórico dado pela equação
(3.12). Simulação realizada para M0 = 2, N = 10
6 e 10 amostras.
podemos notar que a maioria dos vértices possui poucas conexões (vértices azuis).
3.1.1 Propriedades do modelo de Barabási e Albert
Embora o modelo de Barabási e Albert apresente uma distribuição de conectividade em
lei de potência, ele possui outras propriedades, como o coeficiente de agregação e a distância
média, que podem ou não concordar com os resultados emṕıricos de muitas redes reais. Assim,
nesta seção, vamos analisar estas propriedades para redes geradas por este modelo e verificar
se estas apresentam o caráter de mundo pequeno.
A) Coeficiente de Agregação
Observe que no modelo de Barabásie Albert temos uma variável que se refere ao
número ḿınimo M0 de vizinhos que um dado vértice deve ter. Se fizermos M0 = 1, o coeficiente
de agregação será nulo, ou seja, não teremos a formação de ciclos. Logo, vemos que esse
modelo só se torna interessante do ponto de vista prático quando fazemos M0 > 1, afinal as
redes reais que nos interessam têm coeficiente de agregação maior do que zero. Comparando
os resultados encontrados para redes aleatórias podeŕıamos supor que para redes sem escala
t́ıpica iŕıamos encontrar um coeficiente de agregação maior. Entretanto, Barabási e Albert
25
Figura 3.3: Representação da estrutura de uma rede gerada com N = 500 e M0 = 2 através
do modelo de Barabási e Albert. A escala de cores mostra os vértices mais conectados em
vermelho e os menos conectados em azul.
encontraram um coeficiente que decresce lentamente com o tamanho da rede (ver figura 3.4).
Verifica-se neste modelo que o coeficiente de agregação tende a zero quando N →∞.
B) Distância Média
Barabási e Albert estimaram a distância média l̄ e perceberam que esta é muito menor
do que a encontrada no modelo aleatório, independente do número de vértices N de uma
26
Figura 3.4: Coeficiente de agregação versus o tamanho da rede para o modelo de Barabási
e Albert, incluindo também as barras de erro. Simulação realizada considerando M0 = 2 e
utilizando entre 30 e 100 amostras para tamanhos de redes entre N = 1000 e N = 30000.
Observa-se que as barras de erros diminuem com o crescimento do tamanho das redes. Nestes
últimos pontos, as barras de erro tornam-se tão pequenas que encontram-se escondidas pelos
śımbolos usados para representar os pontos.
rede. Esse resultado indica que a rede do modelo de Barabási e Albert é mais compacta do
que as redes aleatórias. Foi mostrado também que a distância média tem uma dependência
aproximadamente linear no logaritmo do tamanho da rede, isto é, l̄ ∼ logN (ver figura 3.5).
O modelo de Barabási e Albert é um dos mais utilizados para gerar redes sem escala
t́ıpica, pois a partir dele vemos que um algoritmo simples pode resultar em uma rede complexa.
Entretanto, apesar dos resultados apresentados nesta seção, não podemos deixar de mencionar
que quando este modelo é comparado com redes reais ele apresenta algumas limitações. Por
exemplo: pressupor distribuições de conectividade em lei de potência com um expoente fixo
γ = 3, enquanto que as redes reais normalmente apresentam expoentes situados na faixa de
valores que vai de 2 a 3. Outra limitação que pode ser citada é o fato de que o vértice a ser
introduzido na rede possui informação completa sobre a conectividade de todos os vértices
que já compõem a rede. Essas limitações, entre outras, originaram questionamentos sobre a
possibilidade de se obter outros modelos teóricos com valores diferentes para o expoente, o
que tem motivado mais estudos nessa área.
27
Figura 3.5: Distância média versus o tamanho da rede para o modelo de Barabási e Albert,
incluindo também as barras de erro. Simulação realizada considerando M0 = 2 e utilizando
entre 30 e 100 amostras para tamanho de redes entre N = 1000 e N = 30000.
3.2 Modelo de Bianconi-Barabási
O modelo de Barabási e Albert, descrito na seção anterior, era baseado nos mecanis-
mos de crescimento e ligação preferencial, os quais, sem dúvidas, são fundamentais para a
ocorrência da distribuição em lei de potência, ou seja, sem escala t́ıpica. No entanto, este mo-
delo negligencia um importante aspecto de sistemas competitivos: nem todos os vértices são
igualmente predispostos a adquirir ligações. O mecanismo de ligação preferencial, prenuncia
uma tendência dos vértices mais antigos se tornarem os polos da rede. Entretanto, vários siste-
mas reais demonstram que vértices mais novos podem atrair um grande número de conexões,
conseguindo se tornar os mais conectados da rede. Em outras palavras, esse fato mostra que a
taxa com que a conectividade de um vértice varia com o tempo não depende exclusivamente
de sua idade, isto é, do tempo que ele já faz parte da rede. Por exemplo, na Web, o site de
busca Google se tornou o maior polo (hub) em poucos anos de existência, atraindo grande
parte das conexões de sites que já estavam na rede há muito mais tempo [20]. Outro exemplo,
são alguns trabalhos cient́ıficos que em um pequeno espaço de tempo adquirem um grande
número de citações, ultrapassando trabalhos publicados anteriormente e se tornando polos da
rede de citação de artigos cient́ıficos [21].
Diante disto, em 2001, Bianconi e Barabási propuseram um novo modelo buscando
associar este comportamento a alguma qualidade espećıfica do vértice, tal como o conteúdo
de uma página da Web ou de um artigo cient́ıfico [22]. Este fator reflete a capacidade (fitness)
que o vértice possui de competir por ligações e foi chamado de “qualidade” do vértice. Neste
28
modelo, a cada vértice da rede é atribúıdo um parâmetro ηi, que caracteriza o mesmo. Este
parâmetro é a principal caracteŕıstica do modelo de Bianconi, também conhecido como modelo
Bianconi-Barabási ou modelo de qualidade, e altera a dinâmica a ligação preferencial. Vejamos
então, como isso se reflete na construção de uma rede de Bianconi. O algoritmo é o seguinte:
(1) Inicia-se a rede com N0 vértices conectados entre si, onde cada um deles possui um
parâmetro de qualidade intŕınseco η. Este parâmetro é escolhido aleatoriamente, a partir
de uma distribuição de qualidade ρ(η), que para o modelo original de Bianconi é uniforme.
(2) A cada passo de tempo adiciona-se um novo vértice à rede, o qual já possui o seu parâmetro
de qualidade η. Este vértice possui um número ḿınimo M0(< N0) de arestas, que co-
nectam o novo vértice a M0 vértices diferentes pré-existentes na rede. A probabilidade de
um vértice pré-existente i receber a ligação do vértice recém adicionado é proporcional à
conectividade ki e a qualidade ηi do vértice i pré-existente na rede e é dada por:∏
(ki) =
ηiki∑
j ηjkj
(3.13)
(3) Repete-se o passo anterior até o tamanho desejado do sistema. Depois de t passos de
tempo este procedimento resulta em uma rede com N = N0 + t vértices e M0(M0 +
1)/2 +M0t ligações.
Note que neste modelo a adição do parâmetro de qualidade na ligação preferencial
torna posśıvel que vértices jovens com poucas ligações possam adquirir novas ligações a uma
taxa elevada (ver figura 3.6). Este parâmetro dá a oportunidade de um vértice recém inclúıdo
se tornar um polo da rede, bastando que para isso este possua um alto valor do parâmetro
de qualidade. Portanto, enquanto no modelo de Barabási e Albert o fator determinante para
que um vértice se torne um polo é apenas a “idade” dele, no modelo de Bianconi e Barabási
tanto a idade quanto a qualidade do śıtio contribuem para que ele se torne um polo ou não.
Bianconi e Barabási mostraram analiticamente que para este modelo proposto, a distribuição
de conectividade, agora na forma de uma lei de potência com correção logaŕıtmica, possui
um expoente γ = 2.25, no limite termodinâmico. Pode-se explicar este resultado utilizando
o tratamento cont́ınuo introduzido na seção anterior. Os cálculos e considerações a seguir
seguem bem de perto as ideias apresentadas por [22, 3].
Tratamento cont́ınuo: Um vértice i qualquer da rede aumenta a sua conectividade
ki com uma taxa que varia de acordo com a probabilidade
∏
(ki) (equação 3.13). Assim:
dki
dt
= M0
∏
(ki) = M0
ηiki∑
j ηjkj
(3.14)
onde o fator M0 representa as ligações que cada vértice realiza ao entrar na rede. Baseados
no modelo BA, Bianconi e Barabási assumiram que a evolução de conectividade de um vértice
neste modelo é dado por:
29
Figura 3.6: Ilustração da dinâmica de crescimento de uma rede seguindo o modelo de Bianconi
com m = 1. No centro de cada vértice