Adaptive Curvature-Guided Node Sampling (ACNS) for Complex Networks: A Novel Geometric Approach to Structure-Preserving Subgraph Extraction
Vivek Kumar Gupta *
Department of Mathematics, Chas College, Chas, Jharkhand, India.
*Author to whom correspondence should be addressed.
Abstract
Node sampling in complex networks is a basic challenge in network science, with applications in graph neural network training, epidemiology, and social network analysis. Current approaches, such as random walk methods, forest fires, and Metropolis-Hastings random walk (MHRW), are generally topology-agnostic. They rely on local degree or adjacency matrix information but do not leverage the geometric properties of the network, especially the boundaries and interiors of communities. In this paper, we introduce Adaptive Curvature-Guided Node Sampling (ACNS), a new node sampling approach that uses a light-weight approximation of the Ollivier-Ricci edge curvature to score and sample nodes based on the geometric stress landscape of the network. Each node is assigned a compound score that balances its contribution as a community boundary node (negative curvature region) and a cluster-core node (positive curvature region), controlled by a single interpretable parameter β ∈ [0, 1]. A neighbor-decay diversity mechanism prevents spatial clustering of sampled nodes, thus ensuring network coverage. Experiments on four standard network models, Karate Club, Barab´asi-Albert, Erd˝os-R´enyi, and Watts-Strogatz, show that ACNS preserves community structure significantly better than all baselines, with a 6–16% improvement in NMI, while remaining computationally efficient with a complexity of O(|E|). We offer a completely documented open-source Python code for easy reproducibility.
Keywords: Network sampling, graph theory, Ollivier-Ricci curvature, community detection, complex networks, graph neural networks