MINISTÉRIO DA DEFESAEXÉRCITO BRASILEIRO

DEPARTAMENTO DE CIÊNCIA E TECNOLOGIAINSTITUTO MILITAR DE ENGENHARIA

(Real Academia de Artilharia, Fortificação e Desenho, 1792)

CURSO DE GRADUAÇÃO EM ENGENHARIA DE COMPUTAÇÃO

UTILIZAÇÃO DE PARÂMETROS ESPECTRAIS EM REDES SOCIAIS

TEN DIEGO ANDRÉS DE BARROS LIMA BARBOSATEN LEONARDO BORGES AVELINOTEN RARYLSON FREITAS DE SOUZA

Projeto de Fim de Curso apresentado ao Curso de Gra-duação em Engenharia de Computação e ao Curso deGraduação em Engenharia Eletrônica do Instituto Militarde Engenharia, como requisito parcial para a graduação emengenharia.

Orientador: Claudia Marcela Justel - D. C.

Rio de Janeiro2011

2

c2011

INSTITUTO MILITAR DE ENGENHARIAPraça General Tibúrcio, 80 - Praia VermelhaRio de Janeiro - RJ CEP: 22290-270

Este exemplar é de propriedade do Instituto Militar de Engenharia, que poderá incluí-lo em basede dados, armazenar em computador, microfilmar ou adotar qualquer forma de arquivamento.

É permitida a menção, reprodução parcial ou integral e a transmissão entre bibliotecas destetrabalho, sem modificação de seu texto, em qualquer meio que esteja ou venha a ser fixado, parapesquisa acadêmica, comentários e citações, desde que sem finalidade comercial e que seja feitaa referência bibliográfica completa.

Os conceitos expressos neste trabalho são de responsabilidade dos autores e do orientador.

Barbosa, Diego Andrés de Barros Lima;004.62B238u

Utilização de Parâmetros Espectrais em Redes Sociais / Diego An-drés de Barros Lima Barbosa; Leonardo Borges Avelino; Rarylson Fre-itas de Souza. Rio de Janeiro: Instituto Militar de Engenharia, 2011.

85 p.: il, tab.

Projeto Final de Curso - Instituto Militar de Engenharia - Rio deJaneiro, 2011.

1. Análise de redes 2. Parâmetros espectrais - rede 3. Parâmetrosnão espectrais - rede I. Avelino, Leonardo Borges. II. Souza, Raryl-son Freitas. III. Título. IV. Instituto Militar de Engenharia.

CDD 004.62

3

MINISTÉRIO DA DEFESAEXÉRCITO BRASILEIRO

DEPARTAMENTO DE CIÊNCIA E TECNOLOGIAINSTITUTO MILITAR DE ENGENHARIA

(Real Academia de Artilharia, Fortificação e Desenho, 1792)

UTILIZAÇÃO DE PARÂMETROS ESPECTRAIS EM REDES SOCIAIS

TEN DIEGO ANDRÉS DE BARROS LIMA BARBOSATEN LEONARDO BORGES AVELINOTEN RARYLSON FREITAS DE SOUZA

Projeto de Fim de Curso apresentado ao Curso de Graduação em Engenharia de Compu-tação e ao Curso de Graduação em Engenharia Eletrônica do Instituto Militar de Engenharia,como requisito parcial para a graduação em engenharia.

Orientador: Claudia Marcela Justel - D. C.

Aprovada em 15 de Junho de 2011 pela seguinte Banca Examinadora:

Claudia Marcela Justel - D. C. do IME - Presidente

Cap Julio Cesar Duarte - D. C. do IME

TC Luiz Henrique da Costa Araújo - D. C. do IME

Rio de Janeiro2011

4

Primeiramente, agradecemos aos nossos familiares pelo carinho, motivação e paciência aolongo destes cinco anos. Agradecemos também aos amigos, que tanto nos apoiaram no

transcorrer desta jornada. Por fim, agradecemos à nossa orientadora, Claudia Justel, por,através de seu conhecimento, experiência e otimismo, fornecer todo o apoio necessário e

permitir a realização deste trabalho.Diego Andrés de Barros Lima Barbosa, Leonardo Borges Avelino e Rarylson Freitas de Souza

5

“Stay hungry, stay foolish.”Steve Jobs

“Não peça por fardos mais leves, mas sim por ombros mais fortes.”Philips Brooks

6

SUMÁRIO

LISTA DE ILUSTRAÇÕES . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 9

LISTA DE TABELAS . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 10

1 INTRODUÇÃO . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 13

1.1 Objetivo . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 14

1.2 Metodologia . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 14

1.3 Estrutura do Texto . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 15

2 CONCEITOS BÁSICOS . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 17

2.1 Conceitos básicos em grafos . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 17

2.1.1 Definições e propriedades . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 17

2.2 Conceitos básicos em redes sociais . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 19

2.2.1 Exemplos de redes sociais . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 20

2.2.1.1 A rede de Zachary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 22

2.2.2 Contágio . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 22

2.2.3 O fenômeno do mundo pequeno . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 23

3 ESTUDO DE PARÂMETROS ESPECTRAIS E NÃO ESPECTRAIS . . . . . . 25

3.1 Centralidade de vértices . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 25

3.1.1 Centralidade de grau . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 25

3.1.2 Centralidade de intermediação . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 26

3.1.3 Centralidade de proximidade . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 26

3.1.4 Centralidade de autovetor . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 27

3.1.5 PageRank . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 28

3.2 Detecção de comunidades em redes sociais . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 28

3.2.1 O problema de detecção de comunidades . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 29

3.2.2 Algoritmos para detecção de comunidades . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 29

3.2.2.1 Não espectrais . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 30

3.2.2.2 Espectrais . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 31

4 CONSTRUÇÃO DA REDE DE CO-AUTORIA E ANÁLISE DE BIBLIOTE-

CAS UTILIZADAS . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 32

4.1 Coleta de dados . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 32

7

4.2 Análise de aplicativos e bibliotecas . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 33

4.2.1 SNAP . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 33

4.2.2 GSL . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 35

4.2.3 Graphviz . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 35

5 ANÁLISES DA REDE DE CO-AUTORIA E DE ZACHARY . . . . . . . . . . . . . . 37

5.1 Centralidade . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 37

5.1.1 Rede de Zachary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 37

5.1.2 Rede de co-autoria . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 39

5.2 Detecção de comunidades . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 39

5.2.1 Rede de Zachary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 40

5.2.2 Rede de co-autoria . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 41

6 DESENVOLVIMENTO DO APLICATIVO PARA ANÁLISE DE REDES . . 44

6.1 Arquitetura . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 44

6.2 Funcionamento do aplicativo . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 45

7 CONCLUSÕES . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 48

8 REFERÊNCIAS BIBLIOGRÁFICAS . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 50

APÊNDICES . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 52

8

LISTA DE ILUSTRAÇÕES

FIG.2.1 Diferentes modelagens para rede do MSN (imagem de [1]) . . . . . . . . . . . . . . . . . 21

FIG.2.2 Comunicação de email entre funcionários de uma empresa (imagem de

[1]) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 21

FIG.2.3 Rede de Karatê de Zachary (imagem de [1]) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 22

FIG.2.4 Mapa de países afetados pelo H1N1 (imagem de [12]) . . . . . . . . . . . . . . . . . . . . . 23

FIG.4.1 Diagrama da metodologia usada . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 32

FIG.4.2 Grafo de co-autoria montado . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 34

FIG.5.1 Grafo de Zachary simplificado . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 38

FIG.5.2 GN aplicado sobre o grafo de Zachary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 40

FIG.5.3 CNM aplicado sobre o grafo de Zachary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 40

FIG.5.4 Fiedler aplicado sobre o grafo de Zachary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 41

FIG.5.5 GN aplicado sobre o grafo de co-autoria . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 41

FIG.5.6 CNM aplicado sobre o grafo de co-autoria . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 42

FIG.5.7 Bipartição de Fiedler do grafo de co-autoria . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 43

FIG.6.1 Arquitetura da Aplicação de Análise de Redes . . . . . . . . . . . . . . . . . . . . . . . . . . . 46

FIG.6.2 Tela inicial do aplicativo . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 46

FIG.6.3 Aplicativo após executada a detecção de comunidades . . . . . . . . . . . . . . . . . . . . . 46

FIG.6.4 Visualização de grafo clusterizado no aplicativo . . . . . . . . . . . . . . . . . . . . . . . . . . 47

9

LISTA DE TABELAS

TAB.4.1 Resultado da pesquisa avançada na Plataforma Lattes . . . . . . . . . . . . . . . . . . . . . 33

TAB.5.1 Parâmetros espectrais e não espectrais do grafo de Zachary (ordem de-

crescente de relevância) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 38

TAB.5.2 Parâmetros espectrais e não espectrais do grafo de co-autoria (ordem

decrescente de relevância) - Vértices numerados . . . . . . . . . . . . . . . . . . . . . . . . 39

10

RESUMO

Este trabalho tem por objetivo desenvolver um aplicativo que permita a análise de redessociais. Para atingir este objetivo, primeiramente foi realizada a análise de uma rede socialreal utilizando parâmetros espectrais e não espectrais. Foram analisadas medidas relativas àcentralidade de vértices e à detecção de comunidades.

A centralidade de vértices é uma medida relacionada à importância de um vértice em umarede, ao passo que à detecção de comunidades é um processo que consiste, basicamente, emagrupar vértices relacionados, que compartilham de determinadas características.

Foi realizado, inicialmente, um estudo sobre medidas de centralidade (grau, intermediação,proximidade, autovetor e Pagerank) e algoritmos de detecção de comunidade (algoritmos deGirvan e Newman e de Clauset, Newman e Moore, bipartição de Fiedler e, com menor profun-didade, algoritmo espectral de Newman).

