Discovering key users for defending network structural stability

The structural stability of a network reflects the ability of the network to maintain a sustainable service. As the leave of some users will significantly break network stability, it is critical to discover these key users for defending network stability. The model of k -core, a maximal subgraph whe...

Full description

Saved in:
Bibliographic Details
Published in:World wide web (Bussum) 2022-03, Vol.25 (2), p.679-701
Main Authors: Zhang, Fan, Xie, Jiadong, Wang, Kai, Yang, Shiyu, Jiang, Yu
Format: Article
Language:English
Subjects:
Algorithms
Apexes
Best practice
Computer Science
Database Management
Experiments
Graph theory
Greedy algorithms
Information Systems Applications (incl.Internet)
Operating Systems
Social networks
Special Issue on Large Scale Graph Data Analytics
Structural stability
World Wide Web
Citations: Items that this one cites
Items that cite this one
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary:The structural stability of a network reflects the ability of the network to maintain a sustainable service. As the leave of some users will significantly break network stability, it is critical to discover these key users for defending network stability. The model of k -core, a maximal subgraph where each vertex has at least k neighbors in the subgraph, is often used to measure the stability of a network. Besides, the coreness of a vertex, the largest k such that the k -core contains the vertex, is validated as the “best practice” for measuring the engagement of the vertex. In this paper, we propose and study the collapsed coreness problem: finding b vertices (users) s.t. the deletion of these vertices leads to the largest coreness loss (the total decrease of coreness from every vertex). We prove that the problem is NP-hard and hard to approximate. We show that the collapsed coreness is more effective and challenging than the existing models. An efficient greedy algorithm is proposed with powerful pruning rules. The algorithm is adapted to find the key users within a given time limit. Extensive experiments on 12 real-life graphs demonstrate the effectiveness of our model and the efficiency of the proposed method.
ISSN:1386-145X
1573-1413
DOI:10.1007/s11280-021-00905-3