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

Area of Science:

• Network Science
• Statistical Physics
• Computer Science

Background:

• The k-core is a fundamental concept in network analysis, representing the dense inner core of a graph.
• Identifying the smallest set of nodes to remove for an empty k-core is crucial for understanding network resilience and contagion processes.
• This problem is also known as finding the minimal contagious set.

Purpose of the Study:

• To analyze the performance of the corehd algorithm on random graphs using deterministic differential equations.
• To establish improved upper bounds for the size of the minimal contagious set.
• To introduce and evaluate a new heuristic algorithm, the weak-neighbor algorithm.

Main Methods:

• Analysis of the corehd algorithm using deterministic differential equations on random graphs from the configuration model.
• Development and evaluation of the weak-neighbor algorithm.
• Comparison of the weak-neighbor algorithm with existing local methods.

Main Results:

• The study provides deterministic differential equation-based analyses of the corehd algorithm's performance.
• New upper bounds on the minimal contagious set size were derived, improving upon existing literature.
• The weak-neighbor algorithm demonstrated superior performance compared to current local methods in the studied regimes.

Conclusions:

• The corehd algorithm's performance on random graphs can be effectively analyzed using deterministic differential equations.
• The derived upper bounds offer significant improvements for estimating minimal contagious set sizes.
• The weak-neighbor algorithm presents a promising new heuristic for efficient network analysis and contagion studies.