Na sequência, foi construída uma rede de co-autoria com dados provenientes da PlataformaLattes (CNPq). Essa rede foi, então, analisada conforme os parâmetros estudados. As bi-bliotecas SNAP e GSL e o aplicativo Graphviz foram ferramentas que auxiliaram as análisesrealizadas.

Por fim, foi desenvolvido o aplicativo para análise de redes. Este aplicativo foi desenvolvidoem QT e integrou as bibliotecas utilizadas, simplificando, assim, o processo de análise de umarede social através da detecção de comunidades.

11

ABSTRACT

This work aims to develop an application that allows the analysis of social networks. Toachieve this objective, was first performed an analysis of a real social network by using spectraland non spectral parameters. Measures related to vertex centrality and community detectionwere examined.

The vertex centrality is a measure related to the importance of a vertex in a network,whereas the detection of communities is a process that basically consists in grouping relatednodes, which share certain characteristics.

It was performed, firstly, a study on measures of centrality (degree, betweenness, close-ness, eigenvector and PageRank) and community algorithms detection (Girvan and Newman’salgorithm, Clauset, Newman and Moore’s algorithm, Fiedler’s bipartition and, with less depth,Newman’s spectral algorithm).

On the sequence, it was built a co-authorship network with data from the Lattes Platform(CNPq). This network was analyzed according to the parameters studied. The libraries SNAPand GSL and the application Graphviz were tools that helped the performes analysis.

Finally, tha application for network analysis was developed. This application used the QTframework and integrated the libraries used, simplifying the analysis process through a socialnetwork community detection.

12

1 INTRODUÇÃO

No mundo atual, podemos visualizar e analisar o grande número de redes de relaciona-

mentos que nos cercam, como: redes sociais (facebook, twitter, orkut), redes biológicas (redes

de dispersão de doenças como dengue: gripe suína, malária), redes de colaboração (autores e

co-autores de artigos, Mathematics Genealogy Projects), dentre outras.

Os membros que formam parte de uma rede possuem papeis e propriedades: podem ser mais

centrais e mais periféricos, podem pertencer a regiões fortemente conectadas da rede, podem

pertencer às fronteiras de uma região fortemente conectada, dentre outras. Muitas vezes, é

importante o estudo da estrutura das redes para entender o significado e/ou papel dos membros

da mesma.

No caso de redes sociais, que guardam informações sobre o comportamento humano, tem

cada vez mais surgido a necessidade de se extrair informações de sua estrutura. Por exemplo, a

análise de uma rede social pode ajudar a responder questões tais como:

a) Que interesses em comum existem entre os membros de uma rede social?

b) Um determinado comportamento entre membros de uma rede é mais perceptível ao se

considerar proximidade geográfica ou proximidade de interesses?

A modelagem de uma rede geralmente é realizada através de um grafo. Por exemplo, re-

des de comunicações são frequentemente modeladas com os vértices sendo computadores e

as arestas representando ligações direcionadas ao longo das quais mensagens podem ser envi-

adas. Nas redes de informação, os vértices muitas vezes são recursos de informação, como as

páginas Web ou os documentos, e as arestas representam conexões como, por exemplo, hyper-

links, citações ou referências cruzadas. As redes sociais, por sua vez, geralmente apresentam os

vértices representando pessoas ou grupos de pessoas e as arestas representando algum tipo de

interação social.

A Teoria Clássica dos Grafos e a Teoria Espectral dos Grafos são, portanto, ferramentas que

podem ser utilizadas para extrair informações relevantes de redes dos mais variados domínios,

inclusive redes sociais.

13

1.1 OBJETIVO

O objetivo principal deste trabalho é o desenvolvimento de um aplicativo que permita inte-

grar resultados obtidos na análise de uma rede social com uma ferramenta de visualização de

grafos, facilitando a análise da estrutura da rede.

Foi definido como objetivo secundário a criação de uma rede de co-autoria baseada em

dados reais.

Os resultados obtidos sobre comunidades para essa rede de co-autoria serão utilizados como

exemplo de uso do aplicativo.

1.2 METODOLOGIA

Para atingir o objetivo deste trabalho, as atividades propostas para ser realizadas durante a

execução deste projeto foram divididas em 6 fases:

a) Fase 1: Revisão de conceitos da Teoria Clássica dos Grafos e da Teoria Espectral dos

Grafos.

b) Fase 2: Estudo sobre redes; Pesquisa sobre os tipos de redes sociais existentes; Estudo de

invariantes espectrais e não espectrais usados na análise de redes sociais.

c) Fase 3: Pesquisa e estudo de aplicações e bibliotecas para análise de redes sociais.

d) Fase 4: Criação de rede de co-autoria a partir de dados reais.

e) Fase 5: Análise da rede criada sobre dois aspectos: centralidade e detecção de comu-

nidades.

f) Fase 6: Desenvolvimento de um aplicativo que utiliza ferramentas open source para de-

tecção e visualização de comunidades de uma rede dada.

Para iniciar a pesquisa e estudar os conceitos básicos em redes sociais foi adotado o livro

recentemente publicado por Kleinberg e Easely [1], o artigo de Kleinberg [2] que tratam sobre

redes em geral e redes sociais em particular. Um texto introdutório sobre Teoria Espectral de

Grafos [3] foi usado como referência neste tópico.

Existem diversas análises realizadas em redes sociais como, por exemplo, [4] e [5], que

tratam redes socias obtidas de telefonia móvel e epidemiologia, e Newman [6], que trata de

redes de co-autoria. Outros artigos estudam o problema de deteção de comunidades em redes

sociais ([7] e [8]). As referências citadas foram usadas na fase 2.

14

Na fase 3, diversas ferramentas open source foram estudadas e analisadas para serem uti-

lizadas tanto no processo de análise da rede de co-autoria, quanto na criação do aplicativo de

visualização de comunidades.

A Plataforma Lattes do CNPq foi escolhida como fonte de informações sobre colaborações

em trabalhos e artigos no âmbito brasileiro. Dados reais sobre pesquisadores desta plataforma

foram usados para criar a rede da fase 4 deste projeto, que foi analisada posteriormente.

A análise realizada na fase 5 considerou, inicialmente, um conjunto de parâmetros espec-

trais e não espectrais relativos à centralidade. Na sequência, foram realizadas divisões em co-

munidades da rede proposta através de algoritmos não espetrais (Girvan-Newman [7] e Clauset-

Newman-Moore [8]) e espectral (algoritmo de bipartição usando vetor de Fiedler).

O aplicativo desenvolvido na fase 6, então, integrou bibliotecas e aplicativos e disponibilizou

uma interface de usuário que facilita a análise de detecção de comunidades em redes.

1.3 ESTRUTURA DO TEXTO

Este relatório é composto pelas seguintes seções:

a) A Seção 1 faz uma introdução, contendo os objetivos do trabalho e a metodologia uti-

lizada para atingir os mesmos;

b) A Seção 2 apresenta conceitos básicos sobre grafos e realiza uma introdução às redes

sociais;

c) A Seção 3 contem as definições das medidas de centralidade de vértices utilizadas em

rede social, além de apresentar o problema de deteção de comunidades em redes sociais

e apresentar os algoritmos estudados;

d) A Seção 4 apresenta os detalhes da construção do grafo de co-autoria baseado nos dados

da plataforma Lattes, além de apresentar as bibliotecas utilizadas na análise desta rede;

e) A Seção 5 traz a análise dos resultados obtidos para o grafo de co-autoria com respeito as

medidas de centralidade de vértices e detecção de comunidades;

f) A Seção 6 mostra a arquitetura e o funcionamento do aplicativo desenvolvido;

g) A Seção 7, então, apresenta as conclusões do trabalho;

Este relatório, ao fim, também contém um apêndice, no qual estão contidos o grafo cons-

truído a partir da plataforma Lattes (vértices, arestas e mapeamentos utilizados), as saídas dos

15

algoritmos utilizados (centralidade e detecção de comunidades) e ilustrações, geradas à partir

do programa Graphviz, com o intuito de apresentar as funcionalidades deste programa.

16

2 CONCEITOS BÁSICOS

Neste capítulo inicial, serão abordados alguns conceitos básicos e introdutórios no estudo de

grafos e redes sociais. Na primeira seção, serão apresentados definições e teoremas utilizados

ao longo deste texto. A segunda seção, por sua vez, apresenta conceitos importantes de redes

sociais, além de apresentar propriedades e exemplos destas redes.

2.1 CONCEITOS BÁSICOS EM GRAFOS

Segundo Kleinberg et al. ([1]), de uma maneira geral, podemos considerar uma rede como

uma coleção de objetos na qual, alguns pares deles estão relacionados por conexões. Essa

definição é muito flexível e depende da forma na qual as relações são utilizadas para definir

as ligações. Devido a essa flexibilidade, existem exemplos de redes em diversos domínios.

Podemos citar, dentre eles, as redes de comunicação, redes sociais, redes biológicas e redes de

informação. Nos últimos anos foram desenvolvidas várias linhas de pesquisa na área de redes.

Por exemplo:

a) Análise da estrutura da mesma por meio de teoria de grafos;

b) Estudo do comportamento interdependente de grupos de indivíduos da rede, por meio da

teoria de jogos; e

c) Relacionamento entre a dinâmica da rede e suas consequências na estrutura da mesma.

A teoria de grafos é a forma mais utilizada para modelar matematicamente a estrutura de

uma rede, permitindo a análise de aspectos topológicos da mesma. As análises sobre as redes

