Incremental Graph Computation: Anchored Vertex Tracking in Dynamic Social Networks
- 17 August 2022
- journal article
- research article
- Published by Institute of Electrical and Electronics Engineers (IEEE) in IEEE Transactions on Knowledge and Data Engineering
- Vol. PP (10414347) , 1-14
Abstract
User engagement has recently received significant attention in understanding the decay and expansion of communities in many online social networking platforms. When a user chooses to leave a social networking platform, it may cause a cascading dropping out among her friends. In many scenarios, it would be a good idea to persuade critical users to stay active in the network and prevent such a cascade because critical users can have significant influence on user engagement of the whole network. Many user engagement studies have been conducted to find a set of critical (anchored) users in the static social network. However, social networks are highly dynamic and their structures are continuously evolving. In order to fully utilize the power of anchored users in evolving networks, existing studies have to mine multiple sets of anchored users at different times, which incurs an expensive computational cost. To better understand user engagement in evolving network, we target a new research problem called Anchored Vertex Tracking (AVT) in this paper, aiming to track the anchored users at each timestamp of evolving networks. Nonetheless, it is nontrivial to handle the AVT problem which we have proved to be NP-hard. To address the challenge, we develop a greedy algorithm inspired by the previous anchored $k$ -core study in the static networks. Furthermore, we design an incremental algorithm to efficiently solve the AVT problem by utilizing the smoothness of the network structure's evolution. The extensive experiments conducted on real and synthetic datasets demonstrate the performance of our proposed algorithms and the effectiveness in solving the AVT problem.
Keywords
All Related Versions
This publication has 39 references indexed in Scilit:
- From link-prediction in brain connectomes and protein interactomes to the local-community-paradigm in complex networksScientific Reports, 2013
- Structural diversity in social contagionProceedings of the National Academy of Sciences, 2012
- The Spread of Behavior in an Online Social Network ExperimentScience, 2010
- Identification of influential spreaders in complex networksNature Physics, 2010
- Origins of Homophily in an Evolving Social NetworkAmerican Journal of Sociology, 2009
- K-core decomposition of Internet graphs: hierarchies, self-similarity and measurement biasesNetworks and Heterogeneous Media, 2008
- A model of Internet topology usingk-shell decompositionProceedings of the National Academy of Sciences, 2007
- Empirical Analysis of an Evolving Social NetworkScience, 2006
- Clustering and preferential attachment in growing networksPhysical Review E, 2001
- A threshold of ln n for approximating set coverJournal of the ACM, 1998