On Minimal Sets to Destroy the $k$-Core in Random Networks - CEA - Commissariat à l’énergie atomique et aux énergies alternatives Accéder directement au contenu
Pré-Publication, Document De Travail Année : 2018

On Minimal Sets to Destroy the $k$-Core in Random Networks

Résumé

We study the problem of finding the smallest set of nodes in a network whose removal results in an empty $k$-core; where the $k$-core is the sub-network obtained after the iterative removal of all nodes of degree smaller than $k$. This problem is also known in the literature as finding the minimal contagious set. The main contribution of our work is an analysis of the performance of the recently introduced COREHD algorithm [Scientific Reports, 6, 37954 (2016)] on random networks taken from the configuration model via a set of deterministic differential equations. Our analyses provides upper bounds on the size of the minimal contagious set that improve over previously known bounds. Our second contribution is a new heuristic called the WEAK-NEIGHBOR algorithm that outperforms all currently known local methods in the regimes considered
Fichier principal
Vignette du fichier
1806.03134.pdf (1.39 Mo) Télécharger le fichier
Origine : Fichiers produits par l'(les) auteur(s)
Loading...

Dates et versions

cea-01933160 , version 1 (23-11-2018)

Identifiants

Citer

Christian Schmidt, Henry D. Pfister, Lenka Zdeborová. On Minimal Sets to Destroy the $k$-Core in Random Networks. 2018. ⟨cea-01933160⟩
42 Consultations
117 Téléchargements

Altmetric

Partager

Gmail Facebook X LinkedIn More