sociais realizadas neste trabalho são baseadas em grafos, tanto na Teoria Clássica dos Grafos

quanto na Teoria Espectral dos Grafos.

2.1.1 DEFINIÇÕES E PROPRIEDADES

A seguir, serão apresentadas algumas definições matemáticas de grafos. Tais definições são

importantes sobre dois aspectos: o primeiro é situar o leitor sobre os conceitos utilizados, e

o segundo é criar um entendimento único sobre cada conceito, uma vez que existem algumas

diferenças entre as definições na literatura. São apresentadas tanto definições provenientes da

17

Teoria Clássica quanto da Teoria Espectral dos Grafos. Além das definições, são apresentados

também algumas propriedades (resultados de lemas e teoremas).

a) Um grafo não-orientado G = (V,E) é formado por dois conjuntos V e E, onde V é um

conjunto finito e não vazio, |V | = n, cujos elementos são denominados vértices e E,

|E| = m, é um conjunto de subconjuntos de dois elementos de V , cujos elementos são

denominados arestas. Cada aresta é notada por e = (vi,v j), onde vi,v j ∈V . Neste texto,

quando nada for dito, subentende-se que o termo grafo se refere a um grafo não orientado.

b) O grau do vértice vi, denotado por grau(vi), é o número de arestas incidentes a eles.

Dois vértices vi e v j são ditos adjacentes se existe uma aresta entre eles, ou seja, se

ei j = (vi,v j) ∈ E.

c) Um caminho é uma sequência de vértices distintos v1,v2, ...,vk tal que (vi,vi+1) ∈ E para

1≤ i≤ k−1, k > 1. O comprimento do caminho v1,v2, ...,vk é igual a k−1.

d) Um grafo é conexo quado existe um caminho entre qualquer par de seus vértices. Caso

contrário, ele é denominado desconexo.

e) A distância entre dois vértices v e w de um grafo G denotada por dG(v,w) é o compri-

mento do menor caminho entre v e w.

f) A excentricidade de um vértice v, é definida por e(v) = maxdG(v,w), com w ∈V .

g) O valor máximo das distâncias entre todos os pares de vértices do grafo é o diâmetro do

grafo. Denotamos o diâmetro por diam(G) = maxdG(v,w), com v,w ∈V .

h) O centro do grafo G é o subconjunto de V formado pelos vértices de excentricidade

mínima.

i) Um corte é um particionamento do conjunto de vértices do grafo G = (V,E) em dois

conjuntos disjuntos não vazios S e V −S. Denota-se o corte pelo par (S,V −S).

j) Um grafo não direcionado G de n vértices pode ser representado como uma matriz A(G)=

(ai j) de dimensão n× n, denominada matriz de adjacência de G, onde a entrada (ai j) é

igual a 1 se vi e v j são adjacentes ou iguais a 0 caso contrário.

k) Seja G(V,E) um grafo nao direcionado e M sua matriz de adjacência. Define-se por

matriz Laplaciana a matriz L em que as entradas (li j) é: li j = grau(vi)−ai j.

18

l) Um número complexo λ é um autovalor da matriz M de dimensão n× n quando existe

x ∈ Cn não-nulo tal que M · x = λ · x.

m) Uma matriz M de entradas reais e simétrica possui, conforme teorema espectral [9], todos

os seus autovalores reais.

n) O autovalor com maior valor absoluto de uma matriz simétrica é denominado raio espec-

tral.

o) Uma matriz com entradas reais positivas admite um autovetor associado ao raio espectral

com todas as componentes positivas, denominado vetor de Perron, além disso, seu raio

espectral é positivo (Teorema de Perron-Frobenius [9]).

É importante perceber que algumas dessas definições podem ser estendidas. Por exemplo,

o conceito de matriz de adjacência pode ser extendido para grafos direcionados ou com pesos.

As análises realizadas neste trabalho não necessitam de tais estenções, embora os estudos sobre

bibliotecas e aplicativos realizados na Seção 4.2 apresentem algumas funcionalidades destas

que possam ser usadas com conceitos estendidos. Outros conceitos sobre grafos, algoritmos

e complexidade podem ser obtidos em [20]. Definições e conceitos básicos em teoria espec-

tral de grafos são apresentados em [1]. Uma abordagem mais completa sobre as propriedades

espectrais podem ser encontradas em Prasolov ([9]) e Putnam ([10]).

2.2 CONCEITOS BÁSICOS EM REDES SOCIAIS

Uma rede social pode ser entendida como uma rede na qual o conjunto de objetos são as

pessoas e as conexões entre elas são relações sociais. Sob o ponto de vista da Teoria dos Grafos,

uma rede social é modelada por uma grafo onde os vértices representam pessoas, ao passo que

as arestas representam relações sociais.

Há algum tempo, pode-se perceber um grande crescimento do número de redes socias obti-

das a partir de vários modelos de interação humana e social. Redes sociais como Facebook,

Linkedin, Wikipedia, entre outras, mostram a atual tendência de organização e comunicação

entre as pessoas.

As redes sociais, assim, guardam informações importantes sobre o comportamento humano.

Diversas informações acerca da estrura de uma rede social podem ser extraídas através da

análises de parâmetros, tanto não espectrais quanto espectrais, e existem diversas aplicações

reais provenientes da análise de tais parâmetros. Nos últimos anos, a análise destas informações

tornou-se uma grande área de pesquisa. Por exemplo, podemos citar as seguintes relações entre

parâmetros da Teoria dos Grafos e aplicações em redes sociais:

19

a) Centralidade: Descobrir qual membro possui maior influência ou exerce um papel de

liderança sobre os demais membros da rede;

b) Detecção de Comunidades: Levantar os perfis de pessoas predominantes em determinada

região; Definir uma estratégia de marketing eficiente para divulgar os produtos de uma

empresa aos diversos tipos de pessoas;

c) Contágio: Descobrir a capacidade que um microorganismo causador de uma dada patolo-

gia possui de invadir e de se estabelecer em uma comunidade

Neste trabalho são abordados dois problemas importantes na análise da estrutura de uma

rede: a determinação dos elementos mais importantes da mesma utilizando medidas de centra-

lidade e a determinação de grupos de elementos fortemente relacionados entre si dentro da rede

por meio da detecção de comunidades. Essa análise será aplicada numa rede de co-autoria, que

é um tipo particular de rede social. As seções a seguir apresentam exemplos de redes sociais

e conceitos relacionados. Outros conceitos sobre as redes abordadas neste trabalho podem ser

consultados em Kleinberg e Easley ([1]) e Newman ([6]).

2.2.1 EXEMPLOS DE REDES SOCIAIS

Existem diversos tipos de redes sociais, e diversos exemplos de redes reais são encontrados

na literatura. Alguns dos exemplos apresentados à seguir são abordados em Kleinberg e Easley

([1]). Inicialmente, na FIG. 2.1, são mostrados diferentes grafos criados a partir do Microsoft

Service Network (MSN). Os vértices são usuários do software e existe uma arestas entre dois

usúarios se os mesmos mantiveram algum tipo de comunicação usando o MSN. Variando o

critério da definição de aresta (por exemplo o tipo de comunicações mantidas entre usuários,

unilateral ou bilateral), obtém-se grafos diferentes. Este exemplo, além de ilustrar uma porção

de uma rede real bastante conhecida (a rede do MSN), ilustra que diferentes tipos de informação

podem ser extraídos da mesma rede, apenas variando-se as relações definidas. Assim, a FIG.

2.1 mostrada anteriormente ilustra a importância de uma boa modelagem.

Um outro exemplo de rede é exibido na FIG. 2.2 e representa um grafo obtido a partir do

espalhamento de emails entre pessoas. Os emails deste grafo se devem à comunição interna de

436 funcionários do laboratório de pesquisa da Hewlett Parckard (HP). Neste exemplo, é im-

portante ressaltar a distinção entre pequenos grupos internos, provavelmente grupos de trabalho

distintos.

Um terceiro exemplo de rede social é a rede de co-autoria, tipo de rede escolhida para

ser utilizada nas análises realizadas neste trabalho. Neste exemplo, cada vértice representa um

20

FIG. 2.1: Diferentes modelagens para rede do MSN (imagem de [1])

FIG. 2.2: Comunicação de email entre funcionários de uma empresa (imagem de [1])

21

pesquisador e existe uma aresta entre dois pesquisadores se existe publicações entre os mesmos.

2.2.1.1 A REDE DE ZACHARY

A FIG. 2.3 mostra o um desenho do grafo criado pelo Antropólogo Wayne Zachary nos

anos 70, baseado na relação entre os membros de um clube de Karatê. Durante o período

de observação desta rede social, um desentendimento entre o administrador do clube (vértice

numerado 34) e o instrutor de karatê (vértice numerado 1) produziu a saída do instrutor e quase

a metades dos membros, que formaram um novo clube. O grafo, conhecido na literatura como

o grafo do clube de Karatê de Zachary, contém vértices representando os membros do clube

original e existe uma aresta entre dois vértices, se os atletas mantém uma amizade fora do clube.

Neste grafo, é interessante perceber a distinção visível entre duas comunidades (identificadas

por cores distintas), cada qual possuindo um vértice mais central, que pode ser entendidos

como o centro das comunidades (vértices numerados 1 e 34). Este grafo é bastante difundido

na literatura, e diversas análises sobre ele já foram feitas.

FIG. 2.3: Rede de Karatê de Zachary (imagem de [1])

2.2.2 CONTÁGIO

Em alguns momentos, os indivíduos que forma parte de uma rede tem incentivos para adotar

o mesmo comportamento dos seus vizinhos. Esse novo comportamento se inicia desde um pe-

