Pruebas de hipótesis en la detección de comunidades de gráficas

Ponente(s): Marcos Torres Vivanco

Consideramos una gráfica aleatoria con N vértices y donde las aristas tienen la misma probabilidad p de aparecer. Una comunidad es una subgráfica de nuestra gráfica aleatoria que tiene mayor probabilidad de conectarse. Por ejemplo, en una red social una comunidad puede representar un grupo de amigos. El problema de detectar la presencia de una comunidad se puede plantear como un problema de pruebas de hipótesis. Se presentarán algunas estadísticas usadas para detectar una comunidad y se comparará la potencia de aquellas que se pueden realizar en tiempo polinomial usando aproximaciones de Monte Carlo.