UNIVERSIDADE FEDERAL DO RIO GRANDE DO NORTE CENTRO DE ... · tam a origem das correspondências e o estado em verde ... 3.4 Coeﬁciente de agregação versus o tamanho da rede do

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

ANÁLISES ESTATÍSTICAS EM REDES COMPLEXASHOMOFÍLICAS

ANTONIO MARQUES DOS SANTOS

NATAL-RNDEZEMBRO 2014

ANTONIO MARQUES DOS SANTOS

ANÁLISES ESTATÍSTICAS EM REDES COMPLEXASHOMOFÍLICAS

Tese de Doutorado apresentada ao Programa de Pós-Graduação

em Física do Departamento de Física Teórica e Experimental da

Universidade Federal do Rio Grande do Norte como requisito par-

cial para a obtenção do grau de doutor em Física.

Orientador: Prof. Dr. Luciano Rodrigues da Silva

Co-orientador: Dr. Gabriel Alves Mendes

NATAL-RNDEZEMBRO 2014

Para Pessoas Especiais:

À Deus, à minha família. Em especial à minha mãe

Maria da Conceição, ao meu pai Bartolomeu

Ferreira, aos meus irmãos, à minha namorada

Marília Gabriela.

i

AGRADECIMENTOS

Agradecimento é sempre um ato de reconhecimento grandioso, para a vida e para

a alma humana, é fonte inesgotável de gratidão para com aqueles que fazem da nossa

vida, um constante compartilhar de momentos únicos e insubstituíveis.

Primeiramente quero agradecer a DEUS o que seria de mim sem a fé que eu tenho

nele.

Ao meu orientador, professor Dr. Luciano Rodrigues da Silva, por todo o apoio

e conhecimento que me deu durante o tempo que passei no Programa de Pós-Graduação

e, especialmente pela confiança em mim depositada ao assumir a orientação.

Ao meu co-orientador Dr. Gabriel Alves Mendes pela colaboração, paciência e

por seus conhecimentos repassados durante todo o desenvolvimento do trabalho.

Ao Dr. Mauricio Lopes de Almeida pelos momentos de descontração, compa-

nheirismo, e pelos inúmeros auxílios durante a realização deste trabalho.

Aos secretários da Pós-Graduação Celina Pinheiro e Francisco Silvestre.

A Universidade Federal do Rio Grande do Norte, por ter me dado a oportunidade

de concluir meu mestrado e doutorado em um programa de excelência e ter-me proporci-

onado a obtenção dos conhecimentos necessários para a realização e concretização deste

trabalho.

A todos os professores, em especial os que contribuiram para minha formação

e também aqueles funcionários que poucos são citados mais que muito colaboram man-

tendo o ambiente limpo e mas agradável. Dentre eles posso citar Adeída, que Deus aben-

çoe.

Aos amigos do DFTE, em especial os do grupo de pesquisa, MSc. Gerdivane,

Mestranda Larissa Ribeiro, Renann Gleyson, MSc. Samuraí Gomes Aguiar, Thamires

Germano, MSc. Tiago Medeiros, MSc. Tiago Crisostomos e MSc. Thiago Rafael.

A Dona Euzélia, Veruska, seu Ivo, Taynná, Rubens e Wanessa, por toda preocu-

pação, atenção, dedicação e carinho durante esses seis anos que passei no programa, isso

fez deles pessoas especiais e hoje são mais que amigos, considero parte da minha família,

agradeço a Deus por ter colocado voces na minha vida.

ii

Agradeço a meus amigos, Renato Antonio e Guilherme Weber que sempre estive-

ram por perto preocupados com o andamento da tese, sempre incentivando, motivando,

sempre mostrando que tudo vai dá certo no final. Obrigado amigos e a tantos outros que

não citei aqui por que são muitos, mas que com certeza não irei esquecer todo o auxílio

que me deram.

Agradeço a Dona Arlete, seu "Didi", Max, Renato, Evilânia, que foram as pessoas

que me acolheram assim que cheguei em Natal. Obrigado por todo o apoio e todo auxílio,

voces foram fundamentais no início da jornada. Realmente sem palavras para agradecer,

que Deus os abençoe sempre.

A minha namorada Marília Gabriela ofereço um agradecimento mais do que es-

pecial por ter vivenciado comigo passo a passo todos os detalhes do trabalho. Por ter me

ajudado, por ter me dado todo o apoio que necessitava nos momentos mais difíceis, todo

carinho, respeito, e por tornar minha vida mais feliz.

A meus amigos da igreja, Aline Torres, Luana Pereira, Edvanilson Alves, Elida

Rodrigues e Ravenia, pela acolhida no ínicio da caminhada no grupo, por sempre acredi-

tarem em meu potencial, por sempre acreditarem em mim, por todas as orações.

A meus irmãos, Walbermark, Walbetise, Bartolomeu, Walberto, Walbelice, Walbe-

nice e Walbenise pelo companheirismo, pela força e motivação. Agradeço também ao(s)

meu(s) cunhado(as) Edwilson, Fabiana e Kristiane por todas as orações, palavras de apoio,

a todos meus primos(as), tios(as), por toda a torcida, por toda a confiança.

Um super agradecimento a meus pais, Maria da Conceiçao e Bartolomeu Ferreira

dos Santos que souberam me amar, me educar, me transmitindo os mais valorosos saberes,

compartilhando comigo cada vitória, cada derrota, cada lágrima e alegrias. O meu eterno

agradecimento, AMO VOCÊS.

À CAPES pelo apoio financeiro.

iii

“Jesus nos fez um lutador nos ensina a guerrear e nos mos-

tra o caminho, mais não pense que é pela força de seu braço

que as vitórias vêem, elas vêem quando aprendemos a valo-

rizar Deus, os amigos e a família só assim temos bagagem

suficiente para vencer o confronto final.”

(Vitor Belfort)

iv

RESUMO

Propomos um simples processo de crescimento de rede complexa, onde a ligação

preferencial contém dois parâmetros essenciais: a homofilia, tendência que sítios locais

têm de ligar-se com outros similares, bem como o número de vizinhos ligados. Assim

obtivemos uma rede que contempla o modelo de Barabási-Albert (BA) e o modelo Ho-

mofílico de livre escala onde o parâmetro de controle ajusta o grau de importância da

homofilia no processo da ligação preferencial. Os resultados embasam uma discussão de-

talhada sobre os diferentes tipos de correlações, em especial a correlação da qualidade,

que foi introduzida nesta tese, e comparações entre o modelo BA, modelo homofílico de

livre escala, e nosso modelo atual, considerando suas propriedades topológicas: grau de

distribuição, tempo de dependência da conectividade e o coeficiente de agregação.

Palavras-Chave: Redes complexas; Leis de Potência; Ligação Preferencial; Corre-

lações.

v

ABSTRACT

We propose a simple complex network growth process, where the preferential

binding contains two essential parameters: homophily, a trend that local sites have to

connect with other like, as well as the number of connected neighbors. Thus we obtained

a network covering the model of Barabási-Albert (BA) and the scale-free model homophi-

lic where the control parameter sets the degree of importance of homophily in the process

of preferential binding. The results support a detailed discussion of the different types

of correlations, especially the correlation of quality, which was introduced in this thesis,

and comparisons between the BA model, homophilic model of free range, and our cur-

rent model, considering its topological properties: degree distribution, connectivity time

dependence and the coefficient of aggregation.

Keywords: Complex networks; Power-laws; Preferential attachment, correlations.

vi

LISTA DE FIGURAS

2.1 Representação esquemática de uma rede. Figura proveniente da ref [16]. . . . . . . 5

2.2 a) Representação da rede de Bethe. Este é um exemplo de uma rede tipo árvore.

b) Exemplo de uma rede com presença de circuito de ordem n = 3, representado

pelos nós em vermelho e pelas ligações em azul. Essa rede possui número de nós

N = 8 e número de ligações L = 8. Assim podemos determinar o número de

circuitos, neste caso temos I = 1. Figura proveniente da ref [16]. . . . . . . . . . . 6

2.3 O conceito do coeficiente de agregração do sítio i é obtido quando conhecemos

seus primeiros vizinhos e sabemos como estes estão ligados entre si. Para esta

figura temos zi = 6 e yi = 5 logo Ci (zi) =13 . Figura proveniente da Ref [16]. . . . . 10

2.4 Ataque aleatório. A figura 2.4 (a) mostra a estrutura da rede, a figura (b) mostra

os sítios que vão ser atacados, (sítios amarelos), e a figura (c) mostra a estrutura da

rede após o ataque, mostrando que a maior parte da rede ainda continua conec-

tada. Isso significa que a rede é robusta a esse tipo de ataque. . . . . . . . . . . . . 12

2.5 Ataque dirigido. A figura 2.5 (a) mostra a estrutura da rede, a figura (b) mostra os

sítios que vão ser atacados, (sítios amarelos), e a figura (c) mostra a estrutura da

rede após o ataque, mostrando que a rede se desfragmentou de forma rápida. Isso

significa que a rede não é robusta a esse tipo de ataque. . . . . . . . . . . . . . . . 12

vii

2.6 Grau médio dos vizinhos mais próximos. Esta quantidade mede quão correlacio-

nados está o grau médio dos primeiros vizinhos de sítios com conectividade k. Em

(a) ⟨knn (k)⟩ cresce com a conectividade dos sítios, indicando a presença de corre-

lações de grau positivas na rede (assortatividade). Em (b) mostra uma tendência

decrescente de ⟨knn (k)⟩ o que significa que a rede é negativamente correlacionada

(disassortatividade). Finalmente, em (c), com ⟨knn (k)⟩ constante, a rede é descor-

relacionada. Figura proveniente da Ref [20]. . . . . . . . . . . . . . . . . . . . . . 15

2.7 Mapa dos Estados Unidos. Os estados em amarelo (Nebraska e Kansas) represen-

tam a origem das correspondências e o estado em verde (Massachusetts) repre-

senta o destino final. Figura proveniente da Ref [20]. . . . . . . . . . . . . . . . . 17

2.8 Esquema do experimento de Stanley Milgram. Figura proveniente da Ref [20]. . . 17

2.9 Comportamento da distribuição de conectividade da Rede WWW. Figura proveni-

ente da Ref [18]. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 18

2.10 Distribuição de links saindo (a) e entrado (b) em uma Web page. Em (c), menor

caminho médio como uma função do tamanho da rede. Figura proveniente da Ref

[17]. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 20

2.11 Rede de colaborações de atores de cinema com 212250 ⟨k⟩ = 28, 78 e γator = 2, 3.

Figura proveniente da Ref. [23]. . . . . . . . . . . . . . . . . . . . . . . . . . . . 21

3.1 A figura mostra a evolução temporal da conectividade para o modelo BA. Figura

proveniente da Ref. [26]. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 24

3.2 Distribuição de conectividade do modelo de Barabási-Albert. Figura proveniente

da Ref. [26]. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 25

3.3 Gráfico do menor caminho médio l pelo tamanho da rede N , no modelo de Barabási-

Albert com ⟨k⟩ = 4, comparado com um grafo aleatório de igual tamanho e mesma

conectividade média. Figura proveniente da Ref. [13]. . . . . . . . . . . . . . . . . 27

3.4 Coeficiente de agregação versus o tamanho da rede do modelo de Barabási-Albert

com ⟨k⟩ = 4, comparado com o coeficiente de agregação de um grafo aleatório,

Crand ≃ ⟨k⟩/N . Figura proveniente da Ref. [13]. . . . . . . . . . . . . . . . . . . . 28

viii

3.5 Simulação numérica para uma rede com m = 1 e com N = 105, mostrando a

dependência temporal da conectividade kη (t), para sítios com qualidade η = 0.3,

0.6, 0.9. Note que em cada caso kη (t) segue uma lei de potência e o expoente

dinâmico β (η), dado pela inclinação de k (t), aumenta com η. Figura proveniente

da Ref. [27]. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 34

3.6 Comportamento assintótico de C com t → ∞, note que há acordo com a previsão

analítica, linha tracejada, (Equação 3.25). Figura proveniente da Ref. [27]. . . . . . 35

3.7 Distribuição de conectividade no modelo de qualidade, obtida para uma rede com

m = 1 e N = 105. Figura proveniente da Ref. [26]. . . . . . . . . . . . . . . . . . . 36

3.8 Dependência do expoente dinâmico β(η) com o parâmetro da qualidade η para o

caso de uma distribuição uniforme, ρ(η) = constante. Os círculos foram obtidos

por simulação numérica, enquanto a linha corresponde a predição analítica β(η) =

η/1, 255. Figura proveniente da Ref. [27]. . . . . . . . . . . . . . . . . . . . . . . 37

4.1 A distribuição de conectividades para o modelo homofílico (m = 1 e N = 105),

onde ambos os eixos estão em escala logarítmica. Ela segue uma lei de potência

P (k) ∼ k−λ, com γ = 2.84± 0.01, mostrando que a rede é livre de escala. . . . . . 41

4.2 (a) Dependência temporal da conectividade, ⟨ki (t, t0)⟩, para sítios com caracterís-

ticas η = 0.1, 0.5 e 0.8. Note que ⟨ki (t, t0)⟩ segue uma lei de potência em cada caso

e a inclinação cresce linearmente com η até o sítio apresentar característica igual a

0.5. Após esse valor, a inclinação decresce e é, aproximadamente, igual as de sítios

com características abaixo de 0.5. (b) O expoente dinâmico β como uma função de

η. Ele é obtido da inclinação de ⟨ki (t, t0)⟩ versus η (β é uniformemente distribuído,

m = 1 e N = 105). O valor máximo de β ocorre para η = 0.5 e é igual a 0.55, seu

valor mínimo é 0.37 em η=0.0 (ou η = 1.0), indicando que sítios com η ≈ 0.5 ad-

quirem, em média, mais conexões. Isso permite que sítios com características em

torno de 0.5 entrem na rede em um tempo posterior e, ainda assim, consigam um

maior número de ligações do que outros que já estão nela há muito mais tempo. . . 42

ix

5.1 Ilustração de como a generalização do modelo homofílico de escala livre cresce.

Em (a) o número inicial de sítios, mo, é dois. Na sequência em (b), (c) e (d), cada

sítio faz apenas uma nova ligação, m = 1, com um sítio pré-existente. Os valores

para a característica intrínseca de cada sítio são: η1 = 0, 5, η2 = 0, 1, η3 = 0, 6, η4 =

0, 2, η5 = 0, 4. Ao decidir onde estabelecer uma nova ligação (linha pontilhada), o

novo sítio prefere conectar-se com outro de características similares e com maior

número de conexões, conjuntamente. Figura proveniente da Ref. [20] . . . . . . . 47

5.2 Distribuição de conectividades cumulativa P (K) para modelo homofílico genera-

lizado LE (valores típicos σ, m0 = m = 1, N = 105, η, é distribuído uniformemente,

média tomada sobre 12000 realizações independentes) representada em escala lo-

garítmica. Segue a lei de potência. P (k) ∝ k−γ , com valores variando entre 2.84(2)

e 2.92(1). Este comportamento revela a ausência de valores típicos para a conecti-

vidade dos sítios. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 48

5.3 Dependência do expoente γ com σ (m0 = m = 1, N = 105, η, é uniformemente

distribuído, e com média acima de 12000 em realizações). Para σ = 0 o modelo

BA é recuperado; por outro lado, a rede homofílica de livre escala é alcançada por

σ = 1. Um resultado interessante é observado quando σ = 2, o expoente γ é mínimo. 49

5.4 Dependência temporal da conectividade média ⟨ki (t, t0)⟩, para sítios com η=0.1,