queno conjunto de adeptos e se espalha radialmente por toda a rede. Este fenômeno é conhecido

na literatura por contágio social.

No estudo do contágio social, existem duas linhas de pesquisa principais:

a) Modelar como ocorre o contágio;

22

b) Descobrir o grupo inicial de adeptos, que iniciou o contágio.

FIG. 2.4: Mapa de países afetados pelo H1N1 (imagem de [12])

Um exemplo de contágio é a disseminação de uma doença causada por vírus (Como recen-

temente o H1N1). A FIG. 2.4 mostra o mapa de contágio do vírus H1N1 nos diferentes países

(retirado do site da Fiocruz [12]). Nesse exemplo o grupo inicial de adeptos foi um pequeno

número de habitantes do México. Observa-se na figura que a doença se espalhou pelo mundo

todo. Um estudo na rede obtida a partir das informações de contato e contágio permitiria anali-

sar como a doença foi espalhada através dos diferentes países.

2.2.3 O FENÔMENO DO MUNDO PEQUENO

Nos anos 60, o psicólogo Stanley Milgram ([2]) fez um experimento que resultou em um

conceito atualmente popular na comunidade de grafos: a teoria dos seis graus de separação.

A teoria, inicialmente proposta por Milgram, afirma que cada pessoa é separada de outra pes-

soa qualquer no mundo por, no máximo, 6 laços de amizade. Esta teoria foi estabelecida pelo

psicólogo a partir de um experimento com uma carta a ser entregue pessoalmente desde o reme-

tente, morador de uma cidade dos EUA para o destinatário, morador de outra cidade por meio

de pessoas intermediárias. No experimento realizado, o número de pessoas necessárias para a

carta chegar ao destinatário foi menor ou igual a 6.

Muitas críticas são feitas a Milgran, conforme mostrado em [2]. Primeiramente, questiona-

se sua metodologia. Além disso, argumenta-se que, considerando-se pessoas de regiões mais

isoladas, estas, naturalmente, apresentam mais de seis laços de amizade para alguma outra

pessoa isolada, em outro lugar.

Recentemente ([2]), os pesquisadores Leskovec e Horvitz refizeram o experimento numa

rede criada a partir do MSN. Foi construído um grafo com 250 milhões de vértices. Cada

vértice representa um usuário de conta de MSN, e dois usuários são conectados por uma aresta

23

se eles mantiveram alguma conversa num determinado período de tempo. Analisando os dados

da rede, eles perceberam que a distância média dos caminhos mais curtos entre as pessoas era

igual a 6.6, número próximo ao número máximo empírico determinado pelo experimento de

Milgram.

Pode-se perceber que este número excede o número máximo proposto de Milgran, o que

não desmeresse sua teoria. Cabe ressaltar, neste ponto, que Milgran não possuía formação na

área de exatas. Além disso, uma interpretação proposta para sua teoria é que o número proposto

por Milgran deve ser tomado como uma média aproximada.

24

3 ESTUDO DE PARÂMETROS ESPECTRAIS E NÃO ESPECTRAIS

Diversos parâmetros podem ser utilizados para extrair informações de uma rede, conforme

apresentado na Seção 2.2. No escopo deste trabalho, foram estudados, visando sua utilização

na análise de uma rede real, parâmetros de centralidade de vértices (Seção 3.1) e detecção de

comunidades (Seção 3.2).

3.1 CENTRALIDADE DE VÉRTICES

No estudo de teoria dos grafos, bem como no estudo de redes, existe um conceito muito

importante relativo aos vértices de um grafo chamado centralidade de vértice. A centralidade

de um vértice determina a importância relativa do mesmo no grafo ao qual pertence. Desta

forma, ao medir a relativa importância de um vértice em uma rede, estamos mensurando seu

"poder"e sua influência na rede. Nós com maior centralidade possuem mais destaque. Em

uma rede social, a centralidade de um vértice, que pode representar uma pessoa, determina o

quão importante é esta pessoa na rede. Existem 5 medidas de centralidade bastante utilizadas

no estudo da análise de redes, que são: centralidade de grau (degree centrality), centralidade

de intermediação (betweenness centrality), centralidade de proximidade (closeness centrality),

centralidade de autovetor (eigenvector centrality) e PageRank.

3.1.1 CENTRALIDADE DE GRAU

Esta medida de centralidade é a mais simples. A idéia básica desta medida baseia-se na

seguinte premissa: vértices de maior grau, possuem uma posição de maior importância na rede.

Isto é, a centralidade de grau atribui relevância ao vértice em função do número de ligações

diretas que o mesmo estabelece com os demais vértices da rede.

Seja G = (V,E) um grafo com n vértices e v ∈ V um vértice. A centralidade de grau do

vértice v na rede, notada por CD(v), é definida como:

CD(v) =grau(v)

n−1 .

CD(v) também é chamada de grau normalizado de v.

25

3.1.2 CENTRALIDADE DE INTERMEDIAÇÃO

A centralidade de intermediação considera todos os caminhos mínimos entre pares de vér-

tices de uma rede, e os vértices que pertencem a um número maior de caminhos mínimos são os

que possuem maior intermediação. Em outras palavras, vértices que se encontram no caminho

mínimo entre dois vértices são importantes, e essa importância cresce a medida em que eles

aparecem em número maior de caminhos caminho mínimos.

Seja um grafo G = (V,E) com n vértices, a intermediação de v ∈ V , notada por CB(v), é

computada da seguinte forma:

a) Computa-se o número de caminhos mínimos entre os pares de vértices, para cada par

s, t ∈V .

b) Computa-se o número de caminhos mínimos que passam pelo vértice v entre pares de

vértices, para cada par de vértices s, t ∈V .

c) Computa-se a soma do número de caminhos mínimos que passam pelo vértice v con-

siderando todos os pares de vértices s, t ∈V dividido pela soma do números de caminhos

mínimos entre o par de vértices s, t considerando todos os pares de vértices s, t ∈V .

Matematicamente, temos que:

CB(v) = ∑s 6=v6=t∈Vσst(v)

σst,

Onde σst é o número de caminhos mínimos entre s e t, e σst(v) é o número de caminhos

mínimos entre s e t, que passam por v. Esta medida pode ser normalizada, dividindo-se a mesma

pelo número de par de vértices que nào incluem v, isto é (n−1)(n−2) para grafos direcionados

e (n−1)(n−2)2 para grafos não-direcionados.

3.1.3 CENTRALIDADE DE PROXIMIDADE

Esta medida é baseada no conceito de distância entre dois vértices, definida na Seção 2.1.1

e também chamada de distância geodésica. Um vértice tem maior proximidade se ele possui

menores distâncias geodésicas a outros vértices. O conceito de proximidade está diretamente

relacionado com a soma das distâncias entre um vértice e todos os outros vértices alcançáveis

por ele.

A centralidade de proximidade representa a velocidade de acesso de um elemento aos de-

mais da rede. Esta medida é importante na análise da velocidade de acesso do fluxo de dados

ou de informação a partir de um vértice para todos os demais existentes na rede.

26

Existem diversas definições na literatura baseadas nesta relação. Uma definição bastante

comum na literatura [1] é considerá-la como a média das distâncias. Entretanto, neste trabalho,

proximidade será definida como o inverso da soma das distâncias de um vértice a todos os

outros alcançáveis, de forma a concordar com a implementação da biblioteca SNAP, utilizada

neste trabalho (Seção 4.2.1).

Assim, seja G = (V,E) um grafo com n vértices e o vértice v ∈ V . Calculamos para cada

vértice v, a proximidade de v, notada por Cc(v) como:

Cc(v) = 1∑t∈V\v dG(v,t)

,

onde dG(v, t) é o comprimento do menor caminho do vértice v a cada vértice do grafo t 6= v.

3.1.4 CENTRALIDADE DE AUTOVETOR

É uma medida baseada em conceitos de teoria espectral de grafos que define uma pontuação

(score) para cada vértice de um grafo. Nesta medida de centralidade, o cálculo da pontuação de

um vértice está relacionada a todos os demais vértices e às suas respectivas pontuações. Um vér-

tice com alto valor desta medida de centralidade tem grande probabilidade de transmitir o fluxo

para muitos outros elementos da rede de forma indireta, através dos elementos aos quais ele se

conecta. Esta medida, assim, considera mais fatores que os parâmetros não espectrais. Desta

forma, esta medida é bastante usada para analisar casos de difusão de informação, infecção, ou

de comportamento pessoal.

Seja 1 ≤ i ≤ n, xi a pontuação (score) do i-ésimo vértice do grafo G = (V,E) com n vér-

tices. Seja A, a matriz de adjacência do grafo. As entradas da matriz podem ser números reais

representando a força (peso) das conexões (arestas).

Para o i-ésimo vértice, definimos sua pontuação como:

xi =∑ j∈M(i) x j

λ

onde M(i) é o conjunto dos vértices que são adjacentes com o vértice i em G e λ é uma

constante diferente de zero, ou seja:

xi =∑

nj=1 ai jx j

λ

Em forma vetorial, podemos escrever

x = 1λ

Ax,

que é equivalente a

27

Ax = λx,

conhecida como equação que define o autovetor de uma matriz, quando x 6= 0.

A solução da equação anterior determina autovetores diferentes para cada valor de λ pos-

sível. Impondo a condição de que todas as entradas do autovetor devem ser positivas (scores

são números positivos), tem-se, pelo teorema de Perron-Frobenius ([9]) que únicamente o maior

autovalor da matriz A atende à condição dada pela equação Ax = λx,x 6= 0. Dessa forma, o au-

