Towards the computation of motif-based centrality measures over real-world networks

Towards the computation of motif-based centrality measures over real-world networks

Medidas de centralidad

Algoritmos en grafos

Complejidad de conteo

Motivos en grafos

Conteo de subgrafos

620

Ingeniería

Tesis (Master of Science in Engineering)--Pontificia Universidad Católica de Chile, 2023

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.

Bugedo Bugedo, Sebastián

2023-09-01T21:35:31Z

2023-09-01T21:35:31Z

2023

Riveros Jaeger, Cristian

Pontificia Universidad Católica de Chile. Escuela de Ingeniería

acceso abierto

x, 73 páginas

application/pdf

en

tesis de maestría

10.7764/tesisUC/ING/74564

https://doi.org/10.7764/tesisUC/ING/74564

https://repositorio.uc.cl/handle/11534/74564