0.3, 0.5, 0.7 e 0.9 ( m0 = m = 1, N = 105, η é uniformemente distribuído e a

média é feita com 12000 realizações independentes). Comparações entre figuras

(a) e (b) mostram que ⟨ki (t, t0)⟩ segue a lei de potência em cada caso e o expoente

dinâmico β(η) é dependente de σ. Para altos valores de σ ou σ = 0, todos os sítios

aumentam sua conectividade no tempo como ⟨ki (t, t0)⟩ ∝ (t/t0)β onde β = 1/2

e t0 é o tempo em que o sítio i foi adicionado ao sistema, independente de sua

característica intrínseca. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 50

5.5 Dependência do expoente dinâmico β com η (m0 = m = 1, N = 105, η é uniforme-

mente distribuído e com média realizada sobre 12000 realizações independentes)

para σ = 0 (modelo BA), 2 e 10. O valor máximo de β é 0.55 em η = 0.5 e em σ = 2,

indicando que sítios com η em torno de 0.5 adquirem, em média, mais ligações.

Isso possibilita que sítios, com característica intrínseca em torno de 0.5, entrem na

rede um tempo depois e superem sítios que estão na rede por um tempo maior.

Para σ = 0 ou 10, o expoente β é o mesmo, consequentemente, todos os sítios são

igualmente bem sucedidos em adquirir ligações e independentes do tempo. . . . . 51

x

5.6 Simulação numérica do modelo homofílico generalizado LE (o tamanho da rede

foi fixado em 105 sítios, m0 = m, σ = 1 e média tomada sobre 12000 realizações

independentes): dependência do coeficiente de agregação C(k) com o número de

vizinhos k dos sítios para diferentes valores de α e m (número de ligações adici-

onadas a cada passo de tempo). O gráfico retrata que o coeficiente de agregação

apresenta dois comportamentos: (i) para valores menores que k ∼ 100, alto coefi-

ciente de agregação e uma lei de potência é observada; (ii) enquanto para valores

maiores que k ∼ 100, o coeficiente de agregação está estabilizado. Assim, isso

acontece independente do parâmetro α, mas é influenciado pelo parâmetro m. . . 53

5.7 O grau médio dos vizinhos de um sítio, < knn >, como uma função do grau k do

sítio. Ele mostra que a correlação do grau exibe mistura disassortativa. Os símbo-

los são resultados de simulação numérica do modelo homofílico generalizado LE

(o tamanho da rede foi fixado em 105 sítios, m0 = m, σ = 1 e média sobre 12000

amostras). . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 54

5.8 O grau médio < knn > dos vizinhos de um sítio como uma função da característica

intrínseca do sítio η. Os símbolos são resultados da simulação numérica do modelo

homofílico generalizado LE (o tamanho da rede foi fixado em 105 sítios, m0 = m,

σ = 1 e com média obtida de 12000 realizações independentes). Em cada gráfico

foram usados valores diferentes para α: (a) α = 0, isto é, a característica intrínseca

é distribuída uniformemente, (b) α = 1; (c) α = 2; (d) α = 10. Para α = 0 o

comportamento é simétrico e para valores maiores que α = 0 há uma quebra da

simetria em < knn >. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 55

5.9 A característica intrínseca média < ηnn > dos vizinhos de um sítio como uma fun-

ção da característica intrínseca do sítio η. As curvas são resultados da simulação

numérica do modelo homofílico generalizado LE (o tamanho da rede foi fixado em

105 sítios, m0 = m, σ = 1 e com média sobre 12000 realizações independentes). Em

cada gráfico, valores diferentes de α foram usados: (a) α = 0, ou seja, a caracte-

rística intrínseca é uniformemente distribuída; (b) α = 1; (c) α = 2; (d) α = 10.

Na proporção em que α aumenta, um salto aparece na característica intrínseca mé-

dia < ηnn > devido à distribuição não homogênea da característica intrínseca (Ver

equação 3). Note que o parâmetro m é independente em cada figura. . . . . . . . . 56

xi

SUMÁRIO

1 Introdução 1

2 Conceitos Fundamentais 4

2.1 O que são Redes? . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4

2.2 Distribuição de Conectividade . . . . . . . . . . . . . . . . . . . . . . . . . . 7

2.3 Menor Caminho Médio . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 8

2.4 Coeficiente de Agregação . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 9

2.5 Robustez . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 11

2.6 Correlações da Conectividade . . . . . . . . . . . . . . . . . . . . . . . . . . . 13

2.7 Redes Reais . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 15

2.7.1 6 graus de separação . . . . . . . . . . . . . . . . . . . . . . . . . . . . 15

2.7.2 Internet . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 17

2.7.3 World Wide Web . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 19

2.7.4 Rede de colaborações de atores de cinema . . . . . . . . . . . . . . . 20

2.7.5 Rede celular . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 21

3 Modelos de Redes Complexas 22

3.1 Modelo de Barabási - (BA) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 22

xii

3.2 Propriedades do Modelo de Barabási-Albert . . . . . . . . . . . . . . . . . . 26

3.2.1 Comprimento do Menor Caminho Médio . . . . . . . . . . . . . . . . 26

3.2.2 Coeficiente de Agregação . . . . . . . . . . . . . . . . . . . . . . . . . 27

3.3 Modelo de Bianconi - (BB) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 28

3.3.1 Modelo Livre de Escala . . . . . . . . . . . . . . . . . . . . . . . . . . 32

3.3.2 Distribuição de qualidade uniforme . . . . . . . . . . . . . . . . . . . 32

4 Rede Complexa Homofílica 38

4.1 Introdução . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 38

4.2 Modelo Homofílico . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 39

4.3 Resultados e Discussões . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 40

5 Generalização da Rede Complexa Homofílica 44

5.1 Introdução . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 44

5.2 Modelo Generalizado . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 45

5.3 Resultados . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 47

5.3.1 Resultados Topológicos . . . . . . . . . . . . . . . . . . . . . . . . . . 47

5.3.2 Resultados em Correlações . . . . . . . . . . . . . . . . . . . . . . . . 52

6 Conclusões 57

Referências Bibliográficas 59

xiii

CAPÍTULO 1

INTRODUÇÃO

Nas últimas décadas uma verdadeira revolução tem surgido na ciência, interdis-

ciplinarizando vária áreas aparentemente desconexas como Física, Biologia, Economia,

Informática, entre outros. Fenômenos com um alo grau de complexidade como os ob-

servados em avalanches, terremotos, batidas do coração, o funcionamento do cérebro, a

organização das estruturas linguísticas, o comportamento caótico das bolsas de valores,

o dobramento das proteínas, as informações codificadas do DNA, os processos de catá-

lise,entre outros, começam a ser entendidos, de uma forma unificada e lógica dentro de

um campo de pesquisa conhecido, atualmente, como Sistemas Complexos [1], com suas

várias áreas, como podemos citar caos, autômatos celulares, difusão anômala, percolação,

redes complexas. Nesta tese focaremos o estudo sobre as Redes Complexas.

Tradicionalmente o estudo em Redes Complexas tem sua origem na teoria dos

grafos. Os grafos são usados para descrever diferentes sistemas em uma forma compacta

e simples, facilitando o entendimento dos conceitos e propriedades inerentes do sistema e

do próprio modelo representação (grafo ou rede). A teoria dos grafos tem suas raízes no

século XVIII com o famoso problema das pontes de Konigsberg [2], solucionado por Euler.

Euler escreveu um curto artigo sobre um divertido problema que teve como palco Konigs-

berg, uma cidade não muito distante de sua casa. Devido a existência do rio Pregel e da

vocação da cidade para os negócios, uma vez que possuía uma frota muito requisitada

de navios, os mercadores locais e seus familiares podiam desfrutar de uma vida confortá-

1

Capítulo 1. Introdução 2

vel. As boas condições econômicas da cidade eram tais que os responsáveis pela mesma

construíram nada menos do que sete pontes em vários pontos da cidade. A maioria das

pontes, 5 de um total de 7, conectavam a elegante Ilha Kneiphof, cercada pelo rio Pregel,

com o restante da cidade. As outras duas pontes ligavam os outros pontos da cidade. A

população de Konigsberg, aproveitando o clima de harmonia e a paz da cidade, no tempo

livre se divertia com o seguinte quebra-cabeças: "É possível encontrar um caminho atra-

vessando as sete pontes sem nunca atravessar uma mesma ponte duas vezes?"Contudo,

ninguém foi capaz de encontrar um caminho que satisfizesse o quebra-cabeças até que

uma nova ponte fosse construída em 1875. Entretanto, quase 150 anos antes da constru-

ção da nova ponte, em 1736, Euler ofereceu uma rigorosa prova matemática dizendo que

não existia um caminho que passasse por todas as sete pontes uma única vez. Além de

resolver o problema das pontes de Konigsberg, Euler, de forma não intencional, iniciou

uma nova área da matemática conhecida como teoria dos grafos. Essa teoria é hoje a base

de todo nosso conhecimento sobre redes, conjunto de nós conectados por arestas. A partir

de Euler, outros estudiosos se dedicaram a compreender os vários tipos de grafos e como

se dava sua estrutura, ou seja, como seus nós se organizavam.

Desde os anos 50, grandes redes aparentemente sem princípios organizacionais

tem sido descritas através da Teoria dos grafos. Por volta de 1960, os matemáticos Paul

Erdos e Alfred Renyi fizeram as primeiras análises em Redes Complexas Aleatórias. No

modelo de Erdos-Renyi, começamos com N nós e todo par é conectado com probabilidade

p, criando uma rede com aproximadamente pN (N − 1)/2 ligações distribuídas aleatoria-

mente [3]. Baseado no modelo de Erdos-Renyi podemos indagar sobre uma questão: redes

reais se comportam de maneira aleatória? mais adiante discutiremos sobre essa questão e

sobre outros modelos utilizados para gerar redes complexas.

Nos últimos anos, várias redes reais têm sido estudadas pela comunidade cientí-

fica, sendo que algumas delas se tornaram famosas. Mark Newman propôs a classificação

das Redes Complexas da seguinte forma: tecnológicas, biológicas, sociais e de informação

[4]. Embora no passado as redes fossem vistas como objetos estruturais, com proprieda-

des fixadas no tempo, os novos estudos mostram que elas são na verdade elementos di-

nâmicos. Diferentes grandezas ou parâmetros são usados na descrição ou caracterização

das Redes Complexas, uma das maisa usadas é a distribuição de conectividade, que nos

informa como estão distribuidas as ligações entre os vértices da rede, em outras palavras

qual a probabilidade de que um vértice escolhido ao acaso tenha uma certa conectividade.

Pode-se expressar a distribuição de conectividade por P (k) ∼ k−γ onde o expoente γ tem

Capítulo 1. Introdução 3

valor, em geral, entre 2 e 3 [6]. Além dessa medida, pode-se caracterizar as redes reais

através de várias outras medidas, duas outras frequentemente usadas é o menor caminho

e o coeficiente de agregação (mede o número de triângulos presentes na rede), que estão

combinadas, definem a propriedade de mundo pequeno, amplamente discutido na tese.

É importante ressaltar que apesar de exibir várias medidas em redes, a distribuição de

conectividade em lei de potência é a mais discutida. De certa forma, P (k) ∼ k−γ , é um

dos motivos da diminuição do famoso modelo de Erdos-Renyi, modelo padrão durante

quase 30 anos.

A tese está organizada da seguinte forma: no segundo capítulo trataremos de re-

des, onde abordamos os conceitos básicos para a compreensão do estudo de redes, bem

como sua definição, representação e algumas propriedades topológicas, como distribui-

ção de conectividade, robustez, entre outras além de alguns exemplos de redes reais como

redes sociais, internet, entre outras. No terceiro capítulo serão apresentados os modelos

teóricos necessários para a fundamentação deste trabalho: o Modelo de Barabási e o Mo-

delo de Qualidade. No quarto capítulo iremos falar sobre o modelo Homofílico no qual é

baseado nosso trabalho. No quinto capítulo apresentaremos nossa contribuição, a Gene-

ralização do Modelo Homofílico, na sequencia apresentaremos os resultados obtidos. O

último capítulo é destinado as conclusões e perspectivas.

CAPÍTULO 2

CONCEITOS FUNDAMENTAIS

As Redes Complexas estão presentes em nosso dia a dia: Como por exemplo,

a rede mundial de computadores (a Internet), as redes sociais, redes de transmissão de

doenças, redes terroristas, entre outras. Mas o que é exatamente uma rede? Quais os

tipos de redes que existem? Quais são suas propriedades? O estudo da maioria das Redes

Complexas foi motivado pelo desejo de entender vários sistemas reais. Neste capítulo

revisaremos os conceitos fundamentais necessários para a compreensão desses sistemas e

mostraremos algumas características gerais de algumas redes reais.

2.1 O que são Redes?

De uma maneira bem simples, uma rede é um conjunto de vértices (sítios ou nós)

conectados entre si via linhas (ver Figura 2.1) (arestas ou arcos) [12], através de analogia,

podemos representar um sistema formado por pessoas, proteínas, a internet, aeroportos,

entre outros. Um sítio muito conectado é chamado de pólo ou "hub". Algumas caracte-

rísticas podem ser associadas aos sítios e as ligações da rede, como por exemplo, peso,

sentido, etc. No caso que as ligações sentido o sistema estudado é dito direcionado. Caso

contrário é dita não direcionada. Também podemos gerar redes através de um algoritmo

de crescimento assim existirá uma regra para estabelecer ligações entre os sítios.

4

Capítulo 2. Conceitos Fundamentais 5

O número total de conexões de um sítio é chamado de conectividade k. Na rede

com ligações dirigidas, o número de ligações que entram no sítio é chamado de conectivi-

dade de entrada ki, e o número de arestas que saem do vértice é chamado de conectividade

de saída k0. Dessa forma k = ki + k0.

Figura 2.1: Representação esquemática de uma rede. Figura proveniente da ref [16].

Um caso particularmente interessante sobre os grafos, diz respeito às árvores (ver

Figura 2.2). As árvores são um tipo de grafo em que existe, exatamente, um único caminho

ligando cada par de nós [13]. Podemos ainda dizer que uma árvore é uma rede sem

circuitos. Se uma árvore não tem partes separadas, é chamada árvore conectada. Uma

árvore conectada que contam N sítios possui L = N − 1 ligações. Em geral o número I de

circuitos num grafo conectado com ligações sem direção é relacionado ao número da suas

ligações e sítios por:

I = L+ 1−N (2.1)

Outro tipo interessante de rede são as redes aleatórias. Em termos gerais, redes

aleatórias podem ser definidas como sendo um arranjo desordenado de ligações [9, 11]. A

inerente aleatoriedade do sistema, associada a este processo, faz com que as ligações entre

os sítios nem sempre dêem origem ao mesmo arranjo, então dessa forma o conceito não

é tão simples assim. Para a Física Estatística, uma rede aleatória não é única, e sim uma

rede particular de um ensemble estatístico de todas as realizações possíveis, onde cada

realização tem seu peso estatístico.

Para os físicos as redes aleatórias podem ser: estáticas ou dinâmicas. Vamos in-

troduzir essas idéias mostrando alguns exemplos simples.

Exemplo de rede aleatória estática.


Figura 2.2: a) Representação da rede de Bethe. Este é um exemplo de uma rede tipo árvore. b)Exemplo de uma rede com presença de circuito de ordem n = 3, representado pelos nós em verme-lho e pelas ligações em azul. Essa rede possui número de nós N = 8 e número de ligações L = 8.Assim podemos determinar o número de circuitos, neste caso temos I = 1. Figura proveniente daref [16].

