Majority Vote Community Detection with Dynamic Threshold and Bootstrapped Rounds

Detecção de comunidades é um problema fundamental em Ciência de Redes, onde os vértices de uma dada rede devem ser particionados de maneira que vértices num mesmo grupo sejam estruturalmente relacionados. Este problema encontra aplicações em diversas áreas e tem atraído muita atenção a seus aspectos práticos e teóricos. Algoritmos de propagação de rótulos (label propagation algorithms) se baseiam num procedimento que iterativamente atualiza a classificação de cada nó através do voto da maioria dos rótulos de comunidade de seus vizinhos. Estes algoritmos são conhecidos por serem simples e rápidos, e são muito utilizados em aplicações práticas. Nesta dissertação, estudamos variações de um algoritmo de propagação de rótulos aplicado ao problema da recuperação de duas comunidades intrínsecas a uma rede (majority vote algorithm, ou MVA), e propomos as seguintes novas contribuições: (i) um limiar dinâmico que generaliza o limiar fixo utilizado pelo MVA, (ii) um critério de parada que resolve o problema de oscilação das soluções produzidas por algoritmos de propagação de rótulos, e (iii) estratégias de bootstrapping que reutilizam soluções para alcançar melhores resultados. Estas modificações dão origem a novos algoritmos de propagação de rótulos que chamamos Global Average Majority (GAM) e Global Average Majority with Bootstrapping (GAMB). Finalmente, o comportamento e a perfomance dos novos algoritmos são avaliados através de experimentos numéricos com redes sintéticas geradas pelo stochastic block model (SBM) e redes do mundo real com comunidades conhecidas.