Mineracao de grafos e redes sociais

1 de Dezembro de 2015

Conceitos basicos sobre grafos

I Vertices, Arestas, Grafo, Dıgrafos

I Vertices com dados, arestas ponderadas

I Algoritmos para encontrar menor caminho

I Caminhos em largura e em profundidade

I Estruturas de dados: listas de arestas, matriz de adjacencias,listas de adjacencias

I Exemplos: WWW, wikis, tweets, media social, redessemanticas, interacoes entre proteınas, redes de regulacao degenes, rede de citacao em literatura cientıfica

Mineracao de grandes grafosI Grafos de redes sociais: alta densidade localI Comunidades e grupos: indivıduos pertencem a varias

comunidadesI Betweenness (centralidade) de arestas: fracao de menores

caminhos que passam pela aresta. Comunidades sao isoladaspor arestas de baixa centralidade

I Algoritmo de Girvan-Newman: calculo eficiente debetweenness

I Comunidades e Grafos BipartidosI Particionamento de grafosI Cortes normalizadosI Matriz de adjacencia, de grau e laplacianaI Metodos espectrais para particionamento de grafosI SimrankI Triangulos em redes sociaisI Encontrando triangulos com MapReduceI Vizinhancas e Fechos Transitivos

GrafoUm conjunto de vertices conectados em pares por arestas.

Porque estudar grafos?

I Muitas aplicacoes

I Abstracao util e interessante

I Muitos algoritmos para processar grafos existentes

I Campo de conhecimento em constante evolucao

2/1

Transporte publico

3/1

Grafo da interacao entre proteınas humanas

I Network graph of the union of all CCSB-HI and LCIinteractins. Towards a proteome-scale map of the humanprotein-protein interaction network. Rual et al., Nature 2005.

4/1

Grafo da interacao de proteınas humanas com doencas

I Interaction network of disease-associated CCSB-HI1proteins.Towards a proteome-scale map of the humanprotein-protein interaction network. Rual et al., Nature 2005.

5/1

Jogos

1

2

3

6

4

5

7

20

13

21

14

15

8

9

10

1112

16

1724

18

19

22

23

30

26

27

28

25

31

32

29

34

33

6/1

Graph structure in the web, Broder et al. (2000)

7/1

Figura: Peter Bearman, James Moody, and Katherine Stovel. Chains ofaffection: The structure of adolescent romantic and sexual networks.American Journal of Sociology, 110(1): 44-99, 2004.

8/1

Fig. 1.—Thenetwork structureof four models of infection

Figura: Peter Bearman, James Moody, and Katherine Stovel. Chains ofaffection: The structure of adolescent romantic and sexual networks.American Journal of Sociology, 110(1): 44-99, 2004.

9/1

Mapa da Internet

10/1

Rede eletrica

Figure 3. Reconstructed outages of 1996 WSCC blackout.

Kim and Obah: Vulnerability Assessment of Power Grid Using Topological Index

11/1

Grafo de terroristas

12/1

I http://thinkprogress.org/world/2014/06/12/

3447800/iraq-syria-chart/

13/1

Outras aplicacoes de grafos

grafo vertice arestacomunicacoes telefone, computadores fibra otica

circuito porta, registrador, processador fiofinancas acoes, cotacoes transacoes

transporte cruzamento, aeroporto rodovia, rota aerainternet rede classe C conexao

jogos posicao no tabuleiro movimento de pecarede social pessoa, ator amizade, alencorede neural neuronio sinapse

rede proteica proteına interacao de proteınascomposto quımico molecula ligacao

14/1

Representacoes de grafos

Desenho de um grafo

Prove uma ideia sobre a estrutura do grafo.

0

6 1 25

3

4

7

8

9

10 11 12

0

6

1

2

5

3

4

78

910

11

12

Grafos podem ter multiplas representacoes.

28/1

Representacao de grafos

Representacao de vertices

I Usamos numeros inteiros entre 0 e V − 1, onde V e o numerode vertices

I Podemos usar tabela de sımbolos para converter nomes eminteiros

Joao

Maria Jose

Clara Ana

Manuel

1

2 3

4 5

6

29/1

API de Grafos

public class GrafoGrafo(int V) criar grafo vazio com V

verticesGrafo(InputStream in) criar grafo a partir de

entradasvoid novaAresta(int v, int w) criar aresta

Iterable<Integer> adj(int v) vertices adjacentes a vint V() numero de verticesint E() numero de arestas

Exemplo de uso