• O número total de vértices é fixado.

• Escolhe-se aleatoriamente o par de vértices que serão conectados.

Um dos primeiros exemplos desse tipo de rede ou grafo, foi proposto por Erdos e

Renyi em 1959 e é conhecido como grafo aleatório. Neste modelo, os nós são estatistica-

mente independentes e equivalentes.

Um exemplo de rede aleatória evoluindo no tempo é um grafo aleatório simples

crescendo através de adições simultâneas de vértices e arestas. O algoritmo deste grafo é:

• Em cada tempo, um novo vértice é adicionado ao grafo.

• Simultaneamente, um par de vértices escolhidos aleatoriamente são conectados por

uma aresta.

A característica desse tipo de rede é que as ligações não são distribuídas uniforme-

mente e consequentemente, existem nós muito mais conectados que outros. Nesse caso,

os nós, preferencialmente, mais conectados são os mais antigos. Se em algum momento

pararmos de aumentar o número de vértices, mas continuarmos com a adição aleatória de

arestas, então a rede tenderá para o "estado de equilíbrio"sem nunca chegar a este estado.


Isso é possível porque o número de ligações não desaparecem e, assim, a não homoge-

neidade da rede diminuirá. Um estado de equilíbrio pode ser aproximado somente se as

ligações mais antigas desaparecerem de tempo em tempo.

2.2 Distribuição de Conectividade

A distribuição de conectividade é a característica mais simples de uma rede po-

rém muito importante na classificação dos diferentes tipos de redes quanto a sua topolo-

gia. Portanto, a análise da distribuição é fundamental ao criar um modelo de rede, pois

esta determina a classe do grafo. Além do mais, em muitas situações o conhecimento

da distribuição de conectividade é suficiente para o entendimento da rede e o que está

acontecendo nela.

Em algumas Redes Complexas nem todos os nós vão apresentar a mesma cone-

ctividade. Observaremos que existem nós mais conectados que outros. Informações de

como a conectividade está distribuída entre os nós numa rede não direcionada é dada

pelo gráfico P (k), ou pelo cálculo dos momentos de distribuição. O momento de ordem

n é dado como:

⟨kn⟩ =∑k

knP (k) (2.2)

O primeiro momento é a conectividade média da rede [9, 11]. O segundo mo-

mento mede as flutuações da distribuição de conectividade.

(1) Distribuição de Poisson:

A distribuição de conectividade tipo Poisson é expressa pela Equação 2.3.

P (k) =e−⟨k⟩⟨k⟩k

k!(2.3)

onde ⟨k⟩ é a conectividade média [14]. Um grafo aleatório tem sua conectividade seguindo

uma distribuição de Poisson quando seu número de vértices tende ao infinito e sua cone-

ctividade média, ⟨k⟩, é fixa. Esse vínculo para ⟨k⟩ constitui a escala típica da distribuição.


(2) Distribuição tipo Lei de Potência:

A distribuição de conectividade tipo lei de potência é expressa pela Equação 2.4.

P (k) ∝ k−γ (2.4)

com k ̸= 0 e γ sendo o expoente da distribuição [14]. Ao contrário da distribuição de

Poisson, redes que possuem distribuição de conexões comportando-se como lei de potên-

cia não apresentam uma escala característica para sua conectividade. Essa “liberdade de

conexão” faz com que tais redes sejam chamadas de livre de escala.

(3) Distribuição Discreta:

Esse espectro de conectividade é típico de redes que crescem deterministicamente

[15]. As simulações desta tese tem distribuição discreta.

2.3 Menor Caminho Médio

Num grafo, conexões que ligam os vértices formam um caminho. Dados dois vér-

tices pode haver caminho entre eles, mesmo que estes não estejam diretamente conecta-

dos. O comprimento do menor caminho, ou caminho geodésico, é o caminho mais curto

entre dois vértices quaisquer. No caso de um grafo desconectado composto por mais de

um componente, o diâmetro é infinito uma vez que não pode ser possível estabelecer um

caminho entre os diversos componentes. Contudo, sempre é possível redefinir o diâmetro

do grafo como sendo o diâmetro máximo de seus agrupamentos.

A distância geodésica média entre pares de vértices de uma rede não direcionada

é dada pela Equação 2.5,

l =2

N(N − 1)

∑i>j

di,j (2.5)

onde di,j é a distância geodésica entre os vértices i e j. A média de di,j tomada sobre todos

os N(N − 1)/2 pares de vértices resulta no menor caminho médio l.

Alternativamente, pode-se estimar o valor de l numa rede aleatória do tipo árvore.

Para isso, partimos do pressuposto que a rede tenha conectividade média z. Sendo assim,


um sítio qualquer pode visitar, em média, outros z sítios afastados a uma distância de um

passo. Generalizando, pode-se falar que após l passos este sítio visitará outros zl sítios.

A estimativa da distância característica da rede, isto é, o menor caminho médio, é obtida

através da relação N ∼ zl. Dessa relação, chega-se a Equação 2.6.

l ≈ lnN

lnz(2.6)

Na expressão acima, o fato de l relacionar-se com lnN torna-se explícito o porquê

da pequena distância entre os pares de sítios na rede. Esta particularidade está presente

no comportamento de algumas redes reais e é, comumente, conhecida como “efeito de

mundo pequeno”.

2.4 Coeficiente de Agregação

O coeficiente de agregação de um vértice descreve a presença de conexões entre

os primeiros vizinhos dele [13].

Podemos definir o coeficiente de agregação da seguinte forma: Consideramos

uma rede com arestas sem direções e tomamos um vértice i que apresenta zi vizinhos

mais próximos. Observemos dentre o número total de vizinhos do vértice i quantos estão

ligados entre si. A agregação máxima do vértice i é obtida quando todas as z(z − 1)/2

arestas possíveis estão presentes conectando todos os seus primeiros vizinhos.

O coeficiente de agregação de um vértice i qualquer da rede é definido como

sendo a razão entre a quantidade total de arestas que conectam seus primeiros vizinhos

yi e o número máximo possível de arestas entre todos estes vizinhos mais próximos zi,

conforme a Equação 2.7.

Ci =2yi

zi(zi − 1)(2.7)

onde Ci, assume valores no intervalo 0 ≤ Ci ≤ 1. Quando Ci = 0 sabe-se que os vizinhos

do vértice i “não se conhecem” e, portanto, não estabelecem conexões entre si. No entanto,

quando Ci = 1 existem todas as conexões possíveis entre todos os primeiros vizinhos do

vértice i.


A Figura 2.3, ilustra um exemplo simples. Nesse exemplo, temos um nó i (símbolo

vermelho) conectado a seis primeiros vizinhos (símbolos pretos). Queremos determinar o

seu coeficiente de agregação. Para isso devemos verificar inicialmente, qual a vizinhança

de i e quantos dos seus primeiros vizinhos estão conectados entre si. Neste caso, podemos

ver que cinco dos seus seis vizinhos estão conectados (linhas verdes), ou seja, yi = 5 e o

número de conexões do sítio i é zi = 6. Assim é possível mostrar que o coeficiente de

agregação do nó i é Ci (zi) =13.

Figura 2.3: O conceito do coeficiente de agregração do sítio i é obtido quando conhecemos seusprimeiros vizinhos e sabemos como estes estão ligados entre si. Para esta figura temos zi = 6 eyi = 5 logo Ci (zi) =

13 . Figura proveniente da Ref [16].

O coeficiente de agregação de toda a rede, ou seja, o coeficiente de agregação

médio, é obtido fazendo a média dos Ci′s pelo número total de vértices, de acordo com a

Equação 2.8,

C =1

N

∑i

Ci =1

N

∑i

2yizi(zi − 1)

(2.8)

onde C expressa a probabilidade de existência de arestas entre os primeiros vizinhos de

um dado vértice escolhido aleatoriamente.


2.5 Robustez

Falhas aleatórias e ataques maliciosos em redes de larga escala e em crescimento,

como a Internet, podem causar danos em escala proporcionalmente grande - um ataque

a um único hub pode degradar o desempenho de milhões de conexões, podendo afetar a

rede como um todo.

Danos às redes podem ser causados por diversos fatores, entre eles, falhas e ata-

ques. Falhas ocorrem aleatoriamente, afetando um vértice independente de qualquer ca-

racterística específica. Por outro lado, ataques maliciosos têm alvos específicos, escolhi-

dos, possivelmente, devido a suas características (conectividade, pontos de articulação,

etc.) e podem obedecer a seqüências estratégicas.

Uma propriedade estática importante das redes é sua robustez. A robustez (ou

resiliência) de uma rede é medida pela sua capacidade em manter-se conectada frente à

remoção de alguns dos seus vértices. Existem diversas estratégias de remoção de vértices.

Essas estratégias são classificadas como estratégias locais ou globais. A estratégia local

mais simples, é a remoção aleatória. Nesta estratégia, todos os vértices são consultados e

removidos com uma probabilidade p uniforme e independente do estado (ativo/inativo)

dos seus vizinhos ou de seu grau de conectividade. De maneira geral, a remoção aleatória

pode ser associada a falhas esporádicas nos vértices que compõem uma rede.

Por outro lado, existe uma estratégia global que consiste em retirar os vértices

mais conectados, maximizando o número de conexões desativadas. Esta estratégia re-

quer que todos os vértices sejam classificados de acordo com seu grau de conectividade e

então, removidos da rede seguindo a ordem decrescente de graus de conectividade. Tal

estratégia é conhecida como ataque dirigido [16].

As redes livres de escala, por não possuírem uma escala típica, se comportam

diferentemente das redes aleatórias. A sua estrutura heterogênea permite que ela seja

robusta diante de ataques não dirigidos. Entretanto, esse tipo de rede se torna frágil se os

ataques contra elas são direcionados a seus pólos. É o que mostra as figuras 2.4 e 2.5.


Figura 2.4: Ataque aleatório. A figura 2.4 (a) mostra a estrutura da rede, a figura (b) mostra ossítios que vão ser atacados, (sítios amarelos), e a figura (c) mostra a estrutura da rede após o ataque,mostrando que a maior parte da rede ainda continua conectada. Isso significa que a rede é robustaa esse tipo de ataque.

Figura 2.5: Ataque dirigido. A figura 2.5 (a) mostra a estrutura da rede, a figura (b) mostraos sítios que vão ser atacados, (sítios amarelos), e a figura (c) mostra a estrutura da rede após oataque, mostrando que a rede se desfragmentou de forma rápida. Isso significa que a rede não érobusta a esse tipo de ataque.


2.6 Correlações da Conectividade

Sabemos que a distribuição de conectividade de uma rede fornece um panorama

geral a respeito das interconexões entre os sítios. Mas além da distribuição de conecti-

vidade, é possível caracterizar as redes pela presença de correlações [17]. Embora pa-

reça plausível que um sítio possa se conectar a outro independente das características do

segundo, isto não ocorre na maioria dos casos reais. É comum encontrarmos, em tais

sistemas, exemplos de padrões de conexões que se estabelecem pela preferência de nós

se conectarem com outros nós de características similares ou até mesmo opostas. Depen-

dendo das características dos nós, isso dá origem a vários tipos de correlações. Entretanto,

quando consideramos apenas a topologia da rede, o principal tipo de correlação é a cor-

relação grau-grau [17].

É importante ressaltar que todos os modelos de crescimento de redes estão corre-

lacionados, pois em processos de crescimento a presença de ligações entre os nós depende

da idade e do grau desses nós, e existe uma assimetria entre os nós mais jovens e os nós

mais velhos. Portanto as correlações sempre existem, entretanto depende do modelo do

sistema estudado.

Em termos de medidas, correlações grau-grau podem ser, teoricamente, expressas

por meio da probabilidade condicional P(k

′/k). Esta representa a chance de uma ligação,

escolhida ao acaso, conectar sítios de grau k′ e k ou, em outras palavras, representa a

probabilidade de que uma ligação aponte para um sítio de grau k′ , condicionada ao fato

que ela tem origem em um sítio de grau k . Do ponto de vista numérico, é mais conve-

niente caracterizar as correlações grau-grau pelo conceito de grau médio dos primeiros

vizinhos de um nó com conectividade k (brevemente chamado grau médio dos primeiros

vizinhos). Embora menos rigorosa, esta abordagem alternativa, para estudar correlações,

tem sido bastante usada na literatura e permite encontrar como nós de diferentes graus

estão interconectados. Para isso, toma-se como base o grau médio dos primeiros vizinhos

como uma função do grau k dos sítios ⟨knn,i (k)⟩

A fim de obter esta função, consideraremos um sítio i com grau ki, e calculamos o

grau médio dos seus vizinhos mais próximos, knn,i,


knn,i =1

ki

∑j∈V (i)

kj (2.9)

onde a soma se dá sobre todos os vizinhos do sítio i. Desta quantidade podemos obter a

função, ⟨knn,i (k)⟩ para analisar o comportamento das correlações de grau, que é formal-

mente definida como [18]:

⟨knn (k)⟩ =1

Nk

∑i/ki=k

knn,i (2.10)

em que Nk é o número de sítios com grau k e o somatório é feito sobre aqueles sítios com

conectividade ki = k.

A curva resultante desta função pode ser facilmente interpretada e é a base para

uma primeira classificação das redes complexas [19] via correlações de grau. Se ⟨knn (k)⟩for uma função crescente do grau k, a rede apresenta mistura assortativa por grau; isto

é, sítios altamente conectados estão, em média, ligados a vizinhos que também possuem

muitas conexões. Na situação oposta, quando ⟨knn (k)⟩ é uma função decrescente, a rede

analisada exibe mistura disassortativa, indicando que sítios com poucas conexões, em mé-

dia, têm vizinhança com sítios altamente conectados e vice-versa. Na ausência de correla-

ções, ⟨knn (k)⟩ é uma função constante, sugerindo que o grau dos vizinhos é independente

da conectividade do sítio em questão.

Podemos também inspecionar as correlações grau-grau, de uma rede, por meio

de uma outra quantidade, menos rigorosa que knn,i, mas que, historicamente, tem sido

amplamente usada pelos sociólogos. Ela é conhecida como coeficiente de correlação de

Pearson e tem a seguinte definição [11].

r =

⟨kk

′⟩l− ⟨k⟩l

⟨k

′⟩l

⟨k2⟩l − ⟨k⟩2l(2.11)

Aqui k e k′ são os graus dos nós das extremidades de uma ligação, e ⟨⟩l indica a

média sobre todas as ligações da rede. O coeficiente de Pearson é uma função de correla-

ção de par padrão, adequadamente normalizada de tal maneira que r varia no intervalo

[-1,1]. Claramente, se uma rede é descorrelacionada, então o coeficiente de Pearson é

nulo. Se, em média, sítios muito conectados têm vizinhança, também, muito conectada

(mistura assortativa), então r > 0, e assim, existe uma correlação positiva nas interco-


nexões da rede. Caso a rede tenha, em média, nós pouco conectados ligados a vizinhos

bastante conectados e vice-versa (mistura disassortativa), então r < 0, e uma correlação

negativa se faz presente.

Figura 2.6: Grau médio dos vizinhos mais próximos. Esta quantidade mede quão correlacionadosestá o grau médio dos primeiros vizinhos de sítios com conectividade k. Em (a) ⟨knn (k)⟩ crescecom a conectividade dos sítios, indicando a presença de correlações de grau positivas na rede(assortatividade). Em (b) mostra uma tendência decrescente de ⟨knn (k)⟩ o que significa que a redeé negativamente correlacionada (disassortatividade). Finalmente, em (c), com ⟨knn (k)⟩ constante,a rede é descorrelacionada. Figura proveniente da Ref [20].

