An efficient and fast algorithm for community detection based on node role analysis

The community structure of networks provides a comprehensive insight into their organizational structures and functional behaviors. Label propagation is one of the most commonly adopted community detection algorithm with nearly linear time complexity. It ignores the difference between nodes when breaking ties, leading to poor stability and the occurrence of the monster community. We note that different community-oriented node roles impact the label propagation in different ways. In this paper, we propose a role-based label propagation algorithm (roLPA), in which the heuristics with regard to community-oriented node role were used. We have evaluated the proposed algorithm on both real and artificial networks. The result shows that roLPA outperforms other state-of-the-art community detection algorithms.