| dc.description.abstract | Las medidas de centralidad han probado ser una herramienta valiosa para analizar datos en forma de grafos. Algunas aplicaciones sobre bases de datos de grafos, tales como grafos de conocimiento o motores de búsqueda en la web semántica, han sido propuestas últimamente. En esta área, las medidas de centralidad basadas en motivos han surgido como un acercamiento prometedor para entender medidas de centralidad en bases de datos de grafos y para definir una familia de nuevas medidas con propiedades teóricas deseables. No obstante, estas son difíciles de computar en general (i.e. #P-hard). En consecuencia, hasta ahora no existen estudios experimentales de dichas medidas en redes reales. En esta tesis nos embarcamos en el computo de medidas de centralidad basadas en motivos y en comprender cómo se comportan sobre redes reales. Para lograr este objetivo, comenzamos estudiando si es posible aproximar estas medidas. Así, presentamos nuevos resultados teóricos que confirman su dificultad de cómputo y aproximación. Debido a esto, perseguimos un camino diferente usando técnicas algorítmicas avanzadas y paralelización para superar las restricciones teóricas en un contexto práctico. Específicamente, presentamos un algoritmo empírico de parámetros fijos que tiene tiempo lineal sobre el tamaño del grafo, pero exponencial en su treewidth. Más aún, mostramos cómo paralelizar el algoritmo en una arquitectura de múltiples núcleos. De esta forma, presentamos una primera implementación de nuestro algoritmo, capaz de calcular centralidad basada en subgrafos en instancias de miles de nodos. Finalmente, comparamos los resultados con medidas de centralidad usadas en la literatura. Con todo, este trabajo constituye el primer estudio práctico de medidas basadas en motivos, sentando las bases para estudios futuros y
aplicaciones sobre datos en grafos. | |