2.7 Redes Reais

Para que se possa modelar um problema real em uma Rede Complexa, necessita-

se, antes de mais nada, identificar os elementos que a compõe e, sobretudo, saber como

tais elementos interagem. Nos anos recentes, isso vem sendo feito com vários sistemas

reais, objetivando-se assim, identificar e compreender suas características e/ou proprie-

dades topológicas. Procurando seguir essa lógica, veremos daqui por diante, exemplos

de sistemas reais que foram modelados sob a forma de redes e falaremos sobre algumas

características topológicas apresentadas pelas mesmas.

2.7.1 6 graus de separação

Em 1967, Stanley Milgram, um psicólogo social e professor em Harvard se lançou


em mais um de seus experimentos sociais. O objetivo de Milgram agora era encontrar a

distância entre duas pessoas quaisquer nos EUA. Para dar início a esse experimento duas

pessoas foram escolhidas como alvo. A primeira foi a esposa de um estudante de teologia

em Sharon, Massachusetts; e a segunda foi um corretor em Boston. O próximo passo foi

escolher as cidades de Wichita, no Kansas, e Omaha, no Nebraska, como ponto de partida

para o estudo.

O experimento de Milgram exigiu o envio de cartas para moradores, aleatoria-

mente escolhidos, de Wichita e Omaha pedindo a eles que participassem de um estudo de

contato social na sociedade americana. A carta continha informações sobre duas pessoas

escolhidas como alvos, junto com as seguintes instruções:

COMO PARTICIPAR DO ESTUDO

(1) Cada pessoa que receber o caderno deve adicionar seu nome nele. Isto

serve para rastrear de quem partiu o envelope, evitando que este volte para

uma mesma pessoa.

(2) Se você não conhece a pessoa alvo, não tente contactá-la diretamente. Ao

invés disso, repasse este caderno para alguém que você conhece e acredite que,

este, tenha maior chance de conhecer a pessoa alvo.

(3) Se você conhece a pessoa alvo, envie este documento diretamente para

ele(a).

(4) Ao enviar o caderno, cada pessoa deve retirar uma página dele, preenchê-

la e remetê-la ao cientista. Esta, sem dúvida, é uma fase muito importante do

estudo, pois ela permite, a Milgram, acompanhar o progresso da experiência

ao longo do trajeto do caderno até chegar a pessoa alvo. Nas mãos da pes-

soa alvo o caderno deve, agora, ser enviado ao Psicológo para a conclusão do

experimento.

A Figura 2.7 mostra o Mapa dos Estados Unidos e a Figura 2.8 mostra o resultado

final da experiência.

O resultado da experiência foi publicado na revista Psychology Today intitulado

como Problema de Mundo Pequeno [21] e revelou que o número médio de ligações entre a

pessoa inicial e o destinatário final, no caso das experiências que se completaram, era de

aproximadamente seis pessoas. Daí surgiu a expressão seis graus de separação.


Figura 2.7: Mapa dos Estados Unidos. Os estados em amarelo (Nebraska e Kansas) representama origem das correspondências e o estado em verde (Massachusetts) representa o destino final.Figura proveniente da Ref [20].

Figura 2.8: Esquema do experimento de Stanley Milgram. Figura proveniente da Ref [20].

2.7.2 Internet

A internet é o principal exemplo de redes com maior relevância tecnológica e

econômica. Ela é tida como uma enorme rede global de computadores e outros dispo-

sitivos de telecomunicação que são ligados entre si, por ou sem fios. Normalmente, a

estrutura da Internet é descrita em dois níveis distintos: um, trata a mesma a nível de

roteadores, sendo que os nós são os próprios roteadores e as ligações são conexões físi-

cas entre eles. O outro, a concebe a nível de domínios (sistemas autônomos), que são

sub-redes na Internet, composto por milhares de computadores e roteadores, os quais re-


presentam um único nó, onde a ligação se estabelece entre dois domínios se existir, pelo

menos, um roteador que os conecte.

Um aspecto de especial interesse, demonstrado pela Internet, está relacionado a

grande quantidade de nós que ela apresenta, quando comparada com outros sistemas re-

ais. Tal aspecto é importante do ponto de vista das análises estatistícas feitas na rede,

e estas revelaram que a Internet, tanto a nível de roteadores quanto de domínios, apre-

senta propriedades topológicas não triviais; entre elas, a distribuição de conectividade

comportando-se como lei de potência. Esse fato confere a Internet, a inclusão numa classe

de redes denominadas livres de escala.

Figura 2.9: Comportamento da distribuição de conectividade da Rede WWW. Figura provenienteda Ref [18].

Outras características da Internet, como menor caminho médio e coeficiente de

agregação, ratificam a inclusão dela nessa classe de redes. Pastor-Satorras et al [18], estu-

dando a Internet a nível de domínios, entre 1997 e 1999, obtiveram valores para o menor

caminho médio situados abaixo de 4. Estes são diferentes daqueles exibidos por grafos

aleatórios clássicos, quando têm-se o mesmo número total de vértices e conexões. Em

particular, para a Internet no ano de 1998, a relação entre o menor caminho l̄/l̄rand era de

0.6 .

A indicação desse valor para l significa que, dados em torno de 4 passos, pode-se


alcançar a maioria dos vértices e isso faz a Internet exibir o caráter de mundo pequeno. A

nível de roteadores, o menor caminho médio é l̄ ≈ 10 , valor ligeiramente menor do que o

de seu correspondente grafo aleatório clássico.

2.7.3 World Wide Web

A WWW é uma coleção de webpages armazenadas em muitos servidores ao redor

do mundo. Estas páginas são acessadas usando um protoloco de comunicação conhecido

como HTTP (Hyper Text Transfer Protocol). Este processo dita os detalhes de pedido en-

viado pelo cliente para uma certa página. A WWW é uma das maiores redes para o qual

as informações topológicas estão atualmente disponíveis. Os nós da rede são representa-

dos pelos documentos (webpages) e as ligações são representadas por hyperlinks (URLs)

que apontam de um documento para outro. Devido à importância que a WWW tem no

cotidiano das pessoas (informação, marketing, pesquisa...), tem crescido muito o interesse

por pesquisa desse sistema.

As ligações na WWW são direcionadas, portanto a rede é caracterizada por dois

tipos de distribuição: a distribuição de conectividade de saída e entrada do nó, Pout (k),

Pin (k) respectivamente. Estudos tem mostrado que ambas as distribuições tem uma cauda

em lei de potência. Para um subconjunto da rede WWW com N = 32579 o expoente carac-

terístico da distribuição encontrado em 1999 [6] foi γin = 2.1 e γout = 2.45. Posteriormente

Broder et al, em 2000 [22], calcularam o expoente γin e γout da distribuição e verificaram

que, para uma amostra de 200 milhões de documentos, γin = 2.1 e γout = 2.72 mostrando

uma constância no γin um aumento no γout. Apesar do grande número de nós, a WWW

exibe propriedades de pequeno mundo, a qual apresenta um menor caminho médio dado

por l̄ = 11.2.


Figura 2.10: Distribuição de links saindo (a) e entrado (b) em uma Web page. Em (c), menorcaminho médio como uma função do tamanho da rede. Figura proveniente da Ref [17].

2.7.4 Rede de colaborações de atores de cinema

Uma base de dados muito estudada é a rede de colaboração de atores de cinema,

baseada no banco de dados que tem na Internet sobre cinema, que contém todos filmes e

seus elencos desde 1890. Nesta rede, os nós são atores, e dois nós são ligados se os atores

correspondentes atuarem no mesmo filme. Esta é uma rede em expansão contínua [23],

com 225226 nós em 1998, que cresceu para 449913 nós até maio de 2000. O menor caminho

médio de atores da rede é próximo ao de um grafo aleatório com o mesmo tamanho e

conectividade média, 3, 65 comparado com 2, 9, mas seu coeficiente de agregação é cem

vezes maior que a do grafo aleatório. A distribuição de conectividade da rede de atores de


filme é uma lei de potência para k grande, que segue P (k) ∼ k−γator , onde γator = 2, 3±0.1.

Ver figura 2.11.

Figura 2.11: Rede de colaborações de atores de cinema com 212250 ⟨k⟩ = 28, 78 e γator = 2, 3.Figura proveniente da Ref. [23].

2.7.5 Rede celular

Jeong et al. (2000) [24], estudaram o metabolismo de 43 organismos, representa-

dos em três domínios da vida, e organizaram numa rede em que os nós são os substratos

(como ATP, ADP, H2O) e a conexão representa a direção predominante da reação química

em que esses substratos podem participar. A distribuição de saída e de entrada é em lei de

potência para todos organismos, com o expoente variando entre 2, 0 e 2, 4. O coeficiente de

agregação não foi calculado e quanto ao menor caminho médio foi 3, 3 aproximadamente

para todos organismos.

Outra rede importante caracterizando a célula, descreve as interações proteína-

proteína, onde os nós são proteínas. O estudo dessa interações físicas mostram que a

distribuição de conectividade destas seguem uma lei de potência com uma cauda expo-

nencial cortada P (k) ∼ (k + k0)−γek+k0/kc com k0 = 1, kc = 20 e γ = 2, 4 [25].

CAPÍTULO 3

MODELOS DE REDES COMPLEXAS

3.1 Modelo de Barabási - (BA)

Os modelos discutidos até agora possuem um número fixo N de vértices que são

aleatoriamente conectados ou reordenados. Já no modelo de Barabási e Albert, a rede

cresce com a adição contínua de novos sítios [6]. Começam com um pequeno número de

sítios e com o passar do tempo, o número de sítios aumenta durante a idade da rede por

adições sucessivas de sítios novos.

Baseado nos dois princípios fundamentais: crescimento contínuo e conexão pre-

fencial, Barabási e Albert propuseram o modelo decorrente das seguintes regras:

(1) Inicia-se a rede com m0 sítios.

(2) A cada passo de tempo é adicionado um novo sítio. Esse sítio é conectado

com outros m (≤ m0) sítios do aglomerado da rede pré-existente.

(3) A probabilidade de uma conexão ser feita com um determinado sítio i é

proporcional a ki e é dada por l

22

Capítulo 3. Modelos de Redes Complexas 23

Π(ki) =ki∑j

kj(3.1)

(4) Repete-se as operações (2) e (3) até o tamanho desejado e após t passos de

tempo, a rede terá N = m0 + t sítios e mt ligações.

Tratamento contínuo: Foi introduzido por Barabási, Albert e Jeong [6] com o in-

tuito de calcular a dependência temporal da conectividade ki, de um dado sítio i. Essa

conectividade ki cresce à medida que novos sítios entram na rede e ligam-se ao sítio

i, sendo a probabilidade desse processo Π(ki). Admitindo que ki é uma variável real e

contínua, a taxa de variação temporal com que ki muda, deve ser proporcional a Π(ki).

Consequentemente ki satisfaz a Equação dinâmica m.

∂ki∂t

= mΠ(ki) = mki

N−1∑j=1

kj

(3.2)

Observando que a soma no denominador não considera os sítios que estão sendo

introduzidos na rede e que cada ligação é simétrica e por isso contada duas vezes, notemos

que no limite t → ∞, a soma é dada pela Equação n.

N−1∑j=1

kj = 2(mt−m) ⇒ 2mt (3.3)

A simples substituição da Equação n em 3.2, leva a Equação o.

∂ki∂t

=ki2t

(3.4)

Sabendo que o sítio i é adicionado na rede no tempo ti com o número inicial de

conexões ki = m, a solução da Equação o com a condição inicial ki(ti) = m é dada pela

Equação p.

ki(t) = m

(t

ti

)β

com β =1

2. (3.5)


A Equação p mostra que a conectividade de todos os sítios evolui da mesma forma

e segue uma lei de potência, com expoente bem definido. Como mostra a Figura 3.1.

Figura 3.1: A figura mostra a evolução temporal da conectividade para o modelo BA. Figuraproveniente da Ref. [26].

Usando a Equação p, podemos escrever a probabilidade de um nó ter uma cone-

ctividade ki(t) menor que k, P [ki(t) < k], dada pela Equação q.

P

[mtβ

tβi< k

]= P

[tβi >

mtβ

k

]= P

[ti >

m1β t

k1β

](3.6)

A incorporação de novos sítios na rede se dá em intervalos de tempos iguais.

Logo, os valores ti obedecem a uma densidade de probabilidade constante, dada pela

Equação r,

P (ti) =1

m0 + 1(3.7)

substituindo esta na Equação q obtém-se a Equação s.

P

[ti >

m1β t

k1β

]= 1− m

1β t

k1β (m0 + t)

. (3.8)


A distribuição de conectividade P (k) pode ser obtida usando a Equação t.

P (k) =∂P [ki(t) < k]

∂k=

2m1β t

m0 + t

1

k1β+1

. (3.9)

No limite, t → ∞, temos a Equação u,

P (k) ∼ 2m1β k−γ, (3.10)

onde o expoente da lei de potência é dado por:

γ =1

β+ 1 = 3, com β =

1

2. (3.11)

Esse valor concorda muito bem com os resultados numéricos ver Figura 3.2.

Figura 3.2: Distribuição de conectividade do modelo de Barabási-Albert. Figura proveniente daRef. [26].

Como as leis de potência são observadas em várias redes reais, e estas descre-

vem sistemas de tamanhos bastante diferentes, é esperado, então, que um modelo correto

forneça uma distribuição de conectividade independente do tempo. Realmente, a Equa-


ção t prevê que assintoticamente a distribuição de conectividade, do modelo de Barabási-

Albert, independe do tempo (e do tamanho da rede N = m0 + t), indicando que, apesar

do crescimento contínuo, a rede atinge um estado estacionário livre de escala.

3.2 Propriedades do Modelo de Barabási-Albert

Embora o modelo de Barabási-Albert apresente distribuição de conectividade com

cauda em lei de potência, ele tem outras propriedades que podem concordar ou não com

os resultados empíricos das redes reais. Como discutido no capítulo anterior, uma caracte-

rística marcante de algumas redes reais é a coexistência da alta agregação com o pequeno

comprimento do caminho médio (efeito de mundo pequeno). Dessa forma, precisamos

investigar se a rede gerada pelo modelo de Barabási-Albert possui o caráter de mundo

pequeno.

3.2.1 Comprimento do Menor Caminho Médio

A Figura 3.3 mostra a comparação entre o comprimento do menor caminho médio

da rede de Barabási-Albert e de uma rede aleatória. Para efeitos de comparação, a cone-

ctividade média, ⟨k⟩ = 4 e o tamanho da rede N . O gráfico ilustra que o comprimento do

menor caminho médio no modelo de Barabási-Albert é menor que o de uma rede aleató-

ria, para qualquer valor de N . Ou seja neste modelo a rede é mais coesa e o comprimento

do menor caminho médio da rede de Barabási-Albert cresce logaritmicamente com N de

acordo com a Equação tt.

l = A ln(N −B) + C (3.12)

O fato de crescer logaritmicamente com N , expressa que este sistema possui efeito

de mundo pequeno como mostra a Figura 3.3.


Figura 3.3: Gráfico do menor caminho médio l pelo tamanho da rede N , no modelo de Barabási-Albert com ⟨k⟩ = 4, comparado com um grafo aleatório de igual tamanho e mesma conectividademédia. Figura proveniente da Ref. [13].

3.2.2 Coeficiente de Agregação

A Figura 3.4 mostra o coeficiente de agregação da rede de Barabási-Albert e para