tovetor de Perron é usado para definir a medida de centralidade. Assim, a i-ésima componente

do autovetor de Perron, é o score do i-ésimo vértice do grafo G.

3.1.5 PAGERANK

O valor do PageRank de um vértice de um grafo, numerado como i, 1 ≤ i ≤ n é definido

pela componente xi, 1≤ i≤ n, do vetor que é solução da equação:

x = D(D−αA)−1L,

onde A = (ai j) é a matriz de adjacência do grafo, D = (di j) a matriz diagonal dos graus dos

vértices do grafo, L é um vetor com todos os componentes iguais a 1 e α é um parâmetro a ser

ajustado pelo usuários (α = 0,85 é um valor frequentemente utilizado).

O PageRank é considerado uma generalização do valor de centralidade de autovetor, pois a

equação xi =∑ j=1,...,n ai jx j

λou na forma vetorial 1

λAX = x, é generalizada pela adição de constantes

α e β e a matriz D−1 na forma x = α(AD−1)x+βL, para o valor de β = 1.

O termo PageRank é bastante conhecido na literatura e na comunidade de algoritmo de

buscas por ser a base do algoritmo de buscas da empresa Google.

3.2 DETECÇÃO DE COMUNIDADES EM REDES SOCIAIS

Segundo Fortunato ([16]), uma comunidade, também denominada cluster ou módulo, é

formada por um grupo de vértices que possuem propriedades comuns, e/ou desempenham uma

função similar dentro de uma rede dada.

As comunidades são utilizadas em diversas aplicações no contexto de redes reais e permitem

fazer uma análise estrutural da mesma. No caso de redes de grande porte, determinar comu-

nidades permite o armazenamento eficiente da rede em um computador. Identificar módulos e

seus limites permite classificar os vértices que o compõem, desde o ponto de vista da posição

estrutural dentro do módulo. Outro aspecto importante relacionado com a estrutura de comu-

nidade de uma rede é a hierarquia determinada entre os integrantes da rede. Geralmente, as

28

redes reais são formadas por comunidades que contém comunidades menores, que por sua vez

contém outras comunidades.

3.2.1 O PROBLEMA DE DETECÇÃO DE COMUNIDADES

Determinar comunidades em grafos é um assunto bastante explorado na área de computação.

A formulação matemática deste problema é denominada particionamento de grafos (graph clus-

tering).

O artigo [17] faz um resumo sobre diferentes tipos de problemas de particionamento de

grafos, a complexidade dos mesmos e algoritmos aproximados para resolver alguns casos.

O problema de determinar um k-particionamento mínimo de um grafo é um problema de

otimização combinatória que consiste em, dado um conjunto de dados D e uma função de

distância d : D×D→ N tal que d satisfaz a desigualdade triangular, determinar uma partição

do conjunto D em k clusteres C1, . . . ,Ck de maneira tal que Ci ∩C j = /0 para i 6= j e tal que a

maior distância entre pares de clusteres seja minimizada ([17]). A divisão de um conjunto em

clusteres é chamado na literatura de clusterização.

O problema de determinar uma bissecção mínima de um grafo consiste em dividir o conjunto

de vértices de um grafo em dois subconjuntos do mesmo tamanho de maneira tal que o corte seja

