Characterizing spatial networks using β-skeletons

Most classic graph measures used by network science were designed to be applicable to arbitrary, generic graphs. However, the nodes of some real-world networks exist in physical space, with only nearby nodes being connected. This strongly constrains their possible connectivity structures, which renders many classic graph measures uninformative, and of limited use for classification. This is even more true in networks where only direct spatial neighbours are connected, and long-range connections are completely missing. Examples include various transport networks in biological organisms (such as vasculature), networks of streets, or fungal networks. In all these cases, node locations almost completely determine connectivity. We propose a novel approach to characterizing such networks through the concept of β-skeletons, a family of parametrized proximity graphs that captures spatial neighbour relations very well. By constructing a sequence of β-skeletons for the node locations of empirical spatial networks, we can characterize the local geometry of their node arrangements, and study how this influences their network structure. We demonstrate the method on several biological datasets.