1 p u b l i c s t a t i c v o i d main ( S t r i n g a r g s [ ] ) {2 Gra fo G = new Grafo ( System . i n ) ;34 f o r ( i n t v = 0 ; v < G . V( ) ; v++)5 f o r ( i n t w : G . a d j ( v ) )6 System . out . p r i n t l n ( v+”−−”+w) ;7 }

30/1

Implementacao: representacao por lista de arestas

Manter lista de arestas (lista ligada ou vetor)

0

5

1

4

36

78

v w

0 54 30 16 45 47 85 3

33/1

Implementacao: representacao por matriz de adjacencias

Manter matriz adj[][] com V linhas e V colunas. Se existe aaresta v-w, entao a posicao adj[v][w] == adj[w][v] == 1,senao e 0

0

1

2

3

0 1 2 3

0 1 1 0 0

1 1 0 1 1

2 0 1 0 0

3 0 1 0 0

34/1

Implementacao: representacao por listas de adjacencias

Manter um vetor de listas indexado por vertice.

1

2

3

1 2

1 2 3

2

1

2

3

35/1

1 p u b l i c c l a s s Gra fo {2 i n t V ;3 L i s t a <I n t e g e r > [ ] a d j ; // l i s t a s de a d j a c e n c i a s45 p u b l i c Gra fo ( i n t V) {6 t h i s . V = V ;7 a d j = ( L i s t a <I n t e g e r > [ ] ) new L i s t a [ V ] ;8 f o r ( i n t v = 0 ; v < V ; v++)9 a d j [ v ] = new L i s t a <I n t e g e r >() ;

10 }1112 p u b l i c v o i d n o v a A r e s t a ( i n t v , i n t w) {13 a d j [ v ] . add (w) ;14 a d j [w ] . add ( v ) ;15 }1617 p u b l i c I t e r a b l e <I n t e g e r > a d j ( i n t v ) {18 r e t u r n a d j [ v ] ;19 }20 }

36/1

Representacao de grafos

Na pratica: usar listas de adjacencias

I Algoritmo em geral operam nos vertices

I Grafos reais tendem a ser esparsos (numero grande devertices, numero pequeno de arestas por vertice)

representacao espaco criar aresta existe v-w? iterar adj(v)lista de arestas E 1 E E

matriz de adjacencias V 2 1 1 Vlistas de adjacencias E+V 1 grau(v) grau(v)

E = numero de arestasV = numero de vertices

37/1

Grafo direcionado ou Dıgrafo

Conjunto de vertices conectados por arestas direcionadas.

1

2 3

4 5

Em dıgrafo existe grau de saıda e de grau de entrada: grau desaıda de 5 e 2 e grau de entrada de 5 e 1.

2/1

Aplicacoes de dıgrafos

dıgrafo vertice aresta direcionadatransportes cruzamentos ruas de mao-unica

web paginas web linkscadeia alimentar especies predador-presaescalonamento tarefa restricao de precedencia

financas banco transacaocelulares pessoa ligacao

DST pessoa infeccaojogos posicao tabuleiro movimento

literatura cientıfica artigo cientıfico citacaocoletor de lixo objeto ponteiro

3/1

Aplicacoes - Menor caminho

I Roteamento em mapas (GPS)

I Gerencia de projetos - caminho crıtico

I Redimensionamento de imagens

I Planejamento de trafego urbano

I Protocolos de rede (OSPF, BGP)

I Comercio de moedas estrangeiras

74/1

Modeling Users’ Activity on Twitter Networks: Validationof Dunbar’s Number (doi: 10.1371/journal.pone.0022656)

Figura: The data shows that this quantity reaches a maximum between100 and 200 friends, in agreement with Dunbar’s prediction (see figure2A).

Atributos Topologicos I

I Criacao de grafos a partir de matrizes de dadosI wij = sim(xi , xj), se nao ponderado: A(i , j) = 1 se wij ≥ L

I Atributos topologicosI Grau di =

∑j A(i , j)

I Grau medio µd =∑

i din

I Tamanho medio de caminho µL =∑

i

∑j>i d(vi ,vj )

(n2)

I Excentricidade e(vi ) = maxj{d(vi , vj)}I Raio r(G ) = mini{e(vi )}, Diametro d(G ) = maxi{e(vi )}I Coeficiente de agrupamento

C (vi ) = |subgrafo dos vizinhos de i|num. maximo possıvel de arestas na vizinhanca

I Eficiencia ef (G ) = 2n(n−1)

∑i

∑j>i

