Temporal analysis of large dynamic graphs

Abstract

The objective of this thesis is to provide a temporal analysis of the structural and interaction dynamics of large evolving graphs. In this thesis we propose new definitions of important graph metrics in order to include the temporal dimension of the dynamic graphs. We further extend the three important problems of data mining, in the temporal setting. The three problems that we propose are temporal graph summarization, temporal community search and temporal betweenness centrality. Additionally, we propose a distributed version of all our algorithms, that help our techniques to scale up to million vertices. We, finally, evaluate the validity of our methods in terms of efficiency and effectiveness with extensive experimentation on large-scale real-world graphs.

L’objectiu d’aquesta tesi és proporcionar una anàlisi temporal de l'evolució estructural i d’interacció de grans gràfics dinàmics. En aquesta tesi proposem noves definicions de mètriques de gràfiques importants per tal d’incloure la dimensió temporal dels gràfics dinàmics. Ampliem tres problemes importants de mineria de dades en gràfics per a un entorn temporal. Els tres problemes són el resum de gràfics temporals, la cerca temporal de comunitats i la centralitat temporal dels gràfics. A més, proposem una versió distribuïda de tots els nostres algoritmes, que ajuden a les nostres tècniques a escalar fins a milions de vèrtexs. Finalment, avaluem la validesa dels nostres mètodes en termes d’eficiència i eficàcia amb una àmplia experimentació en gràfics del món real a gran escala.

El objetivo de esta tesis es proporcionar un análisis temporal de las dinámicas estructurales y de interacción de grafos masivos dinámicos. Para esto proponemos nuevas definiciones de métricas en grafos importantes para incluir la dimensión temporal de los grafos dinámicos. Además, ampliamos tres problemas importantes de minería de datos en un contexto temporal. Ellos son los resúmenes de grafos temporales, la búsqueda de comunidades en un contexto temporal y la centralidad temporal en grafos. Además, proponemos una versión distribuida de todos nuestros algoritmos, que permiten que nuestras técnicas a escalar hasta millones de vértices. Finalmente, evaluamos la validez de nuestros métodos en términos de eficiencia y efectividad con extensos experimentos en gráfos de gran escala en el mundo real.