INF 1010
Estruturas de Dados Avançadas
A Web como um Grafo
Motivação
•  Modelos baseados em grafos
–  Abstrações de problemas centrais em computação
•  Circuitos integrados, redes de comunicação de dados,…
–  Abstrações para dados e seus relacionamentos
•  A Web, Redes Sociais, Citações bibliográficas,…
•  Problemas novos
–  Alguns grafos são muito grandes!
•  Indexação da Web: vários bilhões de páginas e links
•  Indexação de chamadas telefônicas (quem telefonou para
quem)
•  Redes de sensores
O Grafo da Web
•  Grafo da Web: W=(P,L)
P = Conjunto de nós
= Conjunto de páginas
L = Conjunto de Arcos
= Conjunto de Links
O Grafo da Web
•  Exemplos de problemas sobre o grafo da Web
–  Tamanho
•  Qual o número de nós e arcos?
•  Qual o grau de entrada de uma página, ou seja,
Quantos links apontam para uma página?
–  Conectividade
•  Quais páginas estão linkadas entre si?
•  Qual o número de clicks necessários para passar de
uma página para outra?
–  Aplicações
•  Como pesquisar e minerar dados na Web?
–  Modelos
•  O que o grafo da Web revela sobre processos sociais?
Configuração típica do grafo
(Power Laws)
•  Power Law
–  Uma variável ou distribuição de probabilidade F(x) segue uma power law
se e somente se
F(x) ∝ x-λ
para x > x0
onde λ é chamado de expoente da power law
(Power Laws)
•  Frequência de palavras em textos [Yule, 1944]
•  Análise de citações [Lotka, 1926]
•  Zipf human behavior and the principle of least effort [Zipf,
1947]
•  Cours d’economie politique [Pareto,1897]
•  …
Estatísticas sobre o Grafo da Web
•  Distribuição do grau de entrada (saída) das páginas
–  Segue uma power law
Estatísticas sobre o Grafo da Web
•  Distribuição do tamanho dos componentes
–  Segue uma power law
Aplicações
•  Mineração de dados
–  Comunidades
•  Busca
–  PageRank
Comunidades
•  Comunidades explícitas
–  Redes sociais
–  Mailing lists
•  Comunidades implícitas
–  Exemplo: Empresas de um ramo econômico
–  Há ordens de magnitude mais comunidades implícitas
do que explícitas
–  Definidas por graph cores
–  Exemplo: “Acoplamento Bibliográfico”
•  Páginas co-citadas estão relacionadas
•  Páginas com grande superposição de referências bibliográficas estão
relacionadas
Comunidades
•  Graph Cores
–  Um graph core de um grafo é um subgrafo bipartido completo
K ( 3, 3 )
PageRank
•  PageRank [Page et al. 1999]
–  Criado por Sergey Brin and Larry Page
–  Aproveita a estrutura de hyperlinks da Web:
•  “páginas como mais links apontando para elas são mais importantes”
–  Independe de buscas
–  Sucesso empresarial da Google
PageRank
•  PageRank de uma página p
–  soma dos PageRanks das páginas que apontam para p
dividido pelo número de links de cada página de origem
PageRank
•  Iterações do PageRank página
–  A precisão do PageRank de cada página aumenta
a cada iteração
–  O algoritmo pára após X iterações ou
até que a precisão do Rank seja suficiente
PageRank
•  Convergência e escalabilidade
–  o PageRank converge após um “certo número” de iterações
–  o PageRank escala para um número muito grande de páginas
•  o fator de escalabilidade é aproximadamente linear em log(n)
PageRank
•  Modelo simples
–  Vetor de Origem: representa todas as páginas
–  Vetor de Destino: representa todas as páginas que são referenciadas
–  Matriz de adjacência: representa a estrutura de links
Referência básica
Ravi Kumar , Prabhakar Raghavan , Sridhar Rajagopalan , D.
Sivakumar , Andrew S. Tomkins, Eli Upfal.
“The Web as a graph”.
Proceedings of the Nineteenth ACM SIGMOD-SIGACT-SIGART
Symposium on Principles of Database Systems, Pages 1 – 10.