Skip to main content

Minimal sets to destroy the k-core in random networks.

Publication ,  Journal Article
Schmidt, C; Pfister, HD; Zdeborová, L
Published in: Physical review. E
February 2019

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 subnetwork 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 [Zdeborová, Zhang, and Zhou, Sci. Rep. 6, 37954 (2016)10.1038/srep37954] on random graphs taken from the configuration model via a set of deterministic differential equations. Our analyses provide upper bounds on the size of the minimal contagious set that improve over previously known bounds. Our second contribution is a heuristic called the weak-neighbor algorithm that outperforms all currently known local methods in the regimes considered.

Duke Scholars

Altmetric Attention Stats
Dimensions Citation Stats

Published In

Physical review. E

DOI

EISSN

2470-0053

ISSN

2470-0045

Publication Date

February 2019

Volume

99

Issue

2-1

Start / End Page

022310

Related Subject Headings

  • 51 Physical sciences
  • 49 Mathematical sciences
  • 40 Engineering
 

Citation

APA
Chicago
ICMJE
MLA
NLM
Schmidt, C., Pfister, H. D., & Zdeborová, L. (2019). Minimal sets to destroy the k-core in random networks. Physical Review. E, 99(2–1), 022310. https://doi.org/10.1103/physreve.99.022310
Schmidt, Christian, Henry D. Pfister, and Lenka Zdeborová. “Minimal sets to destroy the k-core in random networks.Physical Review. E 99, no. 2–1 (February 2019): 022310. https://doi.org/10.1103/physreve.99.022310.
Schmidt C, Pfister HD, Zdeborová L. Minimal sets to destroy the k-core in random networks. Physical review E. 2019 Feb;99(2–1):022310.
Schmidt, Christian, et al. “Minimal sets to destroy the k-core in random networks.Physical Review. E, vol. 99, no. 2–1, Feb. 2019, p. 022310. Epmc, doi:10.1103/physreve.99.022310.
Schmidt C, Pfister HD, Zdeborová L. Minimal sets to destroy the k-core in random networks. Physical review E. 2019 Feb;99(2–1):022310.

Published In

Physical review. E

DOI

EISSN

2470-0053

ISSN

2470-0045

Publication Date

February 2019

Volume

99

Issue

2-1

Start / End Page

022310

Related Subject Headings

  • 51 Physical sciences
  • 49 Mathematical sciences
  • 40 Engineering