Webgraph:
algoritmos e métodos
Luciana Salete Buriol
Instituto de Informática,
Universidade Federal do Rio Grande do Sul
(UFRGS)
Slides de Luciana Buriol, Viviane Orengo e Leandro Wives
Webgraph
O Webgraph é o grafo direcionado gerado a partir da
estrutura de links das páginas web.
cada página web é um vértice
cada hyperlink entre páginas é um arco direcionado.
É um grafo de grande dimensão, esparso e desconexo
2/60
Sumário
Motivação e objetivos
Recuperação de Informações
Extração, armazenamento e compactação do
webgraph
Características topológicas e propriedades do
webgraph
Algoritmos de classificação
Algoritmos de aproximação para cálculo de
propriedades do webgraph
Conclusões
3/60
Motivações
Grande dimensão: atualmente possui mais de 24
bilhões de vértices e cerca de 500 bilhões de
arcos
1998: 24 milhões de páginas
1999: 200 milhões
2003: 3.5 bilhões de páginas
2005: 11.5 bilhões de páginas
2006: 24 bilhões de páginas
4/60
Motivações
É a fonte de dados utilizada por ferramentas de busca
para organização e classificação das páginas web
Não se assemelha a outras redes
Diversidade de tópicos, estilos e línguas
Insere uma série de desafios para a área de computação,
possibilitando o surgimento de novas pesquisas e novas
soluções
5/60
Web Crawling
Coleta das páginas web
6/60
Coleta de páginas
A coleta das páginas é realizada por uma máquina de
busca (web crawler)
Faz a busca a partir de um conjunto inicial de páginas
Após extrair a página, identifica seus links
Página web
7/60
Coleta das páginas
É preciso possuir links entrantes para ser coletada
Uma máquina de busca de grande dimensão deve:
Identificar eficientemente páginas já extraídas
Processar em paralelo
Usar banda de rede limitada
Usar a política da “boa educação”
8/60
Estrutura de um crawler
bag  “seed”
while bag  {}
pick p  bag
download p
if p is seen continue
parse p
for each q  outlinks(p) do
if q is new then
bag  bag  {q}
end if
end for
store p
end while
9/60
Estrutura de um crawler
bag  “seed”
while bag  {}
pick p  bag
download p
if p is seen continue
parse p
for each q  outlinks(p) do
if q is new then
bag  bag  {q}
end if
end for
store p
end while
10/60
Coleta das páginas
Problemas práticos:
Tempo x espaço. Ex: 42 milhões de páginas html do domínio
italiano, tendo em média 10 KB por página.
Espaço
 400 GB: 1.33 discos de 300GB
Tempo
 Banda disponível: 2 Mbps
 24 bilhões de páginas: mais de 200  3 pontos de coleta
discos?
 5.5 milhões de páginas por dia
 8 dias executando
11/60
Coleta das páginas
Algumas máquinas de busca:
WIRE: Universidade do Chile
UbiCrawler: Universidade Estadual de Milão;
Nutch (www.nutch.org): USA, implementado em Java, fácil
instalação e utilização, opções para usuário

Maiores
detalhes
http://www.dis.uniroma1.it/buriol/Query.ppt
em
As máquinas de busca comerciais, como Google,
Yahoo, Alta Vista, TodoBR, não são de domínio
público
12/60
Armazenamento do dados
Armazenamento do webgrafo e/ou conteúdo das
páginas?
páginas de diversos formatos: html, txt, doc, pdf, ps, ppt,
etc
Uma página web sem figuras, tem tamanho médio de 10
a 14 Kb
13/60
Recuperação de Informações na
Web
Trata da representação, armazenamento,
organização e acesso à informação
referente às páginas web
R. Baeza-Yates e B. Ribeiro-Neto, Modern
Information Retrieval, 1999,
www2.dcc.ufmg.br/livros/irbook
14/60
Diferenças entre IR e Data Retrieval
Data Retrieval
IR
 Tabelas – dados estruturados
 Documentos – pouca estrutura
 Consultas claras e precisas
expressas em uma linguagem
(SQL)
 Consultas vagas e ambíguas
expressas por meio de palavraschave
 Consultas recuperam todas as
 Consultas não recuperam todos os
tuplas relevantes e todas as tuplas
itens relevantes e nem todos os
recuperadas são relevantes
recuperados são relevantes.
 Todas as tuplas recuperadas são
igualmente relevantes à consulta
 Documentos apresentados em
