Incremental Graph Computation: Anchored Vertex Tracking in Dynamic Social Networks

Authors:

Abstract
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.