CENTRO FEDERAL DE EDUCAÇÃO TECNOLÓGICA DE MINAS GERAIS
Mestrado em Modelagem Matemática e Computacional
Valter Ribeiro Lima Júnior
Uma Investigação acerca da Conectividade da
Web Brasileira
Belo Horizonte
Agosto de 2014
CENTRO FEDERAL DE EDUCAÇÃO TECNOLÓGICA DE MINAS GERAIS
Mestrado em Modelagem Matemática e Computacional
Valter Ribeiro Lima Júnior
Uma Investigação acerca da Conectividade da
Web Brasileira
Dissertação
de
mestrado
submetida
ao
Programa de Pós-Graduação em Modelagem
Matemática e Computacional, como parte
dos requisitos para a obtenção do título
de Mestre em Modelagem Matemática e
Computacional.
Orientador: Prof. Cristina Duarte Murta
Coorientador: Prof. Adriano César Machado Pereira
Belo Horizonte
Junho de 2014
Agradecimentos
Agradeço a minha minha orientadora Cristina e ao meu coorientador Adriano pela
paciência e conhecimentos compartilhados. Agradeço também aos colegas de mestrado
pelo apoio e ajuda nos estudos. Agradeço a CAPES pelo apoio nanceiro tão necessário
para concluir este mestrado. Por m, agradeço a minha família e minha namorada Natália
pelo apoio e incentivo aos estudos.
Resumo
A Web é uma rede complexa de informação e de comunicação construída a partir do
modelo de hipertexto, cujo aspecto central é a conectividade. Na representação da Web
como um grafo, os vértices são documentos HTML, comumente denominados páginas, e
as arestas são links que apontam de uma página para outra. Essa dissertação examina a
seguinte questão: quão conectada é a Web brasileira? Para analisar essa questão, foram feitas duas coletas da Web brasileira, uma tendo como alvo o domínio .br, e a segunda tendo
como alvo a Web governamental brasileira (.gov.br). A amostra da Web obtida representa
cerca de 7% da Web brasileira. Os dados coletados foram modelados como grafos dirigidos
e analisados de acordo com modelos estatísticos e computacionais. A conectividade e a
estrutura topológica dos grafos foi analisada a partir dos resultados de métricas tais como
a distribuição dos graus de entrada e de saída, os componentes fortemente conectados, as
distâncias entre os vértices e o betweenness. Os resultados indicam que a Web brasileira
apresenta características similares às obtidas em estudos correlatos. Além disso, a Web
brasileira contém sítios muito conectados internamente, porém, como rede, é minimamente
conectada.
Palavras-chave:
Web Brasileira, Grafos, Web, Redes Complexas.
Abstract
The Web is a complex network of information and communication built from the hypertext model, whose central feature is the connectivity. In the representation of the Web
as a graph, the vertices are HTML documents, commonly called pages, and the edges are
links pointing from one page to another. This dissertation examines the question: how connected is the Brazilian Web? To examine this question, two datasets were collected from
the Brazilian Web, one focusing the domain .br, and the second targeting the Brazilian
governmental's Web (.gov.br). The sample obtained from the Web crawler is about 7% of
the Brazilian Web. The datasets were modeled as directed graphs and analyzed according
to statistical and computational models. The network connectivity and the topological
graph structure were analyzed from the results of metrics such as the distribution of the
input and output degrees, the strongly connected components, the distances between the
vertices and the betweenness. The results indicate that the Brazilian Web features are
similar to those reported in previous studies. Moreover, the Brazilian Web sites are very
much connected internally, however, as a network, it is minimally connected.
Keywords:
Brazilian Web, Graphs, Web, Complex Networks.
Sumário
Lista de Figuras
9
Lista de Tabelas
11
1 Introdução
12
1.1
Escopo . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 14
1.2
Objetivos . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 16
1.3
Contribuições . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 16
1.4
Estrutura da Dissertação . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 17
2 Conceitos e Trabalhos Relacionados
18
2.1
Redes Complexas . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 18
2.2
Teoria de Grafos . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 19
2.2.1
Grafos Não-dirigidos . . . . . . . . . . . . . . . . . . . . . . . . . . . 20
2.2.2
Grafos Dirigidos . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 20
2.3
O Grafo da Web . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 22
2.4
Registros da Web Brasileira . . . . . . . . . . . . . . . . . . . . . . . . . . . 26
2.5
Considerações Finais . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 27
3 Coleta de Dados e Metodologia
29
3.1
Modelagem dos Grafos . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 30
3.2
Métodos de Análises dos Grafos . . . . . . . . . . . . . . . . . . . . . . . . . 35
3.3
Estudos com o HTTrack . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 36
3.4
Comparação com Estatísticas da Web Brasileira . . . . . . . . . . . . . . . . 40
3.5
Considerações Finais . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 41
6
4 Resultados
4.1
4.2
4.3
42
Resultados do Grafo .br . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 42
4.1.1
Maior Componente Fortemente Conectado do Grafo .br . . . . . . . 51
4.1.2
Análise do Grafo .br via Pajek . . . . . . . . . . . . . . . . . . . . . 54
4.1.3
Resultados do HTTrack . . . . . . . . . . . . . . . . . . . . . . . . . 57
Resultados do Grafo .gov.br . . . . . . . . . . . . . . . . . . . . . . . . . . . 63
4.2.1
Maior Componente Fortemente Conectado do Grafo .gov.br . . . . . 69
4.2.2
Análise do Grafo .gov.br via Pajek . . . . . . . . . . . . . . . . . . . 72
4.2.3
O Censo da Web Governamental Brasileira . . . . . . . . . . . . . . 75
Comparação entre os grafos .br e .gov.br . . . . . . . . . . . . . . . . . . . . 76
5 Conclusão
83
5.1
Contribuições . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 85
5.2
Trabalhos Futuros . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 87
Referências Bibliográcas
88
Lista de Figuras
2.1
(a) Representação de um grafo não-dirigido. (b) Componentes conectados.
(c) Representação de um grafo dirigido. . . . . . . . . . . . . . . . . . . . . 20
2.2
Componentes fortemente conectados em um grafo dirigido. Figura extraída
de [Rocha 2007]. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 21
2.3
Representação do grafo da Web. . . . . . . . . . . . . . . . . . . . . . . . . . 23
2.4
Componentes em um grafo da Web. Figura adaptada de [Vitali et al. 2011].
3.1
Etapas da modelagem dos grafos. . . . . . . . . . . . . . . . . . . . . . . . . 31
4.1
Graus do grafo .br. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 46
4.2
Ranking dos graus do grafo .br. . . . . . . . . . . . . . . . . . . . . . . . . . 46
4.3
Frequência dos graus do grafo .br. . . . . . . . . . . . . . . . . . . . . . . . . 47
4.4
Ajuste dos graus do grafo .br. . . . . . . . . . . . . . . . . . . . . . . . . . . 47
4.5
Graus do maior CFC do grafo .br. . . . . . . . . . . . . . . . . . . . . . . . 52
4.6
Rank dos graus do CFC do grafo .br. . . . . . . . . . . . . . . . . . . . . . . 52
4.7
Frequência dos graus do maior CFC. . . . . . . . . . . . . . . . . . . . . . . 53
4.8
Ajuste dos graus do maior CFC do grafo .br. . . . . . . . . . . . . . . . . . 53
4.9
Graus de entrada do grafo .br no Pajek. . . . . . . . . . . . . . . . . . . . . 55
24
4.10 Graus de saída do grafo .br no Pajek. . . . . . . . . . . . . . . . . . . . . . . 55
4.11 Componentes fortemente conectados do grafo .br no Pajek. . . . . . . . . . 56
4.12 Os 20 vértices com os maiores valores de betweenness no grafo .br. . . . . . 57
4.13 Universos de 5 vértices.
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . 58
4.14 CFCs de 5 vértices. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 60
4.15 Universos de 69 vértices. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 60
4.16 CFCs de 69 vértices. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 62
8
4.17 Graus do grafo. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 67
4.18 Ranking dos graus do grafo .gov.br. . . . . . . . . . . . . . . . . . . . . . . . 67
4.19 Frequência dos graus de entrada e de saída do grafo .gov.br. . . . . . . . . . 68
4.20 Ajuste dos graus do grafo .gov.br. . . . . . . . . . . . . . . . . . . . . . . . . 68
4.21 Graus do maior CFC do grafo .gov.br. . . . . . . . . . . . . . . . . . . . . . 70
4.22 Ranking dos graus do CFC do grafo .gov.br. . . . . . . . . . . . . . . . . . . 71
4.23 Frequência dos graus do CFC do grafo .gov.br. . . . . . . . . . . . . . . . . 71
4.24 Ajuste dos graus do maior CFC do grafo .gov.br. . . . . . . . . . . . . . . . 72
4.25 Graus de entrada do grafo .gov.br no Pajek. . . . . . . . . . . . . . . . . . . 73
4.26 Graus de saída do grafo .gov.br no Pajek. . . . . . . . . . . . . . . . . . . . 73
4.27 Componentes fortemente conectados do grafo .gov.br no Pajek. . . . . . . . 74
4.28 Os 20 vértices com os maiores valores de betweenness no grafo .gov.br. . . . 75
Lista de Tabelas
2.1
Principais domínios da Web brasileira. . . . . . . . . . . . . . . . . . . . . . 27
2.2
Distribuição dos domínios .gov.br por estado. . . . . . . . . . . . . . . . . . 27
3.1
Extração dos sítios das URLs. . . . . . . . . . . . . . . . . . . . . . . . . . . 32
3.2
Distinção entre sítios e subsítios. . . . . . . . . . . . . . . . . . . . . . . . . 32
3.3
Laços após a extração dos sítios. . . . . . . . . . . . . . . . . . . . . . . . . 33
3.4
Arestas repetidas após a extração dos sítios. . . . . . . . . . . . . . . . . . . 33
3.5
Trecho da lista de arestas do grafo .gov.br. . . . . . . . . . . . . . . . . . . . 34
3.6
Números obtidos das modelagens. . . . . . . . . . . . . . . . . . . . . . . . . 34
3.7
Dimensões dos grafos de códigos HTTP 2xx e 3xx. . . . . . . . . . . . . . . 34
3.8
Sítios do componente fortemente conectado de 5 vértices. . . . . . . . . . . . 37
3.9
Sítios do componente fortemente conectado de 69 vértices. . . . . . . . . . . 38
3.10 Extração do domínio de um sítio. . . . . . . . . . . . . . . . . . . . . . . . . 40
4.1
Dados da modelagem do grafo .br. . . . . . . . . . . . . . . . . . . . . . . . 42
4.2
Os 24 vértices com mais laços no grafo .br. . . . . . . . . . . . . . . . . . . . 44
4.3
Os 20 arcos com mais repetições no grafo .br. . . . . . . . . . . . . . . . . . 45
4.4
Dados estatísticos sobre os graus do grafo .br. . . . . . . . . . . . . . . . . . 45
4.5
Os 20 vértices com os maiores graus de entrada. . . . . . . . . . . . . . . . . 48
4.6
Os 20 vértices com os maiores graus de saída. . . . . . . . . . . . . . . . . . 48
4.7
Dados estatísticos das distâncias. . . . . . . . . . . . . . . . . . . . . . . . . 49
4.8
Quantidade de componentes fortemente conectados no grafo .br. . . . . . . . 50
4.9
Dados de domínios por DPN. . . . . . . . . . . . . . . . . . . . . . . . . . . 50
4.10 Dados estatísticos sobre os graus do CFC do grafo .br. . . . . . . . . . . . . 51
4.11 Dados estatísticos das distâncias do CFC. . . . . . . . . . . . . . . . . . . . 54
10
11
4.12 Dimensões do modelo da gravata no grafo .br. . . . . . . . . . . . . . . . . . 56
4.13 Comparação dos graus de saída dos subgrafos de 5 vértices. . . . . . . . . . 59
4.14 Os 20 vértices com os maiores graus de saída dos subgrafos de 69 vértices. . 61
4.15 Conexões inexistentes no CFC do HTTrack. . . . . . . . . . . . . . . . . . . 62
4.16 Dados da modelagem do grafo .gov.br. . . . . . . . . . . . . . . . . . . . . . 63
4.17 Os 20 vértices com mais laços. . . . . . . . . . . . . . . . . . . . . . . . . . . 64
4.18 Os 20 arcos com mais repetições no grafo .gov.br. . . . . . . . . . . . . . . . 64
4.19 Dados estatísticos sobre os graus do grafo .gov.br. . . . . . . . . . . . . . . . 65
4.20 Os 20 vértices com os maiores graus de entrada do grafo .gov.br. . . . . . . 66
4.21 Os 20 vértices com os maiores graus de saída do grafo .gov.br. . . . . . . . . 66
4.22 Dados estatísticos das distâncias do grafo .gov.br. . . . . . . . . . . . . . . . 69
4.23 Quantidade de CFC no grafo .gov.br. . . . . . . . . . . . . . . . . . . . . . . 69
4.24 Dados estatísticos sobre os graus maior do CFC do grafo .gov.br. . . . . . . 70
4.25 Dados estatísticos das distâncias no maior CFC do grafo .gov.br. . . . . . . 72
4.26 Dimensões do modelo da gravata no grafo .gov.br.
. . . . . . . . . . . . . . 74
4.27 Porcentagem de sítios separados por estado. . . . . . . . . . . . . . . . . . . 77
Capítulo 1
Introdução
A Web é uma aplicação da Internet concebida por Tim Berners-Lee entre 1989 e 1991,
cujo objetivo primordial é a troca de informações [Easley and Kleinberg 2010]. Porém, a
Web popularizou-se somente a partir do m da década 1990, fato de grande importância para a comunicação. Como a Web é um meio pouco controlado, qualquer indivíduo
ou organização pode criar sítios sem qualquer restrição em relação a quantidade da páginas ou de links [Barabási et al. 2000a]. Este fato ocasionou um crescimento irregular,
transformando a Web em uma rede grande e complexa, o que dicultou determinar sua
conectividade ou até mesmo identicar a localidade efetiva de determinada informação.
A Web é constituída basicamente por um conjunto de documentos denominados páginas. Estas páginas possuem conexões virtuais para outras páginas, o que ocasiona a
formação de um grafo dirigido. Deste grafo, os vértices são representados por páginas
HTML e as arestas dirigidas por hyperlinks que apontam de uma página para outra.
Os estudos da Web como um grafo tiveram origem no m da década de 1990. Um
dos estudos pioneiros [Barabási and Albert 1999] apresenta um modelo para explicar o
surgimento de redes aleatórias. Neste estudo os autores descrevem sistemas para comparar
suas características com as do modelo apresentado. Destes sistemas pode-se citar a World
Wide Web e outros, como as redes genéticas e padrões de citação em artigos cientícos, que
podem ser representados como redes com uma complexa topologia em que sua principal
característica comum é que a conectividade dos vértices (grau) segue uma distribuição de
lei de potência.
Outro trabalho de destaque apresenta um estudo realizado especicamente acerca da
conectividade do grafo da Web. O estudo apresentou a conectividade, a estrutura ma12
13
croscópica e também a já conhecida distribuição de lei de potência dos graus de um grafo
de cerca de 200 milhões de vértices e 1,5 bilhão de arestas [Broder et al. 2000]. Este foi
o primeiro estudo a representar a estrutura topológica da Web de acordo com o modelo
conhecido como gravata borboleta.
Após esse período, observa-se uma ausência de estudos relacionados ao grafo da
Web na primeira metade da década de 2000. Importantes estudos foram realizados entre 1999 e 2000, destes pode-se citar [Barabási and Albert 1999], [Broder et al. 2000],
[Kumar et al. 2000] e [Barabási et al. 2000a]. Porém, só a partir de meados da década de
2000 sugiram novos estudos relevantes em [Modesto et al. 2005], [Boccaletti et al. 2006] e
[Easley and Kleinberg 2010]. Um fato que deve ser lembrado é que, independentemente do
grafo ou de como ele foi coletado, em todos os estudos foram identicadas as leis de potência na distribuição dos graus, o modelo de gravata borboleta em sua estrutura topológica e
comprimentos de menores caminhos relativamente curtos, que se enquadram no fenômeno
small-world.
A rede da World Wide Web (WWW) ou simplesmente Web possui grande tamanho e
grande quantidade de interações e, por ser uma rede muito dinâmica, produz uma topologia que é desconhecida [Barabási et al. 2000a]. A partir disto, nosso estudo foi motivado
pelo interesse em analisar como está conectada a Web brasileira. Apenas dois estudos relacionados foram encontrados nos trabalhos de [Veloso et al. 2000] e [Modesto et al. 2005].
Apesar de serem estudos sobre a Web brasileira, eles pouco se referem à conectividade,
dando maior enfoque ao conteúdo descoberto nas páginas. A partir de nosso trabalho são
respondidas questões sobre o tema, por exemplo, como a Web está conectada e se a rede é
conexa de maneira a ser possível percorrê-la sem a ajuda de máquinas de busca. Também
é possível responder se a estrutura da Web brasileira atual ainda pode ser representada
pelo modelo em forma de gravata [Broder et al. 2000]. Além disso, investigamos se a Web
governamental brasileira (.gov.br) possui características similares a Web brasileira como
um todo.
A partir desse estudo será possível identicar, dentre outros fatores, quais páginas possuem as maiores quantidades de conexões. A descoberta destas páginas pode ter diversas
nalidades como, por exemplo, ser de interesse para anunciantes que querem divulgar al-
1.1. ESCOPO
14
gum tipo de produto na Web. A partir destas páginas é possível alcançar uma gama maior
de pessoas, pois muitas vezes estas páginas são populares. Além disto, os resultados de
estudos da Web auxiliam no desenvolvimento de algoritmos de classicação de páginas,
como o PageRank, e podem até detectar anomalias na rede [Broder et al. 2000]. Estudos da Web como um grafo servem como base para criação de ferramentas para melhor
estudá-la e também podem servir de base para estudos de disseminação de informação na
rede. A partir do estudo da Web também é possível fazer previsões de como a Web estará
estruturada no futuro [Chayes 2013].
Outro fato caracterizado no estudo da Web é sua interdisciplinaridade, que abrange
três áreas do conhecimento: ciência da computação, matemática e estatística. À ciência
da computação cabe a rede de compartilhamento de informação, neste caso o estudo da
Web. Da matemática são estudados os grafos, que constituem a forma de representar a
Web em estudos de conectividade. Por m, a estatística é usada na obtenção de dados de
métricas dos grafos como a distribuição probabilística dos graus, o coeciente de variação
dos graus, os graus e as distâncias médias.
1.1
Escopo
Este trabalho consiste em realizar uma investigação acerca da conectividade e estrutura
topológica da Web Brasileira. Para tanto, foram estudadas duas partes desta Web, a
primeira caracteriza um estudo que abrange a Web brasileira como um todo. Como Web
brasileira consideramos todos os sítios que nalizam seu domínio com .br. O segundo
estudo tem como foco apenas a Web governamental brasileira, em que foram estudados os
sítios que abrangem o domínio .gov.br.
A investigação foi realizada utilizando-se um conjunto de técnicas de análise que calculam métricas em amostras do grafo da Web. Destas métricas pode-se citar a distribuição
probabilística dos graus de entrada e saída, a identicação dos componentes fortemente
conectados, estatísticas de distância entre vértices, a centralidade e o coeciente de agrupamento.
Foram utilizados dois grafos no estudo, e ambos foram modelados a partir de registros
de duas coletas obtidos com uso do Web crawler Heritrix. O primeiro se trata do grafo de
um retrato da Web .br, do qual teve sua coleta realizada no período de 9 de dezembro
1.1. ESCOPO
15
de 2012 a dia 14 de janeiro de 2013. O segundo grafo foi obtido a partir de um universo
contido dentro da Web brasileira, mais especicamente a Web governamental brasileira
(.gov.br). Este grafo foi modelado a partir de uma coleta realizada no mês de agosto de
2013.
Um fato que deve ser descrito sobre o projeto refere-se às limitações de coletas utilizando
Web crawler. Uma das limitações contidas na coleta está relacionada ao seu tamanho, pois
dicilmente seria possível coletar todas as páginas da Web por crawling. Diante disto,
o processo foi executado em períodos limitados, ou seja, os dados obtidos representam
apenas um retrato da Web a partir de uma coleta feita em um período de tempo. As
congurações do Web crawler também inuenciam o resultado, pois em uma das coletas só
foram registrados sítios do domínio .br e na outra somente sítios do domínio .gov.br, o que
ocasiona a exclusão de links de outros domínios contidos nas páginas visitadas. O protocolo
de exclusão de robôs, que é um arquivo contido em cada sítio que especica as permissões
de acesso para coletores, também é outra limitação. A não coleta de determinados sítios
é prejudicial à navegação da rede, pois afeta a forma de como ela está conectada. Outra
limitação que deve ser levada em consideração é a dinamicidade da Web: páginas podem
ser modicadas, excluídas e novas páginas podem ser criadas enquanto a coleta está sendo
realizada.
Outra limitação de estudos de conectividade de grafos baseados em coletas por Web
crawler é a respeito de como os links são visitados. É uma característica do crawler não
repetir a varredura de links que referenciam páginas já encontradas, isto ocorre pois o
crawler prioriza mais a descoberta de novas páginas que a forma como as páginas conhecidas estão conectadas entre si. Este fato gerará um caminhamento do tipo árvore
geradora mínima no grafo. Para contornar esta situação, foram realizadas coletas exaustivas no software HTTrack de componentes fortemente conectados identicados no grafo
.br. A partir da análise destas coletas completas, bem como a comparação com os dados
do [Registro.br 2013], foi possível estimar o quão próximo a coleta por Web crawler está
de representar elmente a referida amostra da Web.
1.2. OBJETIVOS
1.2
16
Objetivos
O objetivo geral deste trabalho é investigar a conectividade da Web brasileira a partir
de subgrafos construídos com base em coletas realizadas na Web .br e Web .gov.br.
Por ser a Web uma rede com a principal função de estabelecer conexões, o estudo da
conectividade intervém diretamente na localidade de informação na rede. Pode-se descobrir
através do estudo, se a rede está conectada a ponto de ser possível percorrê-la por inteiro
para identicar determinada informação ou se esta tarefa é possível somente com a ajuda
de máquinas de busca.
Os objetivos especícos são:
• Identicar aspectos da conectividade de subgrafos gerados a partir de uma coleta da
Web brasileira, inclusive do subgrafo da Web governamental brasileira;
• Investigar a possibilidade de inferir a conectividade da Web a partir de uma coleta
via crawler ;
• Avaliar se a conectividade contida em um subgrafo gerado a partir de um registro
de coleta do Web crawler Heritrix pode ser considerada representativa por meio de
comparação com o mesmo subgrafo modelado a partir de uma coleta exaustiva do
HTTrack;
• Identicar a similaridade dos resultados obtidos nas análises com os já contidos na
bibliograa sobre a Web.
1.3
Contribuições
Como contribuições desse trabalho, foram respondidas questões relacionadas a conectividade da Web atual, tais como:
• Quais são os sítios mais conectados na Web brasileira;
• Qual é a quantidade de componentes fortemente conectados da Web brasileira e o
quanto ela está fragmentada;
• Se a estrutura topológica da Web brasileira ainda é representada pelo modelo gravata
borboleta;
1.4. ESTRUTURA DA DISSERTAÇÃO
17
• Se um grafo gerado a partir de uma coleta de Web crawler representa elmente a
conectividade da Web;
• Se a conectividade da Web atual possibilita navegar na rede sem a interferência de
buscadores como o Google.
Adicionalmente, para nosso estudo foi desenvolvida uma ferramenta útil na análise da
conectividade de grafos, a qual foi disponibilizada em um repositório online 1 .
1.4
Estrutura da Dissertação
Esta dissertação está estruturada em cinco capítulos para melhor organização e entendimento do texto. O Capítulo 2 apresenta conceitos e trabalhos relacionados sobre grafos,
redes complexas e grafo da Web, que se mostram necessários para contextualizar o trabalho. A metodologia de pesquisa utilizada no desenvolvimento do trabalho é apresentada
no Capítulo 3. O Capítulo 4 apresenta os resultados dos estudos que envolvem os grafos
.br e .gov.br. Por m, o Capítulo 5 apresentam as conclusões, contribuições, trabalhos
futuros e considerações obtidas ao m dos estudos.
1
https://github.com/valtincomp/implementacoes-semish
Capítulo 2
Conceitos e Trabalhos Relacionados
Este capítulo apresenta uma revisão dos conceitos relacionados a grafos, redes complexas e World Wide Web (WWW) necessários ao entendimento desse trabalho. A Seção
2.1 apresenta um estudo sobre diversos tipos de redes complexas e suas características. A
Seção 2.2 apresenta um estudo sobre teoria de grafos, que se trata da forma mais indicada
de representar redes complexas. A Seção 2.3 apresenta denições, características e estudos
relacionados ao grafo da World Wide Web. A Seção 2.4 apresenta dados do registro de
domínios no país. Por m, a Seção 2.5 apresenta as considerações nais do capítulo.
2.1
Redes Complexas
A diculdade da ciência contemporânea para descrever sistemas compostos de elementos não idênticos, que têm interações diversas e não-locais, limita avanços em muitas
disciplinas, que vão da biologia molecular à ciência da computação. A diculdade em descrever esses sistemas reside em seu grande tamanho e também seus aspectos dinâmicos.
Muitos deles formam redes complexas, cujos vértices são os elementos do sistema e as arestas representam as interações entre eles [Barabási and Albert 1999]. Uma forma simples e
objetiva de se denir redes complexas é que se tratam de redes muito grandes, o que torna
difícil sua descrição completa [Hofstad 2010].
Os pesquisadores, tanto os interessados nas aplicações, quanto na teoria, realizaram
estudos a m de descobrir qual é a quantidade de vértices que estas redes possuem, e qual
é a regra para realizar uma conexão de um vértice a outro [Hofstad 2010].
É possível identicar diversos tipos de redes complexas na natureza, também conhecidas por redes reais [Boccaletti et al. 2006]. Entre diversos exemplos destas redes, pode
18
2.2. TEORIA DE GRAFOS
19
ser citado uma grande rede formada pelo sistema nervoso, cujos vértices são células nervosas, ligadas por axônios. As redes complexas ocorrem também em ciências sociais, onde
vértices são indivíduos ou organizações, e as arestas caracterizam a interação social entre
eles. Outra rede complexa existente é a Internet, em que os vértices podem ser sistemas
autônomos ou roteadores e as arestas as conexões físicas entre eles. No nível informacional, pode-se descrever as redes de citações em publicações cientícas, em que os vértices
são os artigos e as arestas são citações a outros artigos; e a WWW, cujos vértices são
documentos HTML conectados por links que apontam a partir de uma página para outra
[Barabási and Albert 1999].
Uma conclusão dos trabalhos empíricos realizados nesta área é que muitas redes reais
compartilham as mesmas características [Hofstad 2010]. Apesar das diferenças inerentes,
a maioria das redes reais são caracterizadas pelas mesmas propriedades topológicas, como,
por exemplo, distribuições de cauda pesada dos graus, comprimento de caminhos relativamente pequenos, elevados coecientes de agrupamento e estrutura das comunidades
[Boccaletti et al. 2006]. Muitas destas redes são livres de escala, o que signica que os
graus dos vértices são invariantes, no sentido de que a distribuição empírica dos graus é
praticamente independente do tamanho do grafo, e a proporção de vértices com grau k
está perto de k −γ para γ > 1, ou seja, muitas redes reais seguem uma lei de potência na
distribuição do grau [Hofstad 2010].
A abordagem do comprimento dos caminhos entre dois vértices pode ser aprofundada
com o estudo de um fenômeno conhecido como small-world, que indica que a partir de um
vértice pode-se alcançar outro vértice na rede com, em média, seis passos [Caldarelli 2007].
Este estudo começou em 1960 por Stanley Milgram. Seu experimento se deu por meio do
envio de uma carta para um destinatário em outra cidade, com o nome do destinatário
e um endereço aleatório da cidade. O experimento revelou que a carta foi repassada em
média seis vezes até chegar ao destino nal [Boccaletti et al. 2006].
2.2
Teoria de Grafos
Tendo em vista que o objetivo desse trabalho é analisar a conectividade de um grafo
da Web brasileira, foi necessário realizar um estudo sobre grafos, que são o modelo mais
empregado para representar redes complexas [Boccaletti et al. 2006].
2.2. TEORIA DE GRAFOS
20
2.2.1 Grafos Não-dirigidos
Matematicamente um grafo não-dirigido pode ser denido por G (V, A), em que V
representa um conjunto de vértices (pontos ou nós) e A representa um conjunto com pares
ordenados de vértices chamados de arestas [Newman 2003]. A visualização gráca de um
grafo é mostrada na Figura 2.1 (a).
Um importante item estudado na teoria de grafos relacionado à conectividade é o grau.
O grau ki de um vértice i é o número de arestas incidentes em i [Diestel 2005].
Além do grau dos vértices, outras métricas são utilizadas para a caracterização da
topologia de um grafo. Uma destas métricas é o componente conectado, que é denido
como um subgrafo máximo em que existe um caminho de cada nó para todos os outros
(isto é, eles são mutuamente alcançáveis) [Newman 2003]. A Figura 2.1 (b) apresenta um
grafo com dez vértices e oito arestas. Esse grafo contém quatro subgrafos.
Figura 2.1: (a) Representação de um grafo não-dirigido. (b) Componentes conectados. (c)
Representação de um grafo dirigido.
2.2.2 Grafos Dirigidos
A representação de algumas redes complexas como as redes de citações de artigos cientícos e a World Wide Web só é possível por grafos dirigidos, também chamados de grafos
direcionados ou dígrafos. Os grafos dirigidos são denidos matematicamente por G (V, A),
em que V representa um conjunto de vértices e A representa um conjunto das chamadas
arestas direcionadas ou arcos [Diestel 2005]. Um exemplo de um grafo dirigido representado
matematicamente é o seguinte: V = {a, b, c, d}, A = {{a, b}, {a, c}, {b, c}, {b, d}, {c, d}}.
Os grafos dirigidos apresentam grande semelhança aos grafos descritos anteriormente, se
2.2. TEORIA DE GRAFOS
21
diferenciando apenas por algumas características. As arestas contidas nestes grafos possuem uma direção, ou seja, uma aresta existente aponta um caminho entre vértices i e j,
não representa um caminho entre j e i. A Figura 2.1 (c) apresenta um grafo dirigido.
A direção do arco no grafo dirigido requer nova denição do grau do vértice. Neste
seguimento existe, para cada vértice, os graus de entrada denotados por kiin , que são o
número de arestas (k in ) apontando para o vértice i em questão. A quantidade de arcos
que têm partida em determinado vértice i é denominada grau de saída do vértice kiout
[Boccaletti et al. 2006]. A soma do grau de entrada e grau de saída resulta no chamado
grau total de um vértice, denotado por kitotal . Em grafos dirigidos, componentes fortemente
conectados (CFCs) são denidos por um conjunto máximo de vértices contidos em V tal
que, para cada par de vértices i e j, existe um caminho dirigido de i para j e um caminho
dirigido de j para i. O grafo dirigido da Figura 2.2 exibe quatro diferentes tipos de
componentes fortemente conectados. Embora este grafo seja conectado, ele não apresenta
um único CFC.
Figura 2.2: Componentes fortemente conectados em um grafo dirigido. Figura extraída de
[Rocha 2007].
Além dos graus de entrada e saída, e o conceito de componente fortemente conectado,
a distância mínima entre dois vértices é outra importante métrica para auxiliar na caracterização da topologia do grafo. O procedimento para calcular a distância entre vértices
também serve de base para se obter outras métricas como a excentricidade, denotada por
(i), que se congura como sendo a maior distância entre um vértice i e um outro vértice
j dentro de um grafo G. A máxima excentricidade dentro de um grafo é chamada de
diâmetro e a mínima é chamada de raio [West 2000]. Das distâncias também é possível se
obter a distância média entre pares de vértices em um grafo dirigido, também chamada de
distância geodésica, esta é representada pela equação:
2.3. O GRAFO DA WEB
22
d=
X
1
dij
n(n − 1)
(2.1)
i≥j
em que n é a quantidade total de vértices e dij é a menor distância entre os vértices i e
j [Newman 2003]. O betweenness também se trata de uma métrica relacionada caminhamento no grafo. Ele é denido pela medida de importância da contagem do número de
menores caminhos de quaisquer vértices j e k passando através de um determinado vértice
i [Boccaletti et al. 2006]. Matematicamente, o betweenness é denotado pela equação:
bi =
X
j,k∈N,j6=k
njk (i)
,
njk
(2.2)
em que njk é o número de menores caminhos que conectam j e k e njk (i) é o número de
menores caminhos que conectam j e k e passam pelo vértice i.
Outra métrica existente é o coeciente de agrupamento. O coeciente de agrupamento de um vértice i, denotado por ci , é a razão entre o número de arestas existentes entre os vizinhos de i e o número máximo de arestas possíveis entre estes vizinhos
[Benevenuto et al. 2011]. O coeciente de agrupamento é representado pela seguinte equação:
ci =
|{ajk : j, k ∈ Ni , ajk ∈ A}|
kitotal (kitotal − 1)
(2.3)
em que ajk vale 1 caso haja uma aresta que conecte os vértices j e k adjacentes de i,
e 0 caso contrário. Nesta equação Ni representa a vizinhança do vértice i, ou seja, seus
vizinhos adjacentes.
O coeciente de agrupamento de um grafo, denotado por hci, é dado pela média de ci
para todos os vértices de G :
C = hci =
1 X
ci
N
(2.4)
iN
2.3
O Grafo da Web
A estrutura da World Wide Web pode ser representada a partir de um grafo dirigido,
em que os vértices são as páginas HTML e as arestas são hyperlinks apontando de uma
2.3. O GRAFO DA WEB
23
página para outra [Boccaletti et al. 2006]. A Figura 2.3 ilustra uma simples representação
do grafo da Web.
O grafo da Web apresenta uma característica marcante.
A distribuição pro-
babilística dos graus tanto de entrada quanto de saída segue uma lei de potência [Barabási et al. 2000a] [Chayes 2013] [Barabási et al. 2000b] [Boccaletti et al. 2006].
Como descrito na Seção 2.1, a equação é descrita por P (k) ∼ k −γ em que k é o grau e γ é
uma constante que varia entre 2 e 3 [Boccaletti et al. 2006]. Alguns estudos já realizados
sobre a Web em diferentes anos encontraram o valor de γ para o grau de entrada em torno de
2,1. Para o grau de saída, γ varia entre 2,3 e 3 [Donato et al. 2007] [Boccaletti et al. 2006]
[Barabási and Albert 1999]. Outra característica marcante na WWW é a dinamicidade da
rede. Isso decorre do fato de que constantemente novas páginas são adicionadas, o que
ocasiona a criação de novos links entre as páginas, além da religação de arestas de páginas
já existentes. Os estudos de [Barabási et al. 2000a] indicam que novas páginas tendem a
se conectar a páginas populares que possuem alto grau de entrada.
Figura 2.3: Representação do grafo da Web.
O estudo de componentes contidos no grafo da Web revela o que alguns autores chamam
de "cyber-comunidades"[Broder et al. 2000]. Estas comunidades são conjuntos contidos no
grafo, que seguem denições já encontradas na literatura, conhecidos como CFC, IN, OUT,
Tubos, Tentáculos e Desconectados. A Figura 2.4 apresenta um grafo com essas denições.
O conjunto CFC é um componente fortemente conectado que ca centralizado no grafo.
O conjunto IN é um componente fraco composto por vértices a partir dos quais é possível
alcançar os vértices do CFC. O componente fraco OUT é onde residem os vértices que
podem ser alcançados a partir de qualquer vértice contido em CFC. O conjunto Tubos é
2.3. O GRAFO DA WEB
24
o conjunto de vértices que conecta vértices de IN diretamente aos de OUT. No conjunto
Tentáculos residem vértices com ligações para vértices desconectados do conjunto CFC. Por
m, o conjunto Desconectado, como sugere o nome é onde residem os vértices desconectados
e pequenos componentes [Donato et al. 2007] [Broder et al. 2000].
Figura 2.4: Componentes em um grafo da Web. Figura adaptada de [Vitali et al. 2011].
Nos estudos realizados por [Broder et al. 2000], foi obtido um grafo de cerca com 200
milhões de vértices e 1,5 bilhão de arestas, gerado a partir de uma coleta no período de
maio a outubro de 1999. Neste grafo foi vericada a quantidade de vértices em cada
componente descrito anteriormente. O componente CFC representou cerca de 56 milhões
de vértices (o maior componente encontrado). No componente IN residiam cerca de 44
milhões de vértices e no componente OUT, também cerca de 44 milhões de vértices. Os
vértices restantes estavam contidos nos conjuntos Tubos/Tentáculos e Desconectados.
Com um grafo de cerca 200 milhões de vértices e 1,4 bilhão de arestas, os resultados dos
estudos de [Donato et al. 2007] apresentaram diferenças do estudo acima. O componente
CFC representou cerca 33% do grafo, o componente IN ocupava cerca de 11% do grafo.
O maior componente contido no grafo foi o OUT, representando cerca de 39% do grafo.
Os componentes Tubos/Tentáculos e Desconectados representaram, respectivamente, 13%
e 4% do grafo.
Outra métrica para ajudar a compreensão da topologia da Web é a distância média entre os vértices (d ), descrita na Seção 2.2.2.
Em um estudo realizado por
[Barabási et al. 2000a], os cálculos de distâncias resultaram que, em média, d vale 18,59,
ou seja, escolhidas duas páginas aleatórias no grafo da Web seriam necessários, em média,
2.3. O GRAFO DA WEB
25
19 passos para alcançar uma página a partir de outra. O mesmo resultado foi encontrado
nos estudos de [Broder et al. 2000], em que a distância média de um vértice i a outro
vértice j é também, em média, 19.
Ao tratar de estudos sobre a Web brasileira, um dos encontrados é o trabalho de
[Veloso et al. 2000]. O estudo apresenta o conteúdo e estrutura da Web brasileira no ano
2000, mais especicamente no mês de abril. Dentre os resultados apresentados, estão os
tipos de documentos encontrados e também suas quantidades, dos quais se destacam os
documentos HTML, PostScript, PDF, MS Word e de texto puro. Ainda neste trabalhos
são exibidos os tipos e quantidade de Domínios de Primeiro Nível (DPN) encontrados na
coleta. O estudo ainda se estende para identicar quais são os idiomas mais comuns na
Web brasileira. Por m, os autores estimam o tamanho da Web brasileira em relação à
quantidade de páginas. Porém, o único resultado do trabalho de Veloso que se assemelha
com o nosso foi a identicação da quantidade média de hyperlinks por página visitada, do
qual foi encontrado o valor 6,74. Em nosso trabalho representamos este valor como grau
médio dos vértices.
O outro estudo encontrado sobre a Web brasileira é o trabalho de [Modesto et al. 2005].
Nesse estudo, os autores apresentam um novo retrato da Web brasileira, demonstrando
ainda seu conteúdo e estrutura, porém com dados de uma coleta mais atualizada, coletada
em março de 2005. Para este trabalho foram buscados praticamente os mesmos resultados
contidos em [Veloso et al. 2000] com o objetivo visualizar as mudanças na Web em um
período de cinco anos. Nosso trabalho se intercede com este quando os autores apresentam
a estrutura topológica do grafo de seus estudos. Os autores encontraram em seu grafo
o modelo gravata já descrito, em que o componente CFC representa 25,27% do grafo, o
componente IN representa 12,95%, o componente OUT representa 45,33% , o componente
Tentáculos representam 3,87%, o componente Tubos representam 0,23% e o componente
Desconectados representam 12,35% do grafo.
Através da pesquisa bibliográca foi encontrado um trabalho que se assemelha ao de
[Veloso et al. 2000] e [Modesto et al. 2005], porém que realiza um caracterização da Web
portuguesa em [Gomes and Silva 2003]. Neste trabalho autores descrevem detalhes de uma
coleta realizada na Web portuguesa, que se entende por sítios com seu domínio terminado
2.4. REGISTROS DA WEB BRASILEIRA
26
em .pt, pelo crawler Viúva Negra (VN). A coleta resultou em um registrou cerca de 4
milhões de páginas de 131 mil sítios. Os autores constataram que 85% da Web portuguesa
está contida no domínio .pt e que os 15% restantes se tratam de sítios portugueses contidos
em domínios como .com, .net, .org e .tv.
2.4
Registros da Web Brasileira
O alcance do objetivo de se comparar os dados da Web obtidos a partir de uma coleta
por Web crawler, mais especicamente relacionado ao número de sítios por domínio, só é
possível se antes for realizada uma pesquisa de como os sítios estão registrados e distribuídos
no país. Atualmente no Brasil o órgão que regula o registro de domínios se trata do
Registro.br [Registro.br 2013]. O órgão disponibiliza estatísticas que quanticam a Web
Brasileira, estes dados poderão ser comparados com os resultados deste estudo. Até o
presente momento que esta seção é redigida, precisamente no dia 19 de julho de 2013, estão
registrados 3.267.353 domínios, distribuídos em cinco categorias. Na categoria Pessoas
Físicas estão registrados 9.738 domínios, o que representa 0,3% do total. Na categoria
Prossionais Liberais estão registrados 59.570 domínios o que representa 1,82% do total
de domínios. Para a categoria de Pessoas Jurídicas estão registrados 106.373 domínios,
este que representa 3,26% do total. A categoria Universidade, que contém os Domínios de
Primeiro Nível (DPN) .edu.br e br, há 3.596 domínios registrados, que representa 0,11%
do total. Por m, a categoria Genéricos que contém os DPNs .com.br, .net.br, .eco.br
e .emp.br, totalizam 3.088.076 domínios registrados, que representam 94,51% do total.
Dos DNPs, o .com.br representa a maioria dos domínios registrados, contendo 2.973.286
domínios com este DPN, o que representa 91% do total. Especicamente os domínios de
maior frequência e importância da Web são demonstrados na Tabela 2.1 juntamente com
a porcentagem de sites que os possuem.
Dentre os diversos registros de domínios contidos na Web brasileira, há um estudo
relacionado ao domínio .gov.br, mais precisamente o Censo da Web Governamental Brasileira [CGI and NIC 2010]. Este trabalho que mede e acompanha a evolução da Web
brasileira, disponibilizando dados numéricos da Web que são importantes referências para
esta dissertação. Estes dados são a distribuição por estados dos 1.351 domínios registrados
sobre o DPN .gov.br no Registro.br. A Tabela 2.2 apresentação a ocorrência de domínios
2.5. CONSIDERAÇÕES FINAIS
27
Tabela 2.1: Principais domínios da Web brasileira.
Domínios
.com.br
.net.br
.org.br
.blog.br
.edu.br
.gov.br
Porcentagens
91,06%
3,05%
1,45%
0,22%
0,07%
0,04%
Tabela 2.2: Distribuição dos domínios .gov.br por estado.
Estado
Paraná
Governo Federal
São Paulo
Santa Catarina
Minas Gerais
Rio Grande do Sul
Rio de Janeiro
Bahia
Ceará
Espírito Santo
Pernambuco
Mato Grosso do Sul
Goiás
Mato Grosso
Pará
Paraíba
Distrito Federal
Sergipe
Tocantins
Alagoas
Amazonas
Rio Grande do Norte
Rondônia
Piauí
Maranhão
Acre
Amapá
Roraima
Domínio
pr.gov.br
gov.br
sp.gov.br
sc.gov.br
mg.gov.br
rs.gov.br
rj.gov.br
ba.gov.br
ce.gov.br
es.gov.br
pe.gov.br
ms.gov.br
go.gov.br
mt.gov.br
pa.gov.br
pb.gov.br
df.gov.br
se.gov.br
to.gov.br
al.gov.br
am.gov.br
rn.gov.br
ro.gov.br
pi.gov.br
ma.gov.br
ac.gov.br
ap.gov.br
rr.gov.br
% de sites do Censo
17%
14%
14%
7%
7%
5%
5%
4%
3%
2%
2%
2%
2%
2%
2%
2%
1%
1%
1%
1%
1%
1%
1%
1%
1%
0%
0%
0%
.gov.br por estado.
2.5
Considerações Finais
O presente capítulo apresentou um estudo teórico da literatura relacionada a redes
complexas, grafos e Web. Iniciado pelos estudos de redes complexas, foram descritos o
2.5. CONSIDERAÇÕES FINAIS
28
que são e quais os tipos de redes complexas, juntamente com quais as características em
comum entre elas. A seguir, foi realizado um estudo sobre grafos, que são o modelo mais
usado para representar redes complexas em estudos. Ainda sobre grafos foram estudadas
algumas formas de quanticá-los e medi-los. Posteriormente foram realizados estudo sobre
a Web, quais suas características e quais os desaos de estudá-la. Um fato constatado
nesta etapa de estudos relacionados é o surgimento de artigos sobre a Web como um grafo
a partir dos anos de 1999 e 2000. Após este período praticamente nenhum artigo que se
relaciona a conectividade foi encontrado até o ano de 2005 em que surgiram novos trabalhos
relevantes sobre o tema. A partir deste estudo bibliográco foi possível também identicar
a principal diculdade de se analisar a Web, que está relacionada ao grande tamanho desta
rede, uma vez que isto demanda de muitos recursos computacionais. Devido a esta grande
demanda de recursos, estudos da Web são somente realizados a partir de amostas na escala
de milhões e até bilhões de URLs, o que mostra a superioridade de empresas como o Google
que em 2008 mapeara um trilhão de URLs [Alpert and Hajaj 2008].
Capítulo 3
Coleta de Dados e Metodologia
Para compreender os desaos de estudar o grafo da Web, inicialmente foi realizado
um estudo da bibliograa sobre o universo que engloba redes complexas, grafos e o grafo
da Web. A partir deste estudo foi possível dimensionar o tamanho do problema, mais
especicamente, saber qual é a forma mais apropriada para representar a Web nesse estudo,
quais são as principais técnicas para analisá-la e também as diculdades ao manusear e
interpretar dados de tal tamanho.
Os dados que compõem a base de estudo deste trabalho foram obtidos por um Web
crawler chamado Heritrix. Um Web crawler é um software que trabalha como um robô
que percorre a Web a partir de um conjunto de sítios iniciais chamados sementes. A partir
das sementes, são realizadas buscas em profundidade nas URLs descobertas, registrando e
armazenando os dados encontrados em um arquivo.
O arquivo de registros de saída do crawler contém uma série de informações da coleta
que podem ser úteis em vários estudos sobre a Web. Cada linha do arquivo de registros
contém doze campos com informações da coleta, como no exemplo abaixo. Os campos são
separados pelo caractere espaço.
2012-06-22T17:03:11.804Z 400 6089
http://tvmissoes.com.br/fotos/displayimage.php?album=topn&cat=0&pos=1606&lang=chinese_big5 LLLLL
http://tvmissoes.com.br/fotos/displayimage.php?album=topn&cat=0&pos=1606 text/html #014
20120622170303419+7563 sha1:HQMN7Z4Z7GFHBH6O5JTHBAQOUWWBBHGT - -
• Campo 1: representa o timestamp ;
29
3.1. MODELAGEM DOS GRAFOS
30
• Campo 2: código de status do protocolo HTTP;
• Campo 3: tamanho em bytes do arquivo hospedeiro;
• Campo 4: URL descoberta na página;
• Campo 5: código de trilha que mostra o rastro de downloads ;
• Campo 6: URL da página visitada;
• Campo 7: Tipo de documento de acordo com o formato MIME;
• Campo 8: identicador da thread que encontrou a página;
• Campo 9: o timestamp no formato RFC2550/ARC;
• Campo 10: resumo do conteúdo de acordo com o algoritmo SHA-1;
• Campo 11: tag source herdada pela URL;
• Campo 12: coluna para possíveis anotações.
Neste trabalho foram utilizadas duas coletas da Web realizadas pelo laboratório eSPEED do DCC da UFMG, realizada por alguns de seus pesquisadores com quem trabalhamos em cooperação. Ou seja, o processo de coleta não coube a este trabalho. A primeira
coleta utilizada foi iniciada em 9 de dezembro de 2012 e se estendeu até o dia 14 de janeiro
de 2013. Para esta coleta, o Heritrix foi congurado para coletar apenas URLs que tenham
seu domínio de primeiro nível terminado em .br, ou seja, apenas URLs pertinentes à Web
brasileira. A coleta partiu de 6.217 sementes e gerou um arquivo de log de 93,8 GBytes
que totalizou 327.370.153 de linhas de registro. A segunda coleta utilizada neste estudo foi
realizada durante o mês de agosto de 2013 e se concentrou apenas na Web governamental
brasileira, ou seja, sítios com o domínio de primeiro nível .gov.br. Esta coleta partiu de
1.386 sementes e gerou um log de 69,6 GBytes com 164.627.908 linhas de registro.
3.1
Modelagem dos Grafos
A partir dos registros de coleta do Heritrix é possível modelar um grafo com as informações contidas nele. Mais especicamente o campo 6, que contém a URL da página
visitada, representa o vértice de origem e o campo 4, que contém o link descoberto na
3.1. MODELAGEM DOS GRAFOS
31
Figura 3.1: Etapas da modelagem dos grafos.
página visitada, representa o vértice de destino. A partir destes campos presentes em cada
linha do arquivo de registros, é possível formar uma aresta dirigida e a junção de todas as
arestas forma o grafo.
Neste processo de modelagem foram usados apenas os registros que não retornaram
erro ao serem acessados, ou seja, páginas que retornaram os códigos HTTP 2xx e 3xx,
especicamente os códigos entre 200 e 399. A utilização dos registros com apenas as duas
classes de códigos reduziu o arquivo de coleta .br a 260.927.712 linhas, 20,3% a menos
que o arquivo da coleta original. Para o registro da coleta .gov.br, houve uma redução de
15,9%, que gerou um arquivo de 138.366.042 linhas de registro. A partir destas informações
iniciou-se a modelagem do grafo, que foi constituído de oito etapas como mostra a Figura
3.1. A primeira etapa foi iniciada extraindo-se os dois campos já citados do arquivo de
log utilizando comandos da linguagem AWK [GNU 2013]. A linguagem AWK é contida
nativamente em sistemas operacionais Linux e é utilizada processar grandes quantidades
de texto. Após este procedimento obtivemos um arquivo que representa uma lista de arcos
contendo uma URL completa como vértice de origem e outra URL completa como vértice
de destino.
A etapa seguinte no processo de modelagem do grafo foi a extração do sítio destas
3.1. MODELAGEM DOS GRAFOS
32
Tabela 3.1: Extração dos sítios das URLs.
Antes
http://www.cefetmg.br/site/instituicao/
http://tvmissoes.com.br/fotos/displayimage.php
Depois
www.cefetmg.br
tvmissoes.com.br
Tabela 3.2: Distinção entre sítios e subsítios.
sítio
terra.com.br
uol.com.br
subsítio
cifraclub.terra.com.br
pagseguro.uol.com.br
URLs. Este procedimento foi realizado por uma função criada na linguagem C que recebe
as URLs completas e retornam seus sítios. Nesta função são extraídos todos os caracteres
que estão entre as duas barras contidas após o protocolo de acesso e a primeira barra que
simboliza o primeiro diretório do sítio. Um exemplo do resultado deste passo pode ser
visualizado na Tabela 3.1 que apresenta a URL e o sítio extraído.
No processo de extração dos sítios cou considerado que subsítios e sítios seriam considerados vértices distintos no grafo. Esta característica adotada na modelagem foi necessária, pois diferentes subsítios de um mesmo sítio podem ser administrados por diferentes
entidades. A Tabela 3.2 apresenta exemplos de tipos de sítios e subsítios encontrados.
Na terceira etapa é feita uma ordenação dos arcos am de agrupar os arcos iguais,
uma vez que o passo anterior produziu arcos iguais. Esta atividade foi desempenhada pelo
programa sort também contido nativamente no Linux, em que cada aresta dirigida foi
ordenada pelo primeiro e logo após pelo segundo vértice.
Na etapa seguinte do processo de modelagem do grafo foi realizada uma ltragem na
lista de arcos, em que foram removidos e contados os laços encontrados, uma vez que se
objetiva neste estudo vericar a conectividades entre sítios distintos. A extração dos sítios
das URLs no passo anterior ocasionou o surgimento destes laços, pois o que anteriormente
eram URLs distintas, que criavam links dentro de um mesmo sítio, agora são vértices
iguais. A Tabela 3.3 apresenta um exemplo de formação de um laço encontrado após a
extração do sítio.
Nesta mesma etapa também foram removidas e contadas as arestas dirigidas repetidas
que surgiram no passo anterior. Estas arestas surgiram porque páginas diferentes de um
sítio A podem ter links para páginas diferentes de um sítio B, o que produziria, ao reduzir
3.1. MODELAGEM DOS GRAFOS
33
Tabela 3.3: Laços após a extração dos sítios.
Estado
Vértice de Origem
Vértice de Destino
Antes
http://tvmissoes.com.br/fotos/displayimage.php
http://tvmissoes.com.br/robots.txt
Depois
tvmissoes.com.br
tvmissoes.com.br
Tabela 3.4: Arestas repetidas após a extração dos sítios.
Estado
Antes
Depois
Vértice de Origem
http://www.techtudo.com.br/plantao.html
http://www.techtudo.com.br/plantao.html
www.techtudo.com.br
www.techtudo.com.br
Vértice de Destino
http://g1.globo.com/
http://g1.globo.com/economia/
g1.globo.com
g1.globo.com
as URLs para sítios, múltiplas arestas A→B. A Tabela 3.4 apresenta estas diferenças.
Terminadas as ltragens, a lista de arestas contém somente arestas direcionadas distintas.
A Tabela 3.5 exibe um trecho deste arquivo.
A quinta etapa executada na modelagem tem o objetivo de calcular a quantidade de
vértices distintos no grafo. Nesta etapa, um procedimento desenvolvido na linguagem
C adiciona todos os vértices distintos encontrados na lista de arcos em um vetor. Esta
atividade foi necessária para o cálculo da quantidade de vértices no grafo. Para facilitar
a pesquisa neste vetor, que será necessária futuramente, foi realizada uma ordenação do
mesmo utilizando o algoritmo Quicksort no sexto passo.
O sétimo passo consiste em salvar em arquivo os sítios que estão ordenados no vetor,
juntamente com seu índice, fazendo assim um mapeamento do sítio para um respectivo
valor numérico dado pelo índice. O oitavo e último passo constitui em substituir cada sítio
contido na lista de arcos ltrados por seu índice, gerando assim uma lista de arcos somente
com números. Esta tarefa foi desempenhada por uma função construída na linguagem C,
que tem como entrada o vértice desejado e o vetor dos vértices mapeados. Por meio de uma
busca binária no vetor, ele retorna o índice numérico do vértice desejado. A transformação
dos vértices em valores numéricos foi necessária pois, ao carregar o grafo na memória
primária da máquina, que irá realizar as análises, o grafo apenas com índices numérico
consumirá menos espaço.
Ao m do processo de modelagem, os grafos estão representados em disco como uma
lista de arcos em que os vértices são índices numéricos que representam os sítios, todos os
arcos são distintos e não há nenhum laço. Também ao m da modelagem foi possível obter
3.1. MODELAGEM DOS GRAFOS
34
Tabela 3.5: Trecho da lista de arestas do grafo .gov.br.
Vértice de Origem
adapec.to.gov.br
adapec.to.gov.br
adapec.to.gov.br
adapta.inpa.gov.br
adapta.inpa.gov.br
adapta.inpa.gov.br
adapta.inpa.gov.br
adapta.inpa.gov.br
adapta.inpa.gov.br
adema.se.gov.br
adm.balneariopinhal.rs.gov.br
adm.balneariopinhal.rs.gov.br
admin.es.gov.br
administracao.hidrolandia.go.gov.br
administracao.hidrolandia.go.gov.br
administrativo.ages.df.gov.br
admin.prodest.es.gov.br
adm.pmf.sc.gov.br
adm.pmf.sc.gov.br
aebescola.aeb.gov.br
Vértice de Destino
to.gov.br
webmail.adapec.to.gov.br
www.to.gov.br
acta.inpa.gov.br
blog.adapta.inpa.gov.br
insetosaquaticos.inpa.gov.br
rodriguesia.jbrj.gov.br
scielolab.iec.pa.gov.br
www.inpa.gov.br
www.adema.se.gov.br
balneariopinhal.rs.gov.br
radio.balneariopinhal.rs.gov.br
www.meioambiente.es.gov.br
comunicacao.hidrolandia.go.gov.br
www.hidrolandia.go.gov.br
www.distritofederal.df.gov.br
www.prodest.es.gov.br
adm2.pmf.sc.gov.br
portal.pmf.sc.gov.br
www.sjc.sp.gov.br
Tabela 3.6: Números obtidos das modelagens.
Valores
Total de Arcos
Laços
Arcos Repetidos
Sementes
Grafo .br
260.927.712
253.395.811
6.387.326
4.571
Grafo .gov.br
138.366.042
137.180.945
1.138.901
892
valores gerados neste processo. A Tabela 3.6 apresenta o número de total de arcos, o número
de laços, o número de arcos repetidos e o número de sementes. Estes valores encontrados na
modelagem dos grafos tiveram base nas coletas com requisições que retornaram os códigos
HTTP 2xx e 3xx. As dimensões dos grafos dos quais foram realizadas as análises estão
detalhadas na Tabela 3.7.
Tabela 3.7: Dimensões dos grafos de códigos HTTP 2xx e 3xx.
Dimensões
Vértices
Arcos
Grafo .br
519.917
1.140.004
Grafo .gov.br
19.523
45.304
3.2. MÉTODOS DE ANÁLISES DOS GRAFOS
3.2
35
Métodos de Análises dos Grafos
Após o término das modelagens dos grafos foi dado início ao processo de análise dos
mesmos. As análises foram feitas utilizando-se métricas para descrever a conectividade
dos grafos. Inicialmente, foram calculados os graus de entrada e de saída, a frequência
dos graus de entrada e de saída, a distância entre os vértices e os componentes fortemente
conectados.
Todas as métricas foram calculadas por algoritmos implementados em linguagem C.
Neste mesmo software que executa as métricas, os grafos em formato de lista de arestas
dirigidas, que estão armazenados em discos, são lidos e carregados na memória principal
como uma matriz de adjacências. A partir desta matriz o procedimento responsável pelo
cálculo dos graus armazena os graus de entrada e de saída dos vértices em vetores, além
de armazenar estes mesmos graus em um arquivo em disco. A partir dos vetores de graus
de entrada e graus de saída, um procedimento calcula quais são os graus mais frequentes
e os armazena em um arquivo em disco.
O cálculo das distâncias entre quaisquer dois vértices escolhidos aleatoriamente no
grafo é feito através do conhecido algoritmo de Dijkstra [Dijkstra 1959]. Do algoritmo
foi alterada sua saída para que ele gravasse em um arquivo em disco as distâncias que
podem ser percorridas no grafo, juntamente com as quantidades de vértices podem ser
alcançados para cada distância. A identicação dos componentes fortemente conectados
no grafo é realizada por um procedimento que percorre o grafo executando uma busca por
profundidade, marcando os vértices que podem ser alcançados. Neste mesmo procedimento
é realizada uma transposição no grafo e novamente é feita uma busca por profundidade
marcando os vértices que podem ser alcançados. Cada um dos componentes fortemente
conectados são encontrados ao identicar os vértices que possuem as mesmas marcações
nos dois grafos.
No processo de análise também foram calculados alguns dados estatísticos que não são
propriamente métricas de análises de grafos, mas são fundamentais para a identicar a
conectividade em qualquer tipo de rede. Os dados estatísticos que couberam a este estudo
foram a identicação do maior e menor valor nas amostras, média, mediana e coeciente
de variação. Estas estatísticas foram calculadas para os graus de entrada e de saída, e para
3.3. ESTUDOS COM O HTTRACK
36
as distâncias.
No processo de análise também foi usado o software Pajek, um programa desenvolvido
na plataforma Windows para análise, criação e visualização de grandes redes [Pajek 2013].
Inicialmente, a primeira atividade a ser desempenhada para o estudo dos grafos no Pajek
é a adequação de nossos grafos. Até então eles eram representados por uma lista de arcos.
É necessário que os grafos estejam nos moldes do Pajek para servirem como entrada. O
arquivo deve representar o que, no Pajek, se chama network, que deve conter primeiramente
a diretiva "*vertices N", em que N é a quantidade de vértices no grafo. Em seguida deve
ser explicitada a lista de vértices. Para esta tarefa, foram copiados os índices numéricos,
juntamente com os vértices que referenciam do arquivo com os vértices mapeados, gerado
na fase de modelagem, para a network a ser criada no Pajek. Em seguida é o momento
de descrever as conexões da rede. Desta vez a diretiva utilizada é "*Arcslist"que assume
que as arestas serão direcionadas. Para descrever as conexões foi necessário apenas copiar
a lista de arcos para a network, nalizando assim sua criação.
Com os grafos já adequados para serem bases de estudo no Pajek, o primeiro recurso
utilizado do software foi a identicação das estruturas topológicas dos grafos, descritas na
Seção 2.3. Esta tarefa é realizada criando-se de uma Partição no Pajek. Esta partição
é uma forma de destacar os vértices que desempenham a atividade desejada, neste caso,
identicar os grupos contidos no modelo gravata. Também no Pajek foi utilizada a criação
de vetores para o cálculo das métricas coeciente de agrupamento e betweenness. Outra
utilidade do Pajek nesta dissertação foi para validar os resultados das demais métricas que
foram implementadas, a saber, os graus de entrada e de saída, os componentes fortemente
conectados e as distâncias entre vértices. Estas métricas também foram calculadas por
meio da utilização de partições no Pajek.
3.3
Estudos com o HTTrack
No processo de coleta do Heritrix é descoberto um número de páginas muito superior
ao número de páginas processadas. Isto ocorre devido a limites físicos de espaço e processamento. O crawler também pode não repetir a varredura de links já encontrados, isto
ocorre pois este último prioriza mais a descoberta de novas páginas que a forma como as
páginas conhecidas estão conectadas entre si.
3.3. ESTUDOS COM O HTTRACK
37
Tabela 3.8: Sítios do componente fortemente conectado de 5 vértices.
sítios
www.anfac.com.br
www.ibfm.com.br
www.sinfac-ms.com.br
www.sinfaces.com.br
www.sinfacpe.com.br
Com base neste fato descrito, para concluir um dos objetivos deste estudo, que é vericar se uma coleta realizada pelo Heritrix é el a realidade da Web em relação à quantidade
de conexões, foi utilizado o software HTTrack [Roche 2013]. O HTTrack é um software
multiplataforma que realiza uma coleta exaustiva da Web, ou seja, realiza um download
completo das páginas desejadas para um diretório local podendo assim realizar uma navegação oine. Devido à grande necessidade de recursos de rede e armazenamento (disco)
exigidas pelo HTTrack foram coletados apenas os sítios de dois componentes fortemente
conectados encontrados no grafo .br. O primeiro CFC coletado contém cinco vértices e o
segundo contém 69 vértices. Este segundo também se trata do terceiro maior componente
fortemente conectado encontrado no grafo .br. Optamos pela escolha do terceiro maior
CFC, pois os vértices do segundo maior CFC do grafo .br são todos subsítios de um mesmo
sítio.
Esta etapa do estudo foi iniciada ao ser realizada uma alteração no algoritmo de descoberta de componentes fortemente conectados desenvolvido na linguagem C. Este novo
procedimento recebe como parâmetro o índice numérico do primeiro vértice do CFC, valor
já identicado no algoritmo que descobriu os componentes. Ainda neste procedimento é
salvo um arquivo de lista de arestas contendo todas as arestas dirigidas do CFC desejado.
A partir deste arquivo foi construído um código ainda na linguagem C para separar todos
os vértices contidos na lista de arestas e substituí-los pelos sítios dos quais fazem referência.
Os sítios encontrados nos componentes podem ser visualizados nas Tabelas 3.8 e 3.9.
Após o término da separação dos sítios encontrados nos CFCs, as listas foram importadas para o HTTrack, no qual foram realizadas as coletas em separado. O HTTrack é um
software bastante congurável em que é possível fazer diversas modicações nos parâmetros da coleta. Para nossas coletas foram alteradas apenas as taxas máximas de downloads.
O seu valor padrão era de 25 KBytes/s e foi alterada para 250 KBytes/s, am de agilizar
3.3. ESTUDOS COM O HTTRACK
38
Tabela 3.9: Sítios do componente fortemente conectado de 69 vértices.
Sítios
www.agualimpapocos.com.br
www.sub100.com.br
www.aguiaimperial.com.br
www.alcro.com.br
www.andreycavalcanteeserpa.com.br
www.anhangueraconstrutora.com.br
www.aplsoftwaremaringa.com.br
www.arqimoveis.com.br
www.arquiteturamais.com.br
www.beltrameimoveis.com.br
www.cantareirabr.com.br
www.centralsoft.com.br
www.ciamaringa.com.br
www.ciplart.com.br
www.construtoraatenas.com.br
www.construtoracidadeverde.com.br
www.construtoraelohim.com.br
www.construtoraglobal.com.br
www.construtorahabitat.com.br
www.construtoraitaminas.com.br
www.construtoramazzia.com.br
www.construtoraplanespaco.com.br
www.construtorazacarias.com.br
www.continentalsul.com.br
www.dalbosco.com.br
www.depositojapura.com.br
www.depositostaterezinha.com.br
www.eletromaringa.com.br
www.energysol.com.br
www.engeblock.com.br
www.granadoimoveis.com.br
www.granviaveiculos.com.br
www.grupoex.com.br
www.grupotoni.com.br
www.imobiliariacidadeverde.com.br
www.imobiliariafortaleza.com.br
www.imobiliariasucesso.com.br
www.itapavi.com.br
www.krum.com.br
www.maisvisaopaineis.com.br
www.marluc.com.br
www.marmorariacoliseu.com.br
www.menin.com.br
www.merlosimoveis.com.br
www.mitralconstrutora.com.br
www.novaenge.com.br
www.novaluzmga.com.br
www.nucleoimobiliariodetoledo.com.br
www.paranadecor.com.br
www.partilha.com.br
www.pisosecia.com.br
www.prfundacoes.com.br
www.procondomino.com.br
www.quadraconstrutora.com.br
www.ramirez.eng.br
www.raulvieiraimoveis.com.br
www.sandri.com.br
www.scobinengenharia.com.br
www.softwarebymaringa.com.br
www.sumei.com.br
www.techplus.ind.br
www.tgmaq.com.br
www.theodorado.com.br
www.trattomaringa.com.br
www.unicaimoveis.imb.br
www.ventaniamotonautica.com.br
www.verrigalvao.arq.br
www.vidrosmaxtemper.com.br
www.washiempreendimentos.com.br
3.3. ESTUDOS COM O HTTRACK
39
o processo de coleta. Ao m das coletas, para o CFC de cinco vértices os dados foram
coletados em torno de cinco horas, totalizando 602,2 MBytes de espaço em disco. Para o
CFC de 69 sítios, os dados foram coletados em aproximadamente de 16 horas, totalizando
cerca de 3,2 GB de espaço em disco.
Terminadas as coletas foram iniciadas as modelagens dos grafos obtidos. O modelo
do grafo quanto aos tipos de ligações entre vértices e identicação de sítios e subsítios
é o mesmo da modelagem anterior. Entretanto, como as bases dos dados da qual serão
formados os grafos se tratam de diretórios, documentos HTML, imagens, arquivos em
ash entre tantos outros, foi necessária a implementação de um novo programa para a
modelagem. O código que realiza a modelagem foi implementado na linguagem JAVA e
percorre os arquivos do diretório indicado buscando por URLs am de montar uma lista de
arestas. Mais especicamente o algoritmo inicia a leitura dos arquivos de código contidos
no diretório raiz, que é um parâmetro do programa. Em cada arquivo, o algoritmo busca,
a cada linha lida, por hyperlinks que direcionam para outra página. Estes hyperlinks são
identicados por expressões regulares que vericam se a string lida contém alguma tag
HTML utilizada para direcionar a navegação. Caso encontre uma tag do tipo <a href> e
esta não esteja direcionando para uma página do mesmo sítio, é realizada a extração da
URL desta string. O processo de armazenamento da URL encontrada é feito primeiramente
identicando o nome do diretório onde está armazenado o arquivo que contém a URL, o
nome do diretório é o sítio no qual é encontrada a URL. A seguir são inseridos em um
arquivo o nome do diretório juntamente com a URL encontrada, formando assim uma
aresta direcionada. O processo é repetido realizando uma busca recursiva em todos os
diretórios a partir da raiz, e assim, ao nal formando uma lista de arcos.
Ao se gerar a lista de arcos a partir da coleta do HTTrack, os vértices ainda são URLs
e devem ser transformados em números, como na modelagem da coleta do Heritrix. Para
isto foi novamente executado o código feito em linguagem C para a modelagem do grafo
do Heritrix, tendo porém, desta vez, a lista de arcos do HTTrack como entrada para o
algoritmo.
Após a conclusão da modelagem do grafo foi iniciado o trabalho de análise do universo
obtido pelo HTTrack e comparação com o mesmo universo encontrado no grafo gerado a
3.4. COMPARAÇÃO COM ESTATÍSTICAS DA WEB BRASILEIRA
40
Tabela 3.10: Extração do domínio de um sítio.
Antes
www.belohorizonte.mg.gov.br
www.pbh.gov.br
Depois
mg.gov.br
pbh.gov.br
partir do log do Heritrix. Como universo denimos todas as conexões do CFC e também
o primeiro nível de conexões para fora do CFC. Para esta comparação foram calculadas as
métricas de graus de saída e componentes fortemente conectados no algoritmo de análise
já desenvolvido. Somente o grau de saída foi calculado pois como foram coletados somente
os vértices dos CFCs, são desconhecidas as conexões de entrada que não sejam de algum
vértice do componente. Na descoberta do componente fortemente conectado foi comparado
seu resultado com o componente gerado a partir do grafo do Heritrix, com o objetivo de
observar alguma novidade ou mudança nas ligações do componente. Também após a modelagem foi utilizado o software Gephi para representar gracamente os dois componentes
fortemente conectados. O Gephi é um software multiplataforma utilizado para criação e
manipulação de redes de menor escala [Gephi 2008].
3.4
Comparação com Estatísticas da Web Brasileira
Para validar o alcance da coleta do Heritrix, além dos estudos com o HTTrack foi
realizada uma comparação das informações encontrados na coleta com os dados contidos
na pesquisa do Censo do .gov.br [CGI and NIC 2010]. Neste momento do estudo foi
realizada uma separação e extração de todos os domínios distintos encontrados nos sítios
descobertos na coleta da Web governamental brasileira. Nesta fase foi desenvolvido um
código na linguagem C para extrair o domínio juntamente com o domínio de primeiro nível
dos sítios, ou seja, todo conteúdo contido em torno dos dois últimos pontos da cadeia de
caracteres. A Tabela 3.10 exibe o resultado desta extração. Esta extração produz, assim
como na fase da modelagem do grafo, domínios repetidos. Para tanto o algoritmo criado
se encarrega de armazenar apenas domínios únicos.
Ao nalizar os experimentos foram comparadas a quantidade de sítios separados por
estados e também a quantidade total de domínios com os dados contidos no Censo
do .gov.br.
Esta separação ocorreu pela identicação do prexo de cada domínio
e contagem de sítios com o mesmo domínio.
Um exemplo seria a adição do sítio
3.5. CONSIDERAÇÕES FINAIS
41
www.belohorizonte.mg.gov.br que pertence ao domínio mg.gov.br à quantidade sítios
do estado de Minas Gerais. Esta é uma outra forma de vericar se dados coletados por
crawling se aproximam dos dados ociais da Web brasileira.
Atividades semelhantes foram desempenhadas no grafo .br, porém, para este foi realizada uma separação dos sítios por domínios de primeiro nível. Esta separação foi realizada
no software LibreOce Calc em que a lista de sítios descobertos na fase de modelagem
foi tratada como uma planilha. Posteriormente, cada sítio foi agrupado aos demais que
possuem o mesmo DPN em uma planilha a parte para serem contabilizados.
3.5
Considerações Finais
O texto descrito neste capítulo representou toda a metodologia executada para a obtenção dos resultados contidos no próximo capítulo. O trabalho inicia-se pelos estudos
da literatura sobre as formas de se entender, manipular e medir redes, grafos e Web, e
descrevendo como e quando foram realizadas as coletas que são a base dos estudos. Posteriormente são descritas as etapas para a obtenção dos grafos .br e .gov.br a partir de
suas perspectivas coletas, bem como as métricas utilizadas para analisá-los. Por m, são
descritas as etapas utilizadas na validação do estudo a partir de coletas realizadas por Web
crawlers, em nosso caso o Heritrix.
Capítulo 4
Resultados
Esse capítulo apresenta os resultados e análises gerados a partir da metodologia descrita
no Capítulo 3. Para melhor descrição e entendimento do texto, este capítulo foi dividido
em três seções. A Seção 4.1 apresenta os resultados obtidos do grafo .br, a Seção 4.2
apresenta os resultados obtidos do grafo .gov.br e, por m, a Seção 4.3 apresenta uma
comparação dos resultados dos dois grafos.
4.1
Resultados do Grafo .br
Inicialmente, os primeiros resultados obtidos foram os do grafo gerado a partir coleta
.br. Após a execução das etapas da modelagem descritas na Seção 3.1, esta retornou
os valores apresentadas na Tabela 4.1. Ao analisar a Tabela, encontramos o primeiro
indício de como a Web é uma rede pouco conectada, uma vez que do total de 260.927.712
arcos apenas 7.527.330 (arcos únicos e arcos repetidos) são de sítios distintos, ou seja,
aproximadamente 2,9% das conexões. A grande quantidade de conexões restante são laços
(97,1%). Esta grande quantidade de laços surge na fase da modelagem do grafo em que dos
arcos de página para página são transformados em arcos de sítio para sítio como mostra a
Tabela 3.3.
Tabela 4.1: Dados da modelagem do grafo .br.
Dimensões
Vértices
Arcos únicos
Laços
Sementes
Arcos Repetidos
Total de Arcos
42
Grafo .br
519.917
1.140.004
253.395.811
4.571
6.387.326
260.927.712
4.1. RESULTADOS DO GRAFO .BR
43
Com o intuito de vericar quais sítios possuem as maiores quantidades de conexões
internas, foram separados todos os vértices que possuíam laços (self-loops ). A análise
desses resultados sugere que a maior quantidade de conexões contidas na Web são para
páginas do mesmo sítio, uma vez que o número médio de laços por sítio é 487,38, um
valor alto comparado ao número médio arcos entre sítios distintos é de 14,48. Destes dados
também pode ser observado que a quantidade de laços em um vértice pode alcançar valores
altos, que superam inclusive os maiores graus de entrada do grafo. Outra descoberta neste
experimento foi que 24 vértices possuem 5.999 laços, que se trata da maior quantidade de
laços encontrada. Pela quantidade de sítios com o mesmo número de páginas, trabalhamos
com a hipótese, que depois foi avaliada no processo do coletor, de que, por ter um volume
grande de sítios no universo de coleta, o Heritrix realizou o escalonamento particionado
de forma igualitária entre os maiores sítios. Como a Web não pode ser toda coletada, a
coleta foi interrompida depois de um certo período, e no momento da interrupção poderia
ser este o status. A Tabela 4.2 lista esses 24 vértices com mais laços no grafo .br.
No processo de pós-modelagem do grafo foram também computados os arcos que mais
se repetem no grafo, conforme apresentado na Tabela 4.3. É possível identicar que com
os arcos ocorreu a mesma limitação identicada na separação das quantidades de laços.
Todos os 20 arcos mais repetições, possuem seus valores próximos a seis mil. Dentre estes
20 arcos que mais repetiram no grafo também é possível notar que todos são conexões
entre subsítios de um mesmo sítio.
As análises do grafo .br começaram ao serem executadas as métricas descritas na Seção
3.2. As análises foram iniciadas pelos graus de entrada e saída e também as frequências
dos graus dos vértices do grafo .br.
Quanto a análise dos graus, seus dados estatísticos podem ser visualizados detalhadamente na Tabela 4.4.
Destes dados foi possível identicar que o vértice
fotoblog.uol.com.br possui o grau de entrada 2.977, o maior encontrado. Também
foi possível identicar o vértice de maior grau de saída, o vértice www.lyrics.com.br, que
possui o grau 76.351. Em contraposição com os maiores graus apresentados, foram identicados os menores graus tanto de entrada quanto de saída, e este estudo resultou no valor
zero para todos eles. O grau médio de entrada é 2,19 para o grafo .br, este valor repete
4.1. RESULTADOS DO GRAFO .BR
44
Tabela 4.2: Os 24 vértices com mais laços no grafo .br.
Vértice
www.urbanotower.com.br
www.tvclubepe.com.br
www.telelista.com.br
www.sonetos.com.br
www.satoru.com.br
www.safadasgratis.com.br
www.parador12.com.br
www.lojalge.com.br
www.locaralpha.com.br
www.joharc.com.br
www.jacarei.sp.gov.br
www.hospitalunimedcriciuma.com.br
www.gratismusica.com.br
www.ghellere.com.br
www.domangelo.com.br
www.crcgo.org.br
www.companygraf.com.br
www.bazuah.com.br
www.bariguimotos.com.br
reidocrime.rpgonline.com.br
m.vagalume.com.br
bracirurgica.com.br
blogadao.shopping.uol.com.br
adegaparavinho.com.br
para o grau médio de saída, pois a soma de todos graus de entrada é igual a soma de todos
graus de saída. Os dados de graus de entrada mostraram ser mais simétricos que os graus
de saída, isto ocorre devido a mediana dos graus de entrada ter um valor mais próximo
dos graus médios. No cálculo do coeciente de variação (COV) é possível identicar a
diferença nas amostras dos graus que não é identicada na média. O grafo .br apresenta
o coeciente de variação 4,65 para seu grau de entrada, que difere muito do coeciente de
variação do grau de saída, representado pelo valor 55,96.
A Figura 4.1 apresenta um gráco que contrasta o grau de entrada com o grau de
saída dos vértices. Deste gráco é possível identicar vértices com valor alto para os graus
de entrada e de saída, representados pela aglomeração de pontos no centro do gráco.
Também é possível visualizar que a quantidade de vértices que possuem alto grau de saída
e baixo grau de entrada possui uma proporção similar à quantidade de vértices com baixo
grau de saída e alto grau de entrada. Para melhor visualizar os valores dos graus, as
4.1. RESULTADOS DO GRAFO .BR
45
Tabela 4.3: Os 20 arcos com mais repetições no grafo .br.
Arcos
todaoferta.uol.com.br
messenger.todaoferta.uol.com.br
www.papajogos.com.br
img.papajogos.com.br
www.topvideos.xpg.com.br
www.topvideos.com.br
www.sexotropical.com.br
img.sexotropical.com.br
www.imobox.com.br
ph1.imotrix.com.br
imusica.com.br
fotos.imusica.com.br
www.bueni.com.br
i.bueni.com.br
www.paneteria.com.br
media.paneteria.com.br
itaimpaulista.com.br
www.itaimpaulista.com.br
perl.limao.com.br
com.limao.com.br
dicas-l.com.br
www.dicas-l.com.br
www.ogao.com.br
assets-cache02.ogao.com.br
www.submarino.com.br
img.submarino.com.br
faro.com.br
www.faro.com.br
www.carangoweb.com.br
carangoweb.com.br
ibiubi.com.br
img.ibiubi.com.br
www.belladasemana.com.br
ia.bella.com.br
cbb.com.br
legado.cbb.com.br
gengibre.com.br
www.gengibre.com.br
shopping.uol.com.br
image.shopping.uol.com.br
No de repetições
5.998
5.998
5.998
5.996
5.995
5.994
5.994
5.994
5.993
5.993
5.992
5.992
5.992
5991
5.987
5986
5.985
5.984
5.983
5.980
Tabela 4.4: Dados estatísticos sobre os graus do grafo .br.
Métrica
Grau de entrada
Grau de saída
Menor
0
0
Maior
2.977
76.351
Média
2,19
2,19
Mediana
1
0
COV
4,65
55,96
Figuras 4.2(a) e 4.2(b) apresentam, respectivamente, o ranking dos graus de entrada e dos
graus de saída ordenados em ordem decrescente.
A Figura 4.3 apresenta os resultados da execução da métrica da frequência dos graus
de entrada e de saída. Devido à escala logarítmica do gráco para ambos os eixos, os graus
de valor zero foram transformados em 0,1 apenas para título de visualização. Ao analisar o
gráco é possível notar que, com exceção do grau 0 de entrada, os graus decaem como uma
lei de potência, característica comum no grafo da Web [Barabási and Albert 1999]. Ainda
na métrica de frequência dos graus, foram realizados ajustes para calcular a inclinação do
decaimento dos graus e, consequentemente, obter o valor do expoente desta lei de potência.
As Figuras 4.4(a) e 4.4(b) apresentam os grácos ajustados dos graus de entrada e saída,
respectivamente. Para os graus de entrada foi encontrado o exponente 2,24, enquanto para
os graus de saída foi identicado o exponente 1,71, valores próximos, porém os graus de
4.1. RESULTADOS DO GRAFO .BR
46
Figura 4.1: Graus do grafo .br.
(a) Graus de entrada
(b) Graus de saída
Figura 4.2: Ranking dos graus do grafo .br.
saída apresentam um maior decaimento. Este fato identicado no experimento se opõe
aos estudos de [Boccaletti et al. 2006], que identicou um maior decaimento dos graus
de entrada, com o valor do expoente do grau de saída maior que o expoente do grau de
entrada.
Para melhor apresentar estes resultados no contexto da Web, as Tabelas 4.5 e 4.6
apresentam 20 sítios com os maiores graus de entrada e de saída. As Tabelas exibem os
índices dos vértices, os graus, e os sítios que são referenciados pelos índices, respectivamente
4.1. RESULTADOS DO GRAFO .BR
47
Figura 4.3: Frequência dos graus do grafo .br.
(a) Graus de entrada
(b) Graus de saída
Figura 4.4: Ajuste dos graus do grafo .br.
na primeira, segunda e terceira colunas das Tabelas. Foi observado na Tabela dos vértices
com os maiores graus de entrada, que três sítios são blogs especializados em postagem de
fotograas, e também que, dentre os vinte, cinco sítios pertencem ao Google, bem como
quatro sítios que pertencem ao UOL. Na Tabela dos vértices com os maiores graus de saída
foram identicados cinco sítios especializados em realizar algum tipo de busca na Web.
A métrica seguinte a ser calculada foi as distâncias entre quaisquer dois vértices. Como
resultado, esta métrica apresentou que o grafo pode ser todo percorrido com até 26 passos,
4.1. RESULTADOS DO GRAFO .BR
48
Tabela 4.5: Os 20 vértices com os maiores graus de entrada.
Vértice
93.369
175.280
213.001
53.046
74.150
58.163
150.113
282.196
431.211
502.115
355.943
137.776
501.296
178.755
34.281
438.506
185.332
512.686
103.472
358.322
Grau de Entrada
2.977
1.644
1.536
1.495
1.474
1.013
928
803
754
732
720
700
677
660
597
533
514
489
459
442
Sítio
fotoblog.uol.com.br
onsoftware.softonic.com.br
selos.climatempo.com.br
cifraclub.terra.com.br
dplus.softonic.com.br
contador.s12.com.br
maps.google.com.br
www.band.com.br
www.orkut.com.br
www.vagas.com.br
www.ogao.com.br
letras.terra.com.br
www.uol.com.br
pagseguro.uol.com.br
blog.i.uol.com.br
www.peticaopublica.com.br
picasaweb.google.com.br
www.youtube.com.br
groups.google.com.br
www.fotolog.terra.com.br
Tabela 4.6: Os 20 vértices com os maiores graus de saída.
Vértice
403.756
288.565
397.715
93.369
429.609
369.508
18.701
370.040
481.156
481.918
331.130
400.800
364.108
387.486
309.564
351.906
475.924
260.146
126.189
210.005
Grau de Saída
76.351
34.591
22.166
9.706
4.469
4.413
3.988
3.134
3.119
2.834
2.559
1.968
1.613
1.551
1.475
1.389
1.331
1.325
1.288
1.255
Sítio
www.lyrics.com.br
www.blogorama.com.br
www.letrasdemusicas.com.br
fotoblog.uol.com.br
www.olx.com.br
www.guiademidia.com.br
aonde.com.br
www.guis.com.br
www.softonic.com.br
www.somanuncios.com.br
www.dihitt.com.br
www.loja2.com.br
www.gigabusca.com.br
www.janela.com.br
www.cifras.art.br
www.fechoo.com.br
www.shoppinglocaweb.com.br
www.acontecaeventos.com.br
jotabegeme.dihitt.com.br
sao-jose-estado-de-sergipe.somanuncios.com.br
4.1. RESULTADOS DO GRAFO .BR
49
Tabela 4.7: Dados estatísticos das distâncias.
Métrica
Distâncias
Menor
1
Maior
26
Média
7,66
Mediana
7
COV
1,24
ou seja, o diâmetro do grafo. A Tabela 4.7 apresenta dados estatísticos das distâncias de
forma detalhada. Destes dados é possível notar que a distância média percorrida no grafo
é 7,66, um valor que enquadra o grafo no fenômeno small-world descrito na Seção 2.1. Os
valores próximos entre média e mediana apresentam a distribuição dos dados de distâncias
de maneira aproximadamente simétrica, bem como o baixo coeciente de variação indica
a pouca variabilidade nos valores da amostra.
Por m, a última métrica executada no grafo .br foi a descoberta dos componentes
fortemente conectados (CFC). Como resultado da métrica foram obtidos 1.087 CFCs. Os
componentes com suas dimensões estão detalhados da Tabela 4.8. Dentre eles, o maior
CFC descoberto contém a quantidade de vértices na casa dos milhares, 21 CFCs possuem
vértices na casa das dezenas e 1.065 CFCs possuem a quantidade de vértices na casa das
unidades. Os resultados desta métrica também revelam outra característica no grafo da
Web brasileira, como encontrado na literatura. De acordo com os estudos apresentados na
Seção 2.3, no grafo da Web é encontrado um grande componente fortemente conetado e vários outros com um pequeno número de vértices [Broder et al. 2000] [Modesto et al. 2005]
[Donato et al. 2007].
Além das métricas executadas no grafo .br, cujos resultados auxiliam a análise da conectividade da Web brasileira, no grafo também foram separados os vértices por domínios
para obter suas porcentagens. Esta tarefa reduziu o número de elementos que serão comparados com dados divulgados pelo Registro.br [Registro.br 2013]. A extração dos domínios
reduziu os 519.917 sítios do grafo a 253.136 domínios distintos, esta redução ocorre devido
a remoção dos subsítios que são considerados vértices no grafo. As porcentagens e número
de sítios dos principais domínios são exibidas na Tabela 4.9. Os dados apresentam que a
coleta utilizada nesse estudo contém 7,47% de todos domínios registrados no Brasil, uma
porcentagem considerável. Entretanto, esta porcentagem seria maior se consideramos que
parte dos domínios são registrados apenas para guardar seu nome e não têm páginas com
grande atividade na Web ou então apenas o mantém para respostas de DNS. Os dados
4.1. RESULTADOS DO GRAFO .BR
50
Tabela 4.8: Quantidade de componentes fortemente conectados no grafo .br.
Número de vértices no CFC
57.063
70
69
53
23
21
20
19
18
15
14
13
12
11
10
9
8
7
6
5
4
3
2
Quantidade de CFC
1
1
1
1
1
2
2
1
3
2
1
2
1
1
2
2
6
6
13
15
35
139
849
Tabela 4.9: Dados de domínios por DPN.
DPN
.com.br
.net.br
.org.br
.blog.br
.edu.br
.gov.br
Demais domínios
Total
Registro.br
%
N
91,14% 3.086.226
3,00% 101.748
1,42%
48.220
0,23%
7.639
0,07%
2.473
0,04%
1.361
4,1%
138.498
100% 3.386.165
o
Descobertos
%
N % Descobertos/Registro.br
87,40% 221.263
7,17%
0,48%
1.243
1,22%
5,15% 13.048
27,06%
0,20%
528
6,91%
0,33%
850
34,37%
0,25%
638
46,88%
6,19% 15.566
11,24%
100% 253.136
7,47%
o
também apresentam que as porcentagens entre os Domínios de Primeiro Nível (DNPs) se
mostram não idênticas mas compatíveis, mesmo nossos dados sendo apenas uma amostra
do total de domínios. O domínio .com.br apresenta a maioria dos sítios, seguido pelos demais com valores inferiores. Um fato identicado em nosso estudo é que os DPNs .org.br,
.edu.br e .gov.br apresentaram as maiores porcentagens de domínios descobertos em
relação ao total registrado, se compararmos com os demais DPNs.
4.1. RESULTADOS DO GRAFO .BR
51
Tabela 4.10: Dados estatísticos sobre os graus do CFC do grafo .br.
Métrica
Grau de entrada
Grau de saída
Menor
1
1
Maior
2.975
3.622
Média
7,06
7,06
Mediana
2
2
COV
3,33
4,28
4.1.1 Maior Componente Fortemente Conectado do Grafo .br
A descoberta de um grande CFC e outros com tamanho reduzido já era esperado, uma
vez que essa característica é comum no grafo da Web e muito encontrada na literatura
[Broder et al. 2000] [Modesto et al. 2005]. A partir dos métodos utilizados para descobrir
os CFCs, o maior componente foi extraído e transformado em um grafo a parte para ser
analisado. O subgrafo extraído do grafo principal possui 57.063 vértices e 402.897 arcos.
As análises tiveram início pelo estudo dos graus, em que foram realizados cálculos
estatísticos dos mesmos. Os dados podem ser visualizados na Tabela 4.10. O maior
grau de entrada e o maior grau de saída apresentados na Tabela pertencem ao sítio
fotoblog.uol.com.br. Em comparação com o grafo completo, o sítio citado também
é o vértice de maior grau de entrada, e diminui em dois o seu valor dentro do CFC, o que
indica que dois sítios que se conectam ao fotoblog.uol.com.br estão ausentes no CFC.
Este CFC também apresentou os maiores graus médios, o que congura esse CFC como
o grafo mais conectado estudado nesta dissertação. Diferentemente do grau de entrada,
uma grande redução aconteceu no maior grau de saída (de 76.351 no grafo completo para
3.622). Os menores graus tanto de entrada quanto de saída são 1, isto ocorre devido a
uma das regras que conguram um componente como fortemente conectado, a saber, cada
vértice deve ter no mínimo uma conexão de entrada e uma conexão de saída. O valor da
média dos graus mais que triplicou comparado a média dos graus do grafo completo. Este
aumento ocorreu devido a inexistência de vértices com grau zero na amostra da qual foi
calculada a média. A amostra dos dados dos graus ainda se mostra assimétrica devido ao
baixo valor da mediana comparado à média. Os valores relativamente baixos dos coecientes de variação dos graus de entrada e de saída em relação aos valores do grafo completo
indicam que há menor variação nos valores dos graus na amostra do qual foi calculado.
A Figura 4.5 apresenta um gráco com os graus de entrada em contraste com os graus
de saída. Desta gura visualiza-se que há variabilidade similar entre os graus de entrada
4.1. RESULTADOS DO GRAFO .BR
52
Figura 4.5: Graus do maior CFC do grafo .br.
(a) Graus de entrada
(b) Graus de saída
Figura 4.6: Rank dos graus do CFC do grafo .br.
e saída de um vértice ainda maior que do grafo completo. Também é possível notar que
a quantidade de vértices com alto grau de saída e baixo de entrada é quase simétrica
à quantidade de vértices com alto grau de entrada e baixo grau de saída. Para melhor
visualizar os valores dos graus, as Figuras 4.6(a) e 4.6(b) apresentam respectivamente o
ranking dos graus de entrada e dos graus de saída ordenados em ordem decrescente.
A métrica seguinte calculada, a frequência dos graus, conrma fato anteriormente descrito sobre a similaridade dos graus de entrada e saída. A Figura 4.7 apresenta um gráco,
4.1. RESULTADOS DO GRAFO .BR
53
Figura 4.7: Frequência dos graus do maior CFC.
(a) Graus de entrada
(b) Graus de saída
Figura 4.8: Ajuste dos graus do maior CFC do grafo .br.
com os eixos em escala logarítmica, das frequências dos graus de entrada e saída. O gráco
mostra que as frequências são bastante próximas. Os ajustes feitos nos grácos das Figuras
4.8(a) e 4.8(b) justicam esta proximidade do qual foi encontrado o exponente 1,76 para
o grau de entrada e 1,73 para o grau de saída.
Por m, a última métrica executada foi a distância entre vértices que tem seus dados
estatísticos apresentados detalhadamente na Tabela 4.11. O cálculo retornou que todos os
vértices do CFC podem ser alcançados com até 25 passos, ou seja, o diâmetro do componente. Este valor representa um a menos que o diâmetro do grafo completo, mostrando
4.1. RESULTADOS DO GRAFO .BR
54
Tabela 4.11: Dados estatísticos das distâncias do CFC.
Métrica
Distâncias
Menor
1
Maior
25
Média
7,21
Mediana
7
COV
1,28
como o CFC tem a dimensão em termos estruturais bem próximo ao grafo completo. Com
base na distância média encontrada, um valor em torno de 6, neste CFC também foi identicado o fenômeno small-world. Os dados de distância também se mostraram simétricos,
devido a proximidade dos valores da média e mediana, e também o baixo coeciente de
variação.
4.1.2 Análise do Grafo .br via Pajek
Após a obtenção dos resultados nos experimentos anteriores, fez-se necessário validar
os resultados do algoritmo desenvolvido para análises. Para validar estes resultados foi utilizado o Pajek (palavra eslovena para Aranha), um programa da plataforma Windows para
análise, criação e visualização de grandes redes. Ele está disponível gratuitamente, para
uso não comercial, no endereço Web (http://pajek.imfm.si/doku.php?id=download).
Como descrito na Seção 3.2, inicialmente foi necessário uma adequação do grafo para
servir como entrada para o Pajek. Ao dar início às análises, a primeira métrica calculada
foi os graus de entrada. Para isto é necessária a criação de uma partição para destacar
os graus de entrada dos vértices. A Figura 4.9 apresenta os vértices com os vinte maiores
graus de entrada, que conferem exatamente com os resultados obtidos em nosso algoritmo,
exibido na Tabela 4.5.
A mesma exatidão foi encontrada nos graus de saída dos vértices. A Figura 4.10 exibe
os vinte vértices com os maiores graus de saída encontrados no Pajek. Podemos notar que
todos os campos são exatamente equivalentes aos da Tabela 4.6, que foi gerada pelo nosso
algoritmo.
Pelo Pajek também foi possível criar uma partição que realizasse a descoberta dos
componentes fortemente conectados. Os mesmos 1.087 CFCs foram encontrados no Pajek,
assim como nas execuções de nosso algoritmo. A Figura 4.11 apresenta os CFCs com pelo
menos dez vértices, exceto o cluster 0 que contém os 459.855 vértices que não pertencem
a nenhum CFC. Os mesmos valores podem ser encontrados na Tabela 4.8, gerada com os
resultados de nosso algoritmo, conrmando novamente delidade de nossos resultados. No
4.1. RESULTADOS DO GRAFO .BR
55
Figura 4.9: Graus de entrada do grafo .br no Pajek.
Figura 4.10: Graus de saída do grafo .br no Pajek.
Pajek também foi calculada a distância entre todos os pares de vértices. A partir desta
métrica foi identicado o valor 26 para o diâmetro do grafo e a distância média de 7,66,
exatamente os mesmos valores encontrados em nosso algoritmo.
Além da validação dos resultados dos experimentos, o Pajek também foi utilizado para
identicar a estrutura topológica do grafo em estudo. Assim como descrito na literatura, o
Pajek encontrou uma estrutura que se assemelha a uma gravata borboleta cujas dimensões
dos conjuntos podem ser visualizadas na Tabela 4.12. Os dados da Tabela mostram que
o componente OUT é o maior e o único que não se conecta a nenhum outro componente.
4.1. RESULTADOS DO GRAFO .BR
56
Figura 4.11: Componentes fortemente conectados do grafo .br no Pajek.
Tabela 4.12: Dimensões do modelo da gravata no grafo .br.
Componente
SCC
IN
OUT
TUBOS
TENTÁCULOS
DESCONECTADOS
No
Grafo .br
de Vértices Percentual
57.063
10,98%
12.829
2,47%
290.646
55,90%
4.943
0,95%
152.250
29,28%
835
0,16%
Este fato, do ponto de vista da rede, ao se percorrer o grafo da Web, assim que este
componente for alcançado, em algum momento a navegação será interrompida por falta
de caminhos a serem percorridos. Outro fato que chamou a atenção foi a quantidade de
vértices em TENTÁCULOS, que são do ponto de vista da navegação da rede, caminhos
que não se conectam a nenhum outro componente da rede. Ou seja, em certo ponto a
navegação também será interrompida por falta de caminhos a serem percorridos, o mesmo
princípio do componente OUT.
O Pajek foi também utilizado para calcular o betweenness. Está avaliação retornou
que o vértice que possui o maior valor de betweenness é o sítio www.uol.com.br com o
valor 0,0102. A Figura 4.12 apresenta os vinte vértices com os maiores valores de between-
ness. Os baixos valores apresentados na gura indicam poucas quantidades de caminhos
que passam pelos vértices, o que novamente sugere a Web como uma rede pouco conectada. Um fato identicado ao analisar a gura é que muitos dos vértices apresentados
4.1. RESULTADOS DO GRAFO .BR
57
Figura 4.12: Os 20 vértices com os maiores valores de betweenness no grafo .br.
nela também estão contidos nas listas dos 20 vértices com maiores graus. Mais especicamente o sítio fotoblog.uol.com.br está contido nas listas de maiores graus de entrada
e de saída. Os sítios www.uol.com.br, maps.google.com.br, pagseguro.uol.com.br,
onsoftware.softonic.com.br e cifraclub.terra.com.br estão contidos apenas na lista
dos vértices dos maiores graus de entrada. Os sítios www.dihitt.com.br e aonde.com.br
estão contidos apenas na lista dos vértices com os maiores graus de saída.
Ao m dos experimentos do grafo .br no Pajek foi calculado o coeciente de agrupamento. Como resultado esta métrica apresentou que, dos 519.917 vértices existentes no
grafo, apenas 1.180 vértices possuem o coeciente de agrupamento de valor 1, ou seja,
existem 1.180 vértices no grafo em que todos os vizinhos adjacentes de cada vértice estão
conectados entre si. Esta métrica ainda resultou no coeciente de agrupamento médio
do grafo, que é representado pelo valor 0,0921. Este baixo valor indica que, em geral,
os vizinhos adjacentes de cada vértice estão pouco conectados entre si, o que contraria
a armação de [Boccaletti et al. 2006], que descreve a Web como uma rede com elevado
coeciente de agrupamento.
4.1.3 Resultados do HTTrack
Como descrito na Seção 3.3, um dos objetivos desse estudo foi vericar se uma coleta
feita pelo Heritrix pode ser considerada representativa em relação à conectividade do grafo
coletado. A partir disso foram coletados no HTTrack os sítios contidos em dois dos com-
4.1. RESULTADOS DO GRAFO .BR
(a) Heritrix
58
(b) HTTrack
Figura 4.13: Universos de 5 vértices.
ponentes fortemente conectados existentes no grafo .br. Por o HTTrack ser um software
que consome muitos recursos de rede e armazenamento, os CFCs escolhidos para a coleta
possuem uma pequena quantidade de vértices, mais precisamente 5 e 69 vértices. Dos grafos modelados a partir das coletas do HTTrack foram calculadas as métricas de graus de
saída e componentes fortemente conectados. Destes dois CFCs foram também observadas
as conexões dos vértices para fora do componente a m de se avaliar se uma coleta do
Heritrix se aproxima da quantidade de hyperlinks coletados no HTTrack.
Os estudos dessa etapa dos experimentos começaram pela identicação do universo que
estão contidos os cinco vértices da Tabela 3.8. Como universo, denimos o conjunto de
todas as conexões dentro do CFC e também o primeiro nível de conexões de saída dos
vértices para fora do componente. Neste universo de 5 vértices do grafo gerado da coleta
da Heritrix foram encontrados 18 arcos como mostra a Figura 4.13(a). No mesmo universo
da coleta do HTTrack foram encontrados 120 arcos que podem ser visualizados na Figura
4.13(b). Os dados apresentados dão os primeiros indícios de quão completa é uma coleta
do HTTrack e também é possível notar o surgimento da árvore geradora mínima na Figura
4.13(a), que é uma das características do processo de crawling adotado na coleta de dados
da Web.
Para comparar os dois subgrafos foram calculados os graus de saída e exibidos na Tabela
4.1. RESULTADOS DO GRAFO .BR
59
Tabela 4.13: Comparação dos graus de saída dos subgrafos de 5 vértices.
Vértice
www.anfac.com.br
www.ibfm.com.br
www.sinfac-ms.com.br
www.sinfaces.com.br
www.sinfacpe.com.br
Grau de saída Heritrix
14
1
1
1
1
Grau de saída HTTrack
51
2
31
25
11
4.13. Os dados apresentados na Tabela para o universo dos 5 sítios, gerado da coleta do
HTTrack, mostram uma quantidade maior de conexões na nova coleta do que o universo
do Heritrix.
O último cálculo realizado neste subgrafo foi a descoberta do componente fortemente
conectado para vericar a semelhança entre os componentes. O componente originado da
coleta do Heritrix possui oito arcos e sua topologia se assemelha a uma estrela, em que
existe um vértice centralizado que possui conexão para os demais e os demais se conectam
a ele, como exibido na Figura 4.14(a). O componente fortemente conectado encontrado
a partir dos dados do HTTrack possui 12 arcos. Esta diferença de quatro arcos a mais
comparado ao anterior são os arcos que conectam os vértices que não são o centro da
estrela como mostra a Figura 4.14(b). A primeira etapa deste estudo com a coleta do
HTTrack conrmou o já esperado, coletas por crawling não coletam boa parte dos links
contidos nas páginas. Neste primeiro caso a maioria dos links não coletados se direcionam
para fora do componente.
Ao término dos estudos do CFC de cinco vértices foram iniciadas as análises com o
subgrafo montado a partir dos 69 vértices apresentados na Tabela 3.9. Os arcos extraídos
do grafo .br que tem como vértice de origem algum dos 69 vértices, formaram um universo
que possui 196 arcos que se conectam conforme mostra a Figura 4.15(a). No entanto, o
grafo dos mesmos 69 vértices encontrados a partir da modelagem dos dados do HTTrack
possui 548 arcos, um valor quase triplicado ao se comparar com os dados gerados pelo
Heritrix. Este grafo é exibido na Figura 4.15(b). Os vértices em destaque nas guras que
apresentam os universos com 5 vértices e também com 69 vértices representam os CFCs
contidos nos mesmos.
O cálculo dos graus de saída dão um segundo indício de quão mais completa é uma
coleta por HTTrack pela quantidade maior de conexões de saída de seus vértices. A Tabela
4.1. RESULTADOS DO GRAFO .BR
(a) Heritrix
60
(b) HTTrack
Figura 4.14: CFCs de 5 vértices.
(a) Heritrix
(b) HTTrack
Figura 4.15: Universos de 69 vértices.
4.14 apresenta os vértices com os maiores graus de saída. Nesta Tabela se destacam os
graus do subgrafo do Heritrix, em que apenas um vértice apresenta o grau diferente de um.
A terceira comparação realizada em relação aos subgrafos gerados a partir dos 69
vértices é a identicação dos componentes fortemente conectados nos mesmos. Após o
cálculo da métrica foi identicado um CFC com os 69 vértices e 136 arcos contido no
universo dos 69 vértices gerado da coleta do Heritrix. Assim como no CFC de 5 vértices
gerados do Heritrix, este também apresenta um formato estrela como exibido na Figura
4.1. RESULTADOS DO GRAFO .BR
61
Tabela 4.14: Os 20 vértices com os maiores graus de saída dos subgrafos de 69 vértices.
Vértice
www.sub100.com.br
www.softwarebymaringa.com.br
www.grupotoni.com.br
www.merlosimoveis.com.br
www.dalbosco.com.br
www.raulvieiraimoveis.com.br
www.partilha.com.br
www.ciplart.com.br
www.theodorado.com.br
www.arqimoveis.com.br
www.washiempreendimentos.com.br
www.vidrosmaxtemper.com.br
www.verrigalvao.arq.br
www.ventaniamotonautica.com.br
www.unicaimoveis.imb.br
www.trattomaringa.com.br
www.tgmaq.com.br
www.techplus.ind.br
www.sumei.com.br
www.scobinengenharia.com.br
Grau de saída Heritrix
116
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
Grau de saída HTTrack
386
54
25
9
4
3
3
3
2
2
1
1
1
1
1
1
1
1
1
1
4.16(a).
A identicação do componente fortemente conectado a partir dos dados gerados pelo
HTTrack apresentou resultados que contrariaram a tendência de que os dados do HTTrack
são mais completos em relação a conectividade. O CFC encontrado possui 60 vértices e
119 arcos exibidos na Figura 4.16(b), dos estudos realizados nesta comparação é a única
vez que os dados do Heritrix se mostraram mais completos. Entretanto, foi realizada uma
pesquisa para descobrir o motivo pelo qual o CFC do HTTrack possui dimensões menores
que o CFC do Heritrix. Do ponto de vista da Web, foram buscadas as conexões entre os
sítios que estavam contidas no CFC do Heritrix e não se encontravam no CFC do HTTrack.
Após esta identicação foi constatado que algumas conexões não existiam mais e um sítio
estava desativado. As demais conexões em falta no CFC ainda existiam no grafo, mas não
se enquadravam mais ao CFC por não existir um caminho direcionado nas duas direções
entre os vértices que as conectam. A Tabela 4.15 apresenta as conexões contidas no CFC
do Heritrix mas inexistentes do CFC do HTTrack.
Neste estudo, envolvendo a comparação dos dados do Heritrix e HTTrack, tam-
4.1. RESULTADOS DO GRAFO .BR
62
(a) Heritrix
(b) HTTrack
Figura 4.16: CFCs de 69 vértices.
Tabela 4.15: Conexões inexistentes no CFC do HTTrack.
Conexão
www.arquiteturamais.com.br
Motivo
www.sub100.com.br
Não existe o link
www.ciplart.com.br
www.sub100.com.br
www.dalbosco.com.br
www.sub100.com.br
Não existe o link
www.maisvisaopaineis.com.br
www.sub100.com.br
Sítio não existe mais
www.nucleoimobiliariodetoledo.com.br
www.sub100.com.br
Não existe o link
www.partilha.com.br
www.sub100.com.br
www.raulvieiraimoveis.com.br
www.sub100.com.br
www.sub100.com.br
www.sub100.com.br
Não existe o link
Não existe o link
Não existe o link
www.arquiteturamais.com.br
Link existe mas está fora do CFC
www.ciplart.com.br
Link existe mas está fora do CFC
www.sub100.com.br
www.dalbosco.com.br
Link existe mas está fora do CFC
www.sub100.com.br
www.maisvisaopaineis.com.br
Link existe mas está fora do CFC
www.sub100.com.br
www.nucleoimobiliariodetoledo.com.br
www.sub100.com.br
www.partilha.com.br
www.sub100.com.br
www.raulvieiraimoveis.com.br
Não existe o link
Link existe mas está fora do CFC
Link existe mas está fora do CFC
www.sub100.com.br
www.unicaimoveis.imb.br
www.sub100.com.br
www.washiempreendimentos.com.br
Link existe mas está fora do CFC
Não existe o link
www.unicaimoveis.imb.br
www.sub100.com.br
Link existe mas está fora do CFC
www.washiempreendimentos.com.br
www.sub100.com.br
Não existe o link
bém foram pesquisadas possíveis conexões que estivessem contidas apenas no CFC
do HTTrack.
Foi descoberto nesta pesquisa que o CFC do HTTrack possui uma
única conexão que é inexistente no CFC do Heritrix.
Foi encontrado um hyper-
link no sítio www.softwarebymaringa.com.br que direcionava a navegação para o sítio
www.centralsoft.com.br.
A conclusão desta etapa dos experimentos de comparação entre os componentes coletados pelo Heritrix e HTTrack apresentou os universos coletados pelo HTTrack com
um número maior de conexões. Apesar da diminuição para 60 vértices do componente
fortemente conectado descoberto no universo dos 69 vértices do HTTrack, esta pode ser
explicada como sendo uma mudança na Web. Em geral, como já descrito o HTTrack coletou um número maior de links nas páginas em que ele visitou, porém a coleta do Heritrix
4.2. RESULTADOS DO GRAFO .GOV.BR
63
Tabela 4.16: Dados da modelagem do grafo .gov.br.
Dimensões
Vértices
Arcos Únicos
Laços
Sementes
Arcos Repetidos
Total de Arcos
Grafo .gov.br
19.523
45.304
137.180.945
892
1.138.901
138.366.042
se apresentou mais completa que o esperado.
4.2
Resultados do Grafo .gov.br
A etapa corrente deste documento apresenta os resultados obtidos nos estudos cujo
objetivo é descobrir a conectividade e a estrutura topológica da Web .gov.br. Estes
estudos foram realizados em um grafo modelado do arquivo de registros de coleta do crawler
Heritrix, conforme descrito detalhadamente na Seção 3.1.
Após nalizada a modelagem, foi descoberto o total de 138.366.042 arcos coletados
pelo Heritrix a partir de 892 URLs sementes. Destes arcos, 137.180.945 são links para o
mesmo sítio, ou seja, os laços, estes que representam 99,14% da conexões coletadas pelo
Heritrix. Os vinte sítios com as maiores quantidade de laços são exibidos na Tabela 4.17.
A quantidade de arcos repetidos descobertos totaliza 1.138.901 arcos, nalizando assim
o grafo com um total de 19.523 vértices e 45.304 arcos únicos. Assim como no estudo
da Web .br, a Web .gov.br apresentou ser uma rede pouco conectada devido à baixa
quantidade de conexões entre sítios distintos. De todos os 138.366.042 arcos encontrados
somente 1.184.205 (únicos e repetidos) são entre vértices distintos, que representa 0,86%
do total de conexões coletadas, um valor muito baixo. Os valores obtidos na modelagem
do grafo .gov.br estão detalhados na Tabela 4.16.
Após o processo de modelagem do grafo .gov.br também foram contabilizados os arcos
descobertos na coleta que mais se repetiram, como exibido na Tabela 4.18. Assim como
no grafo .br a maioria dos arcos são entre subsítios de um mesmo sítio.
O trabalho de análise teve início estudando o grafo dirigido modelado que possui 19.523
vértices e 45.304 arestas dirigidas. Deste gráco foram calculadas as métricas graus de
entrada e graus de saída, frequência dos graus de entrada e saída, distâncias entre vértices
e componentes fortemente conectados.
4.2. RESULTADOS DO GRAFO .GOV.BR
64
Tabela 4.17: Os 20 vértices com mais laços.
Vértice
www.bombeiros-bm.rs.gov.br
cidade.jundiai.sp.gov.br
ww1.alesc.sc.gov.br
www.teixeiradefreitas.ba.gov.br
www.alesc.sc.gov.br
www.al.ba.gov.br
www.portaltransparencia.gov.br
www.arquivoestado.sp.gov.br
www.marialva.pr.gov.br
www.amazonasenergia.gov.br:8080
www.dive.sc.gov.br
portal1.trtrio.gov.br:7777
portal.trtrio.gov.br:7777
transparencia.gov.br
celepar7cta.pr.gov.br
portal2.trtrio.gov.br:7777
participatorio.juventude.gov.br
www.lapa.pr.gov.br
www.cmcm.pr.gov.br
www.camaravotorantim.sp.gov.br:8080
Quantidade de laços
446.423
439.754
434.271
429.488
428.672
428.181
424.553
420.261
420.110
419.426
418.373
416.472
416.088
416.019
415.093
414.833
413.618
410.262
409.013
408.148
Tabela 4.18: Os 20 arcos com mais repetições no grafo .gov.br.
Arcos
www.rs.gov.br
sis2.funasa.gov.br
educadores.diaadia.pr.gov.br
www4.planalto.gov.br
www.paraiba.pb.gov.br
consulta.almg.gov.br
www.rj.gov.br
www1.saude.ba.gov.br
alvaraja.rio.rj.gov.br
www.saude.go.gov.br
cade.gov.br
cmbhweb.cmbh.mg.gov.br
saladeimprensa.ibge.gov.br
www.creci-sc.gov.br
www.e-parana.pr.gov.br
@asms.londrina.pr.gov.br
www.jfrn.gov.br
www.almg.gov.br
www.santosdumont.mg.gov.br
www.transparencia.es.gov.br
www.estado.rs.gov.br
sis.funasa.gov.br
www.educadores.diaadia.pr.gov.br
www.planalto.gov.br
static.paraiba.pb.gov.br
mediaserver.almg.gov.br
download.rj.gov.br
cnes.datasus.gov.br
www.rio.rj.gov.br
www.sgc.goias.gov.br
www.cade.gov.br
www.cmbh.mg.gov.br
www.ibge.gov.br
rep.creci-sc.gov.br
www.video.pr.gov.br
asms.londrina.pr.gov.br
www.in.gov.br
mediaserver.almg.gov.br
www.carmodorioclaro.mg.gov.br
www.protocolo.es.gov.br
No de repetições
31.500
2.1211
19.761
18.708
17.398
16.191
16005
14.933
14.018
13.213
13.093
12.957
12.929
12.540
11.918
11.227
10.826
10.126
9.988
9.754
4.2. RESULTADOS DO GRAFO .GOV.BR
65
Tabela 4.19: Dados estatísticos sobre os graus do grafo .gov.br.
Métrica
Grau de entrada
Grau de saída
Menor
0
0
Maior
343
760
Média
2,32
2,32
Mediana
1
0
COV
3,39
5,16
Iniciando os estudos dos graus do grafo .gov.br, foram calculados os dados estatísticos exibidos na Tabela 4.19. Os dados apresentam o maior grau de entrada que pertence ao sítio www.in.gov.br, e também o maior grau de saída, que pertence ao sítio
www.nre.seed.pr.gov.br. Os menores graus encontrados do grafo apresentam o valor
zero, tanto para entrada quanto para saída. O valor baixo dos graus médios indica a baixa
conectividade do grafo. Os dados dos graus de entrada apresentam maior simetria por
ser a mediana mais próxima da média e menor variabilidade por ter menor coeciente de
variação comparados aos graus de saída.
A Figura 4.17 apresenta um gráco com os eixos em escala logarítmica em que os
graus de entrada são contrastados com os graus de saída. Neste gráco a distribuição
dos pontos é semelhante aos grácos dos estudos anteriores, onde existem vértices que
possuem valores altos para graus de entrada e saída. Também são identicados vértices
que possuem alto grau de entrada e baixo grau de saída, bem como vértices com alto grau
de saída e baixo grau de entrada. Vale lembrar que, em todos os grácos com os eixos em
escala logarítmica do estudo, os vértices que possuem grau zero foram substituídos por 0,1
para serem visualizados. Os graus dos vértices também foram separados por ranking para
a visualização de seus valores em ordem decrescente, como mostram as Figuras 4.18(a) e
4.18(b) que apresentam respectivamente o ranking dos graus de entrada e o ranking dos
graus de saída.
A partir da métrica dos graus também foi possível identicar os sítios que possuem
maiores graus de entrada e graus de saída, apresentados respectivamente nas Tabelas 4.20
e 4.21.
A métrica seguinte calculada foi a frequência dos graus de entrada e de saída. A Figura
4.19 apresenta um gráco com os eixos em escala logarítmica com as frequências dos graus.
Deste é possível visualizar a maior incidência de graus com valores baixos e depois um
decaimento como uma lei de potência, com exceção do grau de entrada zero. Este fato
4.2. RESULTADOS DO GRAFO .GOV.BR
66
Tabela 4.20: Os 20 vértices com os maiores graus de entrada do grafo .gov.br.
Vértice
13.737
5.140
13.554
19.169
17.544
15.696
5.158
9.629
15.963
14.814
16.522
14.821
9.468
10.885
16.142
5.141
11.924
12.243
14.692
19.463
Grau de Entrada
343
287
255
245
242
239
237
213
173
166
159
147
145
143
135
133
127
125
119
110
Sítio
www.in.gov.br
portal.mec.gov.br
www.ibge.gov.br
www2.camara.gov.br
www.senado.gov.br
www.planalto.gov.br
portal.saude.gov.br
www.camara.gov.br
www.portaldatransparencia.gov.br
www.mj.gov.br
www.receita.fazenda.gov.br
www.mma.gov.br
www.brasil.gov.br
www.cgu.gov.br
www.prefeitura.sp.gov.br
portal.mj.gov.br
www.cultura.gov.br
www.diaadiaeducacao.pr.gov.br
www.mds.gov.br
www6.senado.gov.br
Tabela 4.21: Os 20 vértices com os maiores graus de saída do grafo .gov.br.
Vértice
15.150
9.337
10.934
11.395
2.269
5.228
18.763
16.935
8.833
17.651
9.468
17.715
15.490
19.119
16.142
19.201
15.950
15.324
5.158
15.743
Grau de Saída
760
716
535
381
286
230
223
221
212
205
198
195
164
155
138
137
135
133
122
117
Sítio
www.nre.seed.pr.gov.br
www.bibliotecavirtual.sp.gov.br
www.cidadao.pr.gov.br
www.comunidade.diaadia.pr.gov.br
dominios.governoeletronico.gov.br
portaldoprofessor.mec.gov.br
www.turismo.mg.gov.br
www.santur.sc.gov.br
www.almg.gov.br
www.servicos.gov.br
www.brasil.gov.br
www.setur.rs.gov.br
www.pe.gov.br
www1.saude.ba.gov.br
www.prefeitura.sp.gov.br
www2.cultura.gov.br
www.portalconsular.mre.gov.br
www.palmares.gov.br
portal.saude.gov.br
www.pm.pb.gov.br
4.2. RESULTADOS DO GRAFO .GOV.BR
67
Figura 4.17: Graus do grafo.
(a) Graus de entrada
(b) Graus de saída
Figura 4.18: Ranking dos graus do grafo .gov.br.
também ocorreu nos grafos estudados anteriormente. A partir da frequência apresentada
no gráco foram realizados ajustes para se obter o expoente das leis de potência. Para
a distribuição dos graus de entrada foi encontrado o expoente 2,28 mostrado no gráco
da Figura 4.20(a), para a distribuição dos graus de saída foi encontrado o expoente 1,72
exibido na Figura 4.20(b).
A métrica seguinte a ser calculada foi as distâncias entre os vértices. Desta métrica
foi encontrada a distância média 5,91, valor que enquadra a rede da Web governamental
4.2. RESULTADOS DO GRAFO .GOV.BR
68
Figura 4.19: Frequência dos graus de entrada e de saída do grafo .gov.br.
(a) Graus de entrada
(b) Graus de saída
Figura 4.20: Ajuste dos graus do grafo .gov.br.
brasileira no fenômeno small-world. No cálculo também foi encontrada a maior distância
que pode ser percorrida entre dois vértices, valor igual a 19, que representa o diâmetro
do grafo. O diâmetro 19 é um valor alto para um grafo de tais dimensões, este valor
indica a baixa conectividade da rede. Como ocorrido nos resultados dos outros grafos, os
dados de distância são simétricos como mostra a proximidade entre média e mediana e
também pelo baixo coeciente de variação. Dados estatísticos das distâncias são exibidos
detalhadamente na Tabela 4.22.
4.2. RESULTADOS DO GRAFO .GOV.BR
69
Tabela 4.22: Dados estatísticos das distâncias do grafo .gov.br.
Métrica
Distâncias
Menor
1
Maior
19
Média
5,91
Mediana
6
COV
1,16
Tabela 4.23: Quantidade de CFC no grafo .gov.br.
Número de vértices no CFC
5.234
16
9
7
5
4
3
2
Quantidade de CFC
1
1
1
1
2
1
25
168
A última métrica calculada no grafo gerado a partir da Web .gov.br foi a descoberta
de componentes fortemente conectados. Esta métrica resultou na descoberta de 200 CFCs
no grafo, que possuem as dimensões mostradas na Tabela 4.23. Mais uma vez os resultados
obtidos se assemelham com uma característica da Web encontrada na literatura que descreve a grande fragmentação de componentes dentro do grafo da Web [Broder et al. 2000].
Destes componentes, é encontrado um grande componente fortemente conectado e uma
grande quantidade de CFCs com as dimensões bastante reduzidas.
4.2.1 Maior Componente Fortemente Conectado do Grafo .gov.br
Após a análise do grafo completo foi realizada a execução das mesmas métricas no
maior componente fortemente conectado encontrado no grafo. Este CFC possui um total
de 5.234 vértices e 23.255 arestas dirigidas e foi inteiramente extraído do grafo completo
para análises à parte. Iniciando os estudos sobre os graus, foram gerados dados estatísticos
sobre os mesmos, exibidos na Tabela 4.24. Comparando-se esses resultados aos equivalentes
do grafo .gov.br, o valor da média mais que dobrou, este fato apresenta apresenta o CFC
como um grafo mais conectado que o grafo completo. Um dos fatores que inuenciaram este
resultado é a não existência da grandes quantidades de vértices com grau zero, tanto para
entrada quanto para saída, no CFC. O coeciente de variação também apresentou valor
reduzido comparado ao grafo completo, os valores encontrados indicam menor variação
entre os graus dos vértices.
4.2. RESULTADOS DO GRAFO .GOV.BR
70
Tabela 4.24: Dados estatísticos sobre os graus maior do CFC do grafo .gov.br.
Métrica
Grau de entrada
Grau de saída
Menor
1
1
Maior
321
268
Média
4,44
4,44
Mediana
1
2
COV
2,96
2,29
Figura 4.21: Graus do maior CFC do grafo .gov.br.
Deste subgrafo, também nos estudos dos graus de entrada e saída, foi apresentado o
gráco com os eixos em escala logarítmica na Figura 4.21, em que os graus de entrada estão
em contraste com os graus de saída dos vértice. Deste gráco nota-se a mesma distribuição
dos pontos encontrada nos grafos completos .gov.br e .br. Os graus dos vértices também
foram separados por ranking para a visualização de seus valores em ordem decrescente,
como mostram as Figuras 4.22(a) e 4.22(b) que apresentam respectivamente o ranking dos
graus de entrada e o ranking dos graus de saída.
Em seguida, destes graus foram calculadas suas frequências e exibidas na Figura 4.23.
É possível visualizar a maior incidência de graus com valores baixos e depois um decaimento como uma lei de potência, assim como em todos os experimentos anteriores dessa
dissertação. No entanto, para a identicação do expoente das leis de potência foram realizados ajustes nos pontos do gráco. A Figura 4.24(a) apresenta o ajuste dos graus de
entrada do qual foi descoberto o valor 2,01 para o expoente. A Figura 4.24(b) apresenta
4.2. RESULTADOS DO GRAFO .GOV.BR
(a) Graus de entrada
71
(b) Graus de saída
Figura 4.22: Ranking dos graus do CFC do grafo .gov.br.
Figura 4.23: Frequência dos graus do CFC do grafo .gov.br.
o ajuste dos graus de entrada com o expoente 1,79. Um fato observado no estudo é que
em todos os cálculos de graus, a distribuição probabilística destes graus apresentaram uma
lei de potência com expoentes maiores nos graus de entrada que nos graus de saída, em
geral isso indica que existem mais vértices com graus de saída elevados do que com graus
de entrada elevados.
Por m, calculamos as distâncias entre quaisquer dois vértices do subgrafo em estudo.
Os dados descobertos são exibidos na Tabela 4.25. Comparando-as aos dados de distâncias
4.2. RESULTADOS DO GRAFO .GOV.BR
72
(a) Graus de entrada
(b) Graus de saída
Figura 4.24: Ajuste dos graus do maior CFC do grafo .gov.br.
Tabela 4.25: Dados estatísticos das distâncias no maior CFC do grafo .gov.br.
Métrica
Distâncias
Menor
1
Maior
17
Média
5,51
Mediana
5
COV
1,09
obtidas para o grafo .gov.br, os dados mostram pouca diferença, apenas uma redução de
2 no valor do diâmetro e uma pequena redução na média. A pequena diferença encontrada
nos valores da média e do diâmetro sugere que este maior CFC abrange a maior parte do
grafo e que o restante do grafo está desconexo de um grande núcleo ou não é alcançável.
4.2.2 Análise do Grafo .gov.br via Pajek
Após a obtenção dos resultados nos experimentos anteriores, também foi necessário
validar os resultados obtidos para as métricas do grafo .gov.br. Para validar estes resultados, novamente foi utilizado o software Pajek. Como descrito na Seção 3.2, foi criada
uma network de nosso grafo para ser a base dos estudos no Pajek. Ao dar início às análises,
a primeira métrica calculada foi a dos graus de entrada. Para isto é necessária a criação de
uma partição para destacar os graus de entrada dos vértices. A Figura 4.25 apresenta os
vértices com os vinte maiores graus de entrada, que conferem exatamente com os resultados
obtidos em nosso algoritmo, exibidos na Tabela 4.20.
A mesma exatidão foi encontrada nos graus de saída dos vértices. A Figura 4.26 exibe
os vinte vértices com os maiores graus de saída encontrados no Pajek. Desta gura é
possível notar que as colunas Vertex, Cluster e Id são exatamente equivalentes as colunas
Vértice, Graus de saída e Sítio da Tabela 4.21, que foi gerada pelo nosso algoritmo.
4.2. RESULTADOS DO GRAFO .GOV.BR
73
Figura 4.25: Graus de entrada do grafo .gov.br no Pajek.
Figura 4.26: Graus de saída do grafo .gov.br no Pajek.
Pelo Pajek também foi criada uma partição para destacar os clusters que indicam os
componentes fortemente conectados encontrados. Os mesmos 200 CFCs foram encontrados no Pajek, assim como nas execuções de nosso algoritmo. A Figura 4.27 apresenta os
CFCs com pelo menos quatro vértices. Todos componentes exibidos na gura são fortemente conectados, exceto o representado pelo cluster 0, que são os 13.832 vértices que não
pertencem a nenhum CFC. Ao realizar uma comparação, as quantidades de vértices da
coluna Freq da gura são exatamente equivalentes à coluna Número de Vértices no CFC
4.2. RESULTADOS DO GRAFO .GOV.BR
74
Figura 4.27: Componentes fortemente conectados do grafo .gov.br no Pajek.
Tabela 4.26: Dimensões do modelo da gravata no grafo .gov.br.
Componente
SCC
IN
OUT
TUBOS
TENTÁCULOS
DESCONECTADOS
Grafo .gov.br
Quant. Vértices % do Total
5.234 26,8094%
623
3,1911%
12.776 65,4408%
63
0,3227%
761
3,8980%
66
0,3381%
da Tabela 4.23, o que mais uma vez conrma a delidade dos nossos resultados.
No Pajek também foi calculada a distância entre quaisquer dois vértices. Desta métrica
foi identicado o valor 19 para o diâmetro do grafo e distância média de 5,91, exatamente
os mesmos valores encontrados em nosso algoritmo.
Assim como nos experimentos do grafo .br, o Pajek também foi utilizado para identicar a estrutura topológica do grafo .gov.br. Para este grafo também foi encontrada a
estrutura que se assemelha a uma gravata borboleta e as dimensões dos conjuntos podem
ser visualizadas na Tabela 4.26. Os dados da Tabela mostram que o componente OUT é
o maior e o único que não se conecta a nenhum outro componente. Este fato, do ponto de
vista da rede, ao se percorrer o grafo da Web, assim que este componente for alcançado em
algum momento a navegação será interrompida por falta de caminhos a serem percorridos.
O Pajek foi utilizado também para calcular a métrica o betweenness do grafo .gov.br.
O cálculo desta métrica veio por meio da criação de um vetor que armazena o resultado para
cada vértice. A Figura 4.28 apresenta os vinte vértices com os maiores valores de between-
ness. O sítio com o maior valor apresentado se trata do portaldoprofessor.mec.gov.br
com o betweenness 0,0363. Os baixos valores desta métrica, juntamente com o alto valor
do diâmetro do grafo .gov.br, sugerem que o grafo possui pouca variedade de caminhos
a serem percorridos. Assim como ocorre no grafo .br, muitos dos vértices que possuem
4.2. RESULTADOS DO GRAFO .GOV.BR
75
Figura 4.28: Os 20 vértices com os maiores valores de betweenness no grafo .gov.br.
os maiores betweenness também possuem um grande valor nos graus. Mais especicamente os sítios www.brasil.gov.br, portal.saude.gov.br e www.prefeitura.sp.gov.br
estão entre os vinte vértices com os maiores graus de entrada e graus de saída.
Os sítios portal.mec.gov.br, www.cgu.gov.br, www.mma.gov.br, www.ibge.gov.br,
www.portaldatransparencia.gov.br,
www.cultura.gov.br,
www.senado.gov.br e
portal.mj.gov.br estão apenas entre os vinte vértices com os maiores graus
de entrada.
Os sítios portaldoprofessor.mec.gov.br, www.cidadao.pr.gov.br,
www.bibliotecavirtual.sp.gov.br e www.nre.seed.pr.gov.br estão apenas entre os
vinte vértices com os maiores graus de saída.
Ao m dos experimentos do grafo .gov.br no Pajek, foi calculado o coeciente de
agrupamento. Como resultado esta métrica apresentou que dos 19.523 vértices existentes
no grafo, apenas 364 vértices possuem o coeciente de agrupamento de valor 1, ou seja,
existem 364 vértices no grafo em que todos os vizinhos adjacentes de cada vértice estão
conectados entre si. Esta métrica ainda resultou no coeciente de agrupamento médio do
grafo, que é representado pelo valor 0,1530. Este baixo valor indica que de forma geral
os vizinhos adjacentes de cada vértice estão pouco conectados entre si, porém, ainda é
superior aos 0,0921 encontrados no grafo .br.
4.2.3 O Censo da Web Governamental Brasileira
A presente seção deste capítulo de resultados, assim como a Seção 4.1.3, apresenta
estudos realizados para validar os dados obtidos na coleta do Heritrix. Porém, desta vez não
4.3. COMPARAÇÃO ENTRE OS GRAFOS .BR E .GOV.BR
76
se referindo à conectividade e sim à quantidade de vértices descobertos, ou contextualizando
pela Web, a quantidade de sítios e domínios descobertos na coleta do .gov.br. Assim
como descrito na Seção 3.4, nossos resultados foram comparados com os fornecidos pelo
órgão regulador de registro de domínios Registro.br [Registro.br 2013] e com um estudo
do Censo da Web Governamental Brasileira realizado pelo Comitê Gestor da Internet no
Brasil [CGI and NIC 2010].
O primeiro resultado obtido foi a quantidade de domínios encontrados nos sítios coletados pelo Heritrix. Dos 19.523 sítios descobertos no conjunto de dados da coleta .gov.br
foram obtidos 828 domínios distintos contidos nestes sítios. Precisamente no dia 8 de abril
de 2014, momento em que esta seção é redigida, estão registrados 1.361 domínios .gov.br
no Registro.br. Isto representa que a coleta realizada alcançou cerca de 60,8% de domínios
existentes na Web governamental brasileira. Um fato que deve ser considerado destes valores é que, do valor total de domínios registrados, muitos deles podem não estar em uso e
sítios que possuem algum dos domínios podem estar desativados. Isto elevaria a porcentagem de domínios descobertos na coleta ao se levar em conta quantidade real de domínios
em uso. Estes fatos caracterizam a coleta .gov.br como um retrato representativo da Web
governamental.
Posteriormente, foram separados os sítios por estados conforme também descrito na
Seção 3.4. Ao se comparar os resultados obtidos com o Censo de 2010 [CGI and NIC 2010],
foi observado que as porcentagens de sítios por estados obtidos em nossos estudos são
equivalentes aos do Censo de 2010. Das poucas exceções, as diferenças mais chamativas
cam por conta dos sítios do Governo Federal (.gov.br) que em nosso estudo apresentou
uma diferença de 14% para um valor próximo de 17,67% e também do estado do Paraná que
reduziu de 17% para 13,44%. As demais porcentagens apresentaram pequena ou nenhuma
diferença dos estudos de 2010 para o presente estudo. As porcentagens de sítios de todos
os estados estão detalhados na Tabela 4.27.
4.3
Comparação entre os grafos .br e .gov.br
A nalização da descrição dos resultados e análises desenvolvidos nesta dissertação é
feita nesta seção, que apresenta uma síntese dos resultados e uma comparação dos grafos
estudados.
4.3. COMPARAÇÃO ENTRE OS GRAFOS .BR E .GOV.BR
77
Tabela 4.27: Porcentagem de sítios separados por estado.
Estado
Governo Federal
São Paulo
Paraná
Minas Gerais
Rio Grande do Sul
Santa Catarina
Rio de Janeiro
Bahia
Ceará
Espírito Santo
Pernambuco
Mato Grosso do Sul
Goiás
Pará
Distrito Federal
Tocantins
Sergipe
Paraíba
Alagoas
Amazonas
Rio Grande do Norte
Mato Grosso
Rondônia
Maranhão
Piauí
Acre
Roraima
Amapá
% de sítios do Estudo
18%
16%
13%
7%
6%
5%
4%
4%
3%
2%
2%
2%
2%
2%
1%
1%
1%
1%
1%
1%
1%
1%
1%
1%
1%
0%
0%
0%
% de sítios do Censo
14%
14%
17%
7%
5%
7%
5%
4%
3%
2%
2%
2%
2%
2%
1%
1%
1%
2%
1%
1%
1%
2%
1%
1%
1%
0%
0%
0%
Ao se iniciar pelo grafo .br o primeiro dado de diferença evidente é entre a quantidade
de arcos encontrados no log do Heritrix e número de arcos após no grafo após a modelagem. De 260.927.712 de arcos contidos no log, a quantidade foi reduzida a 1.140.004
no grafo modelado. Este dado evidencia o quanto a Web é desconectada quando trata-se
de conexões entre sítios distintos, uma vez que o grafo modelado só contém arcos que
conectam sítios diferentes. Esta baixa conectividade ca mais evidente ao se comparar o
número médio de arcos por vértices, considerando somente vértices distintos obtém-se o
valor 2,19, ao considerar também os laços e arcos repetidos este valor aumenta para 501,86.
Esta grande diferença também se repete no grafo .gov.br, onde a quantidade de arcos no
log é de 138.366.042 e ocorre uma redução maior, pois o grafo modelado contém somente
4.3. COMPARAÇÃO ENTRE OS GRAFOS .BR E .GOV.BR
78
45.304 arcos. A diferença na proporção de arcos por vértices é maior neste grafo da Web
governamental, para o grafo somente com vértices distintos tem-se em média 2,32 arcos
por vértice. Entretanto, se forem adicionados os arcos repetidos e laços a este grafo, a
proporção de arcos por vértices se eleva a 7087,33. Estes fatos citados dão indícios de quão
alta é a conectividade da Web intrasítios, bem como a conectividade da Web é baixa ao
considerarmos sítios distintos.
A partir do processo de modelagem do grafo, também foi possível identicar os sítios que
continham as maiores quantidades de laços, ou seja, as maiores quantidades de hyperlinks
para páginas do mesmo sítio. Este dado apresenta uma grande diferença entre o grafo
.br e grafo .gov.br. No grafo .br foram encontrados 24 sítios, exibidos na Tabela 4.2,
com 5.999 laços, este que é o maior número de laços do grafo. Para o grafo .gov.br
foi descoberto o sítio www.bombeiros-bm.rs.gov.br com a quantidade máxima de laços,
446.423. O maior número de laços em um vértice no grafo .gov.br é alto, maior inclusive
que o maior grau de entrada e maior grau de saída. Este fato apresenta novamente a Web
como uma rede muito conectada apenas entre páginas de um mesmo sítio.
Posteriormente, foram calculadas métricas para investigar a topologia de cada um.
Iniciado pelos graus de entrada, o grafo .br tem o sítio fotoblog.uol.com.br como vértice
de maior grau de entrada, seu grau é 2.977. Quanto ao grafo .gov.br, o sítio que possui
o maior grau de entrada é o www.in.gov.br com o grau 343. Nos dois grafos estes valores
são considerados baixos devido à quantidade de conexões existentes nos grafos.
Em contraste com o grau de entrada, foram calculados os graus de saída nos dois grafos.
Nesta métrica o sítio www.lyrics.com.br representa o vértice de maior grau de saída do
grafo .br, seu grau é 76.351. Para o grafo .gov.br o sítio www.nre.seed.pr.gov.br é o
vértice de maior grau de saída, com o grau 760. Nos dois casos ocorreram que os vértices
possuem maiores conexões de saída do que de entrada nos grafos.
Na literatura é encontrado que a distribuição probabilística dos graus segue uma lei de
potência [Barabási and Albert 1999], [Barabási et al. 2000b]. Em todos os graus dos dois
grafos também foi encontrada uma lei de potência, com os seguinte expoentes:
• Grafo .br
Graus de entrada = 2,24
4.3. COMPARAÇÃO ENTRE OS GRAFOS .BR E .GOV.BR
79
Graus de saída = 1,71
Graus de entrada do maior CFC .br = 1,76
Graus de saída do maior CFC = 1,73
• Grafo .gov.br
Graus de entrada = 2,28
Graus de saída = 1,72
Graus de entrada do maior CFC = 2,01
Graus de saída do maior CFC = 1,79
Para os graus de entrada e saída dos dois grafos, foram calculados alguns dados estatísticos que auxiliam na identicação da estrutura topológica dos grafos. Para contrastar com
os maiores graus já apresentados, foram identicados os menores graus tanto de entrada
quanto de saída, e este estudo resultou no valor zero para todos eles. O grau médio de
entrada é 2,19 para o grafo .br e 2,32 para o grafo .gov.br, que são valores próximos ao
levarmos em consideração a grande diferença nas dimensões dos dois grafos. Estes valores
se repetem para os graus médios de saída, pois a soma de todos graus de entrada é igual a
soma de todos graus de saída. No cálculo do coeciente de variação é possível identicar
uma diferença em relação aos graus que não é identicada na média. O grafo .br possui
em seu grau de entrada o coeciente de variação 4,65, que difere muito do coeciente do
grau de saída, representado pelo valor 55,96. O mesmo não acontece no grafo .gov.br que
apresenta o coeciente de variação 3,39 para o grau de entrada e 5,16 para o grau de saída,
uma diferença relativamente pequena.
Cálculos estatísticos também foram executados para os dados de distâncias. Neste
cálculo foi encontrada a distância um, como menor distância para os dois grafos. A maior
distância que pode ser percorrida no grafo também representa o diâmetro do mesmo e
foram encontrados os valores 26 para o grafo .br e 19 para o grafo .gov.br. As distâncias
médias encontradas, 7,66 para o grafo .br e 5,91 para o grafo .gov.br, ambas apresentam
a propriedade de small-world por serem valores próximos a seis.
4.3. COMPARAÇÃO ENTRE OS GRAFOS .BR E .GOV.BR
80
Nos estudos seguintes foram calculadas as descobertas de componentes fortemente conectados (CFCs) nos dois grafos. No grafo .br foram encontrados 1.087 CFCs e no
grafo .gov.br foram encontrados 200 CFCs. Em ambos os grafos foram encontrados
um grande CFC e o restante são CFCs com um quantidade reduzida de vértices. Esta
é uma característica encontrada na literatura sobre o grafo da Web [Broder et al. 2000],
[Modesto et al. 2005].
Em continuidade nos estudos, o maior CFC foi extraído dos dois grafos para serem
realizadas as mesmas investigações em separado. Iniciado pelas estatísticas dos graus, foi
identicado o menor grau com valor um, tanto para entrada quanto para saída nos dois
grafos. O maior grau de entrada do CFC do grafo .br é representado pelo valor 2.985, com
um valor superior, o maior grau de saída do CFC é 3.622. No CFC do grafo .gov.br o maior
grau de entrada foi superior ao maior grau de saída, a única ocorrência do estudo. Seu
maior valor de entrada é 321 e o maior valor de saída é 268. Os graus médios encontrados
no CFC do grafo .br apresentaram o valor 7,06, que difere muito do grau médio 2,19
encontrado no grafo completo. Para o CFC do grafo .gov.br foram encontrados os graus
médios 4,44, valor maior que os 2,32 encontrados no grafo completo. Este aumento nos
valores médios dos graus dá-se a inexistência de vértices com grau zero na amostra da qual
foi calculada as médias. Ainda com os dados estatísticos dos graus, foram calculados os
coecientes de variação. No CFC do grafo .br foi encontrado o coeciente de variação 3,33
para os graus de entrada e 4,28 para os graus de saída. Estes dados mostram uma pequena
diferença de variação entre si comparado aos coecientes do grafo completo. No CFC do
grafo .gov.br, também com pouca diferença, foi encontrado o coeciente de variação 2,96
para os graus de entrada e 2,29 para os graus de saída.
Para os CFCs também foram calculadas as estatísticas das distâncias. A menor distância encontrada para os dois CFCs foi a distância um. O diâmetro encontrado no CFC
do grafo .br é representado pelo valor 25, um valor a menos do diâmetro do grafo .br
completo. Esta proximidade dos diâmetros pode indicar que o CFC representa a maior
porcentagem de vértices que podem ser alcançados no grafo. O mesmo também acontece
no grafo .gov.br, em que o diâmetro do mesmo é 17, dois a menos que no grafo completo.
Nestes subgrafos as distâncias médias também caracterizam o fenômeno small-world, com
4.3. COMPARAÇÃO ENTRE OS GRAFOS .BR E .GOV.BR
81
a média 7,21 para o CFC do grafo .br e 5,51 para o CFC do grafo .gov.br.
Por m, as últimas investigações realizadas foram a identicação da estrutura topológica, juntamente com os betweenness e coeciente de agrupamento. Na literatura, encontramos nos estudos sobre grafos da Web, o que é chamado de estrutura gravata borboleta
[Broder et al. 2000], [Modesto et al. 2005] e [Donato et al. 2007]. Para a identicação de
tal estrutura, nos dois grafos foi utilizado o software Pajek, do qual serão identicados
os conjuntos CFC, IN, OUT, TENTÁCULOS, TUBOS E DESCONECTADOS. Nos dois
grafos foram identicados porcentagens de vértices semelhantes para todos os conjuntos,
exceto o conjunto TENTÁCULOS do grafo .br. Este conjunto contém quase 30% de vértices do total no grafo .br, em comparação, o grafo .gov.br contém aproximadamente 3,9%
no mesmo conjunto. Do ponto de vista de redes, esta grande quantidade de vértices no
conjunto TENTÁCULOS do grafo .br representa uma grande parte da rede que não pode
alcançar ou não pode ser alcançada por outro componente da rede. Outro fato observado
neste estudo da estrutura do grafo da Web é o quanto o conjunto IN diminuiu a quantidade
de vértices em comparado com os dados contidos na literatura. Nos dois grafos o conjunto
não atingiu 3,2% enquanto em [Donato et al. 2007] este conjunto ocupara cerca de 11%
do grafo.
O betweenness, também calculado no software Pajek, apresentou nos dois grafos valores muito baixos, que não alcançam se quer 0,1. O sítio www.uol.com.br do grafo .br é
o vértice com o maior valor de betweenness, 0,0102. No grafo .gov.br o valor do maior
betweenness é levemente superior e pertence o sítio portaldoprofessor.mec.gov.br com
o betweenness 0,0363. Por m, a última métrica a se comparar é o coeciente de agrupamento, que retornou valores médio baixos para os dois grafos. O coeciente de agrupamento
médio do grafo .br é representado pelo valor 0,0921, bem como o coeciente de agrupamento médio do grafo .gov.br é representado pelo valor 0,1530. Isso indica que o grafo
tem pouco grau de agrupamento, ou seja, os vizinhos adjacentes dos vértices são pouco
conectados entre si.
Esta seção apresentou as considerações sobre os resultados dos experimentos, destacando as principais descobertas realizadas com as análise. O capítulo a seguir apresenta
as conclusões do trabalho e direções para trabalhos futuros.
4.3. COMPARAÇÃO ENTRE OS GRAFOS .BR E .GOV.BR
82
Um fato que deve ser novamente citado refere-se a limitação de estudos de conectividade
da Web utilizando coleta geradas por Web crawlers. É uma característica do crawler não
repetir a varredura de links que referenciam páginas já encontradas, isto ocorre pois o
crawler prioriza mais a descoberta de novas páginas que a forma de como as páginas
conhecidas estão conectadas entre si. Um exemplo prático seria de uma página A que tem
um link para uma página B e uma página C que também tem um link para A. Ao visitar
a página C, o link C→A não será processado pois a página A já foi descoberta. Esta
característica de coletas realizadas por crawling afeta muito o estudo da conectividade da
Web, principalmente no cálculo das métricas de coeciente de agrupamente e betweenness
que muito dependem da conectividade de vértices adjacentes.
Capítulo 5
Conclusão
A presente dissertação apresentou um estudo relacionado à conectividade e à estrutura
topológica da Web brasileira. Os resultados foram obtidos através de métricas calculadas para os diferentes grafos estudados, que são o grafo da Web brasileira (.br), o maior
componente fortemente conectado descoberto neste grafo, o grafo da Web governamental
brasileira, e também seu maior componente fortemente conectado. Os grafos foram modelados a partir de coletas de dados realizadas com o Web Crawler Heritrix. Subgrafos desta
coleta que compõem componentes fortemente conectados do grafo .br foram coletados pelo
software HTTrack, que realiza uma coleta exaustiva da Web, para ns de comparação e
validação da coleta do Heritrix. Com o objetivo de comparar e validar as análises, a partir
dos sítios descobertos nas coletas, foram realizadas diversas comparações com dados do
órgão regulamentador de domínios no Brasil, bem como com dados existentes na bibliograa. As URLs descobertas no grafo .br foram agrupadas por domínios de primeiro nível
e tiveram suas porcentagens comparadas com os dados do Registro.br, bem como os sítios
do grafo .gov.br foram separados por estados e suas porcentagens comparadas com os
dados do Censo da Web Governamental Brasileira.
A conclusão deste trabalho só foi possível após uma série de estudos sobre o universo
que envolve grafos e Web, apresentados no Capítulo 2. Os estudos tiveram início nas
denições de redes complexas, quais são seus tipos e suas características. Posteriormente
foi realizado o estudo sobre grafos, forma utilizada para representar a Web neste estudo.
Dos grafos foram estudadas suas características e as melhores formas de medi-las. Ao m
desta pesquisa bibliográca foi estudado o grafo da Web, seu modelo e conceitos, quais são
suas características, quais os desaos encontrados no estudo e quais os estudos já realizados
83
84
sobre o tema, inclusive da Web brasileira.
Posteriormente foram descritas as etapas desempenhadas que se mostraram necessárias
para a obtenção dos resultados, no Capítulo 3. O capítulo se inicia com uma breve descrição
do Web Crawler que realizou a coleta, bem como a descrição do seu registro de coleta.
Desta coleta foi descrita a forma como são modelados os grafos, assim como as métricas
escolhidas para serem executadas nos grafos e a forma como os resultados foram validados.
Em seguida foram descritas as etapas para a modelagem do grafo a partir da coleta pelo
HTTrack e quais comparações realizadas com o grafo gerado da coleta do Heritrix. Por
m, foi descrito como seriam feitas as comparações entre os resultados obtidos e os dados
contidos na bibliograa.
Para tanto, após a descrição da metodologia o Capítulo 4 apresenta os resultados obtidos divididos basicamente em três partes: resultados do grafo .br, resultados do grafo
.gov.br e uma comparação entre os resultados. Para o grafo .br e seu maior CFC inicialmente são apresentados os resultados obtidos a partir do cálculo das métricas, seguidos
pela validação dos resultados no software Pajek e a comparação com o grafo gerado pela
coleta via HTTrack. A segunda parte do capítulo de resultados se inicia com a apresentação dos resultados da métricas calculadas no grafo .gov.br, seguidos pela validação dos
resultados no software Pajek e a comparação dos dados obtidos com os do Censo da Web
Governamental Brasileira. Por m, o capítulo de resultados é nalizado apresentando uma
comparação entre os principais resultados obtidos nos grafos .br e .gov.br.
Ao m deste estudo, pode-se armar que a proposta deste trabalho de se realizar análise
da conectividade da Web brasileira a partir de subgrafos foi alcançada. Um estudo que se
mostrou promissor justamente por não haver no Brasil nenhum outro estudo sobre a Web
que seja focado na conectividade dos sítios e estrutura topológica da rede.
Por últimas considerações, pode-se dizer que a Web brasileira é uma rede grande,
mutável e pouco conectada em que vértices tendem a se conectar a aqueles que possuem
grandes quantidades de conexões. Só se pode dizer que a Web é muito conectada intrasítios,
pois as maiores quantidades de conexões nela são entre páginas do mesmo sítio, ou seja,
os laços. Em relação as coletas utilizadas no estudo, elas se mostraram representativas
em relação ao número de sítios descobertos. Mesmo com apenas uma amostra do total de
5.1. CONTRIBUIÇÕES
85
sítios existentes na Web brasileira, as porcentagens de domínios destes sítios distribuídos
por DPNs se mostraram equivalentes às porcentagens reais fornecidas pelo Registro.br.
Porém, em relação às ligações entre sítios, pode ser que o conjunto real de conexões entre
sítios distintos seja bem maior.
O modelo de gravata ainda representa a Web como estrutura topológica, porém com
diferenças nas porcentagens dos conjuntos, principalmente no conjunto IN que diminuiu
consideravelmente. Ainda da estrutura topológica foi possível concluir que a Web encontrase mais desconectada que no passado se compararmos com os dados contidos na literatura.
Todas os fatos apresentados nos levam a crer que seria improvável navegar por toda a
Web sem o uso de sistemas de busca e que sem estes sistemas boa parte da Web estaria
inacessível.
5.1
Contribuições
Após a realização de todo o processo descrito anteriormente foi possível identicar as
principais contribuições deste trabalho, que são as descobertas obtidas as partir das análises
dos resultados, mais especicamente:
• Nos graus dos vértices em todos os grafos que foi encontrada a distribuição de lei de potência, fato que já era esperado por ser um característica do
grafo da Web muito descrita na bibliograa [Barabási et al. 2000a], [Chayes 2013],
[Barabási et al. 2000b] e [Boccaletti et al. 2006]. Em todos os grafos estudados nesta
dissertação os expoentes dos graus de entrada são maiores que os expoentes dos graus
de saída, fato até então inexistente na bibliograa. Os expoentes dos graus de entrada
são representados por valores entre 2 e 2,3, exceto o expoente dos graus de entrada
do maior CFC do grafo .br. que tem o valor 1,76, enquanto os expoentes dos graus
de saída variam entre 1,7 e 1,8. Os valores baixos nos expoentes dos graus de saída
indicam maior frequência de vértices com elevados graus de saída em comparação aos
vértices com alto grau de entrada. Das análises dos graus também foi interpretado
que a grande variação dos graus sugere que os vértices se conectam a vértices que já
possuem grandes quantidades de conexões.
• Os graus médios descobertos nos grafos .br e .gov.br, respectivamente represen-
5.1. CONTRIBUIÇÕES
86
tados pelos valores 2,19 e 2,32, são inferiores aos 6,74 encontrados nos estudos de
[Veloso et al. 2000]. Esta que foi a única bibliograa encontrada que deniu numericamente o grau médio.
• A Web se mostrou uma rede bastante fragmentada devido à grande quantidade de
componentes fortemente conectados. Tanto no grafo .br quanto no grafo .gov.br
foram encontrados um grande CFC e numerosos outros com dimensões menores. Os
maiores componentes fortemente conectados dos dois grafos apresentam características semelhantes aos seus grafos completos. Nos grafos e seus maiores CFCs são
encontradas as lei de potência na distribuição da frequência dos graus com expoentes
próximos e valores próximos para o diâmetro. Entretanto, o maior CFC do grafo .br,
que possui o grau médio 7,06, bem como os baixos valores 1,76 e 1,73 dos expoentes
das leis de potência dos graus de entrada e de saída, respectivamente, é o grafo mais
conectado estudado nesta dissertação.
• Todos os grafos estudados se enquadram no fenômeno small-world, com distância
médias que variam entre 5,51 e 7,66, valores menores que os valores próximos de 19
contidos nos estudos de [Barabási et al. 2000a] e [Broder et al. 2000]. Entretanto, os
grafos apresentaram valores elevados de diâmetro que variam entre 19 e 26, bem como
os vértices possuem valores de betweenness baixos que indicam a baixa variedade de
caminhos a serem percorridos nos grafos.
• As estruturas topológicas dos grafos .br e .gov.br ainda são representadas pelo modelo gravata. Porém, o conjunto IN apresenta tamanho pequeno que não representa
sequer 3,2% dos vértices de cada grafo. Isto pode ter ocorrido devido ao crescimento
desordenado da rede desde os estudos apresentados na Seção 2.3. Outro fato descoberto neste estudo foi a grande quantidade de vértices no conjunto TENTÁCULOS,
que representam quase 29,3% do grafo .br. Ao percorrer este trecho do grafo, em
algum momento resultará no m da navegação, pois mais nenhum vértice poderá ser
alcançado.
• O HTTrack realiza uma coleta que representa mais elmente as conexões da Web,
porém, ele é inviável devido ao tempo gasto na coleta e também a limites compu-
5.2. TRABALHOS FUTUROS
87
tacionais. Um exemplo é a execução da coleta dos 69 sites que durou em torno de
18 horas em uma conexão de Internet de 10 Mbit/s e o armazenamento dos sítios
que ocuparam em torno de 3,2 GB de espaço em disco. Apesar da coleta pelo Web
crawler Heritrix ser menos completa que no HTTrack ainda sim a diferença entre
eles foi menor que o esperado, fazendo do Heritrix o software mais recomendado para
realizar grandes coletas para estudos da Web. Este argumento é justicado na coleta
.gov.br por a mesma ter coletado 60,9% dos domínios registrados no Registro.br, o
que torna esta coleta um retrato representativo da Web governamental.
5.2
Trabalhos Futuros
Para trabalhos futuros, sugere-se que sejam realizadas pesquisas complementares à
nossa, que atendam aos seguintes delineamentos:
• Realizar este mesmo estudo acerca da conectividade e estrutura topológica da Web
em uma coleta de universo diferente dos já estudados. Um exemplo seria realizar
os estudos apenas em sítios da Web que pertençam ao domínio de primeiro nível
.blog.br.
• Refazer os estudos da Web brasileira (.br) em coletas de diferentes períodos e realizar
cálculos estatísticos nos resultados com o objetivo de se obter previsões de como
estará estruturada a Web no Futuro.
Referências Bibliográcas
[Alpert and Hajaj 2008] Alpert, J. and Hajaj, N. (2008). We knew the Web was big...
http://googleblog.blogspot.com.br/2008/07/we-knew-web-was-big.html. Acesso
em 29 janeiro 2014.
[Barabási and Albert 1999] Barabási, A. L. and Albert, R. (1999). Emergence of Scaling
in Random Networks. Science, 286(509):111.
[Barabási et al. 2000a] Barabási, A.-L., Albert, R., and Jeong, H. (2000a). Scale-free Characteristics of Random Networks: The Topology of the World-Wide Web. Physica A,
281:6977.
[Barabási et al. 2000b] Barabási, A.-L., Albert, R., Jeong, H., and Bianconi, G. (2000b).
Power-law Distribution of the World Wide Web. Science, 287:12.
[Benevenuto et al. 2011] Benevenuto, F., Almeida, J. M., and Silva, A. S. (2011). Explorando Redes Sociais Online: Da Coleta e Análise de Grandes Bases de Dados às
Aplicações. XXIX Simpósio Brasileiro de Redes de Computadores e Sistemas Distribuí-
dos (SBRC), pages 64102.
[Boccaletti et al. 2006] Boccaletti, S., Latora, V., Moreno, Y., Chavez, M., and Hwang,
D. (2006). Complex Networks: Structure and Dynamics. Physics Reports, 424:175308.
[Broder et al. 2000] Broder, A., Kumar, R., Maghoul, F., Raghavan, P., Rajagopalan, S.,
Stata, R., Tomkins, A., and Wiener, J. (2000). Graph Structure in the Web. Computer
Networks, 33:309320.
[Caldarelli 2007] Caldarelli, G. (2007). Scale-Free Networks: Complex Webs in Nature and
Technology. Oxford University Press.
88
REFERÊNCIAS BIBLIOGRÁFICAS
89
[CGI and NIC 2010] CGI and NIC (2010). Dimensões e Características da Web Brasileira:
Um Estudo do .gov.br.
http://cgi.br/publicacoes/pesquisas/govbr/
cgibr-nicbr-censoweb-govbr-2010.pdf. Acesso em 17 dezembro 2013.
[Chayes 2013] Chayes, J. (2013). Mathematics of Web Science: Structure, Dynamics and
Incentives. Philosophical Transactions of the Royal Society A, 371:14.
[Chung and Lu 2004] Chung, F. and Lu, L. (2004). Complex Graphs and Networks. American Mathematical Society.
[Diestel 2005] Diestel, R. (2005). Graph Theory. Springer-Verlag Heidelberg, New York.
[Dijkstra 1959] Dijkstra, E. W. (1959). A Note on Two Problems in Connection with
Graphs. Numerische Mathematik 1, pages 269271.
[Donato et al. 2007] Donato, D., Laura, L., Leonardi, S., and Millozzi, S. (2007). Graph
Mining: Laws, Generators, and Algorithms. ACM Computing Surveys, 7(1):125.
[Easley and Kleinberg 2010] Easley, D. and Kleinberg, J. (2010). Networks, Crowds, and
Markets: Reasoning About a Highly Connected World. Cambridge University Press.
[Gephi 2008] Gephi (2008). Gephi: An Open Source Graph Visualization and Manipulation Software. https://www.gephi.org. Acesso em 15 agosto 2013.
[GNU 2013] GNU (2013). The GNU Awk User's Guide. http://www.gnu.org/software/
gawk/manual/gawk.html. Acesso em 11 dezembro 2013.
[Gomes and Silva 2003] Gomes, D. and Silva, M. J. (2003). A Characterization of the
Portuguese Web. 3rd ECDL Workshop on Web Archives, pages 114.
[Hofstad 2010] Hofstad, R. V. D. (2010). Random Graphs and Complex Networks. Eindhoven University of Technology, Eindhoven.
[Jack and Binns 2012] Jack, P. and Binns, A. (2012). Heritrix - Internet Archive Webteam Conuence. https://webarchive.jira.com/wiki/display/Heritrix/Heritrix.
Acesso em 31 julho 2013.
REFERÊNCIAS BIBLIOGRÁFICAS
90
[Kumar et al. 2000] Kumar, R., Raghavan, P., Rajagopalan, S., Sivakumar, D., Tompkins,
A., and Upfal, E. (2000). The Web as a Graph. Nineteenth ACM SIGMOD-SIGACT-
SIGART Symposium on Principles of Database Systems, pages 110.
[Modesto et al. 2005] Modesto, M., Álvaro R. Pereira Jr., Ziviani, N., Castillo, C., and
Baeza-Yates, R. (2005). Um Novo Retrato da Web Brasileira. SEMISH, (32):20052017.
[Mohr et al. 2004] Mohr, G., Stack, M., Ranitovic, I., Avery, D., and Kimpton, M. (2004).
An Introduction to Heritrix: An Open Source Archival Quality Web Crawler. Interna-
tional Web Archiving Workshop, (4):115.
[Newman 2003] Newman, M. (2003). The Structure and Function of Complex Networks.
SIAM, (45):167256.
[Newman et al. 2006] Newman, M., Barabási, A.-L., and Watts, D. J. (2006). The Struc-
ture and Dynamics of Networks. Princeton University Press, Princeton - New Jersey.
[Pajek 2013] Pajek (2013). Pajek - Program for Large Network Analysis. http://pajek.
imfm.si/doku.php?id=pajek. Acesso em 12 dezembro 2013.
[Registro.br 2013] Registro.br (2013). Registro de Domínios para a Internet no Brasil.
www.registro.br. Acesso em 20 agosto 2013.
[Rocha 2007] Rocha,
Art
of
D.
Computer
A.
M.
(2007).
Programming.
NazaWiki
-
Kung
Fu
and
the
http://danielamaral.wikidot.com/
paa-2007-1-projeto-1-componentes-fortemente-conectados.
Acesso em 18
junho 2013.
[Roche 2013] Roche, X. (2013). HTTrack Website Copier. http://www.httrack.com/.
Acesso em 16 dezembro 2013.
[Veloso et al. 2000] Veloso, E. A., de Moura, E. S., Golgher, P. B., da Silva, A. S., Almeida,
R. B., Laender, A. H. F., Ribeiro-Neto, B., and Ziviani, N. (2000). Um Retrato da Web
Brasileira. Anais do XXI Seminário Integrado de Hardware e Software (SEMISH 00),
pages 110.
REFERÊNCIAS BIBLIOGRÁFICAS
91
[Vitali et al. 2011] Vitali, S., Glattfelder, J. B., and Battiston, S. (2011). The Network
of Global Corporate Control. http://www.plosone.org/article/info%3Adoi%2F10.
1371%2Fjournal.pone.0025995. Acesso em 19 junho 2013.
[West 2000] West, D. B. (2000). Introduction to Graph Theory. Pearson Education.