um grafo aleatório, Crand ≃ ⟨k⟩/N , ambos com a mesma conectividade ⟨k⟩ = 4 e tamanhos

diferentes. O coeficiente de agregação da rede livre de escala é cerca de cinco vezes maior

que o de um grafo aleatório, e diminui lentamente com o crescimento da rede. Além do

mais o coeficiente de agregação da rede livre de escala segue uma lei de potência C ∼N−0.75, enquanto o outro é dado por C ≃ ⟨k⟩N−1 .


Figura 3.4: Coeficiente de agregação versus o tamanho da rede do modelo de Barabási-Albertcom ⟨k⟩ = 4, comparado com o coeficiente de agregação de um grafo aleatório, Crand ≃ ⟨k⟩/N .Figura proveniente da Ref. [13].

3.3 Modelo de Bianconi - (BB)

No sentido de fornecer um modelo simples que nos permita investigar, em termos

quantitativos, o aspecto competitivo das redes reais, Bianconi e Barabási adicionaram na

ligação preferencial um fator de qualidade ηi, para cada sítio da rede. Levando-se em

consideração que a existência de uma qualidade modifica a ligação preferencial dos sí-

tios, ao competir por ligações, encontraremos que sítios com diferentes qualidades terão

ritmos distintos para sua evolução de conectividade. Em outras palavras, a dependência

temporal da conectividade dos sítios continuará, como no modelo de Barabási-Albert, se-

guindo uma lei de potência (ki(t) ∼ tβi). Entretanto, o expoente dinâmico βi dependerá

da qualidade do nó.

Para gerarmos uma rede segundo o Modelo de Bianconi-Barabási utilizaremos o

algoritmo abaixo:


(1) Inicia-se a rede com m0 sítios, onde cada um deles possui um parâmetro de

qualidade η. A qualidade é escolhida aleatoriamente respeitando uma distribuição de

qualidade ρ(η) (que se mantém constante ao longo do tempo).

(2) A cada passo de tempo é adicionado um novo sítio que já possui um parâmetro

de qualidade η, escolhido a partir da distribuição de qualidade (passo 1). Esse novo sítio

é, então, conectado com outros m (≤ m0) sítios do aglomerado da rede pré-existente.

(3) A probabilidade do novo sítio se conectar com um sítio i, que já está presente

na rede, é proporcional a conectividade ki e a qualidade ηi desse sítio i, e é dada pela

Equação xx.

Πi =ηiki∑j

ηjkj. (3.13)

(4) Repete-se as operações (2) e (3) até o tamanho desejado. Para tempos bastante

longos, t → ∞, a rede terá N = m0 + t sítios e mt ligações.

Essa generalização da ligação preferencial, incorpora a combinação mais simples

possível que a qualidade e conectividade presentes determinem a taxa com que novas

ligações são adicionadas a um dado sítio, isto é, possibilita ao sítio relativamente mais

jovem que possui algumas ligações obter uma alta taxa de conexões. Para isso basta ter

um grande parâmetro. Sendo assim o mesmo pode ter a chance de vir a ser um pólo.

Com o desejo de discutir as propriedades de escala do modelo acima, em primeiro

lugar, utilizaremos a teoria contínua que permite-nos prever a distribuição de conectivi-

dade. Os detalhes sobre a teoria contínua foram tratados na seção 3.1. Um sítio i aumen-

tará sua conectividade ki, numa taxa que é proporcional a probabilidade do novo sítio

ligar-se a ele, de acordo com a Equação hh

∂ki∂t

= mηiki∑j

ηjkj. (3.14)

O fator m retrata o fato de que cada novo sítio, adicionado na rede, incrementa m

ligações ao sistema. Um caso particular é ρ(η) = δ(η − 1), onde todas as qualidades são

iguais. Substituindo essa distribuição na Equação hh encontra-se o modelo de Barabási-

Albert que prediz ki(t) ∼ t1/2. Naturalmente, para resolver a Equação 3.14 Bianconi e

Barabási, assumiram que, similarmente ao modelo livre de escala, a evolução temporal


da conectividade dos nós ki segue uma lei de potência. Entretanto, haverá multiescala no

sistema, pois o expoente dinâmico dependerá da qualidade ηi do sítio em questão, logo

kηi(t, t0) = m

(t

t0

)β(ηi)

, (3.15)

onde t0 é o tempo em que o nó i foi incorporado ao sistema. Um outro aspecto, a ser

observado, é que o expoente dinâmico, β(η), é limitado no intervalo 0 < β(η) < 1, pois

um sítio sempre aumenta o número de ligações no tempo (β(η) > 0) e sua conectividade,

ki(t), não pode aumentar mais rapidamente que t (β(η) < 1). Agora, calcularemos a média

da soma∑

j ηjkj . Considerando que cada sítio seja "criado"num tempo diferente de t0, a

soma sobre j pode ser escrita como uma integral em t0.

=

∫dη ρ(η)η mtβ(η)

∫ t

1

dt0

tβ(η)0

=

∫dη ηρ(η)m

(t− tβ(η))

1− β(η). (3.16)

Já que β(η) < 1, no limite em que t → ∞, tβ(η) pode ser desprezado quando

comparado com t, dessa forma, obtemos

⟨∑j

ηjkj

⟩= Cmt(1 +O(t−ϵ)), (3.17)

onde

ϵ = (1− maxβ(η)) > 0,

C =

∫dη ρ(η)

η

1− β(η). (3.18)

Usando a Equação qual05, e a notação kη = kηi(t, t0), a Equação dinâmica hh pode

ser escrita como,

∂kη∂t

=ηkηCt

, (3.19)


a qual tem uma solução da forma (qual03), onde

β(η) =η

C, (3.20)

confirmando, assim, a natureza auto-consistente da suposição da Equação (qual03). Note-

mos que β(η) depende de C e, logicamente, dependerá de ρ(η). Desse modo, precisamos

determinar o valor de C. Na Equação (qual06), substituimos β(η) por η/C, o que resulta

em

1 =

∫ ηmax

0

dηρ(η)1

Cη− 1

, (3.21)

onde ηmax é a máxima qualidade possível no sistema. Aparentemente a Equação (qual09)

é uma integral com uma singularidade. Porém, como β(η) = η/C < 1 para qualquer valor

de η, temos C > ηmax, dessa forma, o limite de integração nunca atinge essa singularidade.

Note que, se∑

j ηjkj ≤ ηmax

∑j kj = 2mtηmax, temos, usando a Equação (qual05), que

C ≤ 2ηmax.

Finalmente, podemos calcular a distribuição de conectividade P (k), que fornece

a probabilidade de um sítio ter k ligações. Se existisse um único expoente dinâmico β,

a distribuição de conectividade seguiria a lei de potência P (k) ∼ k−γ , onde o expoente

da conectividade é dado por γ = 1/β + 1. Entretanto, no modelo de Bianconi-Barabási,

temos um espectro de valores para o expoente dinâmico β(η) e, dessa forma, P (k) será

obtida pela média de diferentes leis de potência. Para encontrar P (k) precisamos calcular

a probabilidade acumulada para um certo sítio, kη > k, logo

P [kη(t) > k] = P

[t0 < t

(m

k

) ηC]

= t

(m

k

)Cη

(3.22)

onde a distribuição de probabilidade, isto é, a probabilidade que um sítio tenha k ligações,

é dada pela integral,


P (k) =

∫ ηmax

0

dη∂P [kη(t) > k]

∂t

∝∫ ηmax

0

dη ρ(η)C

η

(m

k

)Cη+1

(3.23)

a qual depende da escolha da distribuição de qualidade ρ(η).

Dada a distribuição de qualidade ρ(η), a teoria contínua permite-nos prever a di-

nâmica da rede, descrita através do expoente dinâmico β(η) (Equações qual08 e qual09),

e a topologia, caracterizada pela distribuição de conectividade P (k) (qual11). Para de-

monstrar a validade destas previsões, a seguir calcularemos essas quantidades para dois

casos: No primeiro utilizaremos uma distribuição de qualidade que recupera o modelo

livre de escala (modelo de Barabási-Albert); e no segundo usaremos uma distribuição de

qualidade uniforme.

3.3.1 Modelo Livre de Escala

O Modelo de Barabási-Albert é um dos mais simples (ligação preferencial de-

pende apenas da conectividade dos sítios) e apresenta todos os sítios com a mesma qua-

lidade (note que se ηi = constante, da Equação obtêm-se a Equação dinâmica do modelo

de Barabási-Albert). Dessa forma, podemos representar a distribuição de qualidade desse

modelo da seguinte maneira, ρ(η) = δ(η − 1) que inserindo na Equação 3.21, encontra-

mos C = 2, que indicará o maior valor possível para C. Usando a Equação 3.20, obtemos

β = 1/2 e da Equação 3.23 chegamos a P (k) ∼ k−3; a bem conhecida relação do modelo

livre de escala que foi tratada na seção 3.1. Podemos notar que o modelo de Barabási-

Albert representa um caso limite do modelo de qualidade considerado na seção anterior,

com o expoente da conectividade possuindo o maior valor possível.

3.3.2 Distribuição de qualidade uniforme

É mais interessante analisarmos o comportamento de um sistema quando neste


existem sítios com diferentes qualidades competindo por ligações (modelo de Bianconi-

Barabási). Para conseguir essa dinâmica insere-se na Equação 3.23 uma distribuição de

qualidade uniforme. Esta é obtida quando as qualidades são escolhidas uniformemente

do intervalo [0, 1], ou seja, ρ(η) = constante. Com isso, é possível observar diferentes

valores para o expoente dinâmico β (múltiplas escalas). A constante C pode ser determi-

nada da Equação 3.21. Fazendo uma mudança de variável apropriada, onde y = C − η e

dy = −dη, teremos

1 =

∫ C

C−1

dy(C − 1)

y. (3.24)

Essa integral fornece a seguinte expressão

exp(−2/C) = 1− 1/C, (3.25)

a partir da qual encontra-se C∗ = 1, 255. De acordo com a Equação 3.20, cada sítio terá um

expoente dinâmico diferente dado por β(η) ∼ ηC∗ . Utilizando a Equação 3.23, teremos

P (k) ∝∫ 1

0

dηC∗

η

1

k1+C∗/η∼ k−(1+C∗)

log(k), (3.26)

isto é, a distribuição de conectividade segue uma lei de potência generalizada, com um

logaritmo inverso. A validade da teoria contínua para o modelo de Bianconi-Barabási foi

verificada através de simulações númericas. Para a verificação, utilizou-se uma distribui-

ção de qualidade uniforme, onde as qualidades foram escolhidas com igual probabilidade

do intervalo [0, 1]. O maior interesse era testar a validade da Equação 3.15, já que ela pre-

via o comportamento da evolução temporal da conectividade dos sítios com diferentes

parâmetros de qualidades η.

Na figura 3.5 têm-se a constatação de que ki(t) segue uma lei de potência para

todos η. Já na Figura 3.8, vemos que o expoente de escala β(η) depende de η, sendo maior

para nós com maior qualidade. A Equação 3.17 prevê que a soma ⟨∑

i ηiki⟩/mt → C∗ no

limite t → ∞, onde C∗ é dado pela Equação 3.25 sendo C∗ = 1.255, como indicado na

Figura 3.6. Por fim, na Figura 3.7 vemos a concordância entre a predição da Equação 3.26

e os resultados numéricos para a distribuição de conectividade P (k).

Na figura 3.7 tem uma característica muito interessante quando olhamos o com-

portamento dos sítios a nível de ligações feitas durante a evolução da rede. Observamos


neste a existência de alguns sítios que possuem uma alta conectividade ("hubs ou pólos")

e aparecem como uma longa linha horizontal num gráfico log-log, sendo encontrados em

vários sistemas reais, incluindo a rede WWW e a rede metabólica das células. Isso indica

que "super pólos"é uma característica de sistemas competitivos.

Figura 3.5: Simulação numérica para uma rede com m = 1 e com N = 105, mostrando a depen-dência temporal da conectividade kη (t), para sítios com qualidade η = 0.3, 0.6, 0.9. Note que emcada caso kη (t) segue uma lei de potência e o expoente dinâmico β (η), dado pela inclinação dek (t), aumenta com η. Figura proveniente da Ref. [27].


Figura 3.6: Comportamento assintótico de C com t → ∞, note que há acordo com a previsãoanalítica, linha tracejada, (Equação 3.25). Figura proveniente da Ref. [27].


Figura 3.7: Distribuição de conectividade no modelo de qualidade, obtida para uma rede comm = 1 e N = 105. Figura proveniente da Ref. [26].


Figura 3.8: Dependência do expoente dinâmico β(η) com o parâmetro da qualidade η para ocaso de uma distribuição uniforme, ρ(η) = constante. Os círculos foram obtidos por simulaçãonumérica, enquanto a linha corresponde a predição analítica β(η) = η/1, 255. Figura provenienteda Ref. [27].

CAPÍTULO 4

REDE COMPLEXA HOMOFÍLICA

4.1 Introdução

É de conhecimento geral que o processo de formação de conexões, entre os sítios

de uma rede, é influenciado por diferentes aspectos. Por exemplo, no modelo proposto

por Barabási-Albert (BA), a idade dos sítios dá origem ao efeito de vantagem cumulativa,

fazendo que os sítios mais velhos tenham uma alta conectividade e recebam mais cone-

xões à medida que a rede cresce. Esta dinâmica é garantida pela chamada regra de ligação

preferencial do modelo, a qual inevitavelmente produzirá correlações e uma assimetria

entre a conectividade dos sítios mais jovens e os sítios mais velhos. Estes, invariavelmente,

serão os sítios mais conectados da rede e, de certo modo, são os responsáveis diretos pela

cauda em lei de potência para a distribuição de conectividades.

Já no modelo elaborado por Bianconi-Barabási (BB), além da conectividade dos

sítios, outro aspecto, presente na ligação preferencial, que desempenha um papel impor-

tante na formação de ligações é conhecido como qualidade. Ele simboliza a qualidade

intríseca dos sítios e pode representar, por exemplo, o contéudo de uma web page na

WWW ou o talento de um ator na rede de atores de filmes. Dependendo do parâmetro da

qualidade um sítio jovem pode adquirir, em um intervalo de tempo relativamente curto,

uma quantidade significativa de ligações, ultrapassar sítios mais velhos e eventualmente

torna-se um pólo da rede.

38

Capítulo 4. Rede Complexa Homofílica 39

É sabido que, em muitas redes reais, os sítios possuem suas próprias característi-

cas que, dependendo do contexto, podem ganhar diferentes interpretações. Por exemplo,

em redes sociais, a cada indivíduo pode ser atribuído idade, gênero, etnia, nível de esco-

laridade ou outros parâmetros que representam suas demais preferências; na rede de in-

teração de proteínas, cada proteína é caracterizada por suas funções biológicas; na WWW

as web pages são classificadas com base em seu conteúdo. Para estas, e para muitas outras

redes, as evidências empíricas indicam que um fator que desempenha papel fundamental

para a adição de novas ligações entre sítios é a similaridade entre as características dos

mesmos.

Semelhanças nas características de pessoas, por exemplo, elevam a probabilidade

para que se estabeleçam vínculos entre elas. Tanto é assim que observamos facilmente

como pessoas tendem a se relacionar por compartilharem a mesma fé, mesmo time de

futebol, por gostarem do mesmo cantor e etc.

Em todas as situações mencionadas anteriormente, as chances de formação de co-

nexões aumentam mediante o partilhamento de algo comum entre os entes. Esta tendên-

cia para se estabelecer ligações entre aqueles de características semelhantes é conhecida

como homofilia.

