Majority Vote Community Detection with Dynamic Threshold and Bootstrapped Rounds
Autores
|
6709 |
3005,753,2960
|
|
|
6710 |
3005,753,2960
|
|
|
6711 |
3005,753,2960
|
Informações:
Publicações do PESC
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.
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.