Networks with nearly identical degree distributions can place their hubs in sharply different neighborhoods. We develop a model diagnostic based on the mean degree of the neighbors of a degree-$k$ vertex. Under rank-one inhomogeneous random graphs, this statistic has degree-invariant centering and $k^{-1/2}$ fluctuations. Under non-rank-one kernels, posterior uncertainty about the root type can instead determine both centering and scale. Under linear preferential attachment, the statistic grows as $(m+\delta)\log k$. We turn these model-specific limits into goodness-of-fit tests for specified sparse-graph nulls and a weighted log-degree slope test for residual hub-neighborhood trends. Simulations evaluate null calibration, degree-distribution misspecification, and power against degree-matched preferential-attachment alternatives. Applications to high-school contact and arXiv coauthorship networks show that the method separates level misspecification from disassortative and positive residual trends. Reddit interaction networks provide a further appendix example.
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.
We prove recurrence criteria for inhomogeneous long-range percolation in dimensions one and two. In dimension one, recurrence follows from a purely geometric scarcity condition: long edges eventually disappear on exponential scales. This applies to weight-dependent random connection models and related one-dimensional spatial scale-free graphs whenever the standard strong-decay long-edge estimate holds. In dimension two, we combine the linear chemical-distance estimate of L\"uchtrath with an area-order bound on the degree measure. Graph-distance layers in exponentially separated bands then give the required Nash-Williams cutsets for planar random geometric graphs satisfying the polynomial mixing and long-edge estimates [J. Theoret. Probab. 39 (2026), Paper No. 12]. As a concrete consequence, every connected component of the two-dimensional weight-dependent random connection model with interpolation kernel is recurrent throughout the strong-decay region $\delta>2$, $\gamma<1-\frac{1}{\delta}$, and $\alpha<1-\gamma$.
Johannes Bäumler, Lukas Lüchtrath, Christian Mönch· 0 citations
Spatially embedded directed networks, such as airline networks, often exhibit simultaneous high activity at nearby nodes. Preferential attachment (PA) explains hub dominance. We extend it to spatial co-movement through a directed PA model whose out- and in-node weights follow temporally persistent Gaussian-process lognormal fields. Under sublinear PA, out-degree proportions converge to explicit normalized powered weights, whereas self-loop exclusion yields a coupled in-degree limit. We derive a strictly concave inverse that recovers the in-weights from terminal degree proportions. For ordered network histories, we develop a minorization-maximization (MM) weight estimator and profile likelihood for the PA exponent; temporal pre-whitening and a spatial quasi-likelihood estimate the latent covariance. Simulations verify transmission of distance-decaying dependence and show how random segment volume creates a distance-independent common mode in raw degrees. An analysis of U.S. domestic flights (2015-2019) separates network-wide volume variation from a short-range spatial component. An observed-volume reconstruction reproduces the raw-degree common mode, and the fitted field yields an exploratory co-exceedance transition scale of roughly 150 km. A per-carrier analysis of European air traffic also reveals the same decomposition.
We study the spectrum of the adjacency matrix $A_n$ of directed inhomogeneous random graphs on $n$ vertices. We assume that $A_n$ has independent entries and diverging average degree scale $s_n$. This framework includes, as special cases, the directed Chung--Lu random graph and directed stochastic block models. Assuming boundedness of the variance profile and that $s_n$ diverges faster than a suitable logarithmic function of $n$, we show that the rank-one Chung--Lu model satisfies a non-homogeneous version of the circular law, which in some situations allows for an explicit expression. Moreover, under mild conditions, we identify the asymptotic singular value distribution using tools from free probability. Finally, for finite-rank directed models, we prove the existence of eigenvalues outside the bulk and establish their joint Gaussian fluctuations at the scale $\sqrt{s_n/n}$, with an explicit covariance matrix. These results extend the theory of spectral outliers and their fluctuations to directed inhomogeneous random graphs.
Centrality measures are defined for simple graphs -- directed, undirected, weighted or unweighted. Attributed graphs have to be reduced to simple graphs for computing centrality measures. However, when applications with multiple types of relationships are modeled using multilayer networks (MLNs), simple graph algorithms cannot be directly used. Existing approaches typically analyze MLNs by aggregating layers of an MLN into a single graph, which results in the loss of structural and semantic information. The semantic information loss can be more pronounced particularly, in weighted networks. This work focuses on computing degree centrality in weighted homogeneous multilayer networks (HoMLNs) using a decoupling-based framework. The framework performs independent layer-wise analysis on MLNs without reducing them to simple graphs. The decoupling approach allows use of exiting algorithms for each layer and uses minimal information from individual layers for computing degree centrality of HoMLNs. We propose heuristic-based algorithms that strike a balance between accuracy and efficiency. The proposed methods are evaluated against ground truth (GT) results obtained using Boolean OR aggregation and naive baselines. Experimental results on both synthetic and real-world HoMLN datasets demonstrate that the heuristics achieve accuracy comparable to the ground truth while significantly improving computational efficiency, thereby establishing the scalability and effectiveness of the HoMLN algorithms developed using the decoupling approach.
A. Ayowole-Obi, Abhishek Santra, Sharma Chakravarthy· 0 citations
The Ramsey community number $r_\kappa$ is the smallest network size at which a graph is better described by a partition into communities than by no partition, under a prescribed detection rule. On a scale-free graph this question is confounded: a block model can split the network merely to absorb its degree distribution. I compute $r_\kappa$ analytically for the deterministic pseudofractal scale-free web of Dorogovtsev, Goltsev, and Mendes, separating genuine community structure from degree heterogeneity with two closed-form detection rules. Under a plain Bernoulli stochastic block model, the web's natural recursive bipartition is unpreferred while small and breaks at $r_\kappa=1095$ nodes, with a log-evidence growing as $(\ln 3-\tfrac{2}{3}\ln 2)n$. Under a degree-corrected model tested against the configuration-model null, the same partition survives, breaking far earlier at $r_\kappa=42$, with a log-evidence growing as $(2\ln 3-\tfrac{4}{3}\ln 2)n$ -- exactly twice the plain slope, and independent of the prior. Degree correction reverses the ordering of the candidate cuts, demoting the hub-leaf split and elevating the recursive one. Because the web is self-similar, the best description is not two communities but a nested hierarchy: the degree-corrected evidence keeps rising as the partition is refined, and is maximised at of order $\sqrt{n}$ communities of $\sim\sqrt{n}$ nodes. A purely local recursive rule thus builds true hierarchical community structure, over and above the scale-free degree sequence it also produces, in an exactly solvable setting.