4.2 Modelo Homofílico

Os exemplos discutidos anteriormente enfatizam que as diferentes características

dos sítios são, digamos, as suas habilidades para competir por ligações. No entanto, estas

são mais acentuadamente favorecidas entre constituintes similares. Para levar em conta

esta tendência, foi introduzido um termo chamado similitude ver Ref. [38], Aij = |ηi − ηj|,onde ηi e ηjrepresentam, respectivamente, as características intrísecas dos sítos i e j. Ob-

serve que o termo de similitude favaorece o contato entre os sítios de características simi-

lares com um taxa muito maior do que entre aqueles de características dissimilares.

O algoritmo do modelo é descrito abaixo

Primeiro passo: Começamos com a rede contendo m0 sítios, onde as características

de cada um deles estão reunidas no parâmetro ηi, o qual tem valor inalterado no tempo e é

extraído, uniformemente ao acaso, do intervalo entre 0 e 1. Segundo passo: A cada passo


de tempo um novo sítio j, com ηj aleatoriamente escolhido dentro do intervalo definido

como no passo anterior, conecta-se com outros m sítios pré-existentes por novas ligações

não direcionadas e não ponderadas. Terceiro passo: As novas conexões são estabelecidas

considerando que a probabilidade de formação de ligações depende da conectividade do

sítio i, ki e da similitude Aij e é dada por∏i

(1−Aij)ki∑i(1−Aij)ki

. Quarto passo: Este procedimento

é usado para incluir o (m0 + 1)-ésimo sítio, o (m0 + 2)-ésimo sítio, e assim por diante. O

processo de crescimento da rede é sequencialmente repetido até o tamanho desejado para

o sistema (N = t+m0) onde t é a variável temporal.

4.3 Resultados e Discussões

Na Figura 4.1 mostramos uma das mais importantes propriedades da rede gerada

pelo modelo homofílico - a distribuição de conectividade. Seu comportamento (gráfico in-

terno da Figura 4.1) revela algo interessante: a maioria dos sítios possui um baixo número

de primeiros vizinhos, porém existe uma cauda significativa para a distribuição, corres-

pondendo aos sítios de conectividades, substancialmente, maiores. Este fato confere, a

rede homofílica, uma forte heterogeneidade nos padrões de conexões entre seus sítios, o

que, de uma forma mais simples, se traduz na ausência de uma valor típico para a cone-

ctividade dos mesmos.

Outra característica interessante (Figura 4.1), aparece quando se usa escala loga-

rítmica em ambos os eixos. Esta situação indica que a cauda da distribuição obedece uma

lei de potência, P (k) ∼ k−λ, com γ = 2.84± 0.01, mostrando que a rede é livre de escala.

A dinâmica da rede homofílica, ou melhor, a evolução de sua estrutura pode ser

razoavelmente compreendida, observando que a própria ligação preferencial do modelo

já tem, inerentemente, incorporada em si mesma o fato das ligações se formarem, com

maior probabilidade, entre novos sítios e aqueles outros, que conjuntamente, apresentem

grande número de primeiros vizinhos e alta similaridade entre suas características. Dentro

desse contexto, um resultado bastante interessante é visto na Figura 4.2(a). Seu gráfico

mostra a dependência temporal da conectividade dos sítios ⟨ki (t, t0)⟩. Mais precisamente,

ele nos informa como assintoticamente cresce com o tempo t/t0, sendo o t0 instante em que


Figura 4.1: A distribuição de conectividades para o modelo homofílico (m = 1 e N = 105), ondeambos os eixos estão em escala logarítmica. Ela segue uma lei de potência P (k) ∼ k−λ, comγ = 2.84± 0.01, mostrando que a rede é livre de escala.

o sítio i entrou na rede. A função ⟨ki (t, t0)⟩ cresce com o tempo

⟨kηi (t, t0)⟩ ∝(

t

t0

)β

com o expoente dinâmico β, indicando a taxa com que os sítios adquirem ligações. Os

valores do expoente dinâmico β são limitados, 0 < β < 1, por que à medida que o tempo

passa um dado sítio sempre aumenta o número de ligações (β > 0), no entanto ele não

recebe mais que uma ligação em cada passo de tempo (β < 1). Outro fato que chama

atenção sobre a limitação do valores de β está relacionado com as leis de potências associ-


Figura 4.2: (a) Dependência temporal da conectividade, ⟨ki (t, t0)⟩, para sítios com característicasη = 0.1, 0.5 e 0.8. Note que ⟨ki (t, t0)⟩ segue uma lei de potência em cada caso e a inclinação crescelinearmente com η até o sítio apresentar característica igual a 0.5. Após esse valor, a inclinaçãodecresce e é, aproximadamente, igual as de sítios com características abaixo de 0.5. (b) O expoentedinâmico β como uma função de η. Ele é obtido da inclinação de ⟨ki (t, t0)⟩ versus η (β é uniforme-mente distribuído, m = 1 e N = 105). O valor máximo de β ocorre para η = 0.5 e é igual a 0.55, seuvalor mínimo é 0.37 em η=0.0 (ou η = 1.0), indicando que sítios com η ≈ 0.5 adquirem, em média,mais conexões. Isso permite que sítios com características em torno de 0.5 entrem na rede em umtempo posterior e, ainda assim, consigam um maior número de ligações do que outros que já estãonela há muito mais tempo.

adas aos diferentes valores de η. Como podemos ver, a inclinação dos gráficos cresce até

o sítio apresentar característica intrínseca igual a 0.5. A partir daí, ou seja, para sítios com

características intrínsecas superiores a 0.5, temos que a inclinação decresce e, além disso,

seus valores são, aproximadamente, iguais aos dos sítios com características abaixo de

0.5. Isto permite determinar os valores limites (inferior e superior) do expoente dinânico

β conforme indicado na legenda da figura 4.2(b).

A figura 4.2(b) exibe um comportamento simétrico de β no intervalo entre 0 e 1.

Isso ocorre devido à combinação da ligação preferencial (que privilegia conexões entre

sítios de perfis similares) com a distribuição uniforme das características dos sítios. A

partir disso, claramente, observamos que as características intrínsecas, η, potencialmente

semelhantes, a todas as demais, são as daqueles sítios que possuem características da

região central do intervalo [0; 1]. Este fato faz com que tais sítios tenham sua taxa de


recebimento ligação maximizada e, por consequência, tornam-se os prováveis pólos da

rede.

CAPÍTULO 5

GENERALIZAÇÃO DA REDE COMPLEXA HOMOFÍLICA

5.1 Introdução

Muitos sistemas naturais e artificiais, como a Internet, a World Wide Web (WWW),

os mapas de estradas [30, 28], a propagação de fofocas [31, 32] e as bacias hidrográficas [4],

podem ser facilmente associados às Redes Complexas. Isto é possível devido à definição

flexível de uma rede no domínio da ciência complexa, onde um conjunto de sítios e liga-

ções representam respectivamente os constituintes do sistema e as interações entre eles.

Para descrever o alto grau de complexidade, decorrente do inerente emaranhamento de

ligações que acontece durante o processo de crescimento de uma rede, é necessário uma

longa lista de propriedades. Normalmente, para as propriedades estruturais, são utiliza-

das as seguintes: distribuição de conectividade, comprimento do menor caminho médio,

coeficiente de agregação [4, 5], robustez [34, 35] e medições de algum tipo de correlação. Já

as propriedades dinâmicas, por outro lado, são geralmente calculadas no âmbito dos pro-

cessos de propagação, como problema de navegação [80, 81, 82, 83], sistemas magnéticos

[91, 92], sincronização [87, 88] e modelos epidêmicos [84, 85, 86].

Um dos primeiros modelos de redes de crescimento aleatório a mostrar distribui-

ção de conectividades exibindo lei de potência foi introduzido por Barabási e Albert (BA),

em 1999 [23] ver capítulo 1. O mecanismo do modelo, baseado no crescimento (o sistema

se expande através da adição de novos sítios) e na ligação preferencial (um novo sítio tem

44

Capítulo 5. Generalização da Rede Complexa Homofílica 45

uma probabilidade maior de conectar-se com outros mais conectados) produz correlações

como a assimetria entre os sítios mais novos e mais velhos, frequentemente observados

em redes reais. Apesar do sucesso do modelo BA, redes de livre escala (LE) também po-

dem ser geradas por meio de outros modelos [95, 40, 41, 42]. Em particular, a ligação

preferencial pode ser facilmente modificada para incorporar parâmetros observados em

redes reais, tais como: idade, qualidade (como o conteúdo de uma página web na WWW

ou o fator de impacto na rede de citações), o peso de cada ligação que pode representar

a força entre dois sítios, e a homofilia, que está relacionada com a semelhança entre as

características dos sítios.

Considerando as diferenças na qualidade dos sítios, Bianconi e Barabási [23] mo-

dificaram o modelo de ligação preferencial introduzido por BA, incorporando um novo

termo chamado fitness. Este, por sua vez, permite que novos sítios se tornem (hubs) pólos

[93, 94, 95] (sítios altamente conectados) e, além disso, amplia a heterogeneidade da dis-

tribuição de conectividade da rede. Recentemente, diferentes estudos acerca dos efeitos

das distribuições fitness em leis de potência e da inclusão do termo homofílico na regra de

ligação preferencial tem fornecido modelos LE mais realísticos por explicarem a tendência

de sítios se ligarem com outros semelhantes [38, 43]. Em tais modelos, há uma região onde

as características intrínsecas de sítios têm um papel importante não só na taxa de obtenção

de ligações, bem como no número de ligações entre sítios com características similares e

dissimilares.

Apoiado por trabalhos recentes que consideram as características de sítios e liga-

ções [103, 104] nesta tese, generalizamos e complementamos o modelo homofílico, e suge-

rimos uma nova maneira de medir correlações para os sítios que contêm diferentes qua-

lidades, tal como os sítios no modelo fitness. Em primeiro lugar, introduzimos o modelo

de rede generalizada homofílica LE e apresentamos os resultados para o comportamento

topológico da rede. A seguir, apresentamos a metodologia para medir as correlações in-

cluindo a mistura assortativa [19] e mostraremos os resultados das simulações numéricas.

Por fim, as conclusões serão apresentadas.

5.2 Modelo Generalizado

Nossa proposta de generalização tem como objetivo não só ampliar a compreen-


são acerca do modelo homofílico LE, bem como investigar as correlações entre os sítios. O

algoritmo para obter a rede compreende duas etapas básicas, a etapa de inicialização e a de

construção. Na etapa de inicialização atribuímos as propriedades básicas dos sítios, como

suas conectividades e qualidades. Dentro da etapa de construção, onde o crescimento da

rede acontece, adicionamos sítios e ligações seguindo o processo de ligação preferencial.

No nosso modelo, a rede começa com m0 sítios totalmente conectados. Para cada

sítio i atribuímos ao acaso uma característica intrínseca η, que segue uma distribuição ar-

bitrária ρ (η) e toma valores reais entre 0 e 1. Para simplificar, rotulamos todos os sítios

de 1 até o tamanho da rede, no sentido de que, a característica intrínseca de um determi-

nado sítio i é dada por ηi. Na parte de construção do algoritmo, a cada passo de tempo,

nós adicionamos um novo sítio j a ser ligado com m (6 M0) sítios da rede pré-existente.

Consideramos que a probabilidade de ligação∏

i de um sítio novo n a ser ligado com um

sítio i é dada por:

Πi =Aσ

i ki∑j A

σj kj

, (5.1)

onde ki é a conectividade do sítio i, Ai é a similitude entre a característica intrínseca dos

sítios i e n, e σ é um parâmetro para controlar o grau de importância do termo homofílico

na regra da ligação preferencial.

Aqui, definimos que a similitude Ai seja igual a 1−|ηi − ηn|. Observe que 0 < Ai <

1 de modo que para sítios perfeitamente similares, aqueles com características intrínsecas

iguais, (ηi = ηn), Ai = 1. Por outro lado, Ai = 0 para sítios perfeitamente dissimilares

(|ηi − ηn| = 1). Assim, a similitude Ai mede quão similares dois sítios são, e é usada

para levar em conta as diferentes habilidades dos sítios para competir por uma ligação.

Consideramos o parâmetro σ ≥ 0. Portanto, quando σ = 0 o modelo presente se reduz

ao modelo BA [23]. Quando σ = 1, recuperamos o modelo homofílico presente na Ref.

[38]. Note que a presente generalização da ligação preferencial, Eq. 4.1, privilegia, não

somente a conexão entre os novos sítios e aqueles que têm elevado grau, mas também

entre sítios com elevada similitude. A figura 4.1 é uma representação pictórica do processo

de crescimento descrito.


Figura 5.1: Ilustração de como a generalização do modelo homofílico de escala livre cresce. Em(a) o número inicial de sítios, mo, é dois. Na sequência em (b), (c) e (d), cada sítio faz apenas umanova ligação, m = 1, com um sítio pré-existente. Os valores para a característica intrínseca de cadasítio são: η1 = 0, 5, η2 = 0, 1, η3 = 0, 6, η4 = 0, 2, η5 = 0, 4. Ao decidir onde estabelecer uma novaligação (linha pontilhada), o novo sítio prefere conectar-se com outro de características similares ecom maior número de conexões, conjuntamente. Figura proveniente da Ref. [20]

5.3 Resultados

5.3.1 Resultados Topológicos

A rede homofílica generalizada investigada neste capítulo reflete as propriedades

básicas de muitos sistemas reais em que os sítios competem por ligações com outros; assim

um sítio pode adquirir ligações apenas à custa de outros sítios. Por isso, uma melhor

compreensão do parâmetro σ na ligação preferencial e a distribuição de características

intrínsecas serão discutidos e analisados a seguir.

A figura 4.2 mostra que nossa generalização leva a redes LE, onde o valor de cada

σ está relacionado com um grau de distribuição específico seguindo uma distribuição em

lei de potência, P (k) ∝ k−γ , com γ como é observado na figura 4.3. Isto indica que alguns

sítios têm alta conectividade enquanto muitos têm um número pequeno de vizinhos mais

próximos (heterogeneidade de grau) como na rede Apoloniana, modelo BA, modelo fit-

ness, a WWW, a rede dos contatos sexuais humanos, redes de citações entre outros. Esta

distribuição de conectividade tipo cauda longa, associada com o tamanho finito de nossa

rede provoca fortes influências nas propriedades dependentes do tamanho sistema, mas

todas as figuras presentes nesta tese contêm propriedades da rede obtidas com o sistema


em um estado estacionário. Esta é a razão pela qual fixamos o tamanho da rede de 105

sítios em todos os gráficos.

100 101 102 103 10410-8

10-6

10-4

10-2

100

P(k)

K

Figura 5.2: Distribuição de conectividades cumulativa P (K) para modelo homofílico generali-zado LE (valores típicos σ, m0 = m = 1, N = 105, η, é distribuído uniformemente, média tomadasobre 12000 realizações independentes) representada em escala logarítmica. Segue a lei de po-tência. P (k) ∝ k−γ , com valores variando entre 2.84(2) e 2.92(1). Este comportamento revela aausência de valores típicos para a conectividade dos sítios.

A partir da Figura 4.3, dois modelos de rede conhecidos são observados. Para

σ = 0 o modelo BA é recuperado; por outro lado, a rede homofílica LE é obtida por

σ = 1. É interessante observar que para σ = 2, o valor mínimo do expoente γ é obtido

e quando o parâmetro σ aumenta, o expoente γ tende para um valor constante em torno

de 2.9, ou seja, em σ = 2, existem alguns "super hubs"(sítios que têm conexões superiores

aos previstos por outros valores de σ, incluindo modelo BA e rede homofílica LE). Todo

