Dissertação
Majority vote community detection with dynamic threshold and bootstrapped rounds
Detecção de comunidades através do voto da maioria com limiar dinâmico e rodadas bootstrap
Autor
Sales, Guilherme da Costa
Institución
Resumen
Community detection is a fundamental problem in network science, where the
vertices of a given network are to be partitioned such that vertices in the same group
are structurally related. This problem finds applications in a wide range of areas
and has attracted much attention towards both its theoretical and practical aspects.
Label propagation algorithms are based on a procedure that iteratively updates the
classification of each node by a majority vote of its neighbors’ community labels.
These algorithms are known to be simple and fast, and are widely used in practical
applications. In this dissertation, we study variations of a label propagation algorithm applied to the problem of recovering two communities embedded in a network
(majority vote algorithm, or MVA), and propose the following new contributions:
(i) a dynamic threshold that generalizes the fixed threshold used by the majority
vote algorithm, (ii) a stopping criterion that solves the oscillation problem displayed
by the solutions produced by label propagation, and (iii) bootstrapping strategies
that re-utilize solutions to achieve better results. These modifications give rise to
new label propagation algorithms which we call Global Average Majority (GAM)
and Global Average Majority with Bootstrapping (GAMB). Finally, the behavior
and performance of the new algorithms are evaluated by numerical experiments with
synthetic networks generated by the stochastic block model (SBM) and real world
networks with known communities. Detec¸c˜ao de comunidades ´e um problema fundamental em Ciˆencia de Redes,
onde os v´ertices de uma dada rede devem ser particionados de maneira que v´ertices
num mesmo grupo sejam estruturalmente relacionados. Este problema encontra
aplica¸c˜oes em diversas ´areas e tem atra´ıdo muita aten¸c˜ao a seus aspectos pr´aticos
e te´oricos. Algoritmos de propaga¸c˜ao de r´otulos (label propagation algorithms) se
baseiam num procedimento que iterativamente atualiza a classifica¸c˜ao de cada n´o
atrav´es do voto da maioria dos r´otulos de comunidade de seus vizinhos. Estes algoritmos s˜ao conhecidos por serem simples e r´apidos, e s˜ao muito utilizados em aplica¸coes
pr´aticas. Nesta disserta¸c˜ao, estudamos varia¸c˜oes de um algoritmo de propaga¸c˜ao de
r´otulos aplicado ao problema da recupera¸c˜ao de duas comunidades intr´ınsecas a
uma rede (majority vote algorithm, ou MVA), e propomos as seguintes novas contribui¸c˜oes: (i) um limiar dinˆamico que generaliza o limiar fixo utilizado pelo MVA, (ii)
um crit´erio de parada que resolve o problema de oscila¸c˜ao das solu¸c˜oes produzidas
por algoritmos de propaga¸c˜ao de r´otulos, e (iii) estrat´egias de bootstrapping que reutilizam solu¸c˜oes para alcan¸car melhores resultados. Estas modifica¸c˜oes d˜ao origem
a novos algoritmos de propaga¸c˜ao de r´otulos que chamamos Global Average Majority (GAM) e Global Average Majority with Bootstrapping (GAMB). Finalmente, o
comportamento e a perfomance dos novos algoritmos s˜ao avaliados atrav´es de experimentos num´ericos com redes sint´eticas geradas pelo stochastic block model (SBM)
e redes do mundo real com comunidades conhecidas.