1 GRAFOS Codificación y Aplicaciones using std:cpp 2015UC3M- 18 de Noviembre 2015 Este trabajo está financiado parcialmente por el Ministerio de Economía y Competitividad (DPI2010-21247-C02, DPI 2014-53525-C3-1-R) Pablo San Segundo Carrillo (Profesor Titular en la UPM) [email protected]

2 Índice 2  Cadenas de bits  Representación de conjuntos  Librería C++ BITSCAN  Codificación de grafos (simples y no dirigidos) con cadenas de bits  Conjuntos de vértices y subgrafos  Algoritmia  Aplicaciones  Análisis de redes  Grafo de correspondencia  Correspondencia entre imágenes  Reconocimiento de huellas  Otros  Resumen  Bibliografía

3 Cadenas de bits-conjuntos(I) 3  Sea el conjunto [n]={0,1,2,…,n-1}  Sea w el tamaño de los registros de una CPU (tip. 64-bits)  Una cadena de bits B n es una codificación de un subconjunto T  [n] cuando:  B n,T [i]=1,  i  T  B n,T [j]=0,  j  T  Ejemplo  T={0,2,6}  [8]  B 8,T ={10100010} T 026 10100010B 8,T [8] 01234567

4 Cadenas de bits-conjuntos “pequeños”(II) 4  Sean A w y B w dos cadenas de bits que codifican los subconjuntos T A y T B  [w≤64]  Entonces:  Las cadenas de bits A 64 y B 64 son números.  Operaciones entre subconjuntos T A y T B como unión, intersección, diferencia, inclusión etc., pueden computarse como máscaras de bits entre A 64 y B 64 Máscaras w-bits T A U T B A 64 | B 64 TA ∩ TBTA ∩ TB A 64 & B 64 T A \ T B A 64 &~ B 64 (T A  T B )?{B 64 &~ A 64 } = 

5 Cadenas de bits-conjuntos “grandes”(III) 5 #define NUMBER_OF_EMPLOYEES 1000 void main(){ bitarray emp(NUMBER_OF_EMPLOYEES); emp.set_bit(0, NUMBER_OF_EMPLOYEES-1); bitarray emp_assist(NUMBER_OF_EMPLOYEES ); //… determine assistance //employees which did not assist the training sessions bitarray emp_not_assist(emp); emp_not_assist.erase_bit(emp_assist); } O(n/w)

6 BITSCAN: librería C++ para cadenas de bits 6  Cadenas de bits para conjuntos T  [n], con n>64  Librería propia inspirada en mas de una década de investigación en problemas de optimización combinatoria discreta  Algunas de las especificaciones NO encontradas en las soluciones actuales:  Enumeración eficiente de los elementos del conjunto  Bidireccional  Con y sin borrado de los elementos  Manipulación de conjuntos “sparse”  Manipulación de conjuntos “semi-sparse”

7 7 Data types  Main data types  bitblock  bitarray  sparse_bitarray  watched_bitarray simple_bitarraysimple_sparse_bitarray bitarray bbo watched_bitarray bitblock sparse_bitarray n  64 n > 64n > 64 y sparse n > 64 y semi-sparse

8 Tipo bitarray - ejemplo de enumeración 8 #include “bitscan.h" #define POPULATION_SIZE 10000 void main(){ bitarray bba(POPULATION_SIZE); bba.set_bit(0, 9); //first 10 bits to 1 //typical bit-scanning loop int nBit=EMPTY_ELEM; bba.init_scan(bbo::NON_DESTRUCTIVE); while(true){ nBit=bba.next_bit(); if(nBit==EMPTY_ELEM) break; cout

