Community detections for large-scale real world networks have been more popular in social analytics. In particular, dynamically growing network analyses become important to find long-term trends and detect anomalies. In order to analyze such networks, we need to obtain many snapshots and apply same analytic methods to them. However, it is inefficient to extract communities from these whole newly generated networks with little differences every time, and then it is impossible to follow the network growths in the real time. We proposed an incremental community detection algorithm for high-volume graph streams. It is based on the top of a well-known batch-oriented algorithm named DEMON [1]. We also evaluated performance and precisions of our proposed incremental algorithm with real-world big networks with up to 410,236 vertices and 2,439,437 edges and computed in less than one second to detect communities in an incremental fashion — which achieves up to 107 times faster than the original algorithm without sacrificing accuracies.
Most networks will evolve with time instead of keeping unchanged in reality. Therefore, we proposed the incremental label propagation (ILP) algorithm to detect community structures in complex networks in realtime. ILP algorithm will only take the local changed vertexes into consideration. The computation time is greatly decreased, while vertex (edge) is changed. The algorithm will definitely converge for the original version of label propagation algorithm is converged. We also applied ILP to real-time community detection in a relationship network of online game.