Dalaijargal Purevusren

Attention Mechanisms in Physics-Inspired Graph Neural Networks for the Max-Cut Problem

Categories Combinatorial Optimization, Graphs and Matroids, Network Optimization Tags , , ,

Physics-Inspired Graph Neural Networks (PI-GNNs) reformulate MAX-CUT as QUBO energy minimization, training a GNN to produce soft binary node assignments without labeled data. The baseline PI-GCN uses static, degree-normalized aggregation, while its attention-augmented counterpart PI-GAT—built on GATv2—introduces additional hyperparameters whose effects remain uncharacterized. This paper addresses that gap through controlled experiments on five Gset benchmark … Read more

Scalable heuristic algorithm for identifying critical nodes in networks

Categories Combinatorial Optimization, Graphs and Matroids, Network Optimization

This paper presents two heuristic algorithms for the distance-based critical node problem (DCNP) that finds k nodes whose removal minimizes the pairwise connection within D hops in the remaining network. The structural properties of the complex networks have not yet been extensively addressed in the literature. Specifically, the community structure of complex networks needs to … Read more

Efficient heuristic algorithm for identifying critical nodes in planar networks

Categories Combinatorial Optimization, Network Optimization Tags , , , ,

This paper presents a new method for identifying critical nodes in planar networks. We propose an efficient method to evaluate the quality of solutions by using special properties of planar networks. It enables us to develop a computationally efficient heuristic algorithm for the problem. The proposed algorithm assisted on randomly generated planar networks. The experimental … Read more