mínimo (menor número de arestas com uma extremidade em cada conjunto do corte, ou menor

peso das arestas com uma extremidade em cada conjunto do corte no caso do grafo ter pesos

associados às arestas. O problema de determinar se um grafo admite uma bisecção mínima é

NP-Completo ([17]).

Uma vez que o problema de k-particionamento depende do número de clusteres k e da

definição de uma função distância, o problema de detectar comunidades é algo mais genérico e

complexo que o problema de k-particionamento. Para realizar uma detecção de comunidades,

deseja-se uma solução que considere tanto a obtenção do número k de partições (número de

comunidades utilizadas) quanto uma definição coerente para o que seja uma boa separação

entre os clusteres (conceito este relacionado à função distância).

3.2.2 ALGORITMOS PARA DETECÇÃO DE COMUNIDADES

Nesse projeto foram estudados quatro algoritmos de deteccão de comunidades, sendo dois

deles não espectrais, Girvan-Newman ([7]) e Clauset-Newman-Moore ([8]), e outros dois es-

pectrais, Newman ([6]) e Fiedler([3]).

29

3.2.2.1 NÃO ESPECTRAIS

Para realizar a clusterização de um grafo não direcionado, Girvan e Newman ([7]) propõem

um algoritmo que utiliza intermediação de arestas (baseada na definição de intermediação para

vértices apresentada na Secção 4.2). Os autores assumem que arestas com maior valor de in-

termediação (betw(e) = 1k onde k é o número de caminhos mínimos entre as extremidades da

aresta e) são ligações entre clusteres. Dessa forma, a rede é dividida eliminando, uma em cada

interação, as arestas com maiores valores de intermediação, até que seja realizado um corte no

grafo. Após a remoção de uma aresta, os valores de intermediação e os caminhos mínimos

são re-calculados, caso seja necessário. O algoritmo proposto por Girvan e Newman pode ser

implementado com complexidade de tempo O(n.m2) para um grafo G = (V,E) com |V | = n e

|E|= n.

Outro algoritmo foi proposto por Clauset, Newman e Moore ([8]) também baseado em in-

termediação de arestas, apresentando complexidade de tempo O(nlog2) para grafos não dire-

cionados e esparsos. Tal algoritmo apresenta uma abordagem gulosa (retirada de arestas) para

o particionamento e utiliza estruturas de dados mais sofisticadas que o algoritmo anterior.

Tanto o algoritmo de Girvan e Newman quanto o algoritmo de Clauset, Newman e Moore

são métodos globais de particionamento de um grafo G. Os mesmos determinam um conjunto

de clusteres C1, . . .Ck que formam uma partição do conjunto de vértices de G de maneira tal que

Ci∩C j = /0 quando i 6= j.

Neste texto, os algoritmos propostos por Girvan e Newman e por Clauset, Newman e Moore

serão chamados, respectivamente, de algoritmo GN e algoritmo CNM.

Um índice para medir a qualidade de partição de uma rede é denominado modularidade e foi

introduzido por Girvan e Newman em 2004 ([16]). Este fator é utilizado no critério de parada

para os algoritmos GN e CNM. Os algoritmos de detecção de comunidades param quando, após

uma interação (que promove um aumento no número de comunidades), a modularidade da nova

partição é menor que a anterior. Nesse caso, a partição anterior é retornada pelos algoritmos

como solução. Convém observar que a maximização da modularidade ao longo das iterações é

quem determina o número de comunidades do particionamento realizado.

Dada uma partição em clusteres C1, ...,Ck, a modularidade da partição, notada por

M(C1, ...,Ck), é definida como:

M(C1, ...,Ck) = ∑i=1,..., j ϕi,i−∑i6= j,i, j∈1,2,...,k ϕi, j,

na qual

ϕi, j = ∑(u,v)∈E,u∈Ciev∈C j w(e),

30

onde w(e) = 1 se o grafo não tiver peso associado às arestas.

Desta forma, o grau interno e o grau externo de cada cluster pode ser definido, em termos

desta medida de modularidade, como

grauint(Ci) = ϕi,i

e

grauext(Ci) = ∑i 6= j,ie j∈1,...,k ϕi, j−ϕi,i.

O problema de determinar um particionamento do grafo com valor máximo de modularidade

é NP-completo [5]. Por este motivo, os algoritmos GN e CNM, assim como muitos algoritmos

na literatura, utilizam heurísticas para a solução do problema.

3.2.2.2 ESPECTRAIS

Define-se conectividade algébrica como o segundo menor autovalor da matriz laplaciana

(lembrar definição na Seção 2.1.1) associada a um grafo. O algoritmo de Fiedler ([3]) se baseia

no sinal das componentes de um autovetor associado a esse autovalor. A partir desses sinais,

o grafo é bipartido em duas comunidades. O algoritmo de Fiedler pode ser visto como um

algoritmo de detecção com o número de comunidades fixo e igual a dois.

O algoritmo de Newman ([6]) define uma matriz de modularidade para o grafo. A partir

dos autovetores dessa matriz, é criado um método de detecção de comunidades. A metodolo-

gia utilizada é bastante semelhante ao algoritmo de Fiedler. Entretanto, devido a forma que a

matriz de modularidade é definida e devido ao grau de liberdade no número de comunidades

(variável k), o algoritmo de Newman é extremamente complexo em base teórica e a nível de

implementação.

31

4 CONSTRUÇÃO DA REDE DE CO-AUTORIA E ANÁLISE DE BIBLIOTECAS

UTILIZADAS

A metodologia de análise da rede de co-autoria proposta iniciou-se com o processo de cons-

trução do grafo de co-autoria baseado em dados reais da Plataforma Lattes do CNPq. Na se-

quência, esse grafo foi utilizado como entrada para a biblioteca SNAP, visando a obtenção dos

valores de centralidade. Sobre os resultados apresentados pela SNAP, foi realizada a análise

dos resultados. O processo de análise quanto a detecção de comunidades foi semelhante. O

grafo de co-autoria foi submetido às bibliotecas SNAP (algoritmos GN e CNM) e GSL (cálculo

de autovetores e autovalores usados para a bipartição usando vetor de Fiedler). A saída obtida

foi, então, fornecida ao programa Graphviz para a geração de visualizações, sob as quais foram

realizadas as análises.

A FIG. 4.1 apresenta um diagrama que representa, de modo global, o projeto desenvolvido.

Nesta seção será apresentada a descrição da construção do grafo de co-autoria baseado em

dados reais da Plataforma Lattes do CNPq. Também são descritas as bibliotecas utilizadas na

análise do grafo de co-autoria construído, cujos resultados são apresentados na Seção 5.

FIG. 4.1: Diagrama da metodologia usada

4.1 COLETA DE DADOS

Para a construção de uma rede, conforme objetivo, os dados foram retirados do site

do Conselho Nacional de Pesquisa (CNPq). Neste site, existe uma plataforma de currícu-

los de pesquisadores chamada Plataforma Lattes, na qual é possível obter dados acerca de

pesquisadores tais como áres de pesquisa, formação acadêmica, publicações em periódicos,

publicações em congressos, dentre outros.

32

Para determinar a escolha dos pesquisadores, foi realizada uma pesquisa avançada no site

de busca avançada da plataforma [11]. Buscou-se a palavra chave "grafos"dentre o conjunto de

pesquisadores com bolsa de produtividade em pesquisa. Foram selecionados os pesquisadores

com resultados de grau de aderência maior ou igual que 90% no dia 11/10/2010. Dessa forma,

foram escolhidos 13 pesquisadores. Para cada pesquisador, extraiu-se da seção "Artigos com-

pletos publicados em periódicos"do respectivo currículo Lattes a informação correspondente

aos artigos publicados em periódicos, incluindo os co-autores dos mesmos. A partir dessa in-

formação, foi criado o grafo de co-autoria, contendo 207 vértices e 520 arestas, cujos vértices

são os 13 pesquisadores e seus co-autores e existe uma aresta entre dois pesquisadores, se eles

tiveram pelo menos uma publicação conjunta.

Os 13 pesquisadores são listados na TAB. 4.1 por ordem decrescente de fator de aderência

da pesquisa:

TAB. 4.1: Resultado da pesquisa avançada na Plataforma Lattes

Posição na pesquisa Nome Aderência Bolsa1 Celia Picinin de Mello 100% Bolsista nível 1C2 Lilian Markenzon 99% Bolsista nível 1D3 Márcia Rosana Cerioli 98% Bolsista nível 24 Nair Maria Maia de Abreu 98% Bolsista nível 1B5 Cláudio Leonardo Lucchesi 98% Bolsista nível 1A6 Sulamita Klein 95% Bolsista nível 1C7 Fábio Protti 93% Bolsista nível 1C8 Loana Tito Nogueira 93% Bolsista nível 29 Orlando Lee 92% Bolsista nível 210 Marcelo Henriques de Carvalho 92% Bolsista nível 1D11 Celina Miraglia Herrera de Figueiredo 91% Bolsista nível 1B12 Carla Silva Oliveira 91% Bolsista nível 213 Jayme Luiz Szwarcfiter 90% Bolsista nível 1A

A FIG. 4.2 representa o grafo de co-autoria obtido. A rotulação utilizada, bem como a

representação textual obtida e utilizada neste texto, é apresentada no Apêndice A.

4.2 ANÁLISE DE APLICATIVOS E BIBLIOTECAS

Neste seção, serão apresentados os aplicativos e bibliotecas estudados e utilizados ao longo

do trabalho, seja na análise da rede real ou no desenvolvimento do aplicativo de análise de redes.

4.2.1 SNAP

A Stanford Network Analysis Package, ou SNAP ([14]), é uma biblioteca de análise de redes

de propósito geral criada por alunos de PhD da universidade de Stan f ord. Essa biblioteca

33

FIG. 4.2: Grafo de co-autoria montado

foi desnvolvida na linguagem C++ e foi projetada para manipular redes de grande porte, com

centenas de milhões de vértices e bilhões de arestas. Ela contém rotinas para manipular grafos,

calcular propriedades estruturais dos mesmos, gerar grafos aleatórios e suporta atributos em

vértices e arestas.

No contexto deste trabalho, as rotinas da biblioteca SNAP foram utilizadas no cálculo de

centralidade espectrais e não espectrais (pacote centrality) e no uso dos algoritmos GN e CNM

(pacote community).

O cálculo das medidas de centralidade utilizados nos algoritmos implementados nesta bi-

blioteca tem algumas particularidades. Primeiramente, a centralidade de proximidade utiliza

a fórmula definida na Seção 3.1.3, ao contrário de muitas definições encontradas na literatura.

Além disso, esta medida é calculada usando o algoritmo de busca em largura para determinar os

comprimentos dos caminhos mínimos necessários, e portanto apenas pode ser usada no caso de

grafos sem pesos nas arestas (esta restrição não existe no caso dos demais algoritmos). O valor

de centralidade de intermediação calculado por esta biblioteca considera sempre um caminho

com origem em um vértice vi e destino em v j diferente do caminho que inicia em v j, termina em

vi e possui os mesmos vértices intermediários. Por fim, no cálculo do PageRank, o valor padrão

do parâmetro α é 0,85, embora esse valor possa ser alterado pelo usuário (esse valor default foi

utilizada nas análises realizadas neste trabalho).

34

Além disso, as implementações dos algoritmos GN e GNM, embora baseadas nos artigos de

seus autores ([7] e [8], respectivamente), possuem algumas pequenas otimizações e extensões,

que não afetam a complexidade de tempo dos mesmos.

4.2.2 GSL

O GNU Scientific Library (GSL [15]) é uma biblioteca numérica desenvolvida nas lingua-

gens de programação C e C++ disponibilizada pelo projeto GNU de software livre. A bi-

blioteca oferece uma ampla variedade de rotinas matemáticas, tais como geradores de números

aleatórios, funções espaciais e funções para estimação de mínimos quadrados. A GSL é ampla e

completa, possuindo mais de mil as quais são regularmente submetidas a um conjunto rigoroso

de testes, garantindo a robustez desta biblioteca.

No contexto deste projeto foram usadas as funções desta biblioteca pertencentes ao pacote

Vectors and Matrices, que permitem calcular autovetores e autovalores de matrizes.

4.2.3 GRAPHVIZ

O Graph Visualization Software, Graphviz ([16]), é um software Open Source de visualiza-

ção gráfica criado pela AT &T Labs Research para desenhar grafos. A forma mais comum e

difundida de utilização desta biblioteca é através de especificações de grafos em scripts da lin-

guagem DOT . As visualizações geradas por este aplicativo são bastante completas e flexíveis,

podendo serem geradas visualização específicas para aplicações em diversos domínios, tais

como redes, bioinformática, engenharia de software e banco de dados.

O Graphviz possui diversas engines de geração gráfica que serão utilizadas na visualização

de grafos deste trabalho. As seis engines que foram analizadas para obter a visualização dos

grafos deste trabalho são: dot, neato, f d p, s f d p, twopi e circo. A seguir, é apresentada uma

breve descrição de cada uma delas.

a) Dot: Desenho em camadas de grafos direcionados. É a ferramenta padrão se as arestas

são direcionadas.

b) Neato: Layout "modelo de molas". É a ferramenta padrão a se utilizar se o grafo não for

muito grande (por volta de 100 vértices) e não se sabe mais nada sobre o grafo.

c) FDP: Layout "modelo de molas", semelhante ao Neato.

d) SFDP: Versão multiescala do FDP para grafos muito grandes.

35

e) Twopi : Layout radial. Vértices são colocados em círculos concêntricos dependendo de

sua distância de uma dado vértice raiz.

f) Circo: Layout circular. Muito usado em redes de telecomunicações.

O Apêndice C apresenta uma série de visualizações geradas pelo Graphviz com a finalidade

de ilustrar o funcionamento de várias engines deste aplicativo utilizando diversos parâmetros.

36

5 ANÁLISES DA REDE DE CO-AUTORIA E DE ZACHARY

Nesta seção são apresentados os resultados obtidos na análise dos grafo de co-autoria e

Zachary (Seção 2.2.1.1) para as medidas de centralidade e para os algoritmos de detecção de

comunidades. Devido a simplicidade da rede de Zachary, cada algoritmo foi primeiramente

ajustado usando os resultados obtidos por essa rede, pois existem diversos estudos disponíveis

na literatura sobre ela. Após ajustes de parametros de implementação e a certificação da corre-

tude de toda metodologia dos processos e algoritmos propostos, foram executado os algoritmos

para análise de resultados na rede de co-autoria criada. Tendo em vista o elevado número de vér-

tices e sua estrutura bastante complexa (207 vértices e 520 arestas), a análise da rede precisou

ser feita nos mais minuciosos detalhes.

5.1 CENTRALIDADE

Nesta seção, encontra-se a análise dos resultados de centralidade obtidos através da biblio-

teca SNAP ([13]). Para cada vértice do grafo, foi determinado o valor correspondente para cada

medida de centralidade definida na Seção 3.1. Uma lista completa com todos os valores de

centralidade obtidos através da biblioteca SNAP encontra-se no Apêndice B (Seção B.1).

5.1.1 REDE DE ZACHARY

A rede de Zachary é apresentada na Seção 2.2.1.1. Para facilitar a compreensão da análise

realizada, a FIG. 5.1 apresentada uma representação simplificada desta rede, semelhante à FIG.

2.3, com a clusterização proposta por Kleinberg ([1]) omitida.

A TAB. 5.1 apresenta os cinco vértices mais centrais do grafo do clube de Karatê de Zachary

segundo as medidas de centralidade trabalhadas. Os números dos vértices aparecem em ordem

crescente de relevância (dos que possuem maior centralidade, mais importantes, aos que pos-

suem medidas menores).

Observa-se na tabela que os vértices numerados 1 e 34 aparecem como os mais bem classi-

ficados em quase todas as medidas de centralidade calculadas. Vale ressaltar que a medidas de

centralidade autovetor e PageRank, baseadas em conceitos espectrais, apresentaram resultados

