Representações implícitas probabilísticas de grafos

Apresentado no II ETC/CSBC

Transcript

1. REPRESENTAÇÕES DE GRAFOS IMPLÍCITAS PROBABILÍSTICAS Ç JUAN P. A. LOPES FABIANO DE S. OLIVEIRA PAULO E. D. PINTO DICC/IME/UERJ
2. POR QUÊ?
3. REDES SOCIAIS
4. REDES SOCIAIS BIOINFORMÁTICA
5. REDES SOCIAIS BIOINFORMÁTICA REDES DE COMPUTADORES
6. REDES SOCIAIS BIOINFORMÁTICA REDES DE COMPUTADORES GIS
7. Uma representação é ótima se requer O(f(n)) bits para representar uma classe contendo 2ϴ(f(n)) grafos de n vértices. Jeremy P SPINRAD. Efficient graph representations. American mathematical society, 2003. John Harold MULLER. Local structure in graph classes, 1988. Sampath KANNAN, Moni NAOR, e Steven RUDICH. Implicit representation of graphs. SIAM Journal on Discrete Mathematics, 1992.
8. 1 3 2 5 4 1 2 3 4 5 2 1 3 2 2 4 1 3 3 5 LISTA DE ADJACÊNCIA 0 1 1 0 1 1 0 1 0 1 1 1 0 1 0 0 0 1 0 0 0 1 0 0 0 1 2 3 4 5 1 2 3 4 5 MATRIZ DE ADJACÊNCIA
9. 0 1 1 0 1 1 0 1 0 1 1 1 0 1 0 0 0 1 0 0 0 1 0 0 0 1 2 3 4 5 1 2 3 4 5 MATRIZ DE ADJACÊNCIA 1 3 2 5 4
10. 1 3 2 5 4 ESTE É O #42 1 3 2 5 4 ESTE É O #41 1 3 2 5 4 ESTE É O #43
11. REPRESENTAÇÃO IMPLÍCITA Versão generalizada de Spinrad • ASSINTOTICAMENTE ÓTIMA O(f(n)) bits para representar uma classe com 2ϴ(f(n)) grafos de n vértices; • DISTRIBUI INFORMAÇÃO ENTRE OS VÉRTICES Cada vértice precisa de O(f(n)/n) bits para representar a adjacência; • TESTE DE ADJACÊNCIA É LOCAL Para testar a adjacência entre dois vértices, apenas informações locais são usadas.
12. REPRESENTAÇÃO IMPLÍCITA Versão generalizada de Spinrad • ASSINTOTICAMENTE ÓTIMA O(f(n)) bits para representar uma classe com 2ϴ(f(n)) grafos de n vértices; • DISTRIBUI INFORMAÇÃO ENTRE OS VÉRTICES Cada vértice precisa de O(f(n)/n) bits para representar a adjacência; • TESTE DE ADJACÊNCIA É LOCAL Para testar a adjacência entre dois vértices, apenas informações locais são usadas. • TESTE DE ADJACÊNCIA É PROBABILÍSTICO Possui uma probabilidade relativa fixa de causar falsos positivos ou falsos negativos.
13. Na prática, funções hash, permitem simular uma distribuição uniforme, porém mantendo informações sobre os dados originais.
14. FILTRO DE BLOOM Permite realizar consultas de pertinência em um conjunto com O(1) bits por elemento. • APLICAÇÃO DIRETA DA ESTRUTURA Representa-se o conjunto de arestas para permitir teste de adjacência eficiente com O(1) espaço por aresta, isto é, tão eficiente quanto a matriz de adjacência no pior caso. • EFICIENTE PARA GRAFOS ESPARSOS Apenas O(m) memória necessária para representar qualquer grafo. • ERRO RELATIVO A ESPAÇO UTILIZADO 10 bits por elemento = <1% de falsos positivos 4 bits por elemento = <15% de falsos positivos
15. MINHASH Hashing sensível a localidade. • VARIÁVEL DE BERNOULLI • ÍNDICE DE JACCARD
16. MINHASH Hashing sensível a localidade. • CADA FUNÇÃO DEFINE UM ESTIMADOR NÃO-ENVIESADO • MÚLTIPLOS ESTIMADORES COMPÕEM UMA ASSINATURA • COMPARAÇÃO DE ASSINATURAS
17. MINHASH Hashing sensível a localidade. h 1 A 197 98 11 86 Arthur Dent 71 82 57 204 137 68 172 6 Tricia McMillan 132 40 238 106 247 6 253 138 Zaphod Beeblebrox 225 220 229 120 71 182 221 96 Ford Prefect 237 63 209 201 11 193 29 192 Marvin 186 182 113 150 118 207 1 251 Fenchurch 80 34 116 143 h 2 h 3 h 4 h 5 h 6 h 7 h 8 11 6 1 6 MinHash(A) 71 34 57 106 CONJUNTO A
18. MINHASH Hashing sensível a localidade. h 1 B 208 8 198 81 Slartibartfast 195 181 195 153 171 178 130 196 Prostetnic Vogon Jeltz 145 237 73 88 247 6 253 138 Zaphod Beeblebrox 225 220 229 120 71 182 221 96 Ford Prefect 237 63 209 201 11 193 29 192 Marvin 186 182 113 150 118 207 1 251 Fenchurch 80 34 116 143 h 2 h 3 h 4 h 5 h 6 h 7 h 8 11 6 1 81 MinHash(B) 80 34 73 88 CONJUNTO B
19. MINHASH Hashing sensível a localidade. 6 MinHash(A) 71 57 106 81 MinHash(B) 80 34 73 88 6 71 57 106 81 80 73 88 11 6 1 34 11 6 1 34
20. MINHASH Representação baseada em hashing sensível a localidade 0 1 δ A δ B
21. MINHASH Representação baseada em hashing sensível a localidade 0 1 δ A δ B
22. MINHASH Representação baseada em hashing sensível a localidade 1 3 2 4 5 6 7
23. MINHASH Representação baseada em hashing sensível a localidade 1 3 2 4 5 6 7 {1, 2, 3, 4} {1, 2} {1, 3} {1, 2, 5, 6} {1, 2, 7, 8} {1, 3, 9, 10} {1, 5} δ A = 1/3 δ B = 1/2
24. MINHASH Representação baseada em hashing sensível a localidade 1 2 3 4 5 6 7 8 a 1 a 2 1 3 5 7 1 3 6 8 1 4 5 8 1 4 6 7 S 0000 0011 0101 0110 a 3 a 4 a 5 a 6 a 7 a 8 s δ A = 1/3 δ B = 1/2
25. MINHASH Representação baseada em hashing sensível a localidade 0 0 0 0 1 0 0 0 1 0 0 0 1 0 0 0 1 1 1 1 0 x4 x4 0 1 2 3 0 1 2 3 0 1 0 1 0 0 M[i][j] = popcount(i&j)&1; δ A = 1/3 δ B = 1/2
26. MINHASH Representação baseada em hashing sensível a localidade 1 3 2 4 5 6 7 {1, 2, 3, 4} {1, 2} {1, 3} inicial subconjunto
27. MINHASH Representação baseada em hashing sensível a localidade 1 3 2 4 5 6 7 {1, 2, 3, 4} {1, 2} {1, 3} {1, 2, 5, 6} {1, 2, 7, 8} {1, 3, 9, 10} inicial subconjunto extensão
28. MINHASH Representação baseada em hashing sensível a localidade 1 3 2 4 5 6 7 {1, 2, 3, 4} {1, 2} {1, 3} {1, 2, 5, 6} {1, 2, 7, 8} {1, 3, 9, 10} {1, 5} inicial subconjunto extensão subconjunto
29. Esta é uma representação probabilística para árvores com complexidade menor que a melhor representação determinística. Cada vértice é representado com O(1) bits, usando b-bit MinHash. Ping LI, and Christian KÖNIG. b-Bit minwise hashing. Proceedings of the 19th international conference on World wide web. ACM, 2010.
30. Uma classe hereditária C contém 2ϴ(n²) grafos de n vértices se e somente se ela contém todos os grafos bipartidos, todos os co-bipartidos ou todos os grafos split. Jeremy P SPINRAD. Efficient graph representations. American mathematical society, 2003.
31. GRAFOS BIPARTIDOS É sempre possível representá-los? 1 2 3 4 5 6 K 3,3 δ A = 0.4 δ B = 0.6
32. MODELAGEM EM PROGRAMAÇÃO INTEIRA Objetivo: mostrar que uma instância não possui solução viável. x A x AB S A S B S C x B x C x AC x BC x ABC A B C
33. TRANSFORMAÇÃO PARA BIPARTIDO Se há representação eficiente para bipartidos, co-bipartidos ou split, há para todos os grafos. 1 3 2 5 4 1 2 3 4 5 1 2 3 4 5
34. PERGUNTAS?
35. OBRIGADO twitter.com/juanplopes github.com/juanplopes