Física Estatística Aplicada a Sistemas Sociais Através do ... · Centro de Ciências Exatas e da erraT (CCET) ... Física Estatística Aplicada a Sistemas Sociais Através do Estudo

Universidade Federal do Rio Grande

do Norte

Dissertação de Mestrado

Física Estatística Aplicada aSistemas Sociais Através do Estudo

de Redes Complexas

Autora:

Gerdivane Ferreira Duarte

Orientador:

Prof. Dr. Luciano Rodrigues da Silva

Coorientador:

Prof. Dr. Madras Viswanathan Gandhi Mohan

Departamento de Física Teórica e Experimental (DFTE)

Centro de Ciências Exatas e da Terra (CCET)

Natal-RN

Fevereiro de 2014

http://www.ufrn.br

http://www.ufrn.br

http://www.ufrn.br

http://www.ufrn.br

http://www.ufrn.br

Department or School Web Site URL Here (include http://www.dfte.ufrn.br)

Faculty Web Site URL Here (include http://)

Gerdivane Ferreira Duarte

Física Estatística Aplicada aSistemas Sociais Através do Estudo

de Redes Complexas

Dissertação de Mestrado 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 parcial para a obtenção

do grau de Mestra em Física.

Orientador: Prof. Dr. Luciano Rodrigues da Silva

Coorientador: Prof. Dr. Madras Viswanathan Gandhi

Mohan

Natal-RN

Fevereiro de 2014



http://www.ufrn.br

http://www.ufrn.br

�Graças a minha sólida formação acadêmica, hoje eu posso escrever centenas de

palavras sobre 'Física Estatística Aplicada a Sistemas Sociais Através do Estudo

de Redes Complexas', o que me envaidece extremamente cobrindo minha alma com

um luxo de sensações nunca antes experimentadas. Devo tal fato a Universidade

Federal do Rio Grande do Norte."

Gerda Ferreira

http://www.ufrn.br

http://www.ufrn.br

Dedico este trabalho:

A Deus.

Ao meu Pai João Ferreira.

A minha Mãe Maria José Ferreira.

A minha irmã Jane Keyles Ferreira.

Agradecimentos

A Deus pelo talento e força mesmo nos momentos em que acreditei que não

continuaria;

Ao meu pai João Ferreira, que me ensinou a amar matemática quando eu

ainda era uma criança;

À minha mãe Maria José Ferreira, que em muitos momentos de sua vida,

cuidou de mim mais que dela mesma;

Aos meus irmãos, Gerdivan Ferreira e Edivan Oliveira, e irmãs, Jane Keyles

Ferreira, Geise Taise Ferreira e Josiane Ferreira, que nunca entenderam as razões

pelas quais escolhi me dedicar à ciência, mesmo assim sempre apoiaram este sonho,

com palavras de amor e incentivo;

Ao meu Orientador Prof. Dr. Luciano Rodrigues da Silva, pela oportuni-

dade, orientação, conversas descontraídas, serenidade e principalmente pelo en-

tusiasmo com que conduziu esse trabalho. Não há palavra melhor para traduzir

o professor Luciano que �entusiasmo�, este ele partilhou generosamente comigo e

esse fato me trouxe até aqui;

Ao meu Coorientador Prof. Dr. Madras Viswanathan Gandhi Mohan, pela

paciência e por partilhar comigo um pouco da sua sabedoria e experiência, pelos

momentos de amparo e acolhimento, pela con�ança e pelas palavras de força e

incentivo que possibilitaram essa conquista de uma maneira tão afável;

Ao Amigo Me Tiago Medeiros Vieira, pelos comentários, discussões, amparo

e contribuições que proporcionaram melhorar este trabalho;

Aos amigos Me Thiago Crisóstomo Carlos Nunes, e Ma Samuraí Gomes de

Aguiar por todo apoio e ajuda nos momentos mais difíceis, pela companhia, dis-

cussões e ideias, pelas conversar sempre agradabilíssimas;

Aos colegas de turma, Ricardo Borges, Anna Cecília, Wellington e Eloise

Cristina, com os quais dividi momentos de descontração, de dedicação e entrega

aos conteúdos que precisávamos dominar e também algumas poucas tardes de total

improdutividade;

Em espcial ao meu grande amigo Juscimário Gregório Cruz - �In memoriam." ;

Aos colegas do grupo de pesquisa Física Estatística e Sistemas Complexos;

Aos professores do Departamento de Física Teórica e Experimental que con-

tribuíram para minha formação pro�ssional e aos funcionários do departamento,

especialmente a Celina.

Finalmente, a CAPES, pelo apoio �nanceiro concedido.

Research Group Web Site URL Here (include http://)


�Ame a todos, con�e em poucos, não faça mal a nin-

guém."

William Shakespeare

Universidade Federal do Rio Grande do Norte (UFRN)

Resumo

UFRN

Departamento de Física Teórica e Experimental

Mestra em Física

Física Estatística Aplicada a Sistemas Sociais Através do Estudo de

Redes Complexas

por Gerdivane Ferreira Duarte

Neste trabalho é apresentado um estudo das redes sociais baseado na análise

dos nomes de famílias. Faz-se uma abordagem básica do formalismo matemático

dos grafos e em seguida apresenta-se os principais modelos teóricos para as Redes

Complexas com o objetivo de fundamentar a análise das redes dos sobrenomes.

Estas, por sua vez, são trabalhadas de modo a serem extraídas as principais gran-

dezas, tais como coe�ciente de agregação, menor caminho médio e distribuição de

conectividades. Com base nestas grandezas, pode-se a�rmar que as redes de so-

brenomes são um exemplo de rede complexa, exibindo características importantes

como ligação preferencial e o caráter de mundo pequeno.

Palavras-chave: Teoria dos Grafos, Redes Livres de Escala, Análise de Redes

Sociais, Redes dos Sobrenomes, Redes de Mundo Pequeno.

University Web Site URL Here (include http://www.ufrn.br)



Universidade Federal do Rio Grande do Norte (UFRN)

Abstract

UFRN

Departamento de Física Teórica e Experimental

Mestra em Física

Física Estatística Aplicada a Sistemas Sociais Através do Estudo de

Redes Complexas

by Gerdivane Ferreira Duarte

In this work a study of social networks based on analysis of family names is

presented. A basic approach to the mathematical formalism of graphs is developed

and then main theoretical models for complex networks are presented aiming to

support the analysis of surnames networks models. These, in turn, are worked so

as to be drawn leading quantities, such as aggregation coe�cient, minimum ave-

rage path length and connectivity distribution. Based on these quantities, it can

be stated that surnames networks are an example of complex network, showing

important features such as preferential attachment and small-world character.

Keywords: Graph Theory, Scale-free Networks, Social Network Analysis, Surna-

mes Networks, Small-World Networks.

University Web Site URL Here (include http://www.ufrn.br)



Sumário

Agradecimentos iii

Resumo v

Abstract vii

Sumário viii

Lista de Figuras xii

Lista de Tabelas xiv

Abreviações xv

1 Introdução 1

1.1 Apresentação . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1

1.2 O surgimento da Análise de Redes Sociais (ARS) . . . . . . . . . . 2

1.3 O problema para essa Dissertação . . . . . . . . . . . . . . . . . . . 4

1.3.1 Objetivo Geral . . . . . . . . . . . . . . . . . . . . . . . . . 5

1.3.2 Objetivos Especí�cos . . . . . . . . . . . . . . . . . . . . . . 6

viii

Sumário ix

1.4 Por que estudar ARS? . . . . . . . . . . . . . . . . . . . . . . . . . 6

2 Teoria dos Grafos - Uma abordagem sucinta 8

2.1 Apresentação . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 8

2.2 Um pouco da História . . . . . . . . . . . . . . . . . . . . . . . . . 9

2.2.1 As Escolas da TG . . . . . . . . . . . . . . . . . . . . . . . 13

2.3 Formalismo . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 14

2.3.1 De�nição de Grafos . . . . . . . . . . . . . . . . . . . . . . . 14

2.4 Tipos de Grafos . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 18

2.4.1 Grafos simples . . . . . . . . . . . . . . . . . . . . . . . . . . 18

2.4.2 Grafo completo . . . . . . . . . . . . . . . . . . . . . . . . . 19

2.4.3 Grafos bipartidos . . . . . . . . . . . . . . . . . . . . . . . . 19

2.4.4 Grafos planos . . . . . . . . . . . . . . . . . . . . . . . . . . 20

2.4.5 Grafo conexo . . . . . . . . . . . . . . . . . . . . . . . . . . 20

2.4.6 Grafo orientado . . . . . . . . . . . . . . . . . . . . . . . . . 21

2.4.7 Grafo não orientado . . . . . . . . . . . . . . . . . . . . . . 22

2.4.8 Grafos ponderados . . . . . . . . . . . . . . . . . . . . . . . 22

2.4.9 Grafos aleatórios . . . . . . . . . . . . . . . . . . . . . . . . 23

3 Redes Complexas - Modelos e análises de Redes Sociais 25

3.1 Apresentação . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 25

3.2 Aspectos históricos da ARS . . . . . . . . . . . . . . . . . . . . . . 26

3.3 Redes Complexas . . . . . . . . . . . . . . . . . . . . . . . . . . . . 30

Sumário x

3.3.1 Distribuição em Lei de Potência . . . . . . . . . . . . . . . . 30

3.3.2 Redes Livres de Escala . . . . . . . . . . . . . . . . . . . . . 33

3.3.2.1 Menor Caminho Médio e o Efeito de Mundo Pequeno 35

3.4 Propriedades das Redes Complexas . . . . . . . . . . . . . . . . . . 36

3.4.1 Formação de Pólos . . . . . . . . . . . . . . . . . . . . . . . 36

3.4.2 Coe�ciente de Agregação . . . . . . . . . . . . . . . . . . . . 37

3.4.3 Robustez . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 38

3.5 Modelos de Redes Complexas . . . . . . . . . . . . . . . . . . . . . 39

3.5.1 Modelo de Price e ligação preferencial . . . . . . . . . . . . . 39

3.5.2 Modelo de Barabasi-Albert . . . . . . . . . . . . . . . . . . . 40

3.5.3 Modelo de Bianconi-Barabási . . . . . . . . . . . . . . . . . 43

4 Rede dos Sobrenomes 45

4.1 Apresentação . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 45

4.1.1 Preliminares . . . . . . . . . . . . . . . . . . . . . . . . . . . 46

4.1.2 Motivação . . . . . . . . . . . . . . . . . . . . . . . . . . . . 47

4.1.3 Metodologia . . . . . . . . . . . . . . . . . . . . . . . . . . . 47

4.1.3.1 Tipo de Pesquisa . . . . . . . . . . . . . . . . . . . 47

4.1.3.2 Programas Utilizados . . . . . . . . . . . . . . . . . 48

4.1.3.3 Programa para adquirir as listagens . . . . . . . . . 48

4.1.3.4 Programas para o tratamento dos dados . . . . . . 49

4.2 Análise dos Nomes de Família . . . . . . . . . . . . . . . . . . . . . 51

Sumário xi

5 Considerações �nais 59

5.1 Conclusões . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 59

5.2 Perspectivas . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 61

Referências Bibliográ�cas 62

Lista de Figuras

1.1 Redes Sociais . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3

1.2 Redes Sociais Virtuais . . . . . . . . . . . . . . . . . . . . . . . . . 4

1.3 Manifestações Sociais . . . . . . . . . . . . . . . . . . . . . . . . . . 5

1.4 Publicações . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 7

2.1 Grafo Conexo . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 9

2.2 Representação das Pontes de Königsberg . . . . . . . . . . . . . . . 10

2.3 Grafo r-regular . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 17

2.4 Matriz de adjacência . . . . . . . . . . . . . . . . . . . . . . . . . . 17

2.5 Caminho geodésico . . . . . . . . . . . . . . . . . . . . . . . . . . . 18

2.6 Grafo simples . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 19

2.7 Grafo Completo . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 19

2.8 Grafo bipartido . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 20

2.9 Grafo planar . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 21

2.10 Grafo conexo . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 21

2.11 Grafo orientado . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 22

2.12 Grafo não orientado . . . . . . . . . . . . . . . . . . . . . . . . . . 22

xii

Lista de Figuras xiii

2.13 Grafo ponderado . . . . . . . . . . . . . . . . . . . . . . . . . . . . 23

2.14 Grá�co do Modelo de Erdös-Rényi . . . . . . . . . . . . . . . . . . 24

2.15 Grafo Aleatório . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 24

3.1 Grafo Mulheres do Sul . . . . . . . . . . . . . . . . . . . . . . . . . 28

3.2 Grafo movimento social . . . . . . . . . . . . . . . . . . . . . . . . 29

3.3 Rede plana . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 31

3.4 Lei de potência x função exponencial . . . . . . . . . . . . . . . . . 34

3.5 Histograma do Modelo de Barabasi-Albert . . . . . . . . . . . . . . 41

3.6 Rede Barabási-Albert . . . . . . . . . . . . . . . . . . . . . . . . . . 42

3.7 Histograma do Modelo de Bianconi-Barabási . . . . . . . . . . . . . 44

3.8 Rede Bianconi-Barabási . . . . . . . . . . . . . . . . . . . . . . . . 44

4.1 Programa Gephi . . . . . . . . . . . . . . . . . . . . . . . . . . . . 48

4.2 Esquema Sobrenomes . . . . . . . . . . . . . . . . . . . . . . . . . . 50

4.3 Rede Paulos_PT . . . . . . . . . . . . . . . . . . . . . . . . . . . . 52

4.4 Rede Lucianos_BR . . . . . . . . . . . . . . . . . . . . . . . . . . . 54

4.5 Grá�co Marias_BR . . . . . . . . . . . . . . . . . . . . . . . . . . . 55

4.6 Rede Josés_PT . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 56

4.7 Grá�co Josés_PT . . . . . . . . . . . . . . . . . . . . . . . . . . . 57

Lista de Tabelas

2.1 Tabela Lista de adjacência . . . . . . . . . . . . . . . . . . . . . . . 18

3.1 Tabela conectividade dos nós . . . . . . . . . . . . . . . . . . . . . . 31

4.1 Tabela Nomes de famílias no Brasil . . . . . . . . . . . . . . . . . . 53

4.2 Tabela Nomes de famílias em Portugal . . . . . . . . . . . . . . . . 55

4.3 Tabela Redes dos Sobrenomes X Grafos Aleatórios . . . . . . . . . . 58

xiv

Abreviações

Sigla O que ela Representa

ARS Análise de Redes Sociais

CAPES Coordenação de Aperfeiçoamento de Pessoal de Nível Superior

Labic Laboratório de estudos sobre Imagem e Cibercultura

CMAFUL Centro de Matemática e Aplicações Fundamentais da

Universidade de Lisboa

RS Redes dos Sobrenomes

SC Sistemas Complexos

TG Teoria dos Grafos

TRC Teoria de Redes Complexas

xv

Capítulo 1

Introdução

�Algumas pessoas acham que foco signi�ca dizer sim para a coisa em que você vai

se focar. Mas não é nada disso. Signi�ca dizer não às centenas de outras boas

ideias que existem. Você precisa selecionar cuidadosamente."

Steve Jobs

1.1 Apresentação

Este capítulo tem como �nalidade a apresentação deste trabalho e dos obje-

tivos delineados para a concretização do mesmo, além de expor a estrutura orga-

nizacional deste documento.

1

Capítulo 1. Introdução 2

1.2 O surgimento da Análise de Redes Sociais (ARS)

O sociólogo francês Émile Durkheim (1858-1917), tido por muitos como um

dos pais da sociologia moderna, de�ne em seu livro, �As Regras do Método Soci-

ológico� (1895) [1], que o objeto de estudo da Sociologia deve ser o fato social1,

pois ele deriva da vida em sociedade, que é caracterizada pelo conjunto de fatos

sociais estabelecidos.

Desde que o homem se organizou em sociedade, regras e de�nições para o es-

tabelecimento da mesma são criadas, modi�cadas, adaptadas e selecionadas cons-

tantemente. Separar grupos e ditar como cada um deles deve se portar perante

os demais sempre foi uma das grandes preocupações dos mentores2 desse sistema.

Assim foram de�nidos modelos de conduta a serem seguidos pormenorizadamente

por todos, por vezes, estas de�nições de como os membros da sociedade deveriam

se portar privilegiava uma elite, causando muito desconforto nos demais integran-

tes. Todos esses pontos foram motivos para estudos no tocante à Sociologia. O

formalismo matemático utilizado para o estudo da ARS, surgiu dois séculos antes

quando Euler resolveu �O Problema das Pontes de Königsberg" 3.

Alguns autores apontam como marco inicial dos estudos sobre a ARS na

Sociologia, o trabalho de Jacob Levy Moreno (1934), que introduziu sociogramas

para representar as redes de relações interpessoais na Hudson School for Girls.

Entretanto um importante estudo sobre redes sociais foi realizado apenas na dé-

cada de 1960 por Harrison Coyler White e seus alunos, que conseguiram �nalmente

construir uma base consistente para a investigação das redes sociais por meio de

estudos sobre estruturas sociais complexas. White possuia formação em Física,

o que pode ter proporcionado ferramentas adequadas ao estudo quantitativo de

estruturas e processos que envolvem as redes sociais [2].

1O fato social é o objeto central da teoria sociológica de Émile Durkheim, consiste em maneirasde agir, pensar e sentir exteriores ao indivíduo, uma norma coletiva com independência e poderde coerção sobre o indivíduo.

2O termo aqui está sendo usado como uma alusão a um grupo da sociedade (geralmente comfunções políticas e/ou econômicas) que possuem o poder de estabelecer o controle dos �meiossociais de produção�, nele incluído o domínio (geralmente, não aparente) sobre os veículos decomunicação, os estabelecimentos de ensino e a produção cultural.

3Matemático suíço Leonhard Euler (1707-1783).


Figura 1.1: A interação entre pessoas através de interesses em comum a ummesmo grupo (Fonte: Caderno de Sociologia) [3].

Pode-se dizer, grosso modo, que rede social é uma estrutura social composta

por pessoas ou organizações, conectadas por um ou vários tipos de relações, que

geralmente partilham valores e objetivos comuns. Uma das características funda-

mentais na de�nição das redes é a sua abertura (entrada e saída de componentes),

possibilitando relacionamentos horizontais e não hierárquicos entre os participan-

tes. Um estudo mais detalhado sobre as redes sociais é encontrado em [4].

A tendência natural do ser humano é agrupar-se, viver em comunidade, cons-

tituindo uma convivência que possibilita o compartilhamento de informações e

experiências que passam a ser essenciais ao indivíduo. Essa estrutura social que

é criada, nos diferentes círculos frequentados pelos indivíduos, é que os fortalece

e abre oportunidades para realizações. Assim, é nesse contexto que se encontram

as redes sociais, que representam a estrutura, em que os seres estão inseridos e

articulam toda a sua convivência [5].

Atualmente tem-se a febre das redes sociais online que podem operar em dife-

rentes níveis, como, por exemplo, redes de relacionamentos (Facebook, My Space,


Figura 1.2: Redes Sociais Virtuais [6].

Twitter, Badoo), redes pro�ssionais (LinkedIn), entre outras (Figura 1.2). Pode-se

citar ainda as redes comunitárias (redes sociais em bairros ou cidades), as redes

políticas, etc., o que permite analisar a forma como as organizações desenvolvem

a sua atividade, como os indivíduos alcançam os seus objetivos ou medir o capital

social � o valor que os indivíduos obtêm da rede social. Estas redes têm adquirido

importância crescente na sociedade moderna. São caracterizadas primariamente

pela autogeração de seu desenho, pela sua horizontalidade e sua descentralização.

Um ponto em comum dentre os diversos tipos de rede social é o compartilhamento

de informações, conhecimentos, interesses e esforços em busca de objetivos comuns

(Figura 1.3). A intensi�cação da formação das redes sociais, nesse sentido, geral-

mente re�ete um processo de fortalecimento da Sociedade Civil, em um contexto

de maior participação democrática e mobilização social.

1.3 O problema para essa Dissertação

O problema de�nido para essa dissertação é:


Figura 1.3: Movimento estudantil em 2013 que �cou conhecido como Prima-vera brasileira (Fonte: Blog do Sacha)[7].

�Um dos grandes objetivos da Física Estatística é o estudo dos Sistemas Comple-

xos (SC). Tem-se um SC quando suas propriedades não são uma consequência

natural de seus elementos constituintes vistos isoladamente. As propriedades emer-

gentes de um SC decorrem em grande parte da relação não-linear entre as partes.

Costuma-se dizer que em um SC o todo é mais que a soma das partes. O estudo

dos SC incluem sistemas sociais (redes sociais), biológicos (colônias de animais),

físicos (clima) entre outros. No que se refere as redes sociais, como se comportam

as redes reais?"

Para abordar este problema, a dissertação é dividida segundo os objetivos

geral e especí�cos a seguir.

1.3.1 Objetivo Geral

Este trabalho tem por objetivo geral estudar uma rede social real através

da análise de simulações computacionais para a obtenção de dados e consequente

analogia com modelos de redes encontrados na literatura.


1.3.2 Objetivos Especí�cos

Com a �nalidade de alcançar o objetivo geral desta dissertação, foram consi-

derados os seguintes objetivos especí�cos:

• Reproduzir através de simulações computacionais os modelos teóricos para

posteriores analogias;

• Calcular os coe�cientes de agregação local e médio das redes simuladas;

• Calcular o menor caminho médio nas redes simuladas;

• Veri�car o valor do expoente da lei de potência que governa a distribuição

de conectividades de cada rede simulada;

• Simular grafos aleatórios com o mesmo tamanho das redes.

1.4 Por que estudar ARS?

A partir da análise das relações entre os atores4 de uma rede social, podemos

obter informações sobre a dinâmica de uma determinada parcela da sociedade

analisada e, assim, construir estimativas estatísticas acerca da sociedade como um

todo. Além disso, o conhecimento dos dados daARS serve de base para a inspeção

e análise de resultados de investimentos em diversos campos de interesse, sejam

estes econômicos, sociais, mudanças no comportamento coletivo, etc.

Vale a pena frisar que nos últimos anos revistas importantes para a comuni-

dade cientí�ca tais como Physical Review, Nature e Science, publicaram um grande

número de artigos sobre ARS e/ou Redes complexas, na �gura 1.4 é mostrado um

grá�co com as publicações nessa área durante o �nal do século XX e a primeira

década do século XXI.

4Aqui o termo atores está se referindo a ação dos agentes que formam a rede, no capítulo 2

esse termo será chamado de vértice (no caso dos grafos) e no capítulo 3 será chamado de nó (nocaso das redes).


Figura 1.4: Publicações em revistas sobre ARS de 1996 a 2008 - Fonte: Bancode Dados SCOPUS ([8]).

Capítulo 2

Teoria dos Grafos - Uma abordagem

sucinta

�Os computadores são incrivelmente rápidos, precisos e burros; os homens são

incrivelmente lentos, imprecisos e brilhantes; juntos, seus poderes ultrapassam os

limites da imaginação."

Albert Einstein

2.1 Apresentação

Neste capítulo apresentam-se os aspectos históricos da construção da Teoria

dos Grafos, os conceitos básicos de grafo1 em sua formalização matemática, assim

como uma apresentação dos tipos de grafos. Este trabalho tem como objetivo

abordar o tema da forma mais explícita possível, para tanto é feita uma apresen-

tação rápida e simples que permita uma melhor compreensão dos grafos e a sua

utilidade no cotidiano. Os conceitos abordados ao longo deste capítulo podem

1Na conotação atual, a palavra �grafo� foi usada primeiramente pelo matemático inglês James

Joseph Sylvester (1814-1897).

8

Capítulo 2. Teoria dos Grafos - Uma abordagem sucinta 9

ser encontrados em [9] e [10]. As �guras usadas neste trabalho são devidamente

creditadas, excetuando-se as que foram feitas pela própria autora.

2.2 Um pouco da História

Historicamente a TG foi introduzida pelo matemático Leonhard Paul Euler

no século XVIII. Desconsiderando o rigor matemático, um grafo pode ser pensado

como um conjunto de pontos, chamados vértices (nós ou nodos), conectados por

linhas, chamadas de arestas, e a esta estrutura dar-se também o nome de rede.

Figura 2.1: Grafo com 4 vértices e 6 arestas.

Euler �cou conhecido como o pai da TG quando resolveu (em 1736) um

famoso problema de sua época, o Problema das Pontes de Königsberg. Existiam

duas ilhas ligadas uma à outra e ao rio Pregel2 por sete pontes (Figura 2.2a). O

problema consistia em sair de um determinado ponto qualquer, passar por todas

as pontes uma única vez e retornar ao ponto de partida. Euler demonstrou que

o problema não tinha solução e para tanto apresentou à Academia de Ciências

Russa de São Petersburgo um diagrama em que fazia a seguinte analogia: à terra,

representada pelas duas margens, e às duas ilhas, associou quatro pontos; às sete

pontes, associou sete linhas [11], produzindo assim o que hoje chamamos de grafo

(Figura 2.2b).

2Rio que banhava a pequena cidade universitária prussiana de Königsberg, hoje Kaliningrad,Rússia.


Figura 2.2: (a) Problema das sete pontes de Königsberg (Fonte: Site do CMA-FUL) e (b) Grafo do problema das pontes de Königsberg.

Mostrar que o problema não tem solução é equivalente a mostrar que o grafo

da Figura 2.2b não pode ser atravessado [9]. Euler generalizou o problema e

desenvolveu um critério para que um grafo pudesse ser atravessado, este deveria

estar conectado e cada um de seus pontos ser incidente a um número par de linhas.

No caso das pontes de Königsberg a primeira condição era satisfeita, todavia a

segunda não, uma vez que o grafo não possuía nenhum ponto que fosse incidente a

um par de linhas. Sendo assim era necessário a inclusão de pelo menos mais uma

ponte para tornar o problema solucionável.

De acordo com Harary3, �A teoria dos grafos foi redescoberta muitas vezes�.

Neste caso vale observar que durante um período de mais de 150 anos, entre a

demonstração de Euler e a última década do século XIX, foi veri�cado o surgimento

de poucos trabalhos. Entre estes, está o trabalho de Kirchho� 4 que, em 1847,

utilizou modelos de grafos no estudo de circuitos elétricos criando assim o que

3Matemático estadunidense Frank Harary (1921-2005) especializado em TG.4Gustav Robert Kirchho� (1824 � 1887) - Físico alemão. Suas contribuições cientí�cas foram

principalmente no campo dos circuitos elétricos, na espectroscopia, na emissão de radiação doscorpos negros e na teoria da elasticidade (modelo de placas de Kirchho��Love).


�cou conhecido como a teoria das árvores5. Uma década depois, Cayley6 a exemplo

de Kirchho� trilharia as mesmas ideias, embora tendo outra �nalidade e outras

aplicações em mente, dentre as quais se destaca a enumeração dos isômeros dos

hidrocarbonetos alifáticos saturados, em química orgânica. Em 1869, Jordan7 se

ocupou também das árvores, porém com um enfoque estritamente matemático.

Muitos eventos que com o passar dos anos provaram ser importantes, no

que se refere a matemática pura, são relacionados com problemas com pouca

aplicação prática: Hamilton8, em 1859, inventou um jogo que consistia na busca

de um percurso fechado envolvendo todos os vértices de um dodecaedro regular,

de tal modo que cada um deles fosse visitado uma única vez. É interessante,

aliás, observar que os problemas de Hamilton e de Euler encontraram aplicação,

respectivamente um e dois séculos mais tarde, no campo da pesquisa operacional9.

Kempe10 em 1879 procurou, sem sucesso, demonstrar a "conjectura das quatro

cores"11, apresentada por Guthrie12 a De Morgan13, em 1852.

Muitos dos melhores matemáticos do século XX trabalharam seriamente no

problema das quatro cores. Este estudo teve um papel muito importante no de-

senvolvimento da Teoria dos Grafos. Pelo caminho muitas questões foram postas

e vários problemas relacionados foram resolvidos [12].

Heawood14 em 1890 mostrou que a prova de Kempe estava errada, obtendo

uma prova válida, porém para cinco cores; a prova para as quatro cores foi obtida

apenas em 1976. A importância do problema reside nos desenvolvimentos teóricos

5Uma árvore é um grafo no qual existe um caminho entre quaisquer dois de seus vértices eque não possui ciclos.

6Arthur Cayley ( 1821 � 1895) - Matemático britânico. As suas contribuições incluem amultiplicação de matrizes e o teorema de Cayley.

7Wilhelm Jordan (1842 � 1899) - Geodesista e matemático alemão.8William Rowan Hamilton (1805 � 1865) - Matemático, físico e astrônomo irlandês.9É o uso de modelos matemáticos, estatística e algoritmos para ajudar na tomada de decisões.

É uma forma de matemática aplicada.10Sir Alfred Bray Kempe (1849 � 1922) - Matemático inglês.11Trata-se de provar que todo mapa desenhado no plano e dividido em um número qualquer

de regiões pode ser colorido com um máximo de quatro cores sem que duas regiões fronteiriçasrecebam a mesma cor.

12Francis Guthrie (1831 - 1899) - Matemático e botânico sul-africano.13Augustus De Morgan (1806 � 1871) - Matemático e lógico britânico. Formulou as Leis de

De Morgan e foi o primeiro a introduzir o termo e tornar rigorosa a ideia da indução matemática.14Percy John Heawood (1861 - 1955) - Matemático inglês.


trazidos pelas tentativas de resolvê-lo, as quais enriqueceram a TG em diversos

recursos ao longo da primeira metade do século XX: exempli�cando, Birkho� 15

em 1912 de�niu os polinômios cromáticos; Whitney16 em 1931 criou a noção de

grafo dual e Brooks17[13] em 1941 enunciou um teorema fornecendo um limite para

o número cromático de um grafo.

Pode-se citar também outros eventos consideráveis: Menger 18 (1926) demons-

trou um importante teorema sobre a conectividade em grafos �nitos não direci-

onados que �cou conhecido como (Teorema de Menger) e Kuratowski19 em 1930

encontrou uma condição para a caracterização de grafos planares. Turán20 em

1941 foi o pioneiro na teoria extremal dos grafos que resultou no (Teorema de

Turán) e Tutte21 em 1947 classi�cou os grafos simétricos cúbicos pelo menor nú-

mero inteiro s tal que cada dois caminhos orientados de comprimento s podem ser

mapeados entre si por exatamente uma simetria do grafo. Ele mostrou que s é no

máximo 5, e deu exemplos de grafos com cada valor possível de s de 1 a 5[14]. É

importante frisar que o primeiro livro sobre TG foi (Theorie der endlichen und

unendlichen Graphen), publicado pela Akademischen Verlagsgesellschaft Editora

Acadêmica de Leipzig em 1936 escrito por König22, uma época na qual, conforme

Wilder 23, o assunto era considerado "um campo morto".

A partir de 1956, com a publicação dos trabalhos de Ford24 e Fulkerson25,

15George David Birkho� (1884 � 1944) - Matemático estadunidense, mais conhecido pelaelaboração do teorema ergódico.

16Hassler Whitney (1907 - 1989) - Matemático estadunidense. Foi um dos fundadores da teoriada singularidade.

17Rowland Leonard Brooks (1916 - 1993) - Matemático inglês.18Karl Menger (1902 � 1985) - Matemático austríaco.19Kazimierz Kuratowski (1896-1980) - Matemático polonês cuja pesquisa se concentrou na

área de topologia.20Paul (Pál) Turán (1910 � 1976) - Matemático húngaro. Trabalhou principalmente com

teoria dos números. Teve uma longa colaboração com Paul Erdös.21William Thomas Tutte , também conhecido como Bill Tutte (1917 - 2002) - Matemático e

�Codebreaker� britânico. Durante a II Guerra Mundial, ele fez um avanço brilhante e fundamen-tal em Criptoanálise da cifra Lorenz, um dos principais sistemas de cifras alemão. A inteligênciaobtida a partir de seu trabalho teve um impacto signi�cativo sobre a vitória dos Aliados naEuropa.

22Dénes König (1884 � 1944) - Matemático húngaro.23Raymond Louis Wilder (1896 - 1982) - Matemático estadunidense, que se especializou em

topologia e gradualmente adquiriu interesses �losó�cos e antropológicos.24Lester Randolph Ford, Jr (1927, Houston) - Matemático estadunidense.25Delbert Ray Fulkerson (1924 � 1976) - Matemático estadunidense.


Berge26 em 1957 e Ore27 em 1962, o interesse pela TG começou a aumentar,

crescendo rapidamente no mundo todo. A imensa maioria dos livros sobre grafos

foi publicada depois de 1970, em grande parte sob a in�uência das obras de Berge e

Harary. O desenvolvimento dos computadores levou à publicação de várias obras

dedicadas aos algoritmos de grafos, abrindo assim possibilidades crescentes de

utilização aplicada da teoria.

2.2.1 As Escolas da TG

• A primogênita é a Escola húngara, teve origem nos trabalhos de König e foi

desenvolvida por Erdös, Hajnãl, Turán entre outros. O principal interesse dessa

escola derivou da análise combinatória e alguns de seus autores se dedicaram à

teoria extremal. Habitualmente, essa escola trabalha com grafos não orientados.

• A Escola francesa, trabalha com grafos orientados. Nas palavras de Claude

Berge: �todo grafo é orientado, podendo-se eventualmente desconsiderar a orien-

tação�; essa escola dedica-se principalmente às aplicações no campo da pesquisa

operacional. Alguns nomes de extrema relevância tanto na pesquisa quanto na di-

vulgação da teoria e de suas aplicações são Ghouila-Houri, Kaufmann, Roucairol,

Faure e Minoux.

• A Escola americana tem grande in�uência do trabalho de Harary. Nesta

escola há preferência pelo estudo de grafos não orientados como na escola húngara,

mas também dar-se devida atenção ao grafos orientados. Pesquisadores importan-

tes dessa escola são Chartrand, Ore, Hu, Fulkerson e Whitney.

• A Inglaterra, o Canadá e a ex-União Soviética28, deram contribuições sig-

ni�cativas para o tema assim como possuem diversos nomes de relevo.

26Claude Berge (1926 � 2002) - Matemático francês. É conhecido pela conjectura do grafoperfeito e pelo lema de Berge.

27Øystein Ore (1899 � 1968) - Matemático norueguês.28 O�cialmente União das Repúblicas Socialistas Soviéticas URSS, era um Estado socialista

constitucional que existiu na Eurásia entre 1922 e 1991.


• Temos ainda os pesquisadores de aplicações especí�cas, em particular os de-

dicados às aplicações em electricidade: Chen, Seshu, Reed, Johnson. Esse trabalho

se caracteriza pelo uso de um subconjunto bastante característico dos recursos da

teoria, as origens, evidentemente, estão no trabalho de Kirchho�. Têm-se também

a chamada �teoria do equilíbrio estrutural� nas aplicações a psicossociologia, base-

ada nas ideias de Moreno; diversos aspectos da teoria das árvores nas aplicações à

computação; e a teoria dos �uxos em redes nas aplicações de pesquisa operacional

em transportes e comunicações [15].

2.3 Formalismo

2.3.1 De�nição de Grafos

Muitas situações podem ser convenientemente descritas através de diagramas

que consistem de um conjunto de pontos, juntamente com linhas que ligam alguns

pares destes pontos. Por exemplo: os pontos podem representar pessoas, as linhas

ligam pares de amigos; os pontos podem representar centros de comunicação, as

linhas ligações entre os centros. A abstração matemática de situações desse tipo

dá lugar ao conceito de grafo [16].

Doravante serão trabalhados os aspectos básicos da TG de forma sintética sob

a luz dos fundamentos matemáticos. Para qualquer conjunto V , será denotado por

V (2) o conjunto de todos os pares não ordenados de elementos de V . Se V tem n

elementos então V (2) tem (n

2

)=n(n− 1)

2(2.1)

elementos. Os elementos de V (2) serão identi�cados com os subconjuntos de V que

têm cardinalidade29 2. Assim, cada elemento de V (2) terá a forma {v, w} sendo v

e w dois elementos distintos de V .29É a quantidade de elementos que pertencem ao conjunto em questão.


De�nição 2.3.1. Um grafo é um par (V ;A) em que V é um conjunto arbitrário

e A é um subconjunto de V (2) . Os elementos de V são chamados vértices e os de

A são chamados arestas.

Este texto será restrito a grafos em que o conjunto de vértices é �nito e tem

cardinalidade maior que zero.

Uma aresta como {v, w} será denotada simplesmente por vw ou por wv, uma

vez que trata-se de grafos não orientados. A aresta vw incide nos vértices v e w

e estes são as pontas da aresta. Se vw é uma aresta, então os vértices v e w são

vizinhos ou adjacentes.

Nesse trabalho é considerado que um grafo não pode ter duas arestas diferentes

com o mesmo par de pontas (ou seja, não pode ter arestas �paralelas�). Também

não pode ter uma aresta com pontas coincidentes (ou seja, não pode ter �laços�).

Há quem goste de enfatizar esse aspecto dizendo que o grafo é �simples�.

Muitas vezes é conveniente dar um nome ao grafo como um todo. Se o nome

do grafo for G, o conjunto dos seus vértices será denotado por V(G) e o conjunto

das suas arestas por A(G). O número de vértices de G é denotado por n(G) e o

número de arestas por m(G); [10] matematicamente,

n(G) = |V(G)| e m(G) = |A(G)| (2.2)

onde |S| denota a cardinalidade do conjunto S, qualquer que seja ele.

O tamanho do grafo G é a soma do número de seus vértices com o número de

suas arestas. Dessa forma o grafo vazio é aquele que não tem arestas nem vértices,

logo tem tamanho zero.

A expressão G− vw representa o grafo G menos a aresta {v, w}. E dado um

vértice v, então a expressão G − v representa o grafo G menos o vértice v e as

arestas que contêm v. As arestas vw e xz são chamadas adjacentes se, e somente

se, possuem um vértice, digamos o vértice v em comum, ou seja v deve ser igual a


x ou z ou o mesmo para w. A multiplicidade de uma aresta denota a quantidade

de vezes que esta aresta ocorre em A(G). Uma aresta múltipla pode formar um

laço quando v ∈ V(G) e vv ∈ A(G).30.

O grau de um vértice v é dado pelo número de arestas que contêm v e será

chamado de g(v). Dessa forma podem ocorrer vértices pares ou ímpares de acordo

com o número de seu grau.

O Grau máximo de um grafo G, denotado por 4(G), é de�nido por:

4 (G) = max {g(v)|v ∈ V(G)} (2.3)

O Grau mínimo, denotado por δ(G), é de�nido por:

δ(G) = min {g(v)|v ∈ V(G)} (2.4)

A vizinhança de um vértice v é o conjunto dos vértices adjacentes a v,

denotada por V(v):

V(v) = {w ∈ V(G)|vw ∈ A(G)} (2.5)

A ordem de um grafo G é a cardinalidade do conjunto V(G), denotado por

|V(G)|, e a dimensão de G é a cardinalidade do conjunto A(G), denotada por |A(G)|

[17].

Um grafo G cujos vértices são todos de mesmo grau r é chamado regular de

grau r ou r-regular. Assim, temos que o seu número de arestas é

m =1

2nr (2.6)

onde n é o número de vértices. Ao observarmos um grafo Kn31, vemos que Kn é

regular de grau n− 1 [17]. Exempli�ca-se tal a�rmação na �gura 2.3.

De acordo com [16], da de�nição de grafo dada acima segue imediatamente:

30Em grafos simples não pode ter a ocorrência de multiplicidade de arestas nem de laços, nestetrabalho não são considerados grafos com laços, mas grafos contendo apenas arestas simples.

31Kn representa um grafo completo com n vértices.


Figura 2.3: É um grafo K4, mas também é um grafo 3-regular.

Proposição 2.3.1. A soma dos graus dos vértices de um grafo é igual ao dobro

do número de arestas do grafo.

Corolário 2.3.1. Em todo grafo, o número de vértices de grau ímpar é par.

A Matriz de Adjacência de um grafo G é a matriz M com linhas e colunas

indexadas por V(G) tal que M [v, w] = 1 se vw ∈ A(G) e M [v, w] = 0 em caso

contrário. Conforme exemplo ilustrado na �gura 2.4.

Figura 2.4: Representação matricial através da matriz de adjacência (es-querda) e esquemática (direita) de um mesmo grafo.

Uma vez de�nada a matriz de adjacência, é fácil montar a lista de adjacência

de cada vértice (veja de�nição de vizinhança na equação 2.5). A tabela 2.1 mostra

as listas de adjacência para o grafo representado na �gura 2.4.

Um Caminho é um grafo G cujo conjunto de vértices admite uma permutação

(v1, v2, ..., vn) tal que

{v1v2, v2v3, ..., vn−1vn} = A(G) (2.7)


Vértices Vizinhos1 2, 52 1, 3, 53 2, 44 3, 5, 65 1, 2, 46 4

Tabela 2.1: Lista de adjacância do grafo da �gura 2.4

onde os vértices v1 e vn são os extremos do caminho.

O Caminho geodésico também chamado simplesmente de o caminho mais

curto, é um caminho entre dois vértices de tal forma que não exista caminho mais

curto [18] ao longo de todo o grafo.

Figura 2.5: Um caminho geodésico de comprimento dois entre dois vértices.

O comprimento de um caminho geodésico, muitas vezes chamado de distância

geodésica, menor distância ou distância química, é, portanto, a distância mais

curta entre os vértices do grafo em questão.

2.4 Tipos de Grafos

2.4.1 Grafos simples

Um grafo é simples se, no máximo, existe uma aresta unindo quaisquer dois

vértices. Isto é equivalente a dizer que uma aresta qualquer é a única que une


dois vértices especí�cos (�gura 2.6). Um grafo que não é simples, é chamado um

multigrafo.

Figura 2.6: Grafo simples é um grafo no qual uma única aresta une doisvértices.

2.4.2 Grafo completo

Um grafo é completo se existem arestas unindo todos os pares possíveis de

vértices. Ou seja, todo par de vértices (v, w) deve ter uma aresta os unindo (�gura

2.7). O conjunto dos grafos completos é usualmente chamado de K, e denomina-se

Kn o grafo completo com n vértices e n(n− 1)/2 arestas.

Figura 2.7: Exemplo de grafo completo.

2.4.3 Grafos bipartidos

Um grafo G é bipartido se pode ser expresso como G = {VG1 ∪ VG2, AG}, isto

é, seus vértices são a união de dois grupos de vértices, com as seguintes condições:


• VG1 e VG2 são distintos e não vazios;

• Cada aresta de AG une um vértice de VG1 com um vértice de VG2;

• Não existem arestas unindo dois elementos de VG1; o mesmo para VG2.

Obedecidas essas condições, o grafo é considerado bipartido (�gura 2.8) e

pode ser descrito informalmente como o grafo que une ou relaciona dois conjuntos

de elementos diferentes.

Figura 2.8: Exemplo de grafo bipartido.

2.4.4 Grafos planos

Um grafo G é planar se sua representação esquemática num plano é tal que

cada linha representando uma aresta não toca nenhuma outra (�gura 2.9).

2.4.5 Grafo conexo

Um grafo é conexo se quaisquer que sejam os vértices distintos v e w existe

sempre um caminho que os une (�gura 2.10).


Figura 2.9: Exemplos de grafos planos.

Figura 2.10: Exemplo de grafo conexo.

2.4.6 Grafo orientado

Um grafo G é orientado32 quando cada uma de suas arestas está associada a

um par ordenado de vértices onde o primeiro é a extremidade inicial da aresta e

o segundo a extremidade �nal (�gura 2.11). Sendo vi e vj vértices de um grafo

orientado, então a aresta Ak pode ser indicada pelo par ordenado (vi, vj) em que

vi é o extremo inicial e vj é o extremo �nal.

32Também chamado de dirigido ou digrafo.


Figura 2.11: Exemplo de grafo orientado.

2.4.7 Grafo não orientado

É o grafo em que a ligação entre quaisquer dois vértices não tem orientação

(�gura 2.12), logo não existe distinção entre o extremo inicial ou �nal e a aresta

{v, w} é a mesma aresta {w, v}.

Figura 2.12: Exemplo de grafo não orientado.

2.4.8 Grafos ponderados

São grafos em que um número é atribuído a cada uma das arestas (�gura 2.13).

Este numero representa um peso para o percurso através da aresta. Este peso pode

indicar, por exemplo, a distância entre os vértices. De�ne-se o comprimento de


um caminho em um grafo ponderado como a soma dos pesos das arestas que o

formam.

Figura 2.13: Exemplo de grafo ponderado e orientado.

2.4.9 Grafos aleatórios

Fixado um grafo G = (V ;A), um grafo aleatório é um grafo resultante do

processo aleatório de adicionar cada aresta de G com probabilidade p de maneira

independente. O conceito foi introduzido pela primeira vez em [19] por Erdös e

Rényi e utilizado para provar a existência de grafos com uma propriedade especí-

�ca. Trata-se de provar que a probabilidade de obter grafos com uma propriedade

�xada é positiva, portanto tais grafos existem [20].

Como neste trabalho supõe-se que os grafos possuem um número �nito de

vértices, então |V | = n, e o interesse é apenas nas componentes conexas quando n

cresce, doravante será denotado por G(n, p) o grafo aleatório.

Sendo G um grafo completo com n vértices, a probabilidade P de se obter

um grafo �xo com L arestas é:

P(G(n, p)) = pL(1− p)N−L (2.8)

Onde N =(n2

). E este é o grafo do modelo de Erdös e Rényi.


Num grafo aleatório não existe nenhum critério que privilegie umas ligações

em relação a outras, e portanto este �ca caracterizado pelo número n de vértices

e pela probabilidade p de que uma aresta qualquer seja estabelecida.

Figura 2.14: Grá�co da distribuiçao do grau dos vértices do Modelo de Erdös-Rényi com melhor ajuste gaussiano para 105 vértices e 2× 106 arestas.

Figura 2.15: Grafo Aleatório do Modelo de Erdös e Rényi gerado usando oprograma Gephi.

Capítulo 3

Redes Complexas - Modelos e

análises de Redes Sociais

�Conexões podem mudar o mundo; Todo vértice é importante."

Anônimo

3.1 Apresentação

Neste capítulo apresentam-se os aspectos históricos da construção das redes

sociais, os conceitos básicos de ARS, os conceitos de redes e como são usadas as

de�nições de grafos apresentadas no capitulo anterior para construí-las, e alguns

dos modelos teóricos de Redes. Os conceitos abordados aqui podem ser encontra-

dos em [18].

25

Capítulo 3. Redes Complexas - Modelos e análises de Redes Sociais 26

3.2 Aspectos históricos da ARS

A análise das redes sociais procura formatar os percursos existentes nas re-

lações entre as pessoas, as organizações, ou os Estados [21]. Na terminologia das

redes sociais, as pessoas ou grupos são denominados como atores e as conexões

como ligações. As unidades de análise das redes são os conjuntos compostos por

grupos de indivíduos e suas inter-relações [22].

Esse tipo de estudo desenvolveu-se a partir dos conceitos estruturais do an-

tropólogo Radcli�e-Brown1. No período de 1930 a 1970, um número crescente de

antropólogos sociais e de sociólogos começou a trabalhar sobre os conceitos de �es-

trutura social� de Radcli�e-Brown e tentar decifrar as metáforas da vida social por

ele utilizadas. Dessas metáforas, sobressaiu-se a da �rede social�; os pesquisadores

começaram a investigar a �densidade� e a �textura� das redes sociais estudadas. A

partir da década de 1950, um grupo pequeno de especialistas deu início à conceitu-

ação, com maior propriedade, da tradução dessas metáforas, e diversas técnicas de

trabalho e de aplicações especiais apareceram a partir de 1970. Dessas pesquisas

emergiram os conceitos-chave da análise das redes sociais [23].

Para a maioria das pessoas, a expressão �rede social� se refere a serviços de

redes sociais online como o Facebook. O estudo das redes sociais, no entanto,

remonta a algo muito maior que as encarnações modernas de redes de computado-

res. De fato, entre os pesquisadores que estudam redes, os sociólogos têm, talvez,

a mais longa tradição e o melhor estabelecimento de trabalho quantitativo, empí-

rico. Há antecedentes claros de análise de redes sociais que podem ser encontrados

na literatura, alguns datando do �nal do século XIX. O verdadeiro fundamento

do campo, no entanto, é geralmente atribuído ao psiquiatra Jacob Moreno, um

imigrante romeno para a América, que em 1930 tornou-se interessado na dinâmica

das interações sociais dentro de grupos de pessoas. Em uma conferência médica

em Nova York em março 1933 ele apresentou os resultados de um conjunto de es-

tudos que ele tinha realizado que podem ter sido os primeiros verdadeiros estudos

1Alfred Reginald Radcli�e-Brown cientista social britânico, considerado um dos maiores ex-poentes da Antropologia, desenvolveu a teoria do funcionalismo estrutural.


de redes sociais, e o trabalho atraiu atenção su�ciente para merecer uma coluna

no New York Times alguns dias depois. Um ano depois Moreno publicou um livro

intitulado �Quem sobreviverá?� [24], que, embora não seja um trabalho rigoroso

para os padrões modernos, continha as sementes do campo da sociometria, que

mais tarde tornou-se a análise de rede social.

Moreno chamou seus diagramas de interação humana de sociogramas, ao invés

de redes sociais (um termo não cunhado até cerca de vinte anos mais tarde), mas

em tudo, menos no nome eles são claramente o que hoje conhecemos como redes.

Como os sociogramas de Moreno traziam conclusões simples, que são sociologi-

camente interessantes e fáceis de ver, uma vez que traçam um retrato da rede,

rapidamente convenceram os cientistas sociais que havia mérito nos métodos do

pesquisador.

Uma das coisas mais importantes para apreciar sobre redes sociais é que exis-

tem muitas de�nições possíveis diferentes, então uma vantagem em tal rede ou

a de�nição particular ou ainda uma utilidade vai depender de quais perguntas

alguém está interessado em responder. Uma aresta pode representar a amizade

entre os indivíduos, mas também pode representar relações pro�ssionais, a troca de

bens ou dinheiro, padrões de comunicação, relações românticas, ou muitos outros

tipos de conexão. Um estudo sobre propagação de informação numa rede pode ser

encontrado em [25] e [26]. Se alguém estiver interessado, por exemplo, em inte-

rações pro�ssionais entre os conselhos de administração de empresas da Fortune

500, analisar, uma rede de quem está namorando com quem ou quem olha para a

página do Facebook de outra pessoa provavelmente não será de muita utilidade.

Além disso, as técnicas usadas para investigar os diferentes tipos de interação so-

cial também podem ser muito diferentes, logo diferentes tipos de estudos de redes

sociais são normalmente necessários para tratar diferentes tipos de perguntas.

Um experimento com questionamentos diretos de pessoas numa dada socie-

dade é provavelmente o método mais comum de determinar a estrutura das redes

sociais. Outra técnica importante, o uso de documentos de arquivo, é ilustrada por

um exemplo de um estudo de rede social que foi realizado nos EUA na década de


1930 com uma rede social de 18 mulheres em uma cidade sul-estadunidense. Este

estudo, muitas vezes referido na literatura como o "Southern Women Study", foi

descrito pelos pesquisadores em um livro publicado em 1941 [27], apesar de ter sido

baseado em dados de 1939. Eles tomaram uma amostra de 14 eventos sociais com

a participação das mulheres em questão. As mulheres nesta rede estavam conecta-

das se elas participavam de um evento em comum. Uma representação alternativa

e mais completa dos dados é como um �grafo bipartido�, uma rede com dois tipos

de vértices, representando as mulheres e os eventos, com arestas conectando cada

mulher aos eventos que ela participou. A visualização da rede para este estudo

é mostrada na �gura 3.1. Uma razão pela qual este estudo tornou-se tão conhe-

cido, além de sua antiguidade, é que os pesquisadores veri�caram que as mulheres

se dividiram em dois subgrupos, aglomerados fortes de conhecidas, com apenas

poucas interações soltas entre os aglomerados. Um problema clássico na análise

de redes sociais é criar um método ou algoritmo que possa descobrir e extrair tal

agrupamento de dados de rede crus, e um grande número de pesquisadores têm

feito uso dos dados das mulheres do Sul como um teste para o desenvolvimento de

tais métodos [18].

Figura 3.1: Grafo do estudo Mulheres do Sul mostrando as propriedades quese formaram na rede como os aglomerados. Figura retirada de [18].

Atualmente as redes sociais virtuais oferecem um vasto e útil banco de infor-

mações para o estudo das redes sociais, uma vez que a informação �ca acessível a

todos de forma online. As pessoas marcam seus encontros através dessas redes, a

informação é rápida e o alcance é extremo, um pouco dessa dinâmica é mostrada


na �gura 3.2. Frequentemente estamos vendo grupos marcando ações locais e glo-

bais de ocupação das ruas para a reivindicação de novas formas de participação

política. Tais ações são um desdobramento das manifestações iniciadas no ano de

2012, principalmente na Europa, no Oriente Médio, no Norte da África e nos EUA

com a reivindicação de uma �democracia real�. Nesses movimentos vemos emergir

as propriedades das redes sociais e principalmente o caráter de sistema complexo.

Figura 3.2: Grafo gerado a partir do Gephi pelo grupo do Labic (Laboratóriode estudos sobre Imagem e Cibercultura) monitorando a �hashtag� ]12M utili-zada pelos manifestantes em uma rede social virtual. Figura disponibilizada no

site do Labic por Gabriel Herkenho�.


3.3 Redes Complexas

No capítulo anterior estudou-se os conceitos básicos da TG, agora será apre-

sentada uma importante aplicação dessa teoria: a Teoria de Redes Complexas

(TRC). Uma rede corresponde a um grafo, coloquialmente chamamos os vértices

de nós, e no caso especí�co de Redes Sociais, atores, e as arestas de ligações. Esta

rede (ou grafo), é usada para representar quaisquer relações que se queria estu-

dar como a distribuição de amigos numa escola ou bairro residencial, citações de

autores em trabalhos cientí�cos, redes de transporte, redes de comunicação, etc.

O foco principal de um estudo envolvendo redes é a análise das propriedades dos

vários tipos de grafos e suas formações, isto é, a maneira como os nós se agrupam.

Estes estudos embasam a compreensão da complexidade do mundo que nos rodeia.

No �nal do século passado, com o surgimento da Internet passou a ser possível

o acesso a um grande volume de informação, nesse contexto surgiu a TRC. No

tocante à aplicabilidade da TG, a TRC trabalha com modelos de redes reais e

para tanto faz uso de dados empíricos.

3.3.1 Distribuição em Lei de Potência

Conforme visto anteriormente, uma das características fundamentais de um

grafo é a distribuição do grau de seus vértices (no caso das redes, da conectividade

de seus nós ou nodos), pois esta de�ne a estrutura da rede. Tal qual de�nido

na seção 2.2.1 o grau (agora será chamado de conectividade) de um nó (antes

chamado de g(v) agora será chamado de k) é o número de arestas ligadas a ele.

Ao considerar redes não direcionadas2 pode-se de�nir uma grandeza impor-

tante para o estudo da distribuição de conectividades numa rede: a distribuição de

probabilidade das conectividades, que será chamada distribuição de conectividade

pk.

2Este estudo também pode ser feito para redes direcionadas.


De�nição 3.3.1. pk é a fração dos nós em uma rede que têm conectividade k 3.

Como exemplo, tem-se a �gura 3.3 com n = 8, onde n é o número de nós:

Figura 3.3: Rede cujas conectividades dos vértices estão listados na tabela 3.1.

Nós Conectividade k1 12 23 44 15 26 47 18 1

Tabela 3.1: Tabela com a conectividade de cada nó da rede da �gura 3.3.

Assim os valores para pk são:

p1 =4

8, p2 =

2

8, p3 = 0, p4 =

2

8, p5 = 0, p6 = 0, p7 = 0, p8 = 0 (3.1)

O valor pk também pode ser pensado como a probabilidade de que um nó

escolhido aleatoriamente na rede tenha conectividade k [18]. Este será um ponto

de vista útil quando os modelos teóricos de redes forem estudados nas próximas

seções.3Esta de�nição é exatamente verdadeira no limite termodinâmico, ou seja, pra uma rede com

um número de nós altíssimo, que para �ns práticos possa ser considerado in�nito.


No entanto a distribuição da conectividade de uma rede não diz completa-

mente qual é a estrutura da rede, ela dá uma informação muito importante sobre

uma rede, mas não dá toda a informação. Ao fazer um grá�co de pk em função

de k veri�ca-se que muitos nós têm uma conectividade pequena enquanto poucos

têm uma conectividade com número apreciável. Na verdade, observa-se que quase

todas as redes reais têm distribuições de conectividades formando uma cauda con-

tendo os nós mais conectados. Na linguagem estatística, tem-se uma distribuição

das conectividades desviada pra direita [18].

Fazendo um grá�co de pk em função de k em escalas logarítmicas, ou seja,

ambos os eixos logarítmicos, a distribuição de conectividade apresenta uma linha

reta. Em termos matemáticos, o logaritmo da distribuição de conectividade pk é

uma função linear da conectividade k assim:

ln(pk) = −γ ln(k) + c (3.2)

onde γ e c são constantes. O sinal negativo na equação é necessário uma vez que a

constante c é arbitrária e o lado esquerdo da equação é negativo, pois é o logaritmo

de uma probabilidade. Calculando a exponencial dessa equação temos:

pk = Ck−γ (3.3)

onde C é uma constante usada para normalizar a distribuição.

Distribuições dessa forma, variando com uma potência de k, são chamadas de

leis de potência. O parâmetro γ é o expoente da lei de potência. Para redes reais,

observa-se que seus valores típicos variam entre 2 e 3, embora valores ligeiramente

diferentes sejam possíveis e ocorram ocasionalmente [18].

As leis de potência se manifestam em numerosos fenômenos, frequentemente

fractais, onde uma grande quantidade de elementos interage entre si para produzir

uma estrutura em nível superior. Estes sistemas evoluem longe do equilíbrio e,

com frequência, são altamente dissipativos. Não se deve confundir uma lei de


potência com uma função exponencial do tipo:

f(x) = Ca−|x| (3.4)

Convém levar em conta que uma função exponencial tende a zero, ou algum outro

valor, de forma assintótica e de maneira muito mais rápida do que uma lei de

potência [28].

A probabilidade total é:

Pk =∞∑k′=k

pk′ = 1 (3.5)

É importante reconhecer, no entanto, que estudar leis de potência apenas

fazendo uma análise em escalas logarítmicas não é su�ciente em certos casos,

uma vez que alguns exemplares de redes possuem um comportamento apenas

aproximadamente em lei de potência. Para um estudo mais detalhado das leis

de potência recomenda-se [29].

3.3.2 Redes Livres de Escala

Albert-László Barabási e Réka Albert em [30] demonstraram que em certas

redes a distribuição de probabilidade das conectividades não tem um valor típico,

mas apresenta a característica peculiar de lei de potência, ele chamou essas redes

de redes livres de escala. De acordo com os autores supracitados existe uma or-

dem na dinâmica e estruturação dessas redes: ricos �cam sempre mais ricos, ou

seja, quanto mais ligações um nó apresenta, maior é a possibilidade de estabelecer

novas ligações. A esta característica Barabási e Albert deram o nome de ligação

preferencial : um novo nó tende a ligar-se a um nó pré-existente que contém mais

ligações. Isto justi�ca porque as redes não são constituídas por nós com iguais

probabilidades de terem o mesmo número de ligações, havendo com isso, um con-

junto pequeno de nós altamente conectados e uma maioria de nós com poucas


Figura 3.4: Figuras geradas a partir das equações f(x) = ca−x para a funçãoexponencial e P (x) = Cx−b para a lei de potência, com (a) c = 2, a = 4, C = 2e b = 2, 7; (b) c = 2, a = 3, C = 2 e b = 2, 7 e (c) Ajuste log-log para f(x) e

P (x) com c = 2, a = 1, 5, C = 2 e b = 2, 7 usando o gnuplot.

ligações. Além da ligação preferencial de um nó a nós com mais conexões, estas

redes também estão em constante crescimento. A cada novo passo é criado um nó

no qual têm origem outras ligações, existindo uma dinâmica de imitação, na qual

alguns nós atraem outros. O modelo apresentado por Barabási e Albert é tal que


os vértices das redes geradas por ele não têm uma conectividade típica, porque

apenas alguns nós se encontram muito conectados, enquanto a maioria apresenta

poucas ligações [31].

3.3.2.1 Menor Caminho Médio e o Efeito de Mundo Pequeno

Uma das características notáveis em uma rede é o efeito de mundo pequeno:

a constatação de que na maioria das redes reais as distâncias típicas entre os

vértices são surpreendentemente pequenas. Quando trata-se de mundo pequeno

o marco inicial é a experiência de Stanley Milgram4 na década de 1960, em que

pessoas foram convidadas a receber uma carta destinada a uma pessoa alvo dis-

tante, passando-a diretamente para o destinatário caso o conhecesse, caso não o

conhecesse deveria mandar a carta para uma pessoa de suas relações que pos-

suísse maior probabilidade de conhecer a pessoa alvo. As cartas chegaram ao alvo

através de um notável pequeno número de etapas, cerca de seis em média. Este

fato deu origem à expressão seis graus de separação. O experimento de Milgram

é uma demonstração poderosa do efeito de pequeno mundo. Atualmente, com

os dados completos que tem-se para muitas redes é possível medir diretamente

os comprimentos de caminho entre os nós e veri�car o efeito do mundo pequeno

explicitamente.

Como resultado do experimento de Milgram, foram feitos vários estudos acerca

da distância média entre quaisquer pessoas e um exemplo clássico é o oráculo de

Bacon, que mede a distância entre qualquer ator de Hollywood e o ator Kevin

Bacon, baseado na �lenda urbana� de que Bacon seria o ator mais conectado nesse

meio.

Na seção 2.2.1 ao ser estudado o caminho em um grafo, foi de�nido caminho

geodésico como sendo o caminho mais curto entre dois nós através de uma rede.

Com base nisso, suponhamos que dij é o comprimento de um caminho geodésico

do nó i ao nó j. A distância geodésica signi�cativa de i a j, em média, para todos

4Stanley Milgram (1933 - 1984) psicólogo que conduziu a famosa experiência que tornouvisível o efeito de mundo pequeno e deu origem ao conceito dos seis graus de separação.


os nós j na rede, é dada por:

li =1

n− 1

∑j(6=i)

dij (3.6)

onde é tomado j 6= i pelo fato de a distância de i a ele mesmo ser zero.

Em termos matemáticos, o efeito de mundo pequeno é a hipótese de que

a média dessa distância li é pequena. Pode-se imaginar que o efeito de mundo

pequeno pode ter implicações substanciais para sistemas em uma rede. Suponha

que um rumor é espalhado em uma rede social, por exemplo (ou uma doença numa

determinada comunidade). É claro que vai chegar às pessoas muito mais rápido

se a distância entre estas é apenas cerca de seis passos do que se for uma centena,

ou um milhão. Na verdade, quando se olha mais profundamente a matemática

das redes, descobre-se que o efeito de mundo pequeno não é tão surpreendente,

a�nal, como pensado na época do experimento de Milgram. Modelos matemáticos

de redes sugerem que o comprimento de um caminho tende a permanecer pequeno

mesmo para grandes redes, porque o logaritmo cresce lentamente em função de

seu argumento e a menor distancia media, em geral, é uma função do logaritmo

da quantidade de sítios na rede [18].

3.4 Propriedades das Redes Complexas

Para uma melhor compreensão das redes complexas serão apresentadas algu-

mas propriedades importantes das mesmas como os pólos (hubs), o coe�ciente de

agregação e a robustez.

3.4.1 Formação de Pólos

Uma particularidade das redes livres de escala é o fato de existir um vasto

número de nós com baixa conectividade, enquanto poucos nós possuem conecti-

vidade em demasia, isto é, certos nós possuem uma conectividade muito acima


da média. A esses nós damos o nome de Pólos5, e eles possuem um papel de

fundamental importância na rede.

De uma maneira mais precisa, existem dois tipos de nós importantes nesse

tipo de rede: As autoridades que são nós que contêm informações úteis sobre

um tema de interesse; e Pólos que são os nós que nos dizem onde as melhores

autoridades se encontram. Uma autoridade também pode ser um pólo, e vice-

versa. Claramente pólos e autoridades só existem em redes direcionadas, já que

no caso das não direcionadas, não há distinção entre nó que aponta para outro

ou é apontado por ele. Pode-se imaginar a de�nição de dois tipos diferentes de

centralidade para redes dirigidas, a centralidade de autoridade e a centralidade

de pólos, que quanti�cam com proeminência nós nos dois papéis. Esta idéia foi

apresentada pela primeira vez por Kleinberg [32]. A característica que de�ne um

nó com alta centralidade de autoridade é que ele é apontado por muitos pólos, ou

seja, por muitos outros nós com alta centralidade de pólos. E a característica que

de�ne um nó com alta centralidade de pólo é que ele aponta para muitos vértices

com alta centralidade de autoridade6.

Assim, um artigo cientí�co importante (no sentido de autoridade) seria um

citado em muitos comentários importantes (no sentido de pólo) [18].

3.4.2 Coe�ciente de Agregação

Uma propriedade muito importante em redes sociais7, é a transitividade. Uma

relação O é dita ser transitiva se AOB junto com BOC implica que AOC. Podemos

quanti�car o nível de transitividade numa rede da seguinte forma: se u está ligado

a v e v está ligado a w , então temos um caminho uvw com duas ligações na rede.

Se u também está ligado a w, dizemos que o caminho é fechado, esse caminho forma

um laço de comprimento três, ou um triângulo, na rede. Na linguagem de rede

social, u, v e w formam uma tríade fechada. De�nimos o coe�ciente de agregação

5É uma tradução do inglês para o termo "hubs", alguns autores mantêm o termo em inglês.6Um estudo mais detalhado sobre centralidade e autoridade é encontrado na seção 7.5 de

[18].7É menos útil em outras redes.


como a fração de caminhos de comprimento dois na rede que estão fechados. Ou

seja, contamos todos os caminhos de comprimento dois, e contamos quantos deles

estão fechados, e então dividimos o segundo número pelo primeiro para obter o

coe�ciente de agregação C:

C =número de caminhos fechados de tamanho dois

número de caminhos de tamanho dois(3.7)

Então o coe�ciente de agregação mede a probabilidade média de que dois

vizinhos de um vértice sejam vizinhos entre si [18].

A de�nição mais usual para o coe�ciente de agregação local é a seguinte: dado

um nó i então

Ci =número de conexões entre os vizinhos de i

número total de conexões possíveis(3.8)

e o coe�ciente de agregação médio é dado por:

Cm =

∑Cin

(3.9)

onde n é o tamanho da rede. Neste trabalho são adotadas essas equações para o

cálculo do coe�ciente de agregação local e médio nas simulações que serão discu-

tidas no capítulo 4.

3.4.3 Robustez

Uma vez que uma rede livre de escala é estabelecida ela tem a propriedade

de se manter estável. Este tipo de rede tem uma grande capacidade de resistir

à eliminação de alguns dos seus nós ou de suas ligações, desde que a escolha

dos nós ou ligações seja feita aleatoriamente. Contudo são bastante vulneráveis

à perda de nós com elevado grau de conectividade, ou seja, os pólos. Se uma

falha aleatória ocorrer na rede a probabilidade de um pólo ser afetado é muito

pequena já que a maioria dos nós tem um grau de conectividade baixo. Mesmo


na eventualidade de um pólo ser afetado os demais pólos que sobreviverem na

rede deverão conseguir manter a conectividade dos nós, diz-se que a rede é coesa.

Contudo se alguns dos pólos principais forem afetados, a integridade da rede �ca

seriamente comprometida.

3.5 Modelos de Redes Complexas

Foram discutidas anteriormente as principais características das redes comple-

xas. Viu-se que seus nós podem representar o objeto de interesse num determinado

estudo, como autores num estudo de citações de trabalhos cientí�cos, proteínas

em pesquisas biológicas, documentos na www, computadores numa rede, etc. As

ligações representam a interação entre esses objetos de estudos, num estudo de ci-

tações uma ligação estará de�nida se, num artigo cientí�co, um determinado autor

é citado por outro. Essas redes podem ser dirigidas ou não dirigidas, na web, por

exemplo uma página pode conter um link para outra página, já a segunda página

pode ou não conter um link para a primeira. Cada nó da rede tem uma conectivi-

dade, no caso das redes direcionadas têm-se uma conectividade de entrada e uma

de saída, conforme a ligação seja para o nó ou partindo dele, respectivamente. No

tocante aos graus dos nós temos a distribuição de conectividade e a conectividade

média que é dada pelo número de ligações entre os nós, o caminho mais curto entre

quaisquer dois nós, o coe�ciente de agregação e a robustez da rede que diz o quão

a rede é resistente a ataques dirigidos ou aleatórios. Uma rede pode ser estática

quando o número de nós é �xo ou dinâmica quando o número de nós cresce com o

tempo. Dessa forma, os principais modelos teóricos das Redes Complexas podem

ser discutidos.

3.5.1 Modelo de Price e ligação preferencial

Inúmeras redes observadas apresentam uma distribuição de conectividade que

segue aproximadamente uma lei de potência. A lei de potência, apesar de ser


predominante nesse tipo de rede, é uma distribuição um tanto incomum, sendo

assim uma pergunta natural é: como uma rede pode vir a ter essa distribuição?

Esta pergunta foi considerada diretamente pela primeira vez na década de 1970

por Price [33], que propôs um modelo simples e elegante de formação de rede que

dá origem a uma distribuição de conectividade em lei de potência ao estudar a

rede de citações.

Ao considerar as possíveis origens da lei de potência, Price foi inspirado no

trabalho do economista Herbert Simon [34] que propôs uma explicação para a

distribuição de riqueza baseada na idéia de que as pessoas que têm dinheiro ganham

mais a uma taxa proporcional ao que eles já têm. Esta parece ser uma suposição

razoável. Indivíduos ricos ganham dinheiro investindo o dinheiro que têm, e o

retorno sobre o investimento é essencialmente proporcional ao montante investido.

Ou seja �o rico �ca cada vez mais rico� e este efeito dá origem a uma distribuição

em lei de potência. Price adaptou o modelo de Simon para o contexto de redes.

Esse mecanismo proposto por Simon hoje recebe o nome de ligação preferencial,

que foi cunhado em 1999 por Barabási e Albert [35] apud [18].

3.5.2 Modelo de Barabasi-Albert

O modelo proposto por Price de uma rede crescente é elegante e possui so-

lução exata8, mostrando que a sua distribuição de conectividade tem uma cauda

com comportamento em lei de potência. Este fato faz com que o modelo seja

convincente em apontar a ligação preferencial como uma possível origem para o

comportamento em lei de potência. A ligação preferencial não se tornou ampla-

mente aceita como um mecanismo para gerar leis de potência em redes, pois o

modelo de Price não era muito conhecido fora das ciências da informação. Con-

tudo, no �nal da década de 1990, Barabási e Albert propuseram um modelo de

rede crescente (juntamente com a expressão �ligação preferencial�). Este modelo,

8Não será discutido aqui a solução do Modelo de Citações de Price, para tanto é recomendadoa leitura de [33] e da seção 4.2 de [18].


que é certamente o modelo de rede complexa mais conhecido em uso hoje, é seme-

lhante ao de Price, embora não idêntico, sendo um modelo de rede não dirigida,

enquanto que o de Price o era.

No modelo de Barabási e Albert, os nós são, assim como no modelo de Price,

adicionados um a um para uma rede crescente e cada nó se conecta a um conjunto

escolhido de nós previamente existentes. As ligações, no entanto, estão agora sem

direção e no instante em que cada nó entra na rede, ele estabelece exatamente m

ligações9. As ligações são feitas com probabilidade proporcional a conectividade

dos nós. Quanto maior a conectividade do nó, maior é a probabilidade de ele

receber a ligação do nó que está nascendo na rede. A conectividade do nó i será

denominado por ki. Como antes, os nós e as ligações são sempre adicionados à

rede e nunca retirados dela, o que signi�ca, entre outras coisas, que não há vértices

com conectividade k < m . A menor conectividade na rede é sempre k = m e a

distribuição de conectividade é dada por:

pk ∼ k−3 (3.10)

portanto, o modelo de Barabási-Albert gera uma distribuição de conectividade com

uma cauda em lei de potência que tem um expoente γ = 3 no limite assintótico.

Figura 3.5: Distribuição da conectividade do Modelo de Barabási-Albert commelhor ajuste linear para uma rede com 1 milhão de nós e m = 4. A distribuiçãode conectividade do modelo é uma lei de potência com expoente γ ' 2, 97 (à

direita está a distribuição cumulativa).

9No modelo de Price, o número de conexões é usado apenas para tomar um valor médio dem que no caso desse modelo é chamado de c, mas pode variar a cada passo.


O modelo de Barabási-Albert é atraente por sua simplicidade, entretanto esta

tem o efeito adverso de que o valor do expoente γ é �xo, o que fez o modelo não

ser su�ciente para descrever completamente a maioria das redes reais.

Figura 3.6: Rede do modelo de Barabási-Albert com 1000 nós e m = 1.

Uma propriedade importante de uma rede livre de escala, como já citado

anteriormente é o coe�ciente de agregação. Ao construir uma rede do modelo de

Barabási são determinadas quantas ligações terão cada nó ao nascer e chamamos

essa quantidade de m. Para a rede da �gura 3.6 usamos m = 1 e isto gerou um

coe�ciente de agregação nulo, de fato só temos coe�ciente de agregação diferente

de zero para valores de m > 1. No modelo de Barabási-Albert o coe�ciente de

agregação diminue com o tamanho da rede e se aproxima de zero quando N →∞.


3.5.3 Modelo de Bianconi-Barabási

No modelo de Barabási-Albert, quanto maior a conectividade de um nó, maior

a probabilidade de esse nó receber uma nova ligação, isso implica diretamente que

os primeiros nós a nascer na rede serão os pólos e que esses não poderão ser ultra-

passados por nós mais jovens. Em redes reais isso pode não acontecer, por exemplo

a primeira empresa implantada numa cidade ou estado não será necessariamente

um pólo industrial sempre sem que uma outra empresa a ultrapasse. Nesses casos

vê-se que uma empresa jovem com uma ideia criativa que agrade mais os cli-

entes dessa cidade ou estado, poderá ultrapassar a empresa antiga. Essa �ideia

criativa� que faz com que a empresa jovem ultrapasse a antiga é chamada de qua-

lidade10. Em 2001 Barabási e Bianconi acrescentaram esse ingrediente ao modelo

de Barabási-Albert, a�m de fazer com que o modelo se aproximasse de várias redes

reais. No modelo de Bianconi-Barabási surge uma quantidade maior de nós com

conectividade alta, apesar de a maioria dos nós ainda possuírem conectividade

baixa, ou seja, nesse modelo tem-se mais pólos que no anterior.

O modelo baseado na ideia de qualidade traz uma competitividade aos nós

capaz de afetar a evolução da rede. De acordo com esta ideia, a capacidade

intrínseca dos nós para atrair ligações na rede varia de nó em nó, com o mais

e�ciente sendo capaz de reunir mais ligações em detrimento de outros. Nesse

sentido, nem todos os nós são idênticos uns aos outros, cada um nasce com uma

aptidão e esta, juntamente com a conectividade do nó, é que irá aumentar ou não

sua probabilidade de ganhar uma nova ligação.

Bianconi e Barabási [36] propuseram esse novo modelo que �cou conhecido

como modelo de Bianconi-Barabási, que é uma variante do modelo Barabási-

Albert, onde a probabilidade de um nó se conectar a outro é fornecida com um

termo que expressa a aptidão do nó envolvido. O parâmetro de aptidão é inde-

pendente do tempo e a probabilidade do nó i receber uma ligação do próximo nó

a ser adicionado à rede é:

Πi =ηiki∑j ηjkj

(3.11)

10Originalmente é chamada de �tness, será usado aqui o termo em português.


onde η é a qualidade do sítio i e é atribuída de forma aleatória.

Figura 3.7: Grá�co da distribuição de conectividade e do melhor ajuste linearsobre uma média de 100 redes do modelo de Bianconi-Barabási com 1 milhão de

nós e m = 4 cada uma (à direita está a distribuição cumulativa).

Figura 3.8: Rede do modelo de Bianconi-Barabási com 1000 nós.

Capítulo 4

Rede dos Sobrenomes

�Outras coisas podem nos mudar, mas a família é o começo e o �m."

Anthony Brandt

4.1 Apresentação

Os sistemas complexos, que são sistemas essencialmente dinâmicos, descrevem

uma grande variedade de situações na natureza e na sociedade. Como discutido

em capítulos anteriores, as redes complexas são sistemas constituídos por nós e as

conexões entre eles. Como exemplo, cita-se a disseminação de uma determinada

informação em uma rede social, onde os nós são representados por pessoas e as

ligações são as relações sociais, ou seja, quanto mais conectadas forem as pessoas

dessa rede, mais rapidamente a informação será passada a diante. O estudo dessas

redes complexas é motivado pelo entendimento de diversos sistemas reais que não

obedecem a distribuições clássicas como a de Poisson, a Gaussiana, etc. Neste

trabalho estuda-se os sobrenomes das pessoas, obtidos a partir de listagens de

pessoas que estão relacionadas entre si a partir de características comuns especí�cas

45

Capítulo 4. Rede dos Sobrenomes 46

como, por exemplo, uma lista telefônica, uma lista de funcionários de uma empresa,

uma lista de aprovados em vestibulares, e assim por diante. Parte-se da premissa

de que uma grande lista de alguma forma, representa a sociedade em que vivemos

(ou pelo menos parte dela, como uma espécie de espelho de um determinado nicho

social). O interesse consiste em analisar a freqüência desses sobrenomes e construir

os histogramas da conectividade e as redes. E a partir destes obter informações

que ajudem a enquadrar essas redes em algum modelo de redes complexas já

conhecido.

4.1.1 Preliminares

O �estudo do parentesco� entre as pessoas surgiu através da genealogia como

ciência auxiliar da História, mais especi�camente, a História da Família. Neste

contexto os nomes de famílias, cunhados sobrenomes, referem-se a parte do nome

da pessoa que guarda a história de seus antepassados, sua ascendência. A prin-

cípio, esses Sobrenomes tem origem basicamente toponímica1. Historicamente os

sobrenomes, no Brasil, foram largamente adotados por pessoas que chegavam ao

país e queriam começar uma vida nova, sem vínculos com o passado na Europa.

As pessoas que vinham chegando ou os índios que iam sendo batizados recebiam

o sobrenome �da Silva� que signi�ca �da Selva� caso fossem viver nas localidades

com �orestas e �da Costa� caso fossem viver nas áreas litorâneas. No entanto,

certos sobrenomes podem trazer maiores informações sobre o passado de algumas

famílias por essas serem mais tradicionais. Ademais, mesmo no caso dos sobreno-

mes adotados, estes trazem consigo um pouco da história social, não só do Brasil,

mas de qualquer sociedade que se queira estudar.

Uma busca na literatura relacionada ao assunto mostra alguns trabalhos já

feitos neste sentido e como exemplo pode ser citado [37], cujos autores realizaram

um estudo da frequência de aparição dos nomes de famílias japonesas e, como

resultado, encontraram que eles se distribuem segundo uma lei de potência. Ou

seja, encontraram que há poucos nomes de família muito comuns e a maioria deles

1A toponímia é a ciência que estuda os nomes próprios de lugares, sua origem e evolução.


não ocorre com frequência expressiva, o que é semelhante ao comportamento do

número de conexões que um nó deve fazer em uma rede complexa.

4.1.2 Motivação

Observando os resultados obtidos para a sociedade japonesa, pensou-se em

fazer um estudo análogo para a sociedade brasileira e a portuguesa. Com este

tipo de estudo pretende-se veri�car se as redes dos sobrenomes enquadram-se no

grupo da redes complexas e como adicional, também busca-se caracterizar o grau

de miscigenação da sociedade estudada através do expoente da distribuição, pois a

existência de um sobrenome de forma exagerada em relação aos demais é uma con-

dição para uma sociedade fechada, uma comunidade mais homogênea, enquanto

um expoente grande (em comparação com os obtidos em modelos teóricos) cor-

responde a uma sociedade mais heterogênea. Discutir-se-á a análise de algumas

destas listagens, interpretando os resultados e abordando modelos propostos para

tentar explicar esse comportamento estatístico.

4.1.3 Metodologia

Os objetivos desse trabalho foram atendidos, utilizando-se de um conjunto de

procedimentos abaixo descritos.

4.1.3.1 Tipo de Pesquisa

Por se tratar de um estudo empírico e também pelo fato de algumas redes

serem muito grandes, este trabalho tem um caráter mais numérico-simulacional

do que analítico. Com os resultados dos tratamentos dos dados brutos e das

simulações, faz-se uma análise quantitativa com o objetivo de encontrar paralelos

entre as redes simuladas e as redes previstas por modelos teóricos.


4.1.3.2 Programas Utilizados

Os programas utilizados para as simulações foram, na maioria, de desenvolvi-

mento próprio. Além dos programas próprios usou-se o programa Gephi 0.8 beta

para gerar as �guras das redes. Os expoentes das leis de potência foram obti-

dos através do coe�ciente angular da reta obtida com o melhor ajuste linear dos

histogramas das conectividades em escala logarítmica.

Figura 4.1: O programa Gephi foi utilizado para gerar as �guras das Redesutilizadas neste trabalho.

Abaixo descreve-se brevemente os programas próprios.

4.1.3.3 Programa para adquirir as listagens

As listas foram adquiridas na web, em listas telefônicas do Brasil (Telelista2) e

de Portugal (Páginas Brancas3). Foram utilizados programas escritos nas lingua-

gens Java e Python feitos para ler o �código html� das páginas da web e extrair os

2http://www.telelistas.net3http://www.pbi.pai.pt


nomes das pessoas. As listagens eram construídas a partir de uma palavra chave,

por exemplo, a listagem da Rede Anas_BR, foi gerada a partir da lista telefônica

brasileira, coletando todos os nomes que continham a palavra Ana no Brasil.

4.1.3.4 Programas para o tratamento dos dados

Aqui foram utilizados programas próprios, desenvolvidos em C++ para o Mo-

delo de Barabási-Albert e em Python para os modelos teóricos (modelos Barabási-

Albert, Bianconi-Barabási e Erdös-Rényi) e para o tratamentos dos Nomes de

famílias.

Foram desenvolvidos um conjunto de cinco programas:

• O primeiro programa tinha como objetivo a depuração das amostras.

Uma vez que as listagens eram geradas a partir de uma palavra chave, estas

vinham com muitas impurezas, o tratamento consistia em tentar retirar to-

dos os nomes considerados inválidos, como por exemplo nomes de empresas,

hospitais, etc. Ao restar apenas nomes próprios nas listagens eram retirados

os nomes contendo apenas um sobrenome. Uma vez que o interesse consistia

em analisar as relações entre pares de nomes de famílias, era importante que

cada elemento da amostra contivesse o nome de pelo menos duas famílias,

com a contribuição do pai e da mãe (em tese), na �gura 4.2 mostra-se o

esquema do método utilizado;

• O segundo programa calculava as principais informações para a poste-

rior construção da rede como: histograma dos sobrenomes, histograma dos

primeiros nomes, dicionários das ocorrências dos sobrenomes. Além disso

esse programa gerava uma lista de pares de sobrenomes válidos para a cons-

trução da rede, sendo esta sua principal atribuição;

• O terceiro programa montava a rede, através das listas de adjacências.

Estas são uma simpli�cação da matriz de adjacências (vista no capítulo 2 ),

feita ao pegar apenas a metade superior ou inferior da matriz e eliminando


Figura 4.2: Esquema mostrando nomes considerados válidos (balões coloridos)por terem em sua constituição pelo menos dois sobrenomes e nomes inválidos

(balões brancos) por terem apenas um nome de família.

os elementos vazios (que representam a ausência de conexão entre dois nós).

Esta simpli�cação tinha como objetivo auxiliar na simulação das redes, pois

o uso das listas de adjacências minimiza parte dos custos computacionais

envolvidos na simulação. Como cada elemento da amostra traz consigo o

nome de duas famílias, então cada sobrenome já nasce na rede como um

nó que tem pelo menos uma ligação. Este programa também gerava um

arquivo no formato graphml que era usado para a criação da �gura da rede no

programa Gephi (�gura 4.1 ) e com um programa complementar calculava-se

o histograma e a distribuição das conectividades;

• O quarto programa calculava a coe�ciente de agregação médio da rede;

• Ao longo da pesquisa foi necessário a criação de um quinto programa

(usando Python) que calculava o menor caminho médio. Este foi calculado

somente considerando os nós que pertenciam ao aglomerado no qual também

estava o pólo principal da rede. Esta abordagem foi utilizada para driblar

a di�culdade originada no fato de que as redes dos sobrenomes, na verdade,

são compostas por vários aglomerados, sendo um deles gigante, contendo o

pólo principal, e os outros muito pequenos, geralmente contendo não mais

que três ou quatro nós cada.


4.2 Análise dos Nomes de Família

O cenário utilizado para a ARS a partir dos nomes de famílias foi o Brasil,

tanto no âmbito nacional quanto no regional, e Portugal, no nacional. Buscando-

se construir dados su�cientes para associar as redes dos sobrenomes (RS) estuda-

das com algum modelo teórico conhecido. Com os dados obtidos, esperava-se que

as redes geradas apresentassem caracteristicas semelhantes a alguns dos modelos

teóricos, principalmente o modelo de Barabasi-Albert. Porém por se tratar de

dados reais, nos quais sempre há ruídos, a possibilidade de haver uma analogia

completa com os modelos teóricos era remota. O que foi veri�cado, de fato, é que

alguns dos principais componentes dos modelos teóricos podem ser observados nas

redes simuladas.

No modelo Barabási-Albert todos os nós estão conectados como num grafo

conexo, poucos com muitas ligações, inúmeros com poucas ligações. No entanto,

nas RS foram veri�cadas a presença de aglomerados, ou seja, os nós não estão

completamente conectados como num grafo conexo, mas formando alguns grupos

isolados como pode ser veri�cado na �gura 4.3 onde o centro da rede apresenta

um grande aglomerado de nós conectados ao pólo principal, porém, na circunscri-

ção da rede percebe-se a formação de pequenos grupos desconectados do centro.

Logo a analogia com o modelo Barabási-Albert não é totalmente possível devido

a peculiaridades contidas nas RS.

As principais informações obtidas pelas simulações feitas com amostras bra-

sileiras são mostradas na tabela 4.1.

O expoente da distribuição de conectividade dos modelos de redes reais es-

tudados varia entre 2 e 3. Para as RS brasileiras simuladas o valor encontrado

para o parâmetro γ �cou no intervalo de 2,05 a 2,12. Veri�cou-se a predominân-

cia do sobrenome Silva para todas as redes simuladas, além disso as simulações

foram feitas para redes com uma quantidade muito distinta de nós, como no caso

da rede Marias_BR com 102.474 nós e a rede Lucianos_BR com apenas 5.766


Figura 4.3: Rede dos Sobrenomes construída a partir de uma amostra portu-guesa cujos nomes continham a palavra Paulo. Rede com 3.215 nós.

nós, no entanto o parâmetro γ para ambas é da ordem de 2,1, mostrando as-

sim que este parâmetro é independente do tamanho da rede. Pode-se dizer que

os modelos teóricos de Barabási-Albert e Bianconi-Barabási não são su�cientes

para representar com rigor essa sociedade devido a características das RS como

a formação de aglomerados soltos ao longo da rede, mas assim como nos modelos

teóricos temos a predominância de certos pólos através da ligação preferencial, que

como no modelo Barabási-Albert dominam pela quantidade, uma vez que quanto

maior a disseminação desse sobrenome maior será o número de descendentes que


Tabela 4.1: Principais características das Redes dos sobrenomes no Brasil.Onde n representa a quantidade de nós na rede; kp é o grau do pólo principal;Cm é o coe�ciente de agregação médio da rede; ` é o menor caminho médio entre

quaisquer dois nós na rede e γ é o expoente da lei de potência.

Rede Pólo PrincialCaracterísticas das Redes

n kp Cm ` γ

Anas_BR Silva 27.759 2.319 0,054 3,732 2,08 ± 0,02

Franciscos_BR Silva 15.784 1.562 0,048 3,667 2,09 ± 0,02

Joãos_BR Silva 21.176 1.797 0,073 3,635 2,06 ± 0,02

Josés_BR Silva 43.952 4.450 0,069 3,645 2,05 ± 0,01

Lucianos_BR Silva 5.766 567 0,063 3,476 2,12 ± 0,03

Marias_BR Silva 102.474 11185 0,046 3,758 2,08 ± 0,01

o receberão.

Para as simulações feitas, a sociedade brasileira se mostrou mais homogênea,

pois poucos sobrenomes pertencem a maior parte da população. Em certas regiões

interioranas, como no caso da cidade de Carnaúba dos Dantas no estado do Rio

Grande do Norte, onde os casamentos endogâmicos prevaleceram desde o século

XVIII, vindo a diminuir apenas no início do século XX, quando famílias mais

tradicionais começaram a se misturar com novas famílias que vinham chegando

ao local, o que fez com que o sobrenome Dantas prevalecesse na região. Mas esse

fenômeno não foi e não é exclusividade da região do seridó, várias regiões do país

têm em seu histórico a endogamia4.

Na �gura 4.4 tem-se uma rede construída com uma amostra de pessoas brasi-

leiras que possuíam a palavra Luciano em seu nome. E na �gura 4.5 mostra-se o

grá�co da distribuição cumulativa das conectividades, em escala logarítmica, para

a população brasileira que possuía a palavra Maria em seu nome.

As principais informações obtidas pelas simulações feitas com amostras por-

tuguesas são mostradas na tabela 4.2.

4Casamentos entres familiares como primos de primeiro e segundo grau, assim como tios esobrinhos.


Figura 4.4: A rede foi construída a partir de uma amostra da populaçãobrasileira cujos nomes continham a palavra Luciano. Rede com 5.766 nós. O nó

mais conectado é o sobrenome Silva (pintado de roxo) com 567 conexões.

Para as RS portuguesas o valor encontrado para o parâmetro γ �cou no

intervalo de 2,10 a 2,23. Esses valores correspondem com os valores previstos na

literatura da ARS. De acordo com esses parâmetros o modelo teórico que descreve

essas redes de forma mais aproximada é de Bianconi-Barabási. O valor encontrado

para γ mostra que a sociedade portuguesa, nas simulações feitas, mostrou-se mais

heterogênea que a sociedade brasileira. As redes simuladas são pequenas para

representar com clareza a sociedade portuguesa, mas servem como espelho da


Figura 4.5: Grá�co da distribuição cumulativa das conectividades da RedeMarias_BR em escala logarítmica. Dados obtidos a partir de uma amostra da

população Brasileira cujos nomes continham a palavra Maria.

Tabela 4.2: Principais características das Redes dos sobrenomes em Portugal.Onde n representa a quantidade de nós na rede; kp é o grau do pólo principal;Cm é o coe�ciente de agregação médio da rede; ` é o menor caminho médio entre

quaisquer dois nós na rede e γ é o expoente da lei de potência.

Rede Pólo PrincialCaracterísticas das Redes

n kp Cm ` γ

Anas_PT Silva 3.711 521 0,120 3,352 2,14 ± 0,03

Antônios_PT Pereira 4.991 550 0,137 3,361 2,12 ± 0,02

Joãos_PT Santos 4.264 603 0,146 3,303 2,12 ± 0,02

Joaquins_PT Silva 3.061 430 0,136 3,376 2,13 ± 0,03

Josés_PT Silva 5.499 911 0,171 3,268 2,10 ± 0,02

Luíses_PT Santos 3.452 407 0,118 3,390 2,13 ± 0,03

Manueles_PT Martins 4.921 523 0,132 3,413 2,12 ± 0,03

Marias_PT Pinto 3.645 739 0,053 3,510 2,23 ± 0,03

Paulos_PT Silva 3.096 454 0,134 3,285 2,11 ± 0,03


mesma, principalmente para uma melhor analogia com as redes para a sociedade

brasileira.

Na �gura 4.6 tem-se uma rede construída com uma amostra portuguesa de

pessoas que possuíam a palavra José em seu nome. E na �gura 4.7 mostra-se o

grá�co da distribuição cumulativa das conectividades, em escala logarítmica, para

a população portuguesa que possuía a palavra José em seu nome.

Figura 4.6: A rede foi construída a partir de uma amostra da população dePortugal cujos nomes continham a palavra José. Rede com 5.499 nós. O nó

mais conectado é o sobrenome Silva (pintado de preto) com 911 conexões.


Figura 4.7: Grá�co da distribuição cumulativa das conectividades da RedeJosés_PT em escala logarítmica. Dados obtidos a partir de uma amostra da

população Portuguesa cujos nomes continham a palavra José.

As redes estudadas mostraram-se ser redes de mundo pequeno. Uma das

maneiras de veri�car tal característica é confrontando essas com grafos aleatórios,

pois redes de pequeno mundo possuem um coe�ciente de agregação médio grande

e um menor caminho médio pequeno se comparadas com esse tipo de grafo. Na

tabela 4.3 exibe-se valores do coe�ciente de agregação médio e do menor caminho

médio para as redes brasileiras e portuguesas em comparação com grafos aleatórios

com o mesmo número de vértices e de arestas.

Veri�ca-se nos dados mostrados na tabela que para grafos aleatórios com o

mesmo número de vértices que as redes dos sobrenomes, de fato, estas apresenta-

ram coe�ciente de agregação médio alto e menor caminho médio baixo, corrobo-

rando assim que o tipo das redes dos sobrenomes é mundo pequeno.


Tabela 4.3: Principais diferenças entre as Redes dos sobrenomes (Redes de

pequeno mundo) e os Grafos Aleatórios. Onde n representa a quantidade de nósna rede e vértices do grafo; Cm é o coe�ciente de agregação médio e ` é o menor

caminho médio entre quaisquer dois nós na rede (vértices no grafo).

RedeCaracterísticas das Redes

n Arestas Cm `

Anas_BR 27.759 56.160 0,054 3,732

Grafo Aleatório 27.759 56.160 0,0002 7,017

Franciscos_BR 15.784 29.028 0,048 3,667

Grafo Aleatório 15.784 29.028 0,0002 6,880

Joãos_BR 21.176 44.740 0,073 3,635

Grafo Aleatório 21.176 44.740 0,0002 6,691

Josés_BR 43.952 91.490 0,069 3,645

Grafo Aleatório 43.952 91.490 5, 22× 10−5 7,270

Marias_BR 102.474 241.106 0,046 3,758

Grafo Aleatório 102.474 241.106 4, 94× 10−5 7,401

Antônios_PT 4.991 14.685 0,120 3,361

Grafo Aleatório 4.991 14.685 0,001 4,975

Joãos_PT 4.264 13.186 0,146 3,303

Grafo Aleatório 4.264 13.186 0,001 4,761

Josés_PT 5.499 17.129 0,171 3,268

Grafo Aleatório 5.499 17.129 0,001 4,889

Manueles_PT 4.921 15.047 0,132 3,413

Grafo Aleatório 4.921 15.047 0,001 4,827

Capítulo 5

Considerações �nais

� A natureza é um enorme jogo de xadrez disputado por deuses, e que temos o pri-

vilégio de observar. As regras do jogo são o que chamamos de física fundamental,

e compreender essas regras é a nossa meta."

Richard Feynman

5.1 Conclusões

Nesta dissertação foram abordadas as principais características daARS com a

�nalidade de estudar a rede gerada pelas associações entre os sobrenomes presentes

nos nomes das pessoas, o que foi feito no capítulo 4. Para tanto apresentou-se no

capítulo 2 uma introdução à teoria dos grafos, falou-se do surgimento das ideias

com o clássico problema das pontes de Königsberg, citou-se brevemente a historia

do desenvolvimento e surgimento da teoria. Além disso buscou-se mostrar os

conceitos básicos da forma mais clara possível, dando assim, um embasamento

matemático para os capítulos posteriores.

59

Capítulo 5. Considerações �nais 60

No capítulo 3 discutiu-se a teoria das redes complexas. Na seção 3.2 explorou-

se as distribuições de conectividade em lei de potência, as redes livres de escala, e o

menor caminho médio de uma rede, além do conceito de redes de mundo pequeno.

Na seção 3.3 abordou-se as propriedades das redes complexas, como a formação

dos pólos e o coe�ciente de agregação. E na seção 3.4 mostrou-se os modelos

teóricos de Barabási-Albert e Bianconi-Barabási.

No capítulo 4 analisou-se as redes dos sobrenomes através de simulações com-

putacionais, mostrou-se que o numero de conexões que cada sobrenome tem dentro

da rede se comporta como uma lei de potência. Considerando a simplicidade do

método adotado é fortuito ver a qualidade dos resultados, uma vez que em todas

as redes simuladas, os expoentes γ encontrados foram da ordem de 2,1 , valor esse

satisfatório se comparado com aqueles encontrados na literatura para redes reais

e principalmente com o fato de o estudo ter sido realizado com amostras pequenas

no caso de Portugal. Veri�cou-se que o parâmetro γ é independente do tamanho

da rede estudada. Pôde-se constatar também que examinar redes com um número

grande de elementos como a rede Marias_BR, contudo, não é uma tarefa trivial,

apesar do método adotado ser bastante simples o custo computacional ainda é

alto. O tempo gasto para depurar as amostras para a rede mencionada foi da

ordem de minutos ou poucas horas e para simular a rede foi da ordem de horas.

Outra di�culdade é o cálculo do menor caminho médio para essas redes por estas

apresentarem aglomerados, ou seja, grupos desconectados uns dos outros ao longo

da rede.

Por meio do expoente da lei de potência fez-se uma estimativa do grau de

miscigenação das sociedades estudadas. E por �m, com relação ao tipo de redes

analisadas, através da analogia entre o coe�ciente de agregação médio e do menor

caminho médio das redes dos sobrenomes com os grafos aleatórios veri�cou-se, con-

forme mostrado na tabela 4.3, que essas apresentam o caráter de mundo pequeno.

O tipo da rede é um fator muito importante no estudo da mesma, no caso da rede

dos sobrenomes, que é do tipo mundo pequeno, veri�cou-se que os elementos das

amostras estão muito próximos uns dos outros, possuindo um distância média de

três passos para quaisquer dois elementos dentro do maior aglomerado.

Capítulo 5. Considerações �nais 61

5.2 Perspectivas

Pelo fato dessa dissertação ser um trabalho inicial, a mesma possui uma vasta

perspectiva para trabalhos futuros. A mais imediata é tentar ampliar as simulações

para outras sociedades, por exemplo países de língua espanhola e inglesa, e veri�car

se os resultados convergem para um valor universal do expoente γ que caracterize

todas as redes dos sobrenomes. Também pode-se melhorar a base de dados com

amostras mais robustas que as simuladas, coletando assim uma fração maior das

sociedades escolhidas, com a �nalidade de que os resultados encontrados sejam os

mais gerais possíveis.

Referências Bibliográ�cas

[1] É. Durkhein. As Regras do Método Sociológico. Livraria Martins Fontes

Editora Ltda, SP-BR, 1995.

[2] R. Balancieril. Um método baseado em ontologias para explicitação de co-

nhecimento derivado da análise de redes sociais de um domínio de aplicação.

Tese de doutorado, 2010.

[3] O grupo de pares, 2013. URL http://cadernosociologia.blogspot.com.

br/2012/01/o-grupo-de-pares.html.

[4] F. Duarte, C. Quandt, and Q. Souza. O Tempo das Redes. Editora Perspectiva

S/A, SP-BR, 2008.

[5] M. I. Tomaél and R. M. Marteleto. Redes socias: Posições dos atores no

�uxo da informação. Revista Eletrônica de Biblioteconomia e Ciência da

Informação, Esp:75�91, 2006.

[6] Coluna política, 2013. URL http://www.folhavitoria.com.br/politica/

noticia/2012/07.

[7] A primavera brasileira, 2013. URL http://blogdosacha.com.br/

coluna-opiniao/a-primavera-brasileira/.

[8] R. Dandi and A. Sammarra. Social network analysis: A new perspective for

post-fordist organization. Technical report, University of Zurich, ETH Zurich,

August 27-28 2009.

[9] F. Harary. Graph Theory. Addison-Wesley, 1969.

62

http://cadernosociologia.blogspot.com.br/2012/01/o-grupo-de-pares.html

http://cadernosociologia.blogspot.com.br/2012/01/o-grupo-de-pares.html

http://www.folhavitoria.com.br/politica/noticia/2012/07

http://www.folhavitoria.com.br/politica/noticia/2012/07

http://blogdosacha.com.br/coluna-opiniao/a-primavera-brasileira/

http://blogdosacha.com.br/coluna-opiniao/a-primavera-brasileira/


[10] P. Feo�lo�, Y. Kohayakawa, and Y. Wakabayashi. Uma Introdução Sucinta

à Teoria dos Grafos. USP-SP, São Paulo, 2011.

[11] Agnelo �gueiredo, 2013. URL http://users.prof2000.pt/agnelo/grafos/

pontesh.htm.

[12] L. Sousa. O teorema das quatro cores. Millenium - Revista do ISPV, 24,

2001.

[13] R. L. Brooks. On colouring the nodes of a network. Mathematical Proceedings

of the Cambridge Philosophical Society, 37:194�197, 4 1941. ISSN 1469-8064.

doi: 10.1017/S030500410002168X. URL http://journals.cambridge.org/

article_S030500410002168X.

[14] W. T. Tutte. On the symmetry of cubic graphs. Canadian Journal of Mathe-

matics, 11:621�624, 1959.

[15] Um pequeno histórico da teoria dos grafos, 2013. URL http://www.mat.uc.

pt/~mcag/FEA2003/Teoria_de_Grafos.

[16] C. L. Lucchesi. Introdução à Teoria dos Grafos. Unicamp, 1979.

[17] P. P. Costa. Teoria de grafos e suas aplicações. Dissertação de mestrado,

Instituto de Geociências e Ciências Exatas, Universidade Estadual Paulista

JÚLIO DE MESQUITA FILHO - Campus de Rio Claro, 2011.

[18] M. E. J. Newman. Networks: An Introduction. Oxford University Press,

Oxford, 2010.

[19] P. Erdos and A. Renyi. On random graphs. Publ. Math, 6:290�297, 1959.

[20] R. B. Ribeiro. Grafos aleatórios e percolação. Dissertação de mestrado,

Instituto de Ciências Exatas, Universidade Federal de Minas Gerais, 2012.

[21] L. Garton, C. Haythornthwaite, and B. Wellman. Studying online social

networks. Journal of Computer-mediated Communication, 3, 1997.

[22] R. A. Hanneman. Introdution to social networks methods. University of

California, UC, 2001.

http://users.prof2000.pt/agnelo/grafos/pontesh.htm

http://users.prof2000.pt/agnelo/grafos/pontesh.htm

http://journals.cambridge.org/article_S030500410002168X

http://journals.cambridge.org/article_S030500410002168X

http://www.mat.uc.pt/~mcag/FEA2003/Teoria_de_Grafos

http://www.mat.uc.pt/~mcag/FEA2003/Teoria_de_Grafos


[23] M. J. C. Braga, L. A. M. Gomes, and M. A. Ruediger. Mundos pequenos,

produção acadêmica e grafos de colaboração: um estudo de caso dos enanpads.

Revista de Administração Pública, 42:133�154, 2008.

[24] J. L. Moreno. Who Shall Survive? Beacon House, NY, 1934.

[25] P. G. Lind, L. R. da Silva, J. S. Andrade Jr., and H. J. Herrmann. The spread

of gossip in american schools. Europhysics Letters, 78:68005, 2007.

[26] P. G. Lind, L. R. da Silva, J. S. Andrade Jr., and H. J. Herrmann. Spreading

gossip in social networks. Physical Review E, 76:036117, 2007.

[27] A. Davis, B. B. Gardner, and M. R. Gardner. Deep South. University of

Chicago Press, Chicago, 1941.

[28] J.M. García-Manso and J. M. Martín-Gonzáles. Leis de potência ou escala:

sua aplicação ao fenômeno esportivo. Colégio Brasileiro de Atividade Física,

Saúde e Esporte, 7(3):195�202, 2008.

[29] A. Clauseti, C. R. Shalizi, and M. E. J. Newman. Power-law distribuitions in

empirical data. Siam Review, 51, 2009.

[30] A. L. Barabási and R. Albert. Statistical mechanics of complex networks.

Reviews of Modern Physics, 74, 2002.

[31] R. Recuero. Redes Sociais na internet. Editora Sulina - Coleção Cibercultura,

Porto Alegre, 2009.

[32] J.M. Kleinberg. Authoritative sources in a hyperlinked environment. The

Journal of the ACM, 46:604�632, 1999.

[33] D. J. de S. Price. Networks of scienti�c papers. Science, 149:510�515, 1965.

[34] H. A. Simon. On a class of skew distribuition functions. Biometrika, 42:

425�440, 1955.

[35] A.-L. Barabási and R. Albert. Emergence of scaling in random networks.

Science, 286:509�512, 1999.


[36] A.-L. Barabási and G. Bianconi. Competition and multiscaling in evolving

networks. Europhys. Lett, 54:436�442, 2001.

[37] S. Miyazima, Y. Lee, T. Nagamine, and H. Miyajima. Power-law distribution

of family names in japanese societies. Physica A, 278:282�288, 2000.

Documents

Física Estatística Aplicada a Sistemas Sociais Através do ... · Centro de Ciências Exatas e da erraT (CCET) ... Física Estatística Aplicada a Sistemas Sociais Através do Estudo