CS Paper Radar

On the Probability of Network States with Gaussian Connectivity Functions

Amy S. Inwood, Peter J. Smith, Pawel Dmochowski, Carl P. Dettmann, Justin P. Coon, Michail Matthaiou

eess.SP math.PR ·submitted 2026-08-18 10:37 UTC · v1
published

Abstract

In this paper, we consider the connectivity of a random network of N mobile devices in three dimensions (3D), where the location of each device or node has a Gaussian distribution in each dimension. For each pair of nodes, the probability of connectivity is related to the nodes' separation by a Gaussian connectivity function. The fundamental analytical tool for studying such systems is the probability of a given network state, derived and expressed in terms of its graph Laplacian. Leveraging this result, we obtain results for the connectivity of small networks, the probability of a complete network (where all nodes are connected to all other nodes), and the probability of an isolated node, which gives an approximation to the connectivity probability of larger networks. The general results are then simplified for special cases and limiting scenarios.

Comment
Accepted to IEEE GLOBECOM 2026

Closest papers

Nearest neighbours by meaning across the whole index.

Spectral Embeddings of Degree-$α$ Laplacians in Random Dot Product Graphs

cs.LG stat.ML ·2026-08-11 ·John Park, Ning Hao
theory similarity 0.55
Abstract

Spectral clustering methods for network data are commonly based on a few matrix representations, such as the adjacency matrix and the symmetric Laplacian. We study a continuum of degree-normalized spectral embeddings that includes these commonly used choices as special cases. Under a random dot product graph model, we establish a row-wise central limit theorem for this family of embeddings. The result provides an explicit description of how degree normalization affects both population geometry and the local uncertainty of embedded nodes. We use the limiting distributions to compare different normalizations in two-community stochastic block models through a projected-Gaussian Bayes-error diagnostic. These comparisons show that no single normalization is uniformly preferred. Instead, the favored normalization depends on network density, community imbalance, and block-probability structure. Typically, stronger normalization is favored in lower-density or more imbalanced settings. These results provide a unified distributional understanding of when and why alternative normalizations may improve spectral clustering.

0.04

Shortest-path percolation and structural robustness of quantum internet networks

cs.SI physics.soc-phcond-mat.stat-mechquant-ph ·2026-11-16 ·Victor H. F. Francheto, Thomas Peron
code/data similarity 0.55
Abstract · 20 pages, 18 figures. Code available at https://github.com/VictorFrancheto/shortest-path-percolation-implementation

We study shortest-path percolation on spatial networks that model the quantum internet based on optical fibers. In this process, the removal of paths describes the consumption of the entangled links used for communication. We compare finite and unrestricted path-length bounds for networks whose average degree either increases with system size or remains approximately constant. We show that networks become more robust as the average degree increases, whereas networks with approximately constant average degree exhibit a data collapse for the fixed finite bounds considered. Using Monte Carlo sampling of the shortest-path-length distribution, we estimate an equivalent path cost, a finite bound that approximately reproduces the degradation of the network in the unrestricted case. For networks with fixed average degree, this cost grows approximately as the square root of the number of nodes. Increasing the bound beyond this value requires additional computation time without appreciably changing the percolation dynamics. As a complementary result, for Erdős-Rényi random networks, we find an empirical relation between the initial average degree and the approximately common crossing point of the percolation curves for different path-length bounds.

0.39

Multiplicative Path Weights in Networks: From Katz Connectivity to Mean First-Passage Times

cs.SI math.PRphysics.soc-ph ·2026-10-15 ·Robbert van der Burg, Bernd Heidergott, Thao Le, Alessandro Zocca
similarity 0.54
Abstract

Signal dispersion, stress propagation in interbank systems, and transmission probabilities in epidemic and reliability models are all captured by studying paths on directed graphs where the path weight is defined as the product of its edge weights. Connectivity in such networks is naturally quantified by aggregating these multiplicative path weights across nodes. This paper provides a comprehensive treatise on connectivity and ranking measures based on multiplicative path weights. We demonstrate how standard all-path connectivity, such as the standard Katz centrality, can be extended beyond its classical spectral threshold. In addition, we derive closed-form expressions for connectivity based on first-hit paths and introduce a new version of Katz centrality. Furthermore, for random edge weights, we derive resolvent-based expressions for the first and second moments, alongside variance bounds, under a path-indexed coupling framework. Finite irreducible Markov chains are a subclass of the models studied, and we show that the scaled matrix of first-hit path probabilities is the probability-generating function for first-passage and return times, and that differentiation yields the classical first-passage times. Numerical examples illustrate the application of our results in a variety of settings.

