Anchored coreness: efficient reinforcement of social networks

作     者：Linghu, Qingyuan Zhang, Fan Lin, Xuemin Zhang, Wenjie Zhang, Ying 

作者机构：Univ New South Wales Sydney NSW Australia Guangzhou Univ Guangzhou Peoples R China Univ Technol Sydney Ctr AI Sydney NSW Australia 

出 版 物：《VLDB JOURNAL》 (国际大型数据库杂志)

年 卷 期：2022年第31卷第2期

页      面：227-252页

核心收录：

学科分类：08[工学] 0812[工学-计算机科学与技术（可授工学、理学学位）] 

基　　金：ARC [DP200101338, DP210101393, DP200101116, DP180103096] NSFC62002073 FT170100128 Australian Research Council [FT170100128] Funding Source: Australian Research Council 

主　　题：Social network User engagement Network stability Core decomposition Distributed algorithm 

摘      要：The stability of a social network has been widely studied as an important indicator for both the network holders and the participants. Existing works on reinforcing networks focus on a local view, e.g., the anchored k-core problem aims to enlarge the size of the k-core with a fixed input k. Nevertheless, it is more promising to reinforce a social network in a global manner: considering the engagement of every user (vertex) in the network. Since the coreness of a user has been validated as the best practice for capturing user engagement, we propose and study the anchored coreness problem in this paper: anchoring a small number of vertices to maximize the coreness gain (the total increment of coreness) of all the vertices in the network. We prove the problem is NP-hard and show it is more challenging than the existing local-view problems. An efficient greedy algorithm is proposed with novel techniques on pruning search space and reusing the intermediate results. The algorithm is also extended to distributed environment with a novel graph partition strategy to ensure the computing independency of each machine. Extensive experiments on real-life data demonstrate that our model is effective for reinforcing social networks and our algorithms are efficient.