network_dismantling.edge_selectors

Edge Selectors Module.

This module provides algorithms specifically designed for selecting edges (connections) in networks, used for edge-based network dismantling strategies. Unlike node selectors, edge selectors focus on identifying and selecting edges that have the greatest impact on network connectivity.

Design Philosophy

Edge selectors are based on the following theoretical foundations: 1. Edge Betweenness Centrality: Identifying critical edges that act as “bridges” 2. Edge Weights: Considering connection strength impact on network functionality 3. Structural Holes Theory: Finding critical edges connecting different communities 4. Network Flow Theory: Identifying bottleneck edges affecting network transmission capacity

Application Scenarios

Network Types: - Transportation networks: Identifying critical roads and transportation hub connections - Communication networks: Finding core communication links and data transmission bottlenecks - Social networks: Discovering bridge relationships connecting different communities - Biological networks: Identifying critical protein-protein interactions

Dismantling Goals: - Minimize network connectivity - Maximize network segmentation effects - Maintain node integrity (only disconnect connections) - Simulate link failure impacts

Core Components

Abstract Base Class: - EdgeSelector: Base class for edge selectors

Defines standard select(G, num_elements) interface

Returns list of selected edges [(u1, v1), (u2, v2), …]

Supports both directed and undirected graphs

Concrete Implementations: The framework currently supports various edge selection algorithms:

Path Attack Algorithms: - PathAttackLPSelector: Linear Programming-based PATHATTACK for optimal edge cutting - PathAttackGreedySelector: Greedy-based PATHATTACK for efficient edge cutting - NaiveEdgeCutSelector: Baseline naive edge cutting algorithm - EigenScoreCutSelector: Eigen score-based edge cutting algorithm

Deep Learning Algorithms: - SHEARSelector: Deep reinforcement learning-based edge selection

Classical Algorithms: - Edge betweenness centrality selector - Edge weight selector - Random edge selector - Flow-based edge selector

Comparison with Node Selectors

Feature | Node Selectors | Edge Selectors |

|---------|—————-|----------------| | Removal Target | Nodes and all adjacent edges | Only specified edges | | Impact Degree | Aggressive, significant impact | Moderate, controllable impact | | Computational Complexity | Usually higher | Usually lower | | Use Cases | Individual failure simulation | Connection failure simulation | | Network Integrity | May create isolated nodes | Preserves all nodes |

Usage Examples

```python from network_dismantling.edge_selectors import EdgeSelector from network_dismantling.operators import EdgeRemovalOperator from network_dismantling import NetworkDismantler import networkx as nx

# Create test network G = nx.karate_club_graph()

# Custom edge selector example class EdgeBetweennessSelector(EdgeSelector):

def select(self, G, num_elements):
# Calculate edge betweenness centrality edge_betweenness = nx.edge_betweenness_centrality(G) # Sort by betweenness and select top num_elements edges sorted_edges = sorted(edge_betweenness.items(),

key=lambda x: x[1], reverse=True)

return [edge for edge, _ in sorted_edges[:num_elements]]

# Use edge selector for network dismantling edge_selector = EdgeBetweennessSelector() edge_operator = EdgeRemovalOperator()

dismantler = NetworkDismantler(: selector=edge_selector, operator=edge_operator

)

# Execute dismantling result_graph, removed_edges = dismantler.dismantle(G, num_elements=5) print(f”Removed edges: {removed_edges}”) print(f”Original edge count: {G.number_of_edges()}”) print(f”Remaining edge count: {result_graph.number_of_edges()}”) ```

Extension Guide

Creating new edge selectors requires inheriting from the EdgeSelector class:

```python from network_dismantling.edge_selectors import EdgeSelector import networkx as nx

class CustomEdgeSelector(EdgeSelector):

def __init__(self, weight_threshold=0.5):

self.weight_threshold = weight_threshold

def select(self, G, num_elements):

# Implement custom edge selection logic # Example: weight-based selection weighted_edges = [] for u, v, data in G.edges(data=True):

weight = data.get(‘weight’, 1.0) if weight > self.weight_threshold:

weighted_edges.append((u, v, weight))

# Sort by weight and return top num_elements edges weighted_edges.sort(key=lambda x: x[2], reverse=True) return [(u, v) for u, v, _ in weighted_edges[:num_elements]]

```

Performance Considerations

Computational Complexity: - Edge count is usually higher than node count: O(m) vs O(n), where m >> n - Edge selection algorithm complexity typically ranges from O(m) to O(m²) - For dense graphs, edge selection may be more time-consuming than node selection

Memory Usage: - Edge list storage requires more memory - Edge attributes (weights, types, etc.) increase memory overhead - Consider using generator patterns for large-scale edge sets

Optimization Recommendations: - For large-scale networks, consider sampling strategies - Use edge indexing to accelerate lookup operations - Cache intermediate calculation results (such as centrality metrics) - Parallelize independent edge evaluation computations

Classes

`EdgeSelector`	Abstract class for edge selectors.
`SHEARSelector`	SHEAR edge selector implementation.
`PathAttackLPSelector`	Linear Programming-based PATHATTACK edge selector.
`PathAttackGreedySelector`	Greedy-based PATHATTACK edge selector.
`EigenScoreCutSelector`	Eigen score based edge cutting selector.
`NaiveEdgeCutSelector`	Naive edge cutting selector.
`BPDH`	BPDH: Belief Propagation-guided High-order Dismantling.
`BPDH_Accurate`	More accurate BPDH implementation with actual k-core size testing.
`HigherOrderMetrics`	Utility class for computing higher-order structure metrics.