0.23

A Survey of Typical-Cell Volume Distributions in Poisson--Voronoi and Poisson--Delaunay Tessellations: Analytical Theory, High-Dimensional Limits, and Wireless Applications

cs.IT ·2026-08-12 ·Minghua Xia, Tian Shi, Wenkunn Wen
publishedsurvey similarity 0.52
Abstract · 23 pages, 3 figures, 3 tables, Accepted for publication in IEEE Access

Random spatial tessellations generated by point processes provide fundamental models for proximity, space partitioning, and local geometry in stochastic systems. Poisson--Voronoi and Poisson--Delaunay tessellations induced by homogeneous Poisson point processes form a canonical dual pair used in stochastic geometry, computational geometry, spatial statistics, and wireless-network analysis. Their typical-cell volume distributions provide important geometric inputs for modeling coverage, traffic load, clustering, connectivity, and other system characteristics. Despite extensive study, the literature remains analytically asymmetric. For Poisson--Voronoi cell volumes, exact integral representations exist in certain planar settings, while a recent scale--shape factorization provides an exact general-dimensional representation with conditional Gamma structure. However, the normalized shape laws and unbounded facet-count mixture remain implicit, and tractable unconditional closed-form distributions are unavailable. Practical modeling therefore relies largely on simulation, moment characterizations, and empirical approximations. By contrast, Poisson--Delaunay simplex volumes admit dimension-explicit PDFs, CDFs, and moment formulas derived through Mellin-transform analysis and Meijer's \(G\)-function representations. Motivated by this contrast, this paper surveys typical-cell volume distributions in Poisson--Voronoi and Poisson--Delaunay tessellations. We review the main analytical methods, synthesize exact and approximate results, summarize emerging high-dimensional limits, and discuss wireless-network applications, including load modeling, cooperative transmission, and three-dimensional architectures. We also identify open problems concerning unconditional Poisson--Voronoi distributions, non-Poisson spatial models, data-driven geometric inference, and dimension-aware network modeling.

0.62

Learning Random Geometric Graphs Drawn in Probabilistic Metric Spaces

cs.LG stat.MLstat.AP ·2026-08-19 ·Dalia Chakrabarty, Kangrui Wang, Chuqiao Zhang, Ye Liu
similarity 0.52
Abstract

We present a new data-driven learning of a Random Geometric Graph (RGG) of a multivariate dataset, where the graph is drawn in a probabilistic metric space. This graph learning works for generic datasets, irrespective of the type of the observables; their probability distributions; or size of the data. We identify a metric of the space that the graph is drawn in, as a probability distribution of a random variable that we introduce, namely, a variable that represents the disparity between the connectedness of two vertices of the graph, and the correlation between the two random variables that are attached to the respective vertex. It is the closed-form {\it{cdf}} of this disparity variable that we advance as the distance function of the host space of the learnt RGG, such that the edge exists between any two nodes, if this inter-nodal distance falls short of a chosen cutoff probability. Drawing the RGG in this probabilistic space leads to the graph being an Soft RGG, such that any edge - if it exists - exists with an identified probability. We forward a simple Rejection Sampling-based technique for learning the probability of any edge. The expected degree distribution of a vertex of this RGG is identified as local, and dependent on the inter-observable correlation matrix. If said correlation matrix is not known, it can be learnt given the data, using its closed-form posterior probability density function, that we forward. We illustrate our graph learning method by learning multiple RGGs of highly multivariate real datasets.

0.27

Joint Independence Testing for Latent Position Random Graphs

cs.LG stat.MLcs.SI ·2026-10-25 ·Xiaoyi Wen, Zoltan Szabo
theory similarity 0.51
Abstract