muitos semelhantes às medidas não espectrais. Percebe-se também que este resultado está coe-

rente com o apresentado em Kleinberg ([1]), que define os vértices 1 e 34 como os mais centrais

e importantes desta rede.

37

FIG. 5.1: Grafo de Zachary simplificado

TAB. 5.1: Parâmetros espectrais e não espectrais do grafo de Zachary (ordem decrescente derelevância)

Grau Proximidade Intermediação Autovetor PageRank34 1 1 34 341 3 34 1 1

33 34 33 3 333 32 3 33 32 9 32 2 2

38

5.1.2 REDE DE CO-AUTORIA

A TAB. 5.2 apresenta os cinco vértices mais centrais do grafo de co-autoria segundo cada

medida de centralidade definida na Seção 3.1. Assim como na análise anterior, para cada vértice

do grafo de co-autoria, foi determinado o valor correspondente para cada medida. Os vértices

são apresentados conforme a notação numérica definida no Apêndice A. Na FIG. 4.2 mostrada

anteriomente pode-se visualizar a rede de co-autoria.

TAB. 5.2: Parâmetros espectrais e não espectrais do grafo de co-autoria (ordem decrescente derelevância) - Vértices numerados

Grau Proximidade Intermediação Autovetor PageRank190 53 48 53 19053 48 112 190 11 88 190 88 53

157 157 1 157 15788 190 53 48 88

Observa-se nas tabelas que os pesquisadores 190 (SZWARCFITER) e 53 (FIGUEIREDO)

são os mais centrais para todas as medidas. Estas informações concordam com a situação real

da comunidade de pesquisadores. É sabido que tais autores são, de fato, dois grandes nomes da

área de grafos, e era de se esperar que seus nomes aparecessem como centrais no grafo montado.

Novamente, os valores obtidos para as medidas baseadas em conceitos espectrais (autovetor e

PageRank) se assemelham aos obtidos para as medidas baseadas em conceitos não espectrais

(centralidade de grau, intermediação e proximidade).

5.2 DETECÇÃO DE COMUNIDADES

Nesta seção, encontra-se a análise dos resultados de detecção de comunidade obtidos uti-

lizando os algoritmos de Girvan-Newman ([7]) (algoritmo GN) e de Clauset-Newman-Moore

([8]) (algoritmo CNM), da biblioteca SNAP ([13]), e do algoritmo de bipartição de Fiedler,

implementado com o auxílio da biblioteca GSL ([15]). Os algoritmos aqui utilizados foram

apresentados na Seção 3.2.2. As detecções obtidas pelos algoritmos são apresentadas através

de figuras geradas com o auxílio do aplicativo Graphviz ([14]).

Uma lista com as partições obtidas para cada algoritmo utilizado (sob a forma de um con-

junto de pares ordenados, contendo o vértice e a comunidade) pode ser encontrada no Apêndice

B (Seção B.B).

39

5.2.1 REDE DE ZACHARY

O algoritmo de Girvan-Newman ([7]) para a rede de Zachary retornou a detecção mostrada

na FIG. 5.2.

FIG. 5.2: GN aplicado sobre o grafo de Zachary

O algoritmo de Clauset-Newman-Moore ([8]) para a rede de Zachary retornou a detecção

mostrada na FIG. 5.3.

FIG. 5.3: CNM aplicado sobre o grafo de Zachary

Conforme foi explicado na Seção 3.2.2.1, os dois algoritmos se baseiam em critérios dife-

rentes para detecção de comunidade. O GN separou o grafo em cinco comunidades. O algo-

ritmo CNM, por sua vez, dividiu o grafo em apenas três comunidades. Esse resultado mostra

que o algoritmo GN é mais sensível quanto a detecção de comunidades em relação ao algoritmo

CNM.

Na bipartição feita pelo algoritmo de Fiedler (FIG. 5.4), a rede ficou totalmente coerente

com a bipartição feita pela heurística escolhida por Kleinberg ([1]). Além disso, os vértices 1

40

FIG. 5.4: Fiedler aplicado sobre o grafo de Zachary

e 34, mais centrais seguindo a conclusão sobre os critérios de centralidade mostrados na seção

anterior, estão em comunidades separadas.

5.2.2 REDE DE CO-AUTORIA

O algoritmo de Girvan-Newman ([7]) para a rede de co-autoria retornou as comunidades

mostradas na FIG. 5.5.

FIG. 5.5: GN aplicado sobre o grafo de co-autoria

O algoritmo de Clauset-Newman-Moore ([8]) para a rede de co-Autoria retornou o parti-

cionamento apresentado na FIG. 5.6.

41

FIG. 5.6: CNM aplicado sobre o grafo de co-autoria

O algoritmo GN identificou oito comunidades no grafo, enquanto o algoritmo CNM dividiu

o grafo em sete comunidades. Esse resultado, novamente, confirma que o algoritmo GN é mais

sensível quanto a detecção de comunidades em relação ao algoritmo CNM.

A maior parte das comunidades obtidas pelos dois algoritmos diferem em alguns vértices.

Deve-se observar também que os vértices numerados 4, 108, 52, 113, 162 e 22 foram alocados

em comunidades diferentes pelos dois algoritmos. Os vértices 96, 75, 131, 30, 49, 56, 79 e 125

formaram uma comunidade diferente na saída do algoritmo GN, fato que não acontece com a

saída do CNM (na saída deste último, esses oito vértices pertencem à mesma comunidade que

o vértice 157).

Na bipartição feita pelo algoritmo de Fiedler mostrada na FIG. 5.7, a rede de co-autoria apre-

sentou os vértices 190 (SZWARCFITER), 53 (FIGUEIREDO), 157 (PROTTI), 48 (FARIA), 88

(KLEIN), 112 (MARKEZON) e 1 (ABREU), que são os mais mais centrais seguindo a análise

da seção de centralidade, divididos entre as duas comunidades. Os vértices 190 (SZWARC-

FITER), 53 (FIGUEIREDO), 157 (PROTTI), 48 (FARIA) e 88 (KLEIN) pertencem à mesma

comunidade, enquanto os vértices 1 (ABREU) e 112 (MARKEZON) pertencem à outra comu-

nidade. O resultado obtido pelo algoritmo exibe uma bipartição desbalanceada, não distribuindo

os vértices de maior centralidade de maneira equilibrada. A utilização do algoritmo de Newman

([6]), por exemplo, poderia melhorar a distribuição dos vértices mais centrais em comunidades

diferentes.

42

FIG. 5.7: Bipartição de Fiedler do grafo de co-autoria

43

6 DESENVOLVIMENTO DO APLICATIVO PARA ANÁLISE DE REDES

Na fase final deste trabalho, foi desenvolvido um aplicativo permite a análise de redes

através de uma interface simples. Tal aplicação integra os programas e as bibliotecas utilizados

neste trabalho. Além de realizar a integração desejada, o aplicativo desenvolvido apresenta uma

interface de usuário gráfica, desenvolvida utilizando o framework QT. Por esta razão, é interes-

sante a utilização deste aplicativo na análise de comunidades em estudos e trabalhos futuros.

Neste trabalho, o aplicativo desenvolvido será chamado de “Aplicativo de Análise de Re-

des”.

As seções a seguir apresentam a arquitetura deste aplicativo e o funcionamento básico do

mesmo.

6.1 ARQUITETURA

O Aplicativo de Análise de Redes possui, como principais características, a integração do

aplicativo Graphviz e da biblioteca SNAP, a automatização de tarefas, e uma interface de usuário

para facilitar o uso da aplicação. A arquitetura utilizada no desenvolvimento deste aplicativo

possui duas camadas principais.

A camada de mais alto nível é a camada de interface, desenvolvida utilizando o framework

de código aberto QT, da Nokia. Tal framework possui como principal característica a portabili-

dade. Assim, uma interface gráfica utilizando tal framework é portável entre plataformas Linux

e Windows (além do Symbian, sistema operacional utilizado em alguns dispositivos móveis)

([18]). A interface gráfica do Aplicativo de Análise de Redes é bem compacta, possuindo, em

sua janela principal, uma barra de menus, um formulário simples e dois botões de ação. A barra

de menus permite ao usuário sair do aplicativo, abrir o diretório onde arquivos de saída gerados

são armazenados, e obter informações sobre o aplicativo. O formulário permite carregar um

grafo para análise e a seleção do algoritmo desejado. Por fim, os botões de ação permitem a

detecção das comunidades (como a consequente geração dos arquivos de saída) e a visualização

do grafo clusterizado gerado.

A camada de negócios, por sua vez, contém a lógica da aplicação. Ela, por sua vez, é

dividida em duas partes, sendo que uma delas (principal) representa a maior parte da imple-

mentação. A segunda parte, por sua vez, chamada de camada de negócios SNAP, é responsável

por realizar as chamadas necessárias a biblioteca SNAP. Em um uso corrente da aplicação, a

44

camada de negócios principal recebe uma chamada para detecção de comunidades utilizando

determinado algoritmo. Na sequência, ela realiza o processamento de strings necessário para

obter os caminhos absolutos utilizados em outras partes do programa. Logo após, é feita uma

chamada à camada de negócio SNAP, que cria as estruturas de dados utilizadas pela biblioteca

SNAP e utiliza os métodos necessários para a geração de um arquivo de saída que contém

a divisão de comunidades obtida. Por fim, a camada de negócios principal continua a exe-

cução, gerando um script DOT (apresentado na Seção 4.2.3) com as propriedades desejadas

e utilizando a aplicação Graphviz para gerar uma visualização da clusterização realizada. Os

parâmetros utilizados na geração desta visualização foram escolhidos com base na experiên-

