How can one test for a multiplicative topological difference between two structured network populations whose fixed-scale additive Betti summaries agree? We model each population as a probability law over finite graphs, considered up to isomorphism, and read each graph through its clique complex. At the working scale, the ordinary summary is the joint Betti vector B=(b0,b1,b2), recording connected components, loops, and voids. The comparison is deliberately single scale: B is the vector of Betti counts at a fixed working scale, not the full persistence diagram of a filtration. We show that this additive summary can be identical under two non-degenerate graph laws while a multiplicative cohomology-ring statistic differs: the cup product, a multiplicative operation recording when two one-dimensional cohomology classes have a nonzero product in degree two, occurs with different frequency under the two laws. Consequently any procedure whose input is only this single-scale B-summary has no power beyond its size against the constructed alternatives, while a simple cup-product statistic separates them. We define a ring-frequency distance, prove finite-sample concentration for its plug-in estimator, and give a consistent two-sample test. The theory is aimed at structured, ring-rich graph complexes—surface-like meshes and coverage complexes—where the cup product is active; we give a deterministic mechanism under which it is vacuous, together with numerical evidence that it can be uninformative in generic random-graph regimes. Numerical illustrations confirm that the ring test detects the difference while calibrated B-only tests stay blind; those same B-only tests have power when the Betti law itself changes. Real-data case studies on surface meshes and nanoporous frameworks illustrate, respectively, the intended ring-rich regime and a cup-vacuous scope boundary.
We prove an impossibility theorem for uniformly consistent recovery of labeled edge probabilities from complete aggregated relational data, even when the population count law identifies every probability. For any known partition into two equal trait groups, we consider an independent-edge logistic network with a balanced rank-one signal and unknown activity effects with bounded total dyadic energy. The signal amplitude is known and fixed at a small positive value. Every node reports its counts to both groups. The minimax mean squared error for the probability matrix remains bounded away from zero as the network grows, whereas it tends to zero under full adjacency on the same parameter class. The lower bound accounts for the dependence across the entire count array through a two-node oracle from which all observed counts can be reconstructed. Conditional binomial smoothing bounds the information about a local sign orientation, and an anchored many-bit construction converts these ambiguities into a nonvanishing normalized matrix loss. A mixed-cumulant identity recovers every edge probability from the population degree law, locating the obstruction in estimation from a single aggregated network rather than in population identification.
The joint asymptotic distribution of any finite collection of network moments in random graphs sampled from a graphon, which includes both the nondegenerate case as well as the degenerate case, provides the higher-order fluctuation theory for subgraph counts in the graphon model.
Anirban Chatterjee, S. Dan, B. Bhattacharya· Annals of Statistics· 0 citations
We consider multipartite random graphs with given degree sequences, within and across different partitions. Under general assumptions, we prove the local limit of this graph is a multi-type branching process, establish that a giant component exists only when the local limit survives, and deduce that the typical distance is of logarithmic order in probability in the supercritical regime. Our analysis removes two major assumptions from Gamarnik and Misra (2015), where the giant component problem for this model was first considered. In particular, we do not assume irreducibility of the local limit, and provide a general framework to extract giant components even when the limiting branching process is reducible, which we hope to be useful in other contexts. We also provide a new simpler survival criterion of multi-type branching processes, which we hope to be useful when direct calculation of the spectral radius of the offspring matrix may prove to be difficult.
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.
This article proposes a linear-time correlation-controlled shuffling method that attenuates Pearson correlation by permuting one variable through local swaps on a random regular graph. Each round processes a fixed edge order and accepts only vertex-disjoint swaps, producing greedy matching rather than a standard interchange-process update. The analysis uses the induced first-moment operator. A uniform lower bound on edge acceptance yields a Laplacian-domination relation, while a lower bound on the probability that vertices remain unmatched controls the negative spectrum. Conditional on the loop-deleted realized graph being connected and having a spectral gap bounded away from zero, the absolute value of the expected correlation contracts exponentially. For every fixed same-sign attenuation target, an activation probability exists that attains the target in expectation. Finite-sample calibration uses a fixed-budget multi-resolution direct search without assuming monotonicity. Because the procedure applies only permutations, the marginal distribution is preserved exactly. Under fixed degree and fixed calibration budgets, both calibration and shuffling scale linearly with sample size. Experiments show small target errors, exact marginal preservation, and approximately linear runtime scaling. A matched-degree spectral ablation further shows that, with degree and edge count held fixed, the higher-gap random regular graph exhibits substantially faster decay of the mean correlation than the low-gap regular circulant graph.
V. Gasimov, N. Mammadzada, E. Mustafayeva et al.· Information· 0 citations
A specific sparse post-processing pipeline for Random Indexing on kinship analogies in a small fairytales corpus is studied; the results do not establish a generally effective embedding method.
S. Loganathan, Gokul Anand, A. B. Bo et al.· 0 citations
We use cookies to run the site and, with your consent, for analytics and to show ads.
See our Cookie Policy.