9 Tipo sparse_bitarray 9 [1000] B 1000 = 1111111111111111111111111···111 B 1000,T = 1100000000000000000000000···000 class sparse_bitarray: public bbo{ struct elem_t{ int index; BITBOARD bb; //a non-empty 64-bit block }; protected: vector vBB; int m_MAXBB;//max num. of bitblocks }; T  [1000] 0 1 Solo se almacenan los bloques de bits B 64 NO VACÍOS B 1000,T = {(0, 1I0…0)} Bloque de 64-bits

10 Tipo watched_bitarray 10  Concebidos para semi-sparse sets  Características  Detección rápida de cadenas de bits vacías  Las operaciones se circunscriben a los bloques entre dos centinelas 1010 1101 1010 1111 C1 C2 0000 1111 1111 0000 Mask & (  ) 0000 1101 1010 0000 0000 0000 1111 0000 0000 0000 1010 0000 0000 0000 0000 0000 0000 0000 0000 0000 [1000] T  [1000] INCONSISTENTE  CADENA VACÍA

11 CODIFICACIÓN DE GRAFOS EN MEMORIA PRINCIPAL MEDIANTE TABLEROS DE BITS

12 Codificación de grafos - metadatos(I) 12 0 1 4 3 2 Vertices01234 0x1100 11x110 211x01 3010x1 40011x Matriz de adyacencia 0 1 2 bitarray 0 bitarray 2 bitarray 3 bitarray 4 bitarray 1 #include “graph.h” #define NUMBER_OF_VERTICES 5 void main(){ //undirected graph ugraph ug(NUMBER_OF_VERTICES); ug.add_edge(0, 1); ug.add_edge(0, 2); ug.add_edge(1, 2); ug.add_edge(1, 3); ug.add_edge(3, 4); //… } #include “graph.h” #define NUMBER_OF_VERTICES 1000000 void main(){ //undirected graph sparse_ugraph ug(NUMBER_OF_VERTICES); ug.add_edge(0, 1); ug.add_edge(0, 2); ug.add_edge(1, 2); ug.add_edge(1, 3); ug.add_edge(3, 4); //… } sparse_bitarray 0 sparse_bitarray 1 sparse_bitarray 2 sparse_bitarray 3 sparse_bitarray 4 Librería C++ GRAPH

13  Sea el grafo G=(V, E) sin pesos, con n vértices y m aristas  Sea A(G) la matriz de adyacencias de G  Entonces:  El conjunto de todos los vértices V=[n] puede codificarse con el tablero B n con todos sus bits a 1  Un subconjunto de vértices W  V puede codificarse con el tablero B n,W donde cada bit a 1 se corresponde con cada vértice v  W  El subgrafo inducido G[W]=(W, E[W]) puede codificarse con B n,W y la codificación de A(G) Codificación de grafos - subgrafos(II) 13 bitarray n > 64 sparse_bitarray n > 64 y sparse watched_bitarray n > 64 y semi-sparse

14 Codificación de grafos - algoritmia(III) 14  Algunas definiciones:  Se dice que un grafo es completo cuando todos los vértices están conectados entre sí.  K n es un grafo completo de n vértices.  El problema del máximo clique consiste en encontrar el mayor subgrafo completo para un grafo dado.  Número de clique ( ω(G)): El número de vértices de cualquier máximo clique de G. ω(G)=3

15 Codificación de grafos-algoritmia(IV) 15 1 4 2 3 G= (V, E) 3 4 2 G[{2,3,4}] SUBPROBLEMA DERIVADO DE LA EXPANSIÓN DE 1 1111 V  B 4,V A 1 (G) 0111 1234 G[{2,3,4}]0111 V  A 1 (G) Grafo: 2dc.2048 n = 2048 m=1591677 Grafo: 2dc.2048 n = 2048 m=1591677

16 Codificación de grafos - redes reales(V) 16  Extracto de 256 redes analizadas  http://www.networkrepository.com/ TypeNetwork|V||E|d max d avg K(G)+1ω Affiliationaff-orkut-user2groups873085732703742031826874.924726 Infrastructureinf-germany_osm1154884512369181132.1443 Infrastructureinf-great-britain_osm7733822815651782.1143 Infrastructureinf-italy_osm6686493701397892.1043 Infrastructureinf-roadNet-CA19570272760388122.7644 Scientific comp.adaptive68157441362432044.0032 Scientific comp.channel-500x100x100-b0504802000426813721817.78104 Scientific comp.delaunay_n22419430412582869236.0054 Socialsoc-youtube-snap11348902987624287545.275217 A new exact maximum clique algorithm for large sparse graphs, San Segundo et al., Computers & Operations Research, 2015

17 Codificación de grafos - redes reales(VI) 17  Tiempos de ejecución para el algoritmo EOC  Toward an Efficient, Highly Scalable Maximum Clique Solver for Massive graphs, Hagan el al., IEEE Conf. On Big Data, EEUU, 2014  Tiempos de ejecución secuencial para el algoritmo BBMCSP  Codificación en memoria: GRAPH (tipo sparse_ugraph) TypeNetworkω#2#5#25#75 Infrastructureinf-roadNet-CA410980s3823s256s153s Socialsoc-youtube-snap1713860s4451s878s417s TypeNetworkω#1 Infrastructureinf-roadNet-CA40.001s Socialsoc-youtube-snap170.227s

18 APLICACIONES Análisis de imágenes y reconstrucción 3D Mobile robotics (SLAM) Robótica Móbil (SLAM) Análisis de redes Reconocimiento de huellas

19 The Handshake principle 19 Sea una reunión de cualquier de personas. Entonces se cumple que: El número total de personas que dan la mano a un número impar de personas es par 1 1 2 1 1 1 3

20 Análisis de redes temporales(I) 20  Búsqueda de componentes fuertemente conexos (tCC)  Definición tCC: Subgrafo localmente máximo tal que existe un camino temporal entre cualesquiera de dos de sus vértices 1 2 3 4 G R  Reachability graph La búsqueda de subgrafos completos en G R permite determinar componentes fuertemente conexos en G 1 2 3 5s10s 30s 4 3s G G R  (u, v) se conectan si existe un camino temporal entre u y v 1 2 3

21 Análisis de redes temporales(II) 21  Red temporal de retweets entre personas vinculadas a partidos políticos en relación con las elecciones en EEUU de noviembre del 2010 G R  Reachability graph tCC de mayor tamaño (166 individuos) Parallel Maximum Clique Algorithms with Applications to Network Analysis, Rossi et al., SIAM Journal on Scientific Computing, 2015

22 Encontrar un Máximo Subgrafo Común(I) 22  Modelo de correspondencia L1L1 L2L2 L3L3 L4L4 L5L5 w 12 w 34 w 23 O3O3 O1O1 O2O2 O4O4 w’ 12 w’ 13 w’ 34 GLGL GOGO

23 Encontrar un Máximo Subgrafo Común(II) 23  Se define un grafo de correspondencia G C  Los nodos son parejas de vértices (Li, Oj) L1O1L1O1 L1O2L1O2 L1O3L1O3 L1O4L1O4 L2O1L2O1 L2O2L2O2 L2O3L2O3 L2O4L2O4 L3O1L3O1 L3O2L3O2 L3O3L3O3 L3O4L3O4 L4O1L4O1 L4O2L4O2 L4O3L4O3 L1L1 L2L2 L3L3 L4L4 L5L5 w 12 w 34 w 23 O3O3 O1O1 O2O2 O4O4 w’ 12 w’ 13 w’ 34 GCGC

24 O3O3 O1O1 O2O2 O4O4 w’ 12 w’ 13 w’ 34 Encontrar un Máximo Subgrafo Común(III) 24  Existe la arista (L 1 O 3, L 2 O 1 ) si w 12  w’ 13 L1O1L1O1 L1O2L1O2 L1O3L1O3 L1O4L1O4 L2O1L2O1 L2O2L2O2 L2O3L2O3 L2O4L2O4 L3O1L3O1 L3O2L3O2 L3O3L3O3 L3O4L3O4 L4O1L4O1 L4O2L4O2 L4O3L4O3 L1L1 L2L2 L3L3 L4L4 L5L5 w 12 w 34 w 23

25 Encontrar un Máximo Subgrafo Común(IV) 25 L1O1L1O1 L1O2L1O2 L1O3L1O3 L1O4L1O4 L2O1L2O1 L2O2L2O2 L2O3L2O3 L2O4L2O4 L3O1L3O1 L3O2L3O2 L3O3L3O3 L3O4L3O4 L4O1L4O1 L4O2L4O2 L4O3L4O3 L1L1 L2L2 L3L3 L4L4 L5L5 w 12 w 34 w 23 O3O3 O1O1 O2O2 O4O4 w’ 12 w’ 13 w’ 34 GCGC Propiedad Un máximo subgrafo común entre G L y G O es un máximo subgrafo completo en el grafo de correspondencia G C GLGL GOGO

26 Aplicaciones: modelo de correspondencia 26  Correspondencia entre parejas de imágenes  Reconstrucción 3D  Reconocimiento de huellas  Encontrar la pose de un robot  Construcción de mapas (SLAM)  Identificación de propiedades de proteínas  Síntesis de nuevas drogas  Otros Modelling enzyme-ligand binding in drug discovery, Konc et al., Journal of Cheminformatics, 2015

27 Correspondencia entre dos imágenes(I) 27 Algoritmo para correspondencia entre dos imágenes A y B I.Detección de puntos de interés de ambas imágenes (KP A y KP B ) Algoritmos públicos (SIFT, SURF) II.Generación del Grafo de correspondencia G C Restricciones para reducir la escala del problema III.Búsqueda del mayor subgrafo completo en G C A novel clique formulation for the visual feature matching problem, San Segundo et al., Applied Intelligence, 2015

28 Correspondencia entre dos imágenes(II) 28 Número de 3 o más imágenes consecutivas en las que un mismo punto es seguido correctamente Tiempo total para el data set Reduced

29 Reconocimiento de huellas 29  Asociación entre dos imágenes con detectores de puntos de interés (minutae) específicos Matching OK

30 Resumen 30  Cadenas de bits para la codificación de conjuntos  Librería BITSCAN (C++)  Codificación de grafos en memoria principal  Metadatos  Conjuntos de vértices y subgrafos inducidos  Aplicaciones de grafos simples no dirigidos  Análisis de redes  Modelo general de correspondencia con aplicaciones en diferentes campos de la ciencia.

31 Bibliografía relacionada 31  A new exact maximum clique algorithm for large sparse graphs, San Segundo et al., Computers & Operations Research, 2015.  A novel clique formulation for the visual feature matching problem, San Segundo et al., Applied Intelligence, 2015.  Modelling enzyme-ligand binding in drug discovery, Konc et al., Journal of Cheminformatics, 2015.  Parallel Maximum Clique Algorithms with Applications to Network Analysis, Rossi et al., SIAM Journal on Scientific Computing, 2015.  Robust Global Feature Based Data Association with a Sparse Bit Optimized Maximum Clique Algorithm. San Segundo, P., Rodriguez-Losada, D.; Transactions on Robotics, 2013.  An exact bit-parallel algorithm for the maximum clique problem. San Segundo et. al., Computers & Operations Research 2011.