ordem decrescente de relevância
15/60
O processo de IR
O usuário tipicamente precisa traduzir sua necessidade de
informações em forma de uma consulta (keywords).
Exemplo:
Necessidade de Informação: “Quais as vinícolas do RS que produzem
vinho com a uva Melot?”
Palavras-chave: vinícola RS merlot
16/60
Índice invertido
Índice
Lista de postings
(dicionário)
t1
t2
t3
.
.
.
tn
Em memória,
se possível
17
Normalmente em
disco
17/60
Dicionário de Termos: observações
 Cerca de 100 milhões de palavras!
 Uma estimativa de Grossman e Frieder (2004), 2 milhões de
termos ocupam menos de 32MB (sem compressão)
 Busca binária, com complexidade relativamente baixa:
O (log n); ou

Funções hash com lista de colisão
 Em coleções dinâmicas, usar outras estruturas (TRIE, PAT,
PATRICIA, B-TREES)
18
18/60
Componentes de um sistema de IR
Query
Process Text
Search Index File
Results
Tokenization,
Stop Word Removal,
Stemming &
Term Weighting
Inverted File
Retrieve
Documents
Document
Collection
Produce ranked
list of matches
Ranking Algorithm
Tokenization,
Stop Word Removal,
Stemming &
Term Weighting
19/60
Formato do Webgraph
os nós recebem identificadores
Representação do grafo no formato IPS: lista de
adjacência forward and backward
Dividido em vários arquivos
Tamanho para um conjunto de 200 milhões de
páginas: 15 GB (21 arquivos)
20/60
Link Analysis
Identificação da estrutura topológica do grafo
Cálculo de diversas propriedades do grafo
classificação das páginas web
21/60
Medidas Elementares
Distribuição do indegree e outdegree
É referente ao número de páginas que possuem
grau di, para i=1,2…maxd;
Em geral a distribuição para o webgraph se
apresenta como uma power law: a probabilidade
de um nó possuir degree d é proporcional a 1
d
para algum >1
α
22/60
Distribuição do grau das páginas
23/60
Indegree Distribution
24/60
Outdegree Distribution
25/60
Pagerank Distribution
26/60
Estrutura Macroscópica do
Webgraph
Graph structure in the Web, Broder et al, 2000
27/60
Identificando tentáculos e tubos
28/60
Ilhas: nós restantes
29/60
Medidas da estrutura bow-tie para
wikigraphs
30/60
Biblioteca de Algoritmos para Análise
de grafos de grande dimensão
Desenvolvida no Dipartimento di Informatica e
Sistemistica della Universita’ La Sapienza, Roma, Itália.
Disponível gratuitamente em:
http://www.dis.uniroma1.it/~cosin/html_pages/COSINTools.htm
Documentação em:
http://www.dis.uniroma1.it/~cosin/publications/deliverable
D13.pdf
31/60
Estrutura da Biblioteca
Generators
Measures
Search algorithms
Bow-tie discovering
File converters
Miscellaneous
32/60
Pagerank
As páginas web são apresentadas em ordem
decrescente de seu pagerank
PageRank (PR) é um valor numérico que representa
o quão importante uma página é
Simula o procedimento de um internauta!
Selecione uma página ao acaso (aleatória)
Repita até convergir:
 com probabilidade visita uma página vizinha
 com probabilidade 1-visita uma página vizinha
Em geral 
33/60
PageRank algorithm [BP 97]
Um nível de propagação
Boas paginas devem ser apontadas
por boas paginas!
1/3
1/3
1/3
1
PR  j 
PR i  = ε + 1  ε  
N
j : j i D j 
PageRank: propagação do ranking
35/60
Algoritmo HITS (Kleinberg)
Define:
Autority: páginas com muitos links de entrada
Hub: páginas com muitos links de saída
Inicialize todos pesos com valor 1
Repita ate convergir
– Os hubs recebem os pesos dos authorities
– Os authorities recebem os pesos dos hubs
ai =  h j
hi =  a j
j: j i
Normalize os pesos
j :i  j
Pagerand and HITS Algorithms
ambos são algoritmos iterativos;
cálculo através de um processo algébrico
convergem para o principal autovetor da matriz de links
da do webgraph (matriz de transição de uma cadeia de
Markov)
Algoritmos de Classificação
Outros alg. de classificação: Salsa, ExpertRank, etc.
Avaliação:
Classificação adequada
Cálculo rápido
Estabilidade
Menos susceptível a link spamming
38/60
Algoritmos de memória secundária
O grafo não pode ser carregado em memória principal,
mas armazenado em memória secundária
Algoritmos de memória secundária buscam minimizar o
acesso a disco
Tratando-se de grafos de grande dimensão, quase na
totalidade os algoritmos não são executados em memória
principal
Algoritmos de memória principal, semi-externos e de
memória secundária
39/60
Webgraph do domínio .br
Um novo retrato da web brasileira, M. Modesto, A.
Pereira, N. Ziviani, C. Castillos, R. Baeza-Yates, 2005
(Brasil + Chile)
domínio .br
7.7 milhões de páginas e 126 milhões de links (média de
16 links por página)
40/60
Webgraph do domínio .br
Média de 14,4 Kb por página. Anteriormente era de 9 Kb
(Um retrato da web brasileira, Veloso et al, 2000)
6.4% das páginas são duplicadas
41.7% das páginas são dinâmicas
41/60
Webgraph do domínio .br
Idioma:
português 88,6%
inglês 11,2% e
espanhol 1,16%
Domínio:
 Extensão:
