An Increment-and-Density Based Community Detection Algorithm For Dynamic Networks

As an important method to describe and analyze the complicated system, complexnetwork has been fully studied on its physical meaning and mathematical characteristics.As we know, complicated system gradually changes with time, so the system states indifferent time can be sampled to form the complex dynamic networks concerned in thispaper. Community detection and evolutionary analysis of dynamic networks can behelpful for understanding the whole network’s characteristics and development trend,and so has great theoretical and practical significance.Dynamic networks usually consist of many consecutive static networks. Thetraditional methods need to detect the communities at each timestamp respectively, andthen analyze the relationship between communities of the adjacent timestamps.However, not only can those methods often produce significantly varied communitiesbetween different timestamps, but also lead to high time complexity. Incrementalapproach regards the communities of current timestamp as the input of the nexttimestamp to ensure that communities of adjacent timestamps have good consistencyand the algorithm is highly efficient. We propose an increment-and-density basedcommunity detection algorithm that adjust most increment related vertexes by analyzingtheir community affinity and deal with new vertexes by a local expansion based ondensity. Our method overcomes the deficiency that the general incremental approachesassume only a fixed number of communities and cannot produce new communitiesbetween different timestamps.We experimentally evaluate the performance of our method on synthetic data setsand real data sets. The results demonstrate that our algorithm achieves a higher accuracythan incremental approaches in the similar time complexity, so it can be used in thelarge-scale complex dynamic networks because of its excellent ability of communitydetection. In addition, out method obtains some special communities in real data sets byanalyzing the life cycle of vertexes in long-term conserved communities during theirevolution progress.