esse comportamento do modelo pode ser atribuído à ligação preferencial que privilegia

conexões entre sítios que têm elevado número de vizinhos próximos e a alta similaridade


em conjunto.

A figura 4.4 mostra a dependência temporal da conectividade média, ⟨ki (t, t0)⟩para dois valores diferentes de σ. Esta nos informa como a conectividade média cresce,

assintoticamente, com o tempo t/t0, em que t0 é o tempo no qual o sítio i foi adicionado ao

sistema. Matematicamente, a dependência temporal da conectividade média é dada por:

⟨ki (t, t0)⟩ ∝(

t

t0

)β

, (5.2)

0 2 4 6 8 10

2.84

2.86

2.88

2.90

2.92

2.94

Modelo de Barabasi

Modelo H

omofilico

Figura 5.3: Dependência do expoente γ com σ (m0 = m = 1, N = 105, η, é uniformementedistribuído, e com média acima de 12000 em realizações). Para σ = 0 o modelo BA é recuperado;por outro lado, a rede homofílica de livre escala é alcançada por σ = 1. Um resultado interessanteé observado quando σ = 2, o expoente γ é mínimo.

Onde β é o expoente dinâmico, indicando a taxa com a qual os sítios obtêm li-

gações. Para σ = 2, notamos um comportamento simétrico de β no intervalo de 0 a 1,

bem como a existência de uma característica ideal para os sítios, 0.5, que maximiza a taxa

de ligações que um dado sítio específico adquire. O mesmo comportamento é observado


100

101

102

103

100 101 102 103 104100

101

102

103

a)

Kt,t

0=9

b)

K

t,t0=9

t/t0

Figura 5.4: Dependência temporal da conectividade média ⟨ki (t, t0)⟩, para sítios com η=0.1, 0.3,0.5, 0.7 e 0.9 ( m0 = m = 1, N = 105, η é uniformemente distribuído e a média é feita com 12000realizações independentes). Comparações entre figuras (a) e (b) mostram que ⟨ki (t, t0)⟩ segue a leide potência em cada caso e o expoente dinâmico β(η) é dependente de σ. Para altos valores de σ

ou σ = 0, todos os sítios aumentam sua conectividade no tempo como ⟨ki (t, t0)⟩ ∝ (t/t0)β onde

β = 1/2 e t0 é o tempo em que o sítio i foi adicionado ao sistema, independente de sua característicaintrínseca.

quando o modelo homofílico LE é considerado, σ = 1 [mais detalhes, veja 34]. Por outro

lado, para σ = 0 (modelo BA) e para altos valores de σ, as linhas de dependência temporal

da conectividade média se sobrepõem, ou seja, os valores das características intrínsecas

levam à mesma lei de potência, Eq. 2, independente de sua idade. Consequentemente,

os sítios mais velhos terão maiores números de ligações, pois tiveram um longo tempo

para adquiri-las. Isto negligencia um aspecto importante dos sistemas competitivos: nem

todos os sítios são igualmente bem sucedidos em adquirir ligações.


Observando a figura 4.5, podemos concluir que valores de σ maior que 0 e menor

que 10 tornam β dependente de η. É importante lembrar dois pontos: (i) nem todas as

distribuições ρ(η) resultarão em uma dependência temporal da conectividade tipo lei de

potência; e (ii) β > 0 porque um sítio sempre aumenta o número de conexões com o passar

do tempo e β < 1 porque a conectividade do sítio não ganha mais que m ligações em cada

passo, t, isto é, o expoente dinâmico β é limitado.

0.0 0.2 0.4 0.6 0.8 1.00.2

0.3

0.4

0.5

0.6

Figura 5.5: Dependência do expoente dinâmico β com η (m0 = m = 1, N = 105, η é unifor-memente distribuído e com média realizada sobre 12000 realizações independentes) para σ = 0(modelo BA), 2 e 10. O valor máximo de β é 0.55 em η = 0.5 e em σ = 2, indicando que sítios comη em torno de 0.5 adquirem, em média, mais ligações. Isso possibilita que sítios, com característicaintrínseca em torno de 0.5, entrem na rede um tempo depois e superem sítios que estão na rede porum tempo maior. Para σ = 0 ou 10, o expoente β é o mesmo, consequentemente, todos os sítiossão igualmente bem sucedidos em adquirir ligações e independentes do tempo.

Além disso, a figura 4.5 mostra um comportamento simétrico de β no intervalo

de 0 a 1, que desaparece quando σ assume um valor nulo ou valores elevados. Isto indica

que o modelo BA compartilha do mesmo comportamento para o expoente β, mas não po-

demos inferir que σ = 10 (a valores elevados para σ) representa o modelo BA. Quando

σ ̸= 0, sítios com perfis semelhantes são importantes na ligação preferencial, refletindo-se


em correlação e diferentes redes do modelo BA (correlações serão discutidas adiante). Por

exemplo, em redes sociais, os amigos são geralmente semelhantes entre si em termos de

etnia, idade, ocupações, interesses, crenças e opiniões. Então, pessoas que são mais seme-

lhantes entre si são melhores em transformar um encontro casual em uma relação social.

Os exemplos não se limitam apenas neste tipo de rede, mas acontece com frequência em

muitas outras.

5.3.2 Resultados em Correlações

Nesta seção, apresentaremos os resultados numéricos considerando as caracterís-

ticas intrínsecas dos sítios sendo distribuídas pela lei de potência e dadas por:

ρ(η) = Bηα

Onde B é uma constante. Portanto, vamos rotular todos os sítios da rede e atri-

buir à característica intrínseca do sítio i, ηi (ηi variando entre 0 e 1). É importante notar que

a distribuição ρ(η) pode seguir outro tipo de distribuição, como a distribuição gaussiana

ou uniforme. A principal razão da escolha da distribuição em lei de potência é a popu-

laridade dela nos problemas acadêmicos, como redes LE, sistemas com geometria fractal,

percolação, difusão reorganizada de agregados, entre outros.

As figuras 4.6 e 4.7 descrevem a correlação em função da conectividade onde a pri-

meira figura é a dependência do coeficiente de agregação C(k) com o número de vizinhos

dos sítios k; e a segunda é o grau médio dos vizinhos versus o número de vizinhos dos sí-

tios k. Note que em ambas as figuras há uma dependência do parâmetro m, enquanto este

é independente de α. Além disso, o coeficiente de agregação exibe dois comportamentos

que são dependentes da conectividade: (i) coeficiente de agregação alto e lei de potência

para valores menores que k ∼ 100; e (ii) o coeficiente de agregação estabiliza para valores

maiores que k ∼ 100. Por outro lado, a inclinação negativa na figura 4.7 indica que a cor-

relação de grau exibe mistura disassortativa, isto é, sítios menos conectados estão ligados

a sítios altamente conectados.

A figura 4.8 mostra o grau médio de vizinhos de um sítio como uma função das

características intrínsecas dos sítios η. Note que os resultados exibidos são dependen-


100 101 102 103 10410-5

10-4

10-3

10-2

10-1

100 m=2 m=4 m=8 m=2 m=4 m=8 m=2 m=4 m=8 m=2 m=4 m=8C

(k)

K

Figura 5.6: Simulação numérica do modelo homofílico generalizado LE (o tamanho da rede foifixado em 105 sítios, m0 = m, σ = 1 e média tomada sobre 12000 realizações independentes): de-pendência do coeficiente de agregação C(k) com o número de vizinhos k dos sítios para diferentesvalores de α e m (número de ligações adicionadas a cada passo de tempo). O gráfico retrata queo coeficiente de agregação apresenta dois comportamentos: (i) para valores menores que k ∼ 100,alto coeficiente de agregação e uma lei de potência é observada; (ii) enquanto para valores maioresque k ∼ 100, o coeficiente de agregação está estabilizado. Assim, isso acontece independente doparâmetro α, mas é influenciado pelo parâmetro m.

tes dos parâmetros α e m. Portanto, a distribuição das características intrínsecas dos sítios

afeta somente a correlação das características intrínsecas, enquanto a correlação grau-grau

não é influenciada por α, mesmo que a ligação preferencial envolva a conectividade e a

similaridade das características intrínsecas. Em particular, o parâmetro m é responsável,

diretamente, por incrementar a conectividade dos sítios, logo o grau médio dos vizinhos

de um sítio aumenta quando m cresce. Esta é a razão pela qual na figura 4.8 os dados

para maiores valores de m estão no topo da figura. Por outro lado, quando α é maior que

zero, a simetria do grau médio dos vizinhos de um sítio se quebra. Isso mostra a rele-

vância da distribuição das características intrínsecas na correlação entre as características

intrínsecas. Lembrando que para σ = 1 e α = 0, mostrado na figura 8a, os hubs são sítios


com características intrínsecas por volta de 0.5 (ver figura 4.5), ao passo que para dife-

rentes valores de σ e α uma análise mais detalhada se faz necessária para compreender

melhor as influências de α na conectividade média dos sítios. Finalmente, na figura 8d, a

flutuação para n menor que η ∝ 0.3 é alta porque há poucos sítios com baixos valores de

características intrínsecas quando o parâmetro α assume valores altos.

100 101 102 103 104100

101

102

m=2 m=4 m=8 m=2 m=4 m=8 m=2 m=4 m=8m=2

m=4 m=8

<Knm>

K

Figura 5.7: O grau médio dos vizinhos de um sítio, < knn >, como uma função do grau k do sítio.Ele mostra que a correlação do grau exibe mistura disassortativa. Os símbolos são resultados desimulação numérica do modelo homofílico generalizado LE (o tamanho da rede foi fixado em 105

sítios, m0 = m, σ = 1 e média sobre 12000 amostras).

A figura 4.9 mostra a característica intrínseca média dos vizinhos de um sítio

como uma função da característica intrínseca de um sítio para diferentes valores de α

e m onde σ = 1. Ela retrata que m não é um parâmetro importante para a característica

intrínseca média dos vizinhos de um sítio. Porém, uma pequena mudança do parâmetro

α pode provocar um salto abrupto no gráfico. Em particular, α = 0 (ρ(η) é uniforme), isto

leva a um comportamento linear onde a correlação é positiva, ou seja, sítios com carac-

terística intrínseca similar estão conectados entre si. Isto decorre da ligação preferencial

onde a similitude Aij facilita a ligação entre sítios de perfis similares. Á medida que o va-


20

40

60

0.0 0.2 0.4 0.6 0.8 1.020

40

60

0.0 0.2 0.4 0.6 0.8 1.0

m=2 m=4 m=8

a)

b)

<Knn

><K

nn>

c)

d)

Figura 5.8: O grau médio < knn > dos vizinhos de um sítio como uma função da característicaintrínseca do sítio η. Os símbolos são resultados da simulação numérica do modelo homofílicogeneralizado LE (o tamanho da rede foi fixado em 105 sítios, m0 = m, σ = 1 e com média obtidade 12000 realizações independentes). Em cada gráfico foram usados valores diferentes para α: (a)α = 0, isto é, a característica intrínseca é distribuída uniformemente, (b) α = 1; (c) α = 2; (d)α = 10. Para α = 0 o comportamento é simétrico e para valores maiores que α = 0 há uma quebrada simetria em < knn >.

lor de α aumenta, a distribuição da característica intrínseca não se torna homogênea. Por

exemplo, para α = 10, existem muitos sítios com η por volta de um, enquanto há poucos

sites η por volta de zero. Juntamente com a ligação preferencial, este aspecto provoca um

salto abrupto na característica intrínseca média (ver figura 9(d)).


0.3

0.4

0.5

0.6

0.7

0.0 0.2 0.4 0.6 0.8 1.00.0

0.2

0.4

0.6

0.8

1.0

0.0 0.2 0.4 0.6 0.8 1.0

nn

b)

c)

nn

m=2 m=4 m=8

d)

a)

Figura 5.9: A característica intrínseca média < ηnn > dos vizinhos de um sítio como uma funçãoda característica intrínseca do sítio η. As curvas são resultados da simulação numérica do modelohomofílico generalizado LE (o tamanho da rede foi fixado em 105 sítios, m0 = m, σ = 1 e commédia sobre 12000 realizações independentes). Em cada gráfico, valores diferentes de α foramusados: (a) α = 0, ou seja, a característica intrínseca é uniformemente distribuída; (b) α = 1; (c)α = 2; (d) α = 10. Na proporção em que α aumenta, um salto aparece na característica intrínsecamédia < ηnn > devido à distribuição não homogênea da característica intrínseca (Ver equação 3).Note que o parâmetro m é independente em cada figura.

CAPÍTULO 6

CONCLUSÕES

Com o objetivo de contribuir ainda mais para a compreensão do atual estudo das

redes, propusemos uma generalização do modelo homofílico LE que possibilita a análise

de um importante elemento que faltava em muitos modelos de rede: a mistura assortativa

na característica intrínseca. Portanto, os sítios são caracterizados por uma característica in-

trínseca e a ligação preferencial considera dois parâmetros essenciais: a homofilia, tendên-

cia de sítios conectarem-se com outros similares, e o número de vizinhos, que juntamente

com o parâmetro de controle, α, que ajusta o grau de importância do termo homofílico.

Em particular, σ = 0 é o próprio modelo BA e σ = 1 é o modelo homofílico LE. Por-

tanto, em um primeiro momento, estudamos como σ influencia o grau de distribuição, a

dependência temporal da conectividade e o coeficiente de agregação; por fim, fixamos o

valor de σ = 1 e usamos uma distribuição das características intrínsecas tipo lei de po-

tência para analisar como a correlação foi afetada. Nossas principais descobertas foram:

(i) a distribuição de conectividade é pouco influenciada pelo valor de σ; (ii) o parâmetro

σ pode quebrar a dependência temporal da conectividade média quando assume σ = 0

ou valores altos, em relação às características intrínsecas. Para outros valores de σ uma

característica ideal dos sítios emerge, η = 0.5, a qual maximiza a proporção de ligações

que um sítio específico adquire; (iii) para ρ(η) em lei de potência, ρ(η) ∝ ηα, e σ = 1 as

medidas de correlação em função da conectividade dependem apenas de m (número de

ligações adicionadas por passo de tempo). Por outro lado, as medidas de correlação em

função da característica intrínseca dependem apenas de α. Para outros trabalhos, a com-

57

Capítulo 6. Conclusões 58

preensão de como σ e diferentes distribuições das características intrínsecas ratificam uma

lei de potência para P (k) e suas implicações é um desafio formidável.

Por fim, a principal diferença entre o modelo BA, o modelo fitness e nosso mo-

delo generalizado é a ligação preferencial que atua diretamente na conectividade do sítio

e na taxa de crescimento. O primeiro depende somente da conectividade, o segundo de-

pende da característica intrínseca e o último depende da conectividade e da semelhança,

que é ligada diretamente a característica intrínseca. Portanto, o modelo BA negligencia a

complexidade da capacidade de sítios em adquirir ligação (sítios dependem de sua idade

por si só). Um exemplo para contrastar com o modelo BA é o WWW - através de uma

combinação de bom conteúdo e marketing/propaganda, alguns documentos atraem um

grande número de ligações em curto espaço de tempo. Este exemplo é mais bem imitado

quando o modelo fitness é considerado. Por outro lado, podemos imaginar que o WWW

e alguns documentos podem atrair novas ligações, se eles forem similares com outros. Em

todo caso, nosso modelo generalizado é o preferido.

REFERÊNCIAS

[1] SOCIEDADE BRASILEIRA DE FÍSICA. Física para o Brasil: Pensando o Futuro. São