Kernel techniques are among the most powerful methods in data science and statistics. One of the key properties of kernels contributing to their numerous successful applications is that the associated reproducing kernel Hilbert space is expressive enough to encode probability distributions without loss of information or to capture the joint independence of $M\ge 2$ random variables, under mild conditions. Computationally, these measures (i) rely on the so-called Gram matrix which contains the pairwise similarity of sample points, and (ii) converge at a rate $O \left(n^{-\frac{1}{2}}\right)$, where $n$ denotes the sample size. We focus on measuring the independence of latent position random graphs (LPRGs), a model widely-applied for instance in neuroscience, sociology, and epidemiology. In LPRGs a latent representation is associated to each node. The similarity of these representations (meant via a kernel) determines whether two nodes are connected, making the Gram matrices only implicitly observable and the estimation challenging. Despite the fundamental importance of quantifying the independence of $M$ LPRGs, very little is known about the solution of this problem; existing techniques are restricted to $M=2$ components and only guarantee consistency without rates. In this work, (i) we define an independence measure called graph Hilbert-Schmidt independence criterion (GHSIC) for $M\ge 2$ LPRGs, (ii) we prove that it can be estimated at a rate $\tilde{O}\left(n^{-\frac{1}{3}}\right)$ relying on spectral decomposition of adjacency matrices, (iii) without the need to choose kernels and their hyperparameters. Numerical experiments demonstrate the effectiveness of the proposed GHSIC estimator both on synthetic examples and in the analysis of brain functional connectivity subnetworks in natural language perception.

0.19

Spectral Fingerprints of Street-Network Morphology: A Size-Adjusted Graph-Laplacian Descriptor of Urban Fabric

cs.SI physics.soc-ph ·2026-08-17 ·Piotr C. Kaminski
similarity 0.50
Abstract · 18 pages, 7 figures. Under review at Journal of Complex Networks (Oxford University Press)

Decades of space-syntax research have established that the topology of the street network conditions movement, co-presence and urban activity. The standard vocabulary for this -- integration, choice and connectivity -- summarises each street's position as a scalar centrality, yet two streets with identical centrality can sit in radically different morphological fabric. We introduce a compact, comparable, machine-learning-ready encoding of that local fabric: the spectral fingerprint, a fixed-dimensional kernel-density representation of the graph-Laplacian eigenvalue distribution of each node's k-hop ego subgraph, computed on the COINS dual graph of the street network. From it we derive two interpretable scalar readouts: the Mesh Index (MI), a normalised spectral entropy, and the Connectivity Resilience Index (CRI), the algebraic connectivity (Fiedler value). Both are corrected for an ego-subgraph-size confound that dominates raw spectral statistics. Applied to the full street network of Poznan, Poland (1,908 continuity-based strokes), the descriptor is robust to its encoding hyperparameters (spectral resolution and kernel bandwidth; Spearman rho >= 0.98) while remaining scale-dependent in its neighbourhood radius. The size adjustment leaves the Mesh Index near-orthogonal to integration (r = 0.06), carrying information classical centrality does not. The fingerprint separates morphological tissue types without supervision, and the Mesh Index is associated with the functional diversity of street-adjacent activity at the neighbourhood scale (r ~ 0.19, on open OpenStreetMap data). We delineate the method's scope honestly: it characterises what kind of activity a street's position affords, not the price that activity commands. It offers an information-theoretic morphological descriptor that complements space syntax and is directly consumable by modern graph-learning pipelines.

0.25

Detecting Random Geometric Graphs with General Kernel

cs.IT math.STmath.PR ·2026-10-08 ·Dong Huang, Shuangping Li
similarity 0.50
Abstract

We study testing a random geometric graph with a fixed kernel against an Erdős-Rényi graph with the same edge density. Under the null hypothesis, the graph has $n$ vertices and independent edges with probability $p$. Under the alternative hypothesis, latent points $X_1,\ldots,X_n$ are independent and uniform on $\mathbb{S}^{d-1}$, and edges are conditionally independent with probabilities $K(\langle X_i,X_j\rangle)$, where $p=\mathbb{E}[K(\langle X_1,X_2\rangle)]$. The goal is to determine a critical dimension $d_\star = d_\star(n,K)$: the total variation distance between the two graph laws tends to one for $d\ll d_\star$ and to zero for $d\gg d_\star$. For dense graphs, [BDER16] established $d_\star\asymp n^3$ for hard threshold kernels, whereas [MWX26] proved $d_\star\asymp n^{3/4}$ for smooth kernels with $K'(0)\ne0$. We connect these results by characterizing the detection thresholds for kernels that need not be differentiable at zero. We also determine the thresholds for smooth kernels whose first nonzero derivative at zero has finite order greater than one. Throughout these classes, signed triangle or quadrilateral counts attain the optimal detection threshold. For certain nondifferentiable kernels, quadrilateral counts are optimal while triangle counts are suboptimal.

0.30