Upgrade to Pro — share decks privately, control downloads, hide ads and more …

Representações implícitas probabilísticas de gr...

Juan Lopes
November 25, 2017

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

Apresentado no II ETC/CSBC

Juan Lopes

November 25, 2017
Tweet

More Decks by Juan Lopes

Other Decks in Technology

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. 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.
  3. 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
  4. 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
  5. 1 3 2 5 4 ESTE É O #42 1

    3 2 5 4 ESTE É O #41 1 3 2 5 4 ESTE É O #43
  6. 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.
  7. 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.
  8. 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
  9. 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
  10. 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
  11. 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
  12. 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
  13. 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
  14. 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
  15. 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
  16. 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
  17. 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
  18. 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
  19. 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.
  20. 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.
  21. 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
  22. 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