Bloom: A stochastic growth-based fast method of community detection in networks

Networks are characterized by a variety of topological features and dynamics. Classifying nodes into communities, community structure, is important when exploring networks. This paper explores the community detection metric called modularity. The theoretical definitions of modularity are connected with intuitive insights into the compositions of communities. Local modularity costs/benefits are explored and an efficient stochastic algorithm, Bloom, is introduced, based on growing communities using local improvement measures. Three extensions of Bloom are presented that build upon the basic version. A numerical analysis compares Bloom with the popular fast-greedy algorithm and demonstrates the successful performance of the three modifications of Bloom.

► Modularity as a measure of community detection in complex networks. ► We provide theoretical insights to explain experimental observations. ► We introduce a fast stochastic partitioning heuristic based on growing communities. ► This heuristic offers insight into the fuzziness of the communities. ► Modifications of the heuristic outperform popular performance methods.