Paulo: SBF, 2005.

[2] L. Euler, Commentarii Academiae scientiarum Imperialis Petropolitanae 8, 128

(1736).

[3] P. Erdös, A. Rényi, Publ. Math. 6, 290 (1959).

[4] D.S. Watts and S. H. Strogatz, Nature 393, 440 (1998).

[5] L.A.N. Amaral, A. Scala, M. Barthelemy, H.E. Stanley, Proc. Natl. Acad. Sci. USA 97,

509 (2000).

[6] Barabási, A.-L.; Albert, R. Emergence of scaling in random networks. Scienc, Washington,

v. 286, p. 509-512, 1999.

[7] M.E.J. Newman, Networks: An Introduction (Oxford University Press, Oxford, 2010).

[8] S.H. Strogatz, Nature 410, 268 (2001).

[9] S.N. Dorogovtsev and J.F.F. Mendes, Evolution of networks: From Biological Nets to the

Internet and WWW, Oxford University Press, Oxford (2003).

[10] R. Albert, A.-L. Barabási, Rev. Mod. Phys. 74, 47 (2002).

[11] S.N. Dorogovtsev, Lectures on Complex Networks (Oxford University Press, Ox-

ford,2010).

59

Referências 60

[12] Newman, M.; Barabási, A.L. Watts, D.J. Structure and dynamics of networks. New Jer-

sey: Princenton University Press, 2006.

[13] R. Albert and A.-L. Barábasi, Statistical mechanics of complex networks, Rev. Modern

Phys. 74 (2002), pp. 47-97.

[14] R. Albert, A.-L. Barabási, Rev. Mod. Phys. 74, 47 (2002).

[15] A.-L. Barábasi, E. Ravasz and T. Vicsek, cond-mat 0107419.

[16] A.M. Filho, Tese de Doutorado, Departamento de Física - UFRN, (2010).

[17] M. Catanzaro, M. Boguná, R. Pastor-Satorras, Phys. Rev. E 71, 027103 (2004).

[18] R. Pastor-Satorrs, A. Vásquez and A. Vespignani, Phys. Rev. Lett. 87, 258701 (2001).

[19] M.E.J. Newman, Phys. Rev. Lett. 89, 208701 (2002).

[20] M.L. Almeida, Tese de Doutorado, Departamento de Física - UFRN, (2013).

[21] S. Milgram , Psychology Today, 2, 60 (1967).

[22] A. Broder, R. Kumar, F. Maghoul, P. Raghavan, S. Rajagopalan, R. Stata, A. Tomkins

and J. Wiener, Comput. Netw. 33, 309 (2000).

[23] A.-L. Barabási and R. Albert, Science 286, 509-512 (1999).

[24] H. Jeong, B. Tombor, R. Albert, Z. N. Oltvai and A. -L. Barábasi, Nature 407, 651 (2000).

[25] S. Valverde and R.V. Solé, Physica A 312, 636 (2002).

[26] S.G. Aguiar, Dissertação de Mestrado, Departamento de Física - UFRN, (2012).

[27] G.A. Mendes, Tese de Doutorado, Departamento de Física - UFRN, (2010).

[28] G.A. Mendes, K.W. Axhausen, J.S. Andrade, H.J. Herrmann, Int. J. Mod. Phys. C 25,

1450067 (2014).

[29] D.J. Watts, Small Worlds: The Dynamics of networks between Order and Randomness (Prin-

ceton University Press, Princeton, 2003).

[30] G.A. Mendes, L.R. da Silva, H.J. Herrmann, Physica A 391, 362 (2012).

Referências 61

[31] P.G. Lind, H.J. Herrmann, J.S. Andrade, L.R. da Silva, Europhys. Lett. 78, 68005

(2007).

[32] P.G. Lind, L.R. da Silva, J.S. Andrade Jr. and H.J. Herrmann, Europhysics Letters 78,

68005 (2007).

[33] L.A.N. Amaral, A. Scala, M. Barthélémy, and H.E. Stanley, Proc. Nac. Acad. Sci. USA,

97, 11149 (2000).

[34] C.M. Schneider, A.A. Moreira, J.S. Andrade Jr., S. Havlin, H.J. Herrmann, Proc. Natl.

Acad. Sci. USA 108, 3838 (2011).

[35] C.M. Schneider, N. Yazdani, N.A.M. Araújo, S. Havlin, H.J. Herrmann, Sci. Rep. 3,

1969 (2013).

[36] C.M. Schneider, N.A.M. Araújo, S. Havlin, H.J. Herrmann, arXiv:1106.3234v1 [cond-

mat-stat-mech] (2011).

[37] G. Bianconi and A.-L. Barabási, Europhys. Lett. 54, 436-442, (2001).

[38] M.L. Almeida, G.A. Mendes, G.M. Viswanathan and L.R. Silva, Eur. Phys. J. B (2013).

[39] G. Bianconi, P. Pin, M. Marsili, Proc. Natl. Acad. Sci. Usa 106, 11433 (2009).

[40] R.M. D’Souza, C. Borgs, J.T. Chayes, N. Berger, R.D. Kleinberg, Proc. Natl. Acad. Sci.

USA 104, 6112 (2007).

[41] F. Papadopoulos, M. Kitsak, M.A. Serrano, M. Boguñá, D. Krioukov, Nature 489, 537

(2012).

[42] L. Muchnik, S. Pei, L.C. Parra, S.D.S. Reis, J.S. Andrade, S. Havlin, H.A. Makse, Sci.

Rep. 3, 1783 (2013).

[43] G.A. Mendes, L.R. da Silva, Braz. J. Phys. 39, 423 (2009).

[44] I. Gleria, R. Matsushita e S. da Silva, Revista Brasileira do Ensino de Física 26, n. 2, pp.

99-108, (2004).

[45] L. Euler. Solution Problematics ad geometriam situs pertinentis. Commentarii Acade-

miae scientiarum Imperialis Petropolitanae, v. 8, p. 128 - 140.

[46] R. Albert, H. Jeong and A.L. Barábasi, Nature 401, 130 (1999).

Referências 62

[47] F. Liljeros, C.R. Edling, L.A.N. Amaral, H.E. Stanley and Y. Aberg, Nature 411, 907

(2001).

[48] S. Redner, Eur. Phys. J. B 23, 267 (1998).

[49] P. Erdos and A. Réniy, Publ. Math. 6 (1959).

[50] D.J.B. Soares, Tese de doutorado, Departamento de Física-UFRN, (2004).

[51] B. Bollobás, Random Graphs (Academic Press, New York, 1985).

[52] A.L. Barabási, R. Albert and H. Jeong, cond-mat 9907068.

[53] R. Kumar, P. Raghavan, S. Rajagopalan, D. Sivakumar, A. Tomkins and E. Upfal,

Procedings of the 19th ACM Symposium on Principles of Database Sistems, 1-10 (2000a).

[54] M.E.J. Newman, S.H. Strogatz and D.J. Watts, Phys. Rev. E 64, 026118 (2001).

[55] L.A. Adamic and B.A. Huberman, Science 287, 2115a (2000).

[56] L.A. Adamic, Procedings of ECDL’99, LNCS 1696, 443-452 (1999).

[57] A.D.M Pennock, G.W. Flake, S. Lawrence, E.J. Glover and C.L. Giles, Proc. Natl. Acad.

Sci. USA 99, 5207 (2002).

[58] M. Faloutsos, P. Faloutsos and C. Faloutsos, Comp. Commun. Rev. 29, 251 (1999).

[59] R. Govindan and H. Tangmunarunkit, Procedings of the 2000 IEEE INFOCOM Confe-

rence, 1371-1380 (2000).

[60] C. Tsallis and M.P. de Albuquerque, Eur. Phys. J. B 13, 777 (2000).

[61] P.L Krapivsky, S. Redner and F. Leyvraz, Phys. Rev. Lett. 85, 4629 (2000).

[62] P.G. Lind, L.R. da Silva, J.S. Andrade Jr. and H.J. Herrmann, Physical Review E 74,

036117 (2007).

[63] A. Vásquez, Statistics of citation networks, cond-mat/0105031 (2001b).

[64] R. Albert and A.-L. Barabási, Phys. Rev. Lett. 85, 5234 (2000).

[65] M.E.J. Newman, Phys. Rev. E 64, 016131 (2001e).

Referências 63

[66] A.-L. Barabási, H. Jeong, Z. Néda, E. Ravasz, A. Schubert and T. Vicsek, Physica A

311, 590 (2002).

[67] A. Wagner and D.A Fell, Proc. R. Soc. London B 268, 1803 (2001).

[68] H. Jeong, S.P. Mason, A.-L. Barabási and Z.N. Oltvai, Nature 411, 41 (2001).

[69] A. Wagner, Mol. Biol. Evol. 18, 1283 (2001a).

[70] R. Ferrer i Cancho and R.V. Solé, Proc. R. Soc. B 268, 2261 (2001a).

[71] J.M. Montoya and R.V. Solé, Working Papers of Santa Fe Institute, 01-11-069 (2001).

[72] R. Ferrer i Cancho and R. Solé, cond-mat/0111222.

[73] W. Aiello, F. Chung and L. Lu, Proceedings of the Thirty-Second Annual ACM Symposium

on Theory of Computing, 171-180 (2000).

[74] M.D. de Meneses, D.J.B. Soares, S.D. da Cunha and L.R. da Silva, Progress of Theoretical

Physics Supplement, 162, 131-137 (2006).

[75] S. Abe and N. Suzuki, Phys. Rev. E 67, 016106 (2003).

[76] J.P.K. Doye, Phys. Rev. Lett. 88, 238701 (2002).

[77] A.-L. Barabási, R. Albert and H. Jeong, Physica A 272, 173 (1999).

[78] A. Santiago and R. M. Benito, International Journal of Modern Physics C 18, Nº 10, 1591-

16707, (2007).

[79] D.J.B. Soares, C. Tsallis, A.M. Mariz and L.R. da Silva, Europhysics Letters, 70, 70-71

(2005).

[80] J.M. Kleinberg, Nature 406, 845 (2000).

[81] G. Li, S.D.S. Reis, A.A. Moreira, S. Havlin, H.E. Stanley, and J.S. Andrade,Phys. Rev.

Lett. 104, 018701 (2010).

[82] G. Li, S.D.S. Reis, A.A. Moreira, S. Havlin, H.E. Stanley, and J.S. Andrade,Phys. Rev.

E 87, 042810 (2013).

[83] C.L.N. Oliveira, P.A. Morais, A.A. Moreira, and J.S. Andrade,Phys. Rev. Lett. 112,

148701 (2014).

Referências 64

[84] R. Pastor-Satorras, A. Vásques, A. Vespignani, Phys. Rev. Lett. 87, 258701 (2001).

[85] S. Aral, L. Muchnik, A. Sundararajan, Proc. Natl. Acad. Sci. USA 106, 21544 (2009)

[86] N.N. Chung, L.Y. Chew, J. Zhou, C.H. Lai, Europhys. Lett. 98, 58004 (2012).

[87] P.A. Morais, J.S. Andrade, E.M. Nascimento, and M.L. Lyra, Phys. Rev. E 84, 041110

(2011).

[88] V.H.P. Louzada, N.A.M. Araújo, J.S. Andrade, H.J. Herrmann, Sci. Rep. 2, 658 (2012).

[89] A.-L. Barabási, Linked: The New Science of Networks (Perseus Books Group, Cam-

bridge, 2002).

[90] G.L. Mamede, N.A.M. Araújo, C.M. Schneider, J.C. de Araújo, H.J. Herrmann, Proc.

Natl. Acad. Sci. USA 109, 7191 (2012).

[91] R.F.S. Andrade, J.S. Andrade Jr., H.J. Herrmann, Phys. Rev. E 79, 036105 (2009).

[92] N.A.M. Araújo, R.F.S. Andrade, H.J. Herrmann, Phys. Rev. E 82, 046109 (2010).

[93] G. Bianconi, A.-L. Barabási, Europhys. Lett. 54, 036112 (2001).

[94] G. Caldarelli, A. Capocci, P. De Los Rios. M.A. Munoz, Phys. Rev. Lett. 89, 258702

(2002).

[95] G. Bianconi, P. Pin, M. Marsili, Proc. Natl. Acad. Sci. Usa 106, 11433 (2009).

[96] V.H.P. Louzada, N.A.M. Araújo, J.S. Andrade Jr., H.J. Herrmann, Sci. Rep. 2, 658

(2012).

[97] S. Aral, L. Muchnik, A. Sundararajan, Proc. Natl. Acad. Sci. USA 106, 21544 (2009).

[98] N.N. Chung, L.Y. Chew, J. Zhou, C.H. Lai, Europhys. Lett. 98, 58004 (2012).

[99] L.da F. Costa, F.A. Rodrigues, G. Travieso, P.R. Villas Boas, Adv. Phys. 56, 167 (2007).

[100] G. Caldarelli, A. Capocci, P. De Los Rios, M.A. Munoz, Phys. Rev. Lett. 89, 258702

(2002).

[101] G. Bianconi, P. Pin, M. Marsili, Proc. Natl. Acad. Sci. USA 106, 11433 (2009).

[102] G.A. Mendes, L.R. da Silva, Braz. J. Phys. 74, 47 (2002).

Referências 65

[103] L. Ferretti, M. Cortelezzi, Phys. Rev. E 84, 016103 (2011).

[104] L. Ferretti, M. Cortelezzi, B. Yang, G. Marmorini, G. Bianconi, Phys. Rev. E 85,

066110 (2012).

[105] W.N.H.C. Shrum Jr., S.M.D. Hunter, Sociol. Educ. 61, 227 (1988).

[106] S.H. Yook, Z.N. Oltvai, A.-L Barabási, Proteomics 4, 928 (2004).

[107] J. Park, A.-L. Barabási, Proc. Natl. Acad. Sci. USA 104, 17916 (2007).

[108] M.E.J. Newman, J. Park, Phys. Rev. E 68, 036122 (2003).

[109] M. McPherson, L. Smith-Lovin, J.M. Cook, Annu. Rev. Soc. 27, 415 (2001).

[110] S. Cuenda, J.A. Crespo, Europhys. Lett. 95, 38002 (2011),

[111] R.D. Alba, J. Math. Soc. 3, 113 (1973).

[112] S.B. Seidman, Social Networks 5, 97 (1983).

[113] L.D. Sailer, S.J.C. Gaulin, Am. Anthropol. 86, 41 (1984).

[114] S.P. Borgatti, M.G. Everett, P.R. Shirey, Social Networks 12, 337 (1990).

[115] D.R. White, F. Haray, Sociological Methodology 31, 305 (2001).

[116] N.A. Christakis, J.H. Fowler, N. Engl. J. Med. 357, 370 (2007).

[117] M.E.J. Newman, G.T. Parkema, Monte Carlo Methods in Statistical Physics (Oxford

University Press, Oxford, 1999).

[118] J.S. Andrade Jr., H.J. Herrmann, R.F.S. Andrade, L.R. da Silva, Phys. Rev. Lett. 94,

018702 (2005).

[119] P. Holme, B.J. Kim, Phys. Rev. E 65, 026107 (2002).

[120] S.N. Dorogovtsev, Phys. Rev. E 69, 027104 (2004).

[121] A.M. Santos, Dissertação de Mestrado, Departamento de Física - UFRN, (2010).

Documents

UNIVERSIDADE FEDERAL DO RIO GRANDE DO NORTE CENTRO DE ... · tam a origem das correspondências e o estado em verde ... 3.4 Coeﬁciente de agregação versus o tamanho da rede do