Majority vote community detection with dynamic threshold and bootstrapped rounds

Abstract

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.