html: 97.92%
pdf: 0.88 %
doc: 0.48%
91.1% com.br
2.7% org.br
0,3% edu.br
42/60
Propriedades Avançadas
Cálculo do número de triângulos do grafo
Cálculo do número de cliques bipartidos de
pequena dimensão
Cálculo do coeficiente de clustering
43/60
Comunidades Web emergentes
Identifique todos cliques bipartidos de dimensão
3 ≤ i ≤ 10
44/60
Bases de Dados Alternativas
Wikipedia www.wikipedia.org:
maior enciclopédia online do mundo
Cada artigo é um nó e cada hyperlink entre artigos é um arco
do grafo
Poucos links externos
Um grafo pode ser gerado para cada língua
Língua Inglesa: 1.250.000 nós (15 arcos por nó)
Possui informação temporal
45/60
Algoritmos de Data Stream
algoritmos de aproximação baseados em
probabilidade
usam memória limitada
Originalmente: dados são lidos uma única vez em
forma de stream
Usam sketch (tipo e numero de funções hash) ou
amostragem (amostra e tamanho da amostragem)
Já propostos: triângulos, cliques bipartidos e coeficiente de
clustering
46/60
Contando o Número de Triângulos de
um Grafo
• Dado um grafo G=(V,E), onde V e o conjunto de
nós e E o conjunto de arcos, considere todas as
triplas de três nós  V;
T0
T1
T2
T3
47/60
Contando o Número de Triângulos
de um Grafo
O que é uma amostra?
Seleciona-se um arco e=(a,b)  E
e um no v  V \ {a,b}, e observa-se a
ocorrência dos outros arcos.
b
?
a
?
v
Contando o Número de Triângulos de
um Grafo
Quantas amostras deste tipo tem um grafo?
• A seguinte propriedade e verdadeira para
qualquer grafo
T1 + 2T2 + 3T3 = |E|(|V|-2)
• Triplas do tipo T0 nao fazem parte desta amostra
Contando o Número de Triângulos
de um Grafo
Os algoritmos podem se beneficiar da estrutura
dos dados
Em geral são polinomiais de baixa ordem
Motivação: necessidade de cálculos on the fly,
cálculo de propriedades do webgraph, redes de
sensores, etc.
Compressão
Níveis de compressão:
Conteúdo da página
URL da página
Webgraph
Usa técnicas especializadas que permitem grande
compressão e rápido acesso aos dados.
51/60
Observações levadas em
consideração para compressão
Consecutividade: muitos links num mesmo web
site são similares lexicograficamente.
Ex:
http://my.sample.com/whitepaper/nodeA.html
http://my.sample.com/whitepaper/nodeB.html
Localidade: cerca de 80% dos links são locais, ou
seja, apontam para páginas no mesmo domínio
Similaridade: Páginas do mesmo domínio tendem
a ter muitos links que apontam para as mesmas
páginas
52/60
Compressão do Webgraph
Melhor compressão = (3.08 + 2.89) bits por
arco: Universidade Estadual de Milão
(http://webgraph.dsi.unimi.it)
Compressão vs. tempo de acesso
Acesso seqüencial e aleatório
56/60
Conclusões
Tópico atual, com muitos trabalhos em aberto e muitas
conferências na área
Deve-se ter uma visão geral, mas especializar-se em
poucos tópicos
Reúne resultados de diversas áreas
Equilíbrio entre teórico e pratico
Os estudos são recentes, de interesse atual, e ainda
carece de muita pesquisa
Muitos problemas de dimensões diversas
57/60
Tópicos de Interesse
GERAL: Algoritmos e Otimização
Algoritmos de memória secundária
propor algoritmos de data stream para o cálculo de
propriedades avançadas
Geração de grafos sintéticos
evolução temporal do grafo: geração de grafos,
propriedades e classificação.
determinar como tais propriedades podem
aprimorar as ferramentas de busca
58/60
Áreas Relacionadas
Algoritmos
Recuperação de informações
Mineração de dados
Banco de dados
Inteligência Artificial
Processamento de Linguagem natural
59/60
Contato
Luciana Salete Buriol
[email protected]
www.inf.ufrgs.br/~buriol
60/60