Approximation algorithms in graphs via sample complexity

Abstract

Resumo: Grafos de grande porte advém de diversos contextos em fenômenos naturais e sociais. Contudo, algoritmos que escalam em complexidade de tempo cúbica e até mesmo quadrática, quando executados nesses grafos, podem ser computacionalmente custosos na prática. Neste trabalho, apresentamos esquemas de aproximação aleatorizados de tempo próximo de linear para dois problemas em grafos onde não se tem algoritmo conhecido de tempo estritamente subcúbico no número de vértices. Adicionalmente, para um terceiro problema, também apresentamos um esquema de aproximação aleatorizado de tempo próximo de linear, mas para o caso em que o grafo de entrada tem diâmetro logarítmico. Os algoritmos propostos foram projetados utilizando análise de complexidade de amostra, teoria de dimensão Vapnik–Chervonenkis e médias de Rademacher. Seja G = (V ,E) um grafo com n = |V| e m = |E|. O primeiro problema tratado neste trabalho é o de centralidade de percolação em um grafo G direcionado com pesos reais não-negativos. Tal medida quantifica a importância de um vértice em um grafo que está passando por um processo de contágio. Neste trabalho, apresentamos um algorimo de aproximação de tempo O(mlog nlog diamV (G)) para estimar a centralidade de percolação de cada vértice de V, onde diamV (G) é número máximo de vértices em um caminho mínimo em G. O segundo problema é uma versão relaxada do problema de computar todos os caminhos mínimos entre todos os pares de vértices (APSP). Nesta versão, iremos computar todos os caminhos de G que tenham "centralidade" pelo menos e, para 0 < epsilon < 1 constante, medida esta que está relacionada a uma generalização da centralidade de intermediação. O algoritmo proposto executa em tempo O(m log n + (diamV (G))2). O terceiro problema é o de coeficiente de agrupamento local de cada vértice de um grafo G. Neste trabalho propomos um algoritmo para este problema que roda em tempo O(delta lg delta +m), onde delta é o grau máximo de um vértice de um grafo. Finalmente, neste trabalho também apresentamos algoritmos de aproximação para os problemas do conjunto dominante mínimo (MDS) e da cobertura por vértices mínima (MVC). Em ambos aplicamos técnicas probabilísticas, contudo não utilizamos análise de complexidade de amostra nestes casos. Para estes problemas, obtivemos limitantes mais justos lidando com o problema diretamente em um modelo específico de grafo aleatório lei de potência. Em particular, mostramos que o fator de aproximação esperado para o problema MDS é assintoticamente no máximo 9.14, e para o problema MVC, o fator é assintoticamente menor do que 2. Tais valores superam os limitantes conhecidos da literatura.

Abstract: Very large graphs arise in many contexts in natural and social phenomena. Algorithms with time complexity that scales in cubic or even in quadratic time in such graphs, although polynomial, can be computationally expensive in practice. In this thesis we present near-linear time randomized approximation schemes for two problems in graphs that are not known to admit algorithms that are truly subcubic in the number of vertices. Additionally, for a third problem, we also present a near-linear time randomized approximation scheme, but under the assumption that the input graph has logarithmic diameter, which is a very common scenario for large graphs in real-world applications. Our algorithms have been built using tools from sample complexity analysis, theory of Vapnik–Chervonenkis dimension, and Rademacher Averages. Let G = (V ,E) be a graph with n = |V| and m = |E|. The first problem we deal with is the percolation centrality in a directed weighted graph G, a measure that quantifies the importance of a vertex in a graph that is going through a contagious process. In this work we present an expected O(mlog nlog DiamV (G)) time approximation algorithm for the estimation of the percolation centrality for all vertices of G, wherein DiamV (G) is the maximum number of vertices in a shortest path in G. The second problem is a relaxed version of the all-pairs shortest paths (APSP) where we are interested in computing all shortest paths with "centrality" at least e, where 0 < epsilon < 1 is a constant. This centrality measure is a certain generalization of the betweenness centrality. We propose an algorithm for this relaxed problem that runs in O(m log n + (DiamV (G))2) time. The third problem corresponds to the computation of the local clustering coefficient of each vertex in a graph G, a measure that quantifies the degree in which a vertex is a part of a cluster in G. The algorithm that estimates the local clustering of each vertex in G runs in O(delta lg delta+m), wherein delta is the maximum degree of a vertex in a graph. Finally, we also propose approximation algorithms for the minimum dominating set (MDS) and the minimum vertex cover (MVC). However, for both problems we apply probabilistic techniques that are not related to sample complexity analysis, since we found tighter bounds for the approximation factor for these problems by attacking them directly using a particular random graph model for power-law graphs. In particular, we show that the expected approximation factor for the MDS problem is assymtotically at most 9.14, and for the MVC problem, the factor is assymptotically smaller than two. Such values outperforms the known bounds of the literature.