BBTA: Detecting communities incrementally from dynamic networks based on tracking of backbones and bridges

Dynamic community detection is an important issue in complex network research. Current algorithms are mostly based on the assumption that networks evolve smoothly; furthermore, many incremental algorithms handle similar network events in the same way regardless of the position the events occur in. Unfounded assumptions and the neglect of networks badly affect an algorithm's detection accuracy. To avoid these drawbacks, in this paper we propose an incremental algorithm, BBTA, to detect dynamic communities based on the tracking of backbones and bridges. We apply the backbones to reflect the critical edges of communities and the bridge edges to describe the key connections between communities, and use the network change rate to evaluate the extent of network changes. For small evolutions, we track the changes on community backbones or bridge edges that have led to broken or connected backbones, and merge historical communities with the connected backbones, or split a historical community with the broken backbones to obtain current communities. Experimental results on real and synthetic dynamic networks illustrate that the proposed algorithm has a higher accuracy and better performance than the current algorithms.

Automated summary

In this paper, an incremental algorithm called BBTA is proposed for detecting dynamic communities based on the tracking of backbones and bridges. The algorithm achieves higher accuracy and better performance by reflecting critical edges and key connections.