Incremental Graph Computation: Anchored Vertex Tracking in Dynamic Social Networks

User engagement has recently received significant attention in understanding the decay and expansion of communities in many online social networking platforms. Many user engagement studies have done to find a set of critical (anchored) users in the static social network. However, the social network is highly dynamic and its structure is continuously evolving. In this paper, we target a new research problem called Anchored Vertex Tracking (AVT) that aims to track the anchored users at each timestamp of evolving networks. To solve the AVT problem, we develop a greedy algorithm. Furthermore, we design an incremental algorithm to efficiently solve the AVT problem. Finally, we conduct extensive experiments to demonstrate the performance of our proposed algorithms.