pycnp 0.1.1

A high-performance Python solver for Critical Node Problems

PyCNP: An Open-Source Python Package for Critical Node Detection Problems

PyCNP is an open-source, high-performance Python solver for the Critical Node Problem (CNP) and Distance-based Critical Node Problem (DCNP).

The Critical Node Problem asks: which nodes should be removed from a network to minimize its connectivity while respecting a budget constraint? This problem has applications in:

• Network security - Identifying critical infrastructure nodes whose removal would most disrupt a network
• Epidemiology - Modeling disease spread by removing highly connected individuals (vaccination strategies)
• Social network analysis - Understanding information flow by identifying influential nodes
• Biological networks - Identifying critical proteins or genes in protein-protein interaction networks

PyCNP currently supports:

• Critical Node Problem (CNP) - Minimize pairwise connectivity in undirected graphs
• Distance-based Critical Node Problem (DCNP) - CNP variant with hop distance constraints
• Multiple search strategies - CBNS, CHNS, DLAS, and BCLS
• Multiple crossover operators - DBX, IRR, and RSC

The package provides a flexible Python interface backed by efficient C++ implementations.

Installation

PyCNP can be installed via pip:

pip install pycnp

To install the latest version from source:

pip install 'pycnp @ git+https://github.com/xuebo100/PyCNP'

For development installation:

git clone https://github.com/xuebo100/PyCNP.git
cd PyCNP
pip install -e .

See the installation guide for detailed requirements and instructions.

Quick Start

import pycnp

# Create a model and add nodes/edges
model = pycnp.Model()
for i in range(10):
    model.add_node(i)
model.add_edge(0, 1)
model.add_edge(1, 2)
model.add_edge(2, 3)

# Solve the problem
result = model.solve(
    problem_type="CNP",
    budget=3,
    stopping_criterion=pycnp.MaxRuntime(60),
    seed=42
)

print(f"Best solution: {result.best_solution}")
print(f"Objective value: {result.best_obj_value}")

See the examples for a more comprehensive introduction.

Key Features

Problem Types

• CNP (Critical Node Problem): The standard CNP on undirected graphs. The objective is to minimize pairwise connectivity by removing at most budget nodes.
• DCNP (Distance-based Critical Node Problem): An extension that introduces a hop distance constraint. Two nodes are only considered connected if they are within the specified hop_distance of each other.

Search Strategies

Strategy	Description	Best For
CBNS	Component-Based Neighborhood Search	General CNP instances
CHNS	Component-Based Hybrid Neighborhood Search	Balance of quality and speed
DLAS	Diversified Late Acceptance Search	When diversification is important
BCLS	Betweenness Centrality-based Late Acceptance Search	DCNP problems

Crossover Operators or Problem Reduction

Operator	Parents	Description
DBX	2	Double Backbone Based Crossover - preserves common nodes between parents
IRR	3	Inherit-Repair-Recombination - designed for DCNP
RSC	2	Reduce-Solve-Combine - can be used for both CNP and DCNP

Stopping Criteria

• MaxIterations - Stop after a fixed number of iterations
• MaxRuntime - Stop after a specified amount of time (seconds)
• NoImprovement - Stop if no improving solution is found

Documentation

The full documentation is available at https://xuebo100.github.io/PyCNP/.

Key resources:

• Introduction to CNP - Learn about the Critical Node Problem
• Installation - How to install PyCNP
• Core Concepts - Understand PyCNP's components
• Examples - Step-by-step examples
• API Reference - Detailed API documentation

Getting Help

If you have questions or need help:

1. Browse discussions
2. Open a new discussion thread for questions
3. Open a bug report for issues

When reporting bugs, please include:

• A minimal, reproducible example
• PyCNP version (run python -c 'import pycnp; print(pycnp.__version__)')
• Python version and operating system
• Any error messages or tracebacks

Contributing

Contributions are welcome! Please see our contributing guide for details.

Before starting, please discuss changes in a GitHub issue first.

How to Cite PyCNP

If you use PyCNP in your research, please cite the relevant papers:

@article{pycnp2026,
  title={PyCNP: An Open-Source Python Package for Critical Node Detection Problems},
  author={Yangming Zhou and Bo Xue and MengChu Zhou and Tieju Ma},
  year={2026},
}

License

PyCNP is licensed under the MIT License. See the LICENSE file for details.