Force-Based Incremental Algorithm for Mining Community Structure in Dynamic Network

Community structure is an important property of network.Being able to identify communities can provide invaluable help inexploiting and understanding both social and non-social networks.Several algorithms have been developed up till now. However, all thesealgorithms can work well only with small or moderate networks withvertexes of order 10^4. Besides, all the existing algorithms areoff-line and cannot work well with highly dynamic networks such asweb, in which web pages are updated frequently. When analready clustered network is updated, the entire network includingoriginal and incremental parts has to be recalculated, even though only slightchanges are involved. To address this problem, an incrementalalgorithm is proposed, which allows for mining community structure inlarge-scale and dynamic networks. Based on the community structuredetected previously, the algorithm takes little time to reclassify the entirenetwork including both the original and incremental parts. Furthermore,the algorithm is faster than most of the existing algorithms such asGirvan and Newman's algorithm and its improved versions. Also, thealgorithm can help to visualize these community structures in networkand provide a new approach to research on the evolving process of dynamicnetworks.