cia obtida após repetidas utilizações do Graphviz ao longo deste trabalho. Desta forma, tais

parâmetros foram assim considerados os mais adequados para a visualização de comunidades

em redes de grande porte.

A divisão da camada de negócios em duas camadas foi realizada devido as dificuldades en-

contradas na compilação da biblioteca SNAP, que necessita de vários parâmetros de compilação,

estes difíceis de serem inseridos no projeto principal, que utiliza o QT SDK e foi desenvolvido

e compilado usando a IDE QT Creator, também da Nokia e contida no SDK. Desta forma, as

chamadas à biblioteca SNAP foram encapsuladas em uma nova camada, que tanto pode ser

compilada com base em arquivos make f ile (Linux), que contém os parâmetros necessários à

compilação da SNAP utilizando o programa make, como através de um projeto da IDE Mi-

crosoft Visual Studio, que possui os parâmetros necessários para a compilação em ambiente

Windows.

Embora a camada de negócios tenha sido projetada visando facilitar a portabilidade, existem

alguns detalhes na implementação da camada de negócio principal que a tornam não-portável,

principalmente devido às chamadas a programas externos, realizadas via API do Windows (API

Win32).

Informações sobre o framework QT (assim como o endereço eletrônico para baixar o SDK)

podem ser encontrados em [18]. Informações sobre o programa make podem ser obtidos em

[19], ao passo que informações sobre o Visual Studio podem ser encontrados em [20].

A FIG. 6.1 apresenta, esquematicamente, a arquitetura desenvolvida.

6.2 FUNCIONAMENTO DO APLICATIVO

O Aplicativo de Análise de Redes possui um funcionamento bastante simples, e seu uso

pressupõe a instalação prévia da aplicação Graphviz. A tela inicial do aplicativo é apresentada

na FIG. 6.3.

45

FIG. 6.1: Arquitetura da Aplicação de Análise de Redes

FIG. 6.2: Tela inicial do aplicativo

O usuário, então, utiliza os campos de formulário do aplicativo para selecionar o grafo e

algoritmos desejados, que deve possuir, em formato texto, uma lista de arestas separadas por

quebra de linha. Cada aresta é formada por dois vértices, representados por um número inteiro,

separados por um espaço. O grafo de co-autoria apresentado no Apêndice A é um exemplo de

entrada válida. Ao pressionar o botão “Gerar Comunidades”, o aplicativo realiza as operações

necessárias (já apresentadas na seção anterior) e gera os arquivos de saída. O botão visualizar

é, então, desbloqueado. A FIG. 6.3 representa a situação do aplicativo neste momento.

FIG. 6.3: Aplicativo após executada a detecção de comunidades

Por fim, o usuário pode pressionar o botão “Visualizar” para ver o grafo particionado (divi-

46

dido em comunidades) na tela, conforme apresentado na FIG. 6.4.

FIG. 6.4: Visualização de grafo clusterizado no aplicativo

Convém observar que, dado a indisponibilidade de tempo, não foi possível implementar a

análise de detecção de comunidades utilizando o algoritmo de Fiedler, nem a utilização dos

parâmetros de centralidade estudados ao longo deste trabalho.

47

7 CONCLUSÕES

A partir do estudo do acervo bibliográfico, consistindo de estudo de grafos, teoria espectral

e redes, notou-se a tamanha importância do assunto e das suas diversas aplicações. Um aspecto

importante concerne à parte de detecção de comunidades, que carrega resultados fundamentais

para uma análise quantitativa e qualitativa das mais diversas redes.

A análise de centralidade da rede de co-autoria mostrou tanto a consistência dos parâmetros

espectrais e não espectrais, quanto uma metodologia adequada de análise. Pôde-se concluir

que tais parâmetros podem extrair, de fato, informações relevantes sobre a importância dos nós

de uma rede, em especial em redes de grande porte, onde uma análise baseada em critérios

subjetivos torna-se mais difícil.

No caso da detecção de comunidades, as análises realizadas (quando apoiadas por uma

ferramenta que permitisse a visualização) mostraram que é possível agrupar elementos que se

relacionam mais fortemente de forma a extrair informações de uma rede social. Além disso,

percebeu-se que os resultados concordam com aqueles obtidos pela análise dos parâmetros de

centralidade.

Também foi constatado que o algoritmo de Girvan e Newman ([7]) é mais “sensível” que

o de Clauset, Newman e Moore ([8]), detectando um número maior de comunidades. Outra

conclusão obtida foi que a bipartição de Fiedler ([3]) nem sempre gera boas divisões devido a

sua limitação de possuir número de comunidades fixo. Esta restrição, entretanto, não ocorre no

algoritmo de Newman ([6]), sendo assim interessante realizar um melhor estudo deste algoritmo

em trabalhos futuros.

O trabalho também mostrou que as bibliotecas SNAP ([13]) e GSL ([15]), assim como

o aplicativo Graphviz ([14]), são ferramentas bastante úteis quando utilizadas em análises de

redes, principalmente no caso de redes de maior porte.

Percebeu-se também que o aplicativo criado foi de grande valia por simplicar, de forma

eficaz, o processo de criação, detecção de comunidades e visualização das redes. Convém

ressaltar que nem todos os parâmetros estudados foram implementados no aplicativo.

Ficam registradas as seguintes sugestões para trabalhos futuros:

a) Estudo mais aprofundado, implementação e análise do algoritmo de Newman;

b) Ampliação da análise da rede de co-autoria, incluindo a utilização do algoritmo de New-

man e variantes do algoritmo de Fiedler, bem como de outros algoritmos que se consi-

48

derem relevantes;

c) Realização de melhorias no aplicativo desenvolvido, tanto adicionando novos algoritmos

de detecção de comunidades, a exemplo dos algoritmos de Fiedler e espectral de New-

man, quanto adicionando novas funcionalidades (por exemplo, aprimorando a interface de

usuário ou adicionando a análise de centralidade). Outra melhoria importante seria a re-

alização das modificações necessárias para tornar o aplicativo portável para a plataforma

Linux.

49

8 REFERÊNCIAS BIBLIOGRÁFICAS

[1] J. KLEINBERG, D. EASLEY, Networks, Crowds and Markets: A reasoning about a

Highly Connected World, Cambridge University Press, 2010.

[2] J. KLEINBERG, The convergence of Social and Technological Networks, Communica-

tions of the ACM, Vol 51, No 11, November 2008, pp. 66-72.

[3] N. ABREU, R. DEL-VECCHIO, C. VINAGRE, D. STEVANOVIC, Introdução à teoria

espectral de grafos com aplicações, SBMAC, 2007.

[4] J.P. ONNELA, J. SARAMAKI, J. HYVONEN, G. SZABÓ, D. LAZER, K. KASKI, J.

KERTÉSZ, A.L. BARABÁSI, Structure and tie strengths in mobile communication net-

works, Proceedings of the National Academy of Sciences of United States of America,

Vol 104 No 18, 2007, pp. 7332-7336.

[5] A. MCKENZIE, I., KASHEF, J.D. TILLINGHAS, V.E. KREBS, L.A. DIEM, B.

METCHOCK, T. CRISP, P. D. MCELROY, Transmition Network analysis to comple-

ment rutine tuberculosis contact investigations American Journal of Public Health, Vol

97 No. 3, 2007, pp. 470-477.

[6] M. E. J. NEWMAN, Fiding community structure in networks using eingenvectors of ma-

trices, Phys. Rev. E 74(3), 036104, 2006.

[7] M. GIRVAN, M. E. J. NEWMAN, Community structure in social and biological net-

works, Academic Science USA 99,7821-7826, 2002.

[8] A. CLAUSET, M. E. J. NEWMAN, C. MOORE, Finding community structure in very

large networks, Phys. Rev. E 70, 066111, 2004.

[9] V. V. PRASOLOV, The Problems and Theorems in Linear Algebra, American Mathemat-

ical Society, 1994.

[10] R. GELCA, T. ANDREESCU, Putnam and Beyond, Springer, 2010.

[11] CNPQ, CNPQ - Busca Textual Avançada, Disponível em:

<http://servicosweb.cnpq.br/rc/inicio?cliente=buscatextual&cod=3957046121364560>,

Acessado em: 20 Set 2010.

50

[12] FIOCRUZ, Mapa de contágio do vírus H1N1, Disponível em:

<http://www.cpqgm.fiocruz.br/?area= 07X03&new= 372 >, Acessado em: 20 Set

2010.

[13] SNAP, Site da Biblioteca SNAP - Stanford, Disponível em: <www.snap.stanford.edu>,

Acessado em: 20 Out 2010.

[14] GRAPHVIZ, Site do projeto Graphviz, Disponível em: <http://www.graphviz.org>,

Acessado em: 16 Nov 2010.

[15] GNU, Site da biblioteca GNU GSL, Disponível em: <http://www.gnu.org/software/gsl>,

Acessado em: 16 Nov 2010.

[16] S. FORTUNATO, Community detection in graphs arXiv:0906.0612v2 [physics.soc-ph]

25 Jan 2010.

[17] S.E. SHAEFFER, Graph clustering Computer Science Review I, 2007, pp. 27-64.

[18] NOKIA, Site do Framework QT, Disponível em: <http://http://qt.nokia.com>, Acessado

em: 22 Jun 2011.

[19] GNU, Site do projeto GNU Make, Disponível em:

<http://www.gnu.org/software/make>, Acessado em: 22 Jun 2011.

[20] MICROSOFT, Site do Microsoft Visual Studio, Disponível em:

<http://www.microsoft.com/visualstudio>, Acessado em: 21 Jun 2011.

51

-2 APÊNDICES

52