1d(vi ,vj

Atributos Topologicos II

I Analise de centralidades (closeness, betweenness)I Closeness c(vi ) = 1∑

i d(vi ,vj )

I Betweenness

I nik(vi ) = “numero de menores caminhos entre vj e vk”

I γjk(vi ) = nik (vi )njk

I c(vi ) =∑

j 6=i

∑k 6=i,k>j γjk

I Centralidades web (PageRank e HITS)

A web: um grafo direcionado

pag. d1 texto ancora pag. d2hyperlink

◮ Premissa 1: Um hyperlink e um sinal de qualidade.◮ O hyperlink d1 → d2 indica que o autor de d1 considera d2

como sendo boa qualidade e relevante.

◮ Premissa 2: O texto ancora descreve o conteudo d2.◮ Consideramos o texto ancora sendo o texto em volta do

hyperlink.◮ Exemplo: “Encontre carros baratos <a

href=http://...>aqui</a>.”◮ texto ancora: “Encontre carros baratos aqui”◮ Usando a definicao formal: apenas texto visıvel em um

hyperlink: aqui

Modelo do PageRank: Caminhada aleatoria

◮ Imagine um navegador fazendo caminhada aleatoria na web◮ Iniciar em uma pagina aleatoria◮ A cada passo, sair da pagina atual e ir para um dos links

daquela pagina, com chances iguais

◮ Depois de muita caminhada, cada pagina tem uma taxa devisita a longo prazo.

◮ Essa taxa de visita de longo prazo e o PageRank da pagina.

◮ PageRank = taxa de visita a longo prazo = probabilidade deestado estavel

Formalizacao caminhada aleatoria: Cadeia de Markov

◮ A Cadeia de Markov consiste de N estados, mais uma matrizde probabilidade de transicao P com N × N valores.

◮ estado = pagina

◮ A cada passo, estamos em uma das paginas

◮ Para 1 ≤ i , j ≤ N, o valor da matriz Pij e a probabilidade de jser a proxima pagina, dado que estamos atualmente na paginai .

◮ Propriedade:∑N

j=1 Pij = 1

di djPij

Exemplo grafo web

d0

d2 d1

d5

d3 d6

d4

carro benz

ford

gm

honda

jaguar

jag

gato

leopardo

tigre

jaguar

leao

cheeta

velocidade

PageRank

d0 0.05d1 0.04d2 0.11d3 0.25d4 0.21d5 0.04d6 0.31

PageRank(d2)<PageRank(d6):porque?

a h

d0 0.10 0.03d1 0.01 0.04d2 0.12 0.33d3 0.47 0.18

Exemplo: matriz de links

d0 d1 d2 d3 d4 d5 d6d0 0 0 1 0 0 0 0d1 0 1 1 0 0 0 0d2 1 0 1 1 0 0 0d3 0 0 0 1 1 0 0d4 0 0 0 0 0 0 1d5 0 0 0 0 0 1 1d6 0 0 0 1 1 0 1

Exemplo: matriz de probabilidades de transicao P

d0 d1 d2 d3 d4 d5 d6d0 0.00 0.00 1.00 0.00 0.00 0.00 0.00d1 0.00 0.50 0.50 0.00 0.00 0.00 0.00d2 0.33 0.00 0.33 0.33 0.00 0.00 0.00d3 0.00 0.00 0.00 0.50 0.50 0.00 0.00d4 0.00 0.00 0.00 0.00 0.00 0.00 1.00d5 0.00 0.00 0.00 0.00 0.00 0.50 0.50d6 0.00 0.00 0.00 0.33 0.33 0.00 0.33

Taxa de visita a longo prazo

◮ PageRank = taxa de visita a longo prazo◮ Taxa de visita a longo prazo da pagina d e a probabilidade que

um navegador aleatorio tem de estar na pagina d em um dadomomento

◮ Quais sao as propriedades que um grafo da web deve ter paraa taxa de visita a longo prazo ser bem definida?

◮ O grafo deve corresponder a uma cadeia de Markov ergodica.

◮ Caso especial: o grafo da web nao deve ter becos sem saıda

Becos sem saıda

??

◮ A web e cheia de becos sem saıda

◮ Caminhada aleatoria pode ficar travada em um beco semsaıda

◮ Se ha becos sem saıda, taxas de visita a longo prazo nao saobem definidas

teletransporte – saıda do caminho sem saıda

◮ Em um beco sem saıda, pular para uma pagina web aleatoriacom prob. 1/N.

◮ Em um caminho normal, com probabilidade 10%, pular parauma pagina web aleatoria (com probabilidade de 0.1/N paracada).

◮ Com probabilidade (90%), ir para um link aleatorio◮ Exemplo: se uma pagina tem 4 links de saıda: escolher um

com probabilidade (1-0.10)/4=0.225

◮ 10% e um parametro, a taxa de teletransporte.

◮ Nota: “sair” de um beco sem saıda e independente da taxa deteletransporte

Resultado de teletransporte

◮ Com teletransporte, nao ficamos presos em um beco semsaıda.

◮ Mas mesmo sem becos sem saıda, um grafo pode nao ter taxade visita a longo prazo bem definida.

◮ E necessario que a cadeia de Markov seja ergodica.

Cadeias de Markov Ergodicas

◮ A cadeia de Markov e ergodica se e somente se for irredutıvele aperiodica.

◮ Irredutibilidade. Ideia: ha um caminho entre quaisquer duaspaginas

◮ Aperiodicidade. Ideia: Paginas nao podem ser separadas deforma que o navegador aleatorio seja obrigado a visita-las emuma ordem especıfica.

◮ Uma cadeia de Markov nao-ergodica:

1.0

1.0

Cadeias de Markov Ergodicas

◮ Teorema: para uma cadeia de Markov ergodica, existe umaunica taxa de visita a longo prazo para cada estado

◮ Essa e a distribuicao de probabilidades em estado estavel.

◮ Em um longo perıodo de tempo, visita-se cada estado naproporcao dessa taxa

◮ Nao importa a pagina inicial

◮ teletransporte faz o grafo da web ser ergodico.

◮ ⇒ Grafo-Web+teletransporte tem uma distribuicao deprobabilidades de estado estavel.

◮ ⇒ Cada pagina no grafo-web+teletransporte tem um valor dePageRank.

Onde estamos

◮ Sabemos como ter certeza que temos um PageRank para cadapagina

◮ Como calcular?

Formalizacao de “visitas”: vetor de probabilidades

◮ Um vetor de probabilidades (vetor-linha) ~x = (x1, . . . , xN) dizonde o navegador aleatorio esta em qualquer momento

◮ Exemplo:( 0 0 0 . . . 1 . . . 0 0 0 )

1 2 3 . . . i . . . N-2 N-1 N

◮ Mais geral: caminhada aleatoria esta na pagina i comprobabilidade xi .

◮ Exemplo:( 0.05 0.01 0.0 . . . 0.2 . . . 0.01 0.05 0.03 )

1 2 3 . . . i . . . N-2 N-1 N

◮∑

xi = 1

Mudanca no vetor de probabilidades

◮ Se o vetor de probabilidades e ~x = (x1, . . . , xN) neste passo,como sera no proximo?

◮ Lembre-se que a linha i da matriz de transicao deprobabilidades P nos diz para onde iremos a partir do estado i .

◮ Entao a partir de ~x , o proximo estado e distribuıdo com asprobabilidades em ~xP .

Notacao de estado estavel

◮ O estado estavel na notacao de vetor e simplesmente umvetor ~π = (π1, π2, . . . , πN) de probabilidades

◮ Usamos ~π para diferenciar da notacao de vetor deprobabilidades ~x .

◮ πi e a taxa de visita a longo prazo (ou PageRank) da pagina i .

◮ Podemos considerar o PageRank como um grande vetor – umvalor por pagina

Exemplo: distribuicao de estado-estavel

◮ O que e o PageRank / estado-estavel nesse exemplo?

d1 d2

0.75

0.25

0.25 0.75

Exemplo: estado estavel

x1 x2Pt(d1) Pt(d2)

P11 = 0.25 P12 = 0.75P21 = 0.25 P22 = 0.75

t0 0.25 0.75 0.25 0.75t1 0.25 0.75 (convergencia)

Vetor PageRank = ~π = (π1, π2) = (0.25, 0.75)

Pt(d1) = Pt−1(d1) ∗ P11 + Pt−1(d2) ∗ P21

Pt(d2) = Pt−1(d1) ∗ P12 + Pt−1(d2) ∗ P22

Como obter o vetor de estado estavel?

◮ Como calcular PageRank?

◮ Vetor PageRank: ~π = (π1, π2, . . . , πN) , . . .

◮ . . . se a distribuicao neste passo e ~x , entao a distribuicao noproximo passo e ~xP .

◮ Mas ~π e o estado estavel!

◮ Entao: ~π = ~πP

◮ Resolvendo essa equacao nos da ~π.

◮ ~π e o auto-vetor principal esquerdo para P . . .

◮ . . . isto e, ~π e o auto-vetor esquerdo com maior auto-valor

◮ Todas as matrizes de probabilidades de transicao tem o maiorauto-valor igual a 1.

Um modo de calcular o PageRank ~π

◮ Iniciar com qualquer distribuicao ~x , e.g., distribuicao uniforme

◮ Depois de um passo, estamos em ~xP .

◮ Depois de dois passos, estamos em ~xP2.

◮ Depois de k passos, estamos em ~xPk .

◮ Algoritmo: multiplicar ~x por potencias de P ate convergencia

◮ Metodo da potencia

◮ Eventualmente chegamos no estado estavel ~π.

Exemplo: metodo da potencia

◮ O que e o PageRank / estado estavel neste exemplo?

d1 d2

0.9

0.3

0.1 0.7

◮ A distribuicao de estado estavel (= os PageRanks) nesseexemplo sao 0.25 para d1 e 0.75 para d2.

Calculando PageRank: metodo das potencias

x1 x2Pt(d1) Pt(d2)

P11 = 0.1 P12 = 0.9P21 = 0.3 P22 = 0.7

t0 0 1 0.3 0.7 = ~xPt1 0.3 0.7 0.24 0.76 = ~xP2

t2 0.24 0.76 0.252 0.748 = ~xP3

t3 0.252 0.748 0.2496 0.7504 = ~xP4

. . . . . .t∞ 0.25 0.75 0.25 0.75 = ~xP∞

Vetor PageRank = ~π = (π1, π2) = (0.25, 0.75)

Pt(d1) = Pt−1(d1) ∗ P11 + Pt−1(d2) ∗ P21

Pt(d2) = Pt−1(d1) ∗ P12 + Pt−1(d2) ∗ P22

Exemplo: metodo da potencia

◮ O que e o PageRank / estado estavel neste exemplo?

d1 d2

0.9

0.3

0.1 0.7

◮ A distribuicao de estado estavel (= os PageRanks) nesseexemplo sao 0.25 para d1 e 0.75 para d2.

Exercıcio: calcular o PageRank usando o metodo daspotencias

d1 d2

0.3

0.2

0.7 0.8

Solucao

x1 x2Pt(d1) Pt(d2)

P11 = 0.7 P12 = 0.3P21 = 0.2 P22 = 0.8

t0 0 1 0.2 0.8t1 0.2 0.8 0.3 0.7t2 0.3 0.7 0.35 0.65t3 0.35 0.65 0.375 0.625

. . .t∞ 0.4 0.6 0.4 0.6

Vetor PageRank = ~π = (π1, π2) = (0.4, 0.6)

Pt(d1) = Pt−1(d1) ∗ P11 + Pt−1(d2) ∗ P21

Pt(d2) = Pt−1(d1) ∗ P12 + Pt−1(d2) ∗ P22

PageRank: resumo

◮ Preprocessamento◮ Dado um grafo de links, construir matriz P◮ Aplicar teletransporte◮ A partir da matriz modificada, calcular ~π◮ ~πi e o PageRank da pagina i .

◮ Processamento da consulta◮ Recuperar paginas satisfazendo a consulta◮ Rankear usando o PageRank◮ Retornar lista rerankeada para o usuario

Problemas com PageRank

◮ Usuarios reais nao sao aleatorios◮ Exemplos de navegacao nao-aleatoria: botao voltar, favoritos,

diretorios – e buscadores◮ → Modelo de Markov nao e um bom modelo de navegacao na

web◮ Mas e bom suficiente para nossos interesses

◮ Ranking PageRank (como descrito anteriormente) podeproduzir resultados ruins para muitas paginas

◮ Considere a consulta [servico vıdeo]◮ A home page Yahoo (i) tem PageRank alto e (ii) contem

ambos vıdeo e servico.◮ Se rankeamos os resultados Booleanos de acordo com o

PageRank, entao o Yahoo seria o melhor ranking◮ Nao desejavel

◮ Na pratica: rankear de acordo com a combinacao ponderadada comparacao do texto do documento, do texto ancora, doPageRank e outros fatores

Exemplo grafo web

d0

d2 d1

d5

d3 d6

d4

carro benz

ford

gm

honda

jaguar

jag

gato

leopardo

tigre

jaguar

leao

cheeta

velocidade

PageRank

d0 0.05d1 0.04d2 0.11d3 0.25d4 0.21d5 0.04d6 0.31

PageRank(d2)<PageRank(d6):porque?

a h

d0 0.10 0.03d1 0.01 0.04d2 0.12 0.33d3 0.47 0.18

Matriz de probabilidades de transicao

d0 d1 d2 d3 d4 d5 d6d0 0.00 0.00 1.00 0.00 0.00 0.00 0.00d1 0.00 0.50 0.50 0.00 0.00 0.00 0.00d2 0.33 0.00 0.33 0.33 0.00 0.00 0.00d3 0.00 0.00 0.00 0.50 0.50 0.00 0.00d4 0.00 0.00 0.00 0.00 0.00 0.00 1.00d5 0.00 0.00 0.00 0.00 0.00 0.50 0.50d6 0.00 0.00 0.00 0.33 0.33 0.00 0.33

Matriz de transicao com teletransporte

d0 d1 d2 d3 d4 d5 d6d0 0.02 0.02 0.88 0.02 0.02 0.02 0.02d1 0.02 0.45 0.45 0.02 0.02 0.02 0.02d2 0.31 0.02 0.31 0.31 0.02 0.02 0.02d3 0.02 0.02 0.02 0.45 0.45 0.02 0.02d4 0.02 0.02 0.02 0.02 0.02 0.02 0.88d5 0.02 0.02 0.02 0.02 0.02 0.45 0.45d6 0.02 0.02 0.02 0.31 0.31 0.02 0.31

Vetores do metodo de potencias ~xPk

~x ~xP1 ~xP2 ~xP3 ~xP4 ~xP5 ~xP6 ~xP7 ~xP8 ~xP9 ~xP10 ~xP11 ~xP12 ~xP13

d0 0.14 0.06 0.09 0.07 0.07 0.06 0.06 0.06 0.06 0.05 0.05 0.05 0.05 0.05d1 0.14 0.08 0.06 0.04 0.04 0.04 0.04 0.04 0.04 0.04 0.04 0.04 0.04 0.04d2 0.14 0.25 0.18 0.17 0.15 0.14 0.13 0.12 0.12 0.12 0.12 0.11 0.11 0.11d3 0.14 0.16 0.23 0.24 0.24 0.24 0.24 0.25 0.25 0.25 0.25 0.25 0.25 0.25d4 0.14 0.12 0.16 0.19 0.19 0.20 0.21 0.21 0.21 0.21 0.21 0.21 0.21 0.21d5 0.14 0.08 0.06 0.04 0.04 0.04 0.04 0.04 0.04 0.04 0.04 0.04 0.04 0.04d6 0.14 0.25 0.23 0.25 0.27 0.28 0.29 0.29 0.30 0.30 0.30 0.30 0.31 0.31

Exemplo grafo web

d0

d2 d1

d5

d3 d6

d4

carro benz

ford

gm

honda

jaguar

jag

gato

leopardo

tigre

jaguar

leao

cheeta

velocidade

PageRank

d0 0.05d1 0.04d2 0.11d3 0.25d4 0.21d5 0.04d6 0.31

PageRank(d2)<PageRank(d6):porque?

a h

d0 0.10 0.03d1 0.01 0.04d2 0.12 0.33d3 0.47 0.18

Importancia do PageRank

◮ Alegacao frequente: PageRank e o componente maisimportante do ranking de paginas na web

◮ A realidade:◮ Ha varios componentes que sao pelo menos tao importantes:

e.g., texto ancora, expressoes, proximidade, ındices emcamadas . . .

◮ Diz-se que o PageRank no formato original (como mostradoaqui) hoje tem um impacto baixo no ranking

◮ Porem, variantes do PageRank sao ainda essenciais para arecuperacao de paginas web

◮ Lutar contra spam baseado em links e difıcil e crucial

Modelos de grafos

I Diferentes grafos possuem caracterısticas e propriedadessimilares

I Muitos grafos costumam ser grandes e esparsosI Grande: alto numero de vertices (n > 100000)I Esparso: numero de arestas m = O(n)

I Grafo com n vertices e um mundo pequeno se o tamanhomedio de caminhos

µL ∝ log n

I Grafo e livre de escala se a distribuicao de graus f (k) edescrita por uma lei de potencia

f (k) ∝ k−λ

Grafos livres de escalaI Muitos vertices com baixo grau e pouco com alto grauI log f (x) = −λ log k + logαI Regressao linear em um grafico log-logI Opcao: usar distribuicao cumulativa complementar

F c(k) = 1− F (k) ∝ k−(λ−1), onde F (k) =∑k

i=0 f (i)

Efeito de agrupamento em grafos

I Dois vertices tem maior probabilidade de conexao secompartilham um vizinho

I Alto coeficiente de agrupamento

I Coeficiente de agrupamentoC (vi ) = |subgrafo dos vizinhos de i|

num. maximo possıvel de arestas na vizinhanca

I Seja C (k) a media de C (vi ) para todos vi com grau j

I Lei de potenciaC (k) ∝ k−λ

I Lei de potencia do coeficiente de agrupamento indicaagrupamento hierarquico

I Vertices com baixo grau sao parte de subgrafos mais agrupadosI Subgrafos sao unidos por vertices centrais com grau mais alto

Exemplo: interacao de proteınas humanasI Vertice = proteına, Aresta = interacao experimental, N =

9521, m = 37060I Relacao linear com γ = 2.85 entre log k e log f (k) indica

propriedade “livre de escala”I Diametro d(g) = 14 ≈ log2 n = 13.22 indica mundo pequenoI Relacao linear entre log k e logC (k) indica agrupamento

hierarquico

Modelo de grafos aleatorios de Erdos-Renyi

I Modelo para obter grafos uniformemente aleatorios paradados numeros de vertices n e arestas m

I Seja M = maxm =(n

2

)e(Mm

)o numero total de grafos

distintos para dados n e m

I Entao a probabilidade de obter um grafo da colecao de grafosG(n,m) e

P(G ) =

(M

m

)−1

I Seja V = {v1, v2, . . . , vn}, fazer m vezes:1. Inicializar grafo G vazio2. Criar aresta nao existente em G entre dois vertices sorteados vi

e vj

I Modelo de Erdos-Renyi nao e livre de escala pois

f (k) ∝ αkk−12 k−k , onde α = np exp e p = 2m

n(n−1)

I Modelo indica comportamento de mundo pequeno pord(G ) ∝ log n

Error and attack tolerance of complex networks(doi:10.1038/35019019)

Figura: Modelo de Erdos-Renyi e exponencial

Modelo de Watts-Strogatz

I Cada vertice do cırculo a conectado a mais k vizinhos aesquerda e k a direita

I Com coeficiente de agrupamento alto: C (G )→ 34

I Mas nao e mundo pequeno (d(G ) ≈ n/2k > log n)

Modelo de Watts-Strogatz com mundo pequenoI Para obter mundo pequeno, pertubacoes aleatorias com

probabilidade r :I Para cada (u, v) ∈ E trocar v aleatoriamente (evitando laco e

aresta duplicada), ouI Criar mais knr arestas aleatorias de “atalho”

I Usar r para controlar “mistura” entre agrupamento e mundopequeno

C (V ) ≈ 3k − 3

4k − 2 + 2r(2kr + 4k − 1)

I Mas nao e livre de escala

Diametro de um grafo Watts-Strogatz

Modelo livre de escala de Barabasi-Albert

I Geracao de grafos com propriedade livre de escalaI Ligacao preferencial (preferential attachment): arestas de

novo vertice tem mais chance de ser ligado a vertices commaior grau

I Inicializacao: Criar G0 com n0 vertices e m0 = n0 arestas emformato circular

I Expansao: Obter Gt+1 usando Gt com novo vertice u e q ≤ n0

novas arestas entre u e q vertices distintos em Gt , onde vj eescolhido com probabilidade

πt(vj) =dj∑

vi∈Gtdi

I Atualizacao de probabilidades: nt = n0 + t, mt = m0 + qt,∑vi∈Gt

d(vi ) = 2mt = 2(m0 + qt), πt(vj) =dj

2(m0+qt)

Caracterısticas do modelo de Barabasi-Albert

I Distribuicao dos graus: f (k) ∝ k−3

I Diametro mundo pequeno: d(Gt) = O( log ntlog log nt

)

I Agrupamento esperado: E [C (Gt)] = O( (log nt)2

nt)

Um grafo de Barabasi-Albert

Mineracao de padroes em grafos

I Padroes sao subgrafos interessantesI ArvoresI Subgrafos completosI Subgrafos regularesI Cliques e quasi-cliquesI Cliques bipartidosI Subgrafos densos

I Padroes representamI Comunidades sociais coesasI Proteınas envolvidas no mesmo processo bioquımicoI Paginas de autoridade e portais na WWWI Perfis comportamentais

DefinicoesI Grafo nao-direcional G = (V ,E ), com vertices V e arestas

E ⊆ V × VI Conjunto de vizinhos de vertice u e

N(u) = {v ∈ V |(u, v) ∈ E}I Grafo pode ter rotulos associados a vertices e a arestas

I Rotulo (label) de u: L(u) ∈ ΣV , rotulo de (u, v): L(u, v) ∈ ΣE

I Uma aresta extendida e uma tupla 〈u, v , L(u), L(v), L(u, v)〉

IsomorfismoI G ′ = (V ′,E ′ e isomorfo a G (V ,E ) se existe funcao bijetoraφ : V ′ → V tal que

I (u, v) ∈ E ′ ⇔ (φ(u), φ(v)) ∈ EI ∀u ∈ V ′ = L(φ(u))I ∀(u, v) ∈ E ′, L(u, v) = L(φ(u), φ(v))I Ou seja, a funcao φ “traduz” os rotulos de G ′ para os rotulos

G sem mudar a estrutura do grafoI Se a funcao φ e apenas injetora e nao sobrejetora, entao G ′ e

isomorfo a um subgrafo de G (por que?)

Figura: Quais sao as tabelas de φ e φ−1?

Subgrafo suporte

I Dados:I Base de grafos: D = {G1,G2, . . . ,Gn}I Grafo referencia G

I Suporte de G em D:

sup(G ) = |{Gi ∈ D|G ⊆ Gi}|

I Ou seja, o numero de grafo em que G e subgrafo

I Problema da mineracao de grafos: encontrar todossubgrafos conectados com suporte maior que um limiarminsup

OO

SS

OO

OO OO

HHHHHH

CC

HH

HH CC

OO

OO HH

CC

OO

OO OO

HH HH

NN

HH

HH HH

Amônia

Ácido carbônico

Ácido acéticoÁcido sulfúrico

Figura: Fonte: slides do livro “Practical Graph Mining With R”

Problema de subgrafos com suporte mınimo

I Objetivo: encontrar todos subgrafos conectados com suportemaior que um limiar minsup

I Tamanho do espaco de busca e exponencialI Subgrafos com m vertices tem

(m2

)= O(m2) arestas

I Numero de subgrafos com m vertices e O(2m2

)(inclusao/remocao de cada aresta possıvel)

I Com rotulos, espaco de busca e maior

I DesafiosI Gerar sistematicamente subgrafos candidatosI Computar o suporte com teste de isomorfismo em subgrafos

I Algoritmos: http://dx.doi.org/10.1109/ICDM.2002.1184038,SUBDUE, SLEUTH

Geracao sistematica de subgrafos candidatos

I Mecanismo de expansao por arestas (edge-growth)I Cuidado para nao gerar subgrafos repetidos (testar

isomorfismo se preciso)

1. Usar grafo G como referencia2. Iniciar com subgrafo vazio3. Adicionar uma aresta por vez em ordem (largura ou

profundidade)I Conectar dois vertices existentes ou criar um novo

4. Computar suporte

Geracao sistematica de subgrafos candidatosI Estrategia: expansao do caminho mais a direita

I Fazer busca em profundidade nos vertices e criar uma arvoregeradora

I Arestas na arvore geradora sao forward (“para a frente”)I Arestas fora da arvore sao backward (“para tras”) e criam

ciclos no grafo

I Definir o caminho mais a direita como o caminho da raiz daarvore para a folha mais a direita

Geracao sistematica de subgrafos candidatos

I Usando o caminho mais a direita...I Adicionar arestas ao grafo candidato somente ligadas a

vertices do caminho mais a direitaI Aresta forward adiciona nova arestaI Aresta backward nao adiciona nova aresta

I Ordem de precedencia das extensoes com arestas:I Primeiro: usar todas as extensoes backward ao vertice mais a

direitaI Se ur e vertice mais a direita a extensao (ur , vi ) e usada antes

de (uv , vj) se i < jI Ou seja, arestas backwards mais perto da raiz sao tentadas

antes que aquelas mais longe

I Depois: usar extensoes forward de vertices no caminho mais adireita

I Se vx e o novo vertice a ser adicionado, (vi , vx) e tentadaantes de (vj , vx) se i > j

I Ou seja, vertices mais longe da raiz sao tentados primeiroI Note: novo vertice sera numerado com x = r + 1

I Em verde, o caminho mais a direita da arvore gerada pelocaminho em profundidade

I O vertice mais a direita e v8

I Linhas contınuas (verdes e pretas) sao as arestas forwardI Linhas vermelhas sao as arestas backwardI Linhas tracejadas sao as possıveis extensoesI A ordem de precedencia e numerada com #1, #2, . . .

Codigo canonico

I No uso de extensoes do caminho mais a direita e possıvel quegrafos isomorficos sejam criados

I Ordenar grafos isomorfos usando uma representacaao canonica

I Grafo G e arvore DFS TG que define a ordem de visitacao devertices

Codigo canonico da busca em profundidade (DFS)

I

Computacao do suporte com teste de isomorfismo emsubgrafos

I Problema: achar grafos que contem o subgrafo candidato

I Conjunto de grafos para testes:http://www.eecs.wsu.edu/MGD/gdb.html

I http://www.csc.ncsu.edu/faculty/samatova/

practical-graph-mining-with-R/

PracticalGraphMiningWithR.html#SampleChapters

Referencias

I Stanford Network Analysis Platform (SNAP) -http://snap.stanford.edu

I Livro Manning e Slides

I Data mining and analysis

I Mining Massive Datasets