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.
Jingyong and Hongsheng proposed an incremental algorithm based on growing social networks considering that most communities tended to evolve gradually over time @cite_10 . They used computer-generated data sets and internet peer-to-peer network data with 10,876 vertices and 39,994 edges for their experiments. Compared with RI (based on Radicci method) and IC (finding nodes that are connected with increments: almost same as this method), the computation time was almost same as the IC method, and better than the other methods especially increasing the total number of vertices.
@cite_10
2157962422
Most existing community detection methods ignored the dynamic nature, a key property of social networks and these methods often lead to unreasonable divisions when faced with dynamic environments. Although there have been several dynamic community detection algorithms, low accuracy and low performing are still two challenging problems to be solved. In order to solve above problems, we proposed a new algorithm based on incremental analysis to mine communities in dynamic social networks. Extensive experimental results demonstrate the performance of our propose algorithm.