Search

Network-linked data, where multivariate observations are interconnected by a network, are becoming increasingly prevalent in fields such as sociology and biology. These data often exhibit inherent noise and complex relational structures, complicating conventional modeling and statistical inference. Motivated by empirical challenges in analyzing such data sets, this paper introduces a family of network subspace generalized linear models designed for analyzing noisy, network-linked data. We propose a model inference method based on subspace-constrained maximum likelihood, which emphasizes flexibility in capturing network effects and provides a robust inference framework against network perturbations. We establish the asymptotic distributions of the estimators under network perturbations, demonstrating the method's accuracy through extensive simulations involving random network models and deep-learning-based embedding algorithms. The proposed methodology is applied to a comprehensive analysis of a large-scale study on school conflicts, where it identifies significant social effects, offering meaningful and interpretable insights into student behaviors., Comment: 52 pages, 7 figures

Community structures represent a crucial aspect of network analysis, and various methods have been developed to identify these communities. However, a common hurdle lies in determining the number of communities K, a parameter that often requires estimation in practice. Existing approaches for estimating K face two notable challenges: the weak community signal present in sparse networks and the imbalance in community sizes or edge densities that result in unequal per-community expected degree. We propose a spectral method based on a novel network operator whose spectral properties effectively overcome both challenges. This operator is a refined version of the non-backtracking operator, adapted from a "centered" adjacency matrix. Its leading eigenvalues are more concentrated than those of the adjacency matrix for sparse networks, while they also demonstrate enhanced signal under imbalance scenarios, a benefit attributed to the centering step. This is justified, either theoretically or numerically, under the null model K = 1, in both dense and ultra-sparse settings. A goodness-of-fit test based on the leading eigenvalue can be applied to determine the number of communities K.

This paper studies the parametric bootstrap method for networks to quantify the uncertainty of statistics of interest. While existing network resampling methods primarily focus on count statistics under node-exchangeable (graphon) models, we consider more general network statistics (including local statistics) under the Chung-Lu model without node-exchangeability. We show that the natural network parametric bootstrap that first estimates the network generating model and then draws bootstrap samples from the estimated model generally suffers from bootstrap bias. As a general recipe for addressing this problem, we show that a two-level bootstrap procedure provably reduces the bias. This essentially extends the classical idea of iterative bootstrap to the network setting with a growing number of parameters. Moreover, the second-level bootstrap provides a way to construct higher-accuracy confidence intervals for many network statistics.

A key challenge in realizing practical quantum networks for long-distance quantum communication involves robust entanglement between quantum memory nodes connected via fiber optical infrastructure. Here, we demonstrate a two-node quantum network composed of multi-qubit registers based on silicon-vacancy (SiV) centers in nanophotonic diamond cavities integrated with a telecommunication (telecom) fiber network. Remote entanglement is generated via the cavity-enhanced interactions between the SiV's electron spin qubits and optical photons. Serial, heralded spin-photon entangling gate operations with time-bin qubits are used for robust entanglement of separated nodes. Long-lived nuclear spin qubits are used to provide second-long entanglement storage and integrated error detection. By integrating efficient bi-directional quantum frequency conversion of photonic communication qubits to telecom frequencies (1350 nm), we demonstrate entanglement of two nuclear spin memories through 40 km spools of low-loss fiber and a 35 km long fiber loop deployed in the Boston area urban environment, representing an enabling step towards practical quantum repeaters and large-scale quantum networks., Comment: 23 pages, 16 figures

Color centers have emerged as a leading qubit candidate for realizing hybrid spin-photon quantum information technology. One major limitation of the platform, however, is that the characteristics of individual color-centers are often strain dependent. As an illustrative case, the silicon-vacancy center in diamond typically requires millikelvin temperatures in order to achieve long coherence properties, but strained silicon vacancy centers have been shown to operate at temperatures beyond 1K without phonon-mediated decoherence. In this work we combine high-stress silicon nitride thin films with diamond nanostructures in order to reproducibly create statically strained silicon-vacancy color centers (mean ground state splitting of 608 GHz) with strain magnitudes of $\sim 4 \times 10^{-4}$. Based on modeling, this strain should be sufficient to allow for operation of a majority silicon-vacancy centers within the measured sample at elevated temperatures (1.5K) without any degradation of their spin properties. This method offers a scalable approach to fabricate high-temperature operation quantum memories. Beyond silicon-vacancy centers, this method is sufficiently general that it can be easily extended to other platforms as well., Comment: 6 pages, 4 figures

Distributing quantum information between remote systems will necessitate the integration of emerging quantum components with existing communication infrastructure. This requires understanding the channel-induced degradations of the transmitted quantum signals, beyond the typical characterization methods for classical communication systems. Here we report on a comprehensive characterization of a Boston-Area Quantum Network (BARQNET) telecom fiber testbed, measuring the time-of-flight, polarization, and phase noise imparted on transmitted signals. We further design and demonstrate a compensation system that is both resilient to these noise sources and compatible with integration of emerging quantum memory components on the deployed link. These results have utility for future work on the BARQNET as well as other quantum network testbeds in development, enabling near-term quantum networking demonstrations and informing what areas of technology development will be most impactful in advancing future system capabilities., Comment: 9 pages, 5 figures + Supplemental Materials

Practical quantum networks require interfacing quantum memories with existing channels and systems that operate in the telecom band. Here we demonstrate low-noise, bidirectional quantum frequency conversion that enables a solid-state quantum memory to directly interface with telecom-band systems. In particular, we demonstrate conversion of visible-band single photons emitted from a silicon-vacancy (SiV) center in diamond to the telecom O-band, maintaining low noise ($g^2(0)<0.1$) and high indistinguishability ($V=89\pm8\%$). We further demonstrate the utility of this system for quantum networking by converting telecom-band time-bin pulses, sent across a lossy and noisy 50 km deployed fiber link, to the visible band and mapping their quantum states onto a diamond quantum memory with fidelity $\mathcal{F}=87\pm 2.5 \% $. These results demonstrate the viability of SiV quantum memories integrated with telecom-band systems for scalable quantum networking applications., Comment: 9 pages, 5 figures + Supplemental Materials

Variational inference has been widely used in machine learning literature to fit various Bayesian models. In network analysis, this method has been successfully applied to solve the community detection problems. Although these results are promising, their theoretical support is only for relatively dense networks, an assumption that may not hold for real networks. In addition, it has been shown recently that the variational loss surface has many saddle points, which may severely affect its performance, especially when applied to sparse networks. This paper proposes a simple way to improve the variational inference method by hard thresholding the posterior of the community assignment after each iteration. Using a random initialization that correlates with the true community assignment, we show that the proposed method converges and can accurately recover the true community labels, even when the average node degree of the network is bounded. Extensive numerical study further confirms the advantage of the proposed method over the classical variational inference and another state-of-the-art algorithm.

Long-distance quantum communication and networking require quantum memory nodes with efficient optical interfaces and long memory times. We report the realization of an integrated two-qubit network node based on silicon-vacancy centers (SiVs) in diamond nanophotonic cavities. Our qubit register consists of the SiV electron spin acting as a communication qubit and the strongly coupled 29Si nuclear spin acting as a memory qubit with a quantum memory time exceeding two seconds. By using a highly strained SiV with suppressed electron spin-phonon interactions, we realize electron-photon entangling gates at elevated temperatures up to 1.5 K and nucleus-photon entangling gates up to 4.3 K. Finally, we demonstrate efficient error detection in nuclear spin-photon gates by using the electron spin as a flag qubit, making this platform a promising candidate for scalable quantum repeaters., Comment: 24 pages, 19 figures

An efficient, scalable source of shaped single photons that can be directly integrated with optical fiber networks and quantum memories is at the heart of many protocols in quantum information science. We demonstrate a deterministic source of arbitrarily temporally shaped single-photon pulses with high efficiency (detection efficiency = 14.9%) and purity ($g^{(2)}(0) = 0.0168$) and streams of up to 11 consecutively detected single photons using a silicon-vacancy center in a highly directional fiber-integrated diamond nanophotonic cavity. Combined with previously demonstrated spin-photon entangling gates, this system enables on-demand generation of streams of correlated photons such as cluster states and could be used as a resource for robust transmission and processing of quantum information.

Networks analysis has been commonly used to study the interactions between units of complex systems. One problem of particular interest is learning the network's underlying connection pattern given a single and noisy instantiation. While many methods have been proposed to address this problem in recent years, they usually assume that the true model belongs to a known class, which is not verifiable in most real-world applications. Consequently, network modeling based on these methods either suffers from model misspecification or relies on additional model selection procedures that are not well understood in theory and can potentially be unstable in practice. To address this difficulty, we propose a mixing strategy that leverages available arbitrary models to improve their individual performances. The proposed method is computationally efficient and almost tuning-free; thus, it can be used as an off-the-shelf method for network modeling. We show that the proposed method performs equally well as the oracle estimate when the true model is included as individual candidates. More importantly, the method remains robust and outperforms all current estimates even when the models are misspecified. Extensive simulation examples are used to verify the advantage of the proposed mixing method. Evaluation of link prediction performance on 385 real-world networks from six domains also demonstrates the universal competitiveness of the mixing method across multiple domains.

Linear regression on network-linked observations has been an essential tool in modeling the relationship between response and covariates with additional network structures. Previous methods either lack inference tools or rely on restrictive assumptions on social effects and usually assume that networks are observed without errors. This paper proposes a regression model with nonparametric network effects. The model does not assume that the relational data or network structure is exactly observed and can be provably robust to network perturbations. Asymptotic inference framework is established under a general requirement of the network observational errors, and the robustness of this method is studied in the specific setting when the errors come from random network models. We discover a phase-transition phenomenon of the inference validity concerning the network density when no prior knowledge of the network model is available while also showing a significant improvement achieved by knowing the network model. Simulation studies are conducted to verify these theoretical results and demonstrate the advantage of the proposed method over existing work in terms of accuracy and computational efficiency under different data-generating models. The method is then applied to middle school students' network data to study the effectiveness of educational workshops in reducing school conflicts.

Random matrix theory has played an important role in recent work on statistical network analysis. In this paper, we review recent results on regimes of concentration of random graphs around their expectation, showing that dense graphs concentrate and sparse graphs concentrate after regularization. We also review relevant network models that may be of interest to probabilists considering directions for new random matrix theory developments, and random matrix theory tools that may be of interest to statisticians looking to prove properties of network algorithms. Applications of concentration results to the problem of community detection in networks are discussed in detail., Comment: Submission for International Congress of Mathematicians, Rio de Janeiro, Brazil 2018

Edge sampling is an important topic in network analysis. It provides a natural way to reduce network size while retaining desired features of the original network. Sampling methods that only use local information are common in practice as they do not require access to the entire network and can be parallelized easily. Despite promising empirical performances, most of these methods are derived from heuristic considerations and therefore still lack theoretical justification. To address this issue, we study in this paper a simple edge sampling scheme that uses network local information. We show that when local connectivity is sufficiently strong, the sampled network satisfies a strong spectral property. We quantify the strength of local connectivity by a global parameter and relate it to more common network statistics such as the clustering coefficient and network curvature. Based on this result, we also provide sufficient conditions under which random networks and hypergraphs can be sampled efficiently.

Complex interactions between entities are often represented as edges in a network. In practice, the network is often constructed from noisy measurements and inevitably contains some errors. In this paper we consider the problem of estimating a network from multiple noisy observations where edges of the original network are recorded with both false positives and false negatives. This problem is motivated by neuroimaging applications where brain networks of a group of patients with a particular brain condition could be viewed as noisy versions of an unobserved true network corresponding to the disease. The key to optimally leveraging these multiple observations is to take advantage of network structure, and here we focus on the case where the true network contains communities. Communities are common in real networks in general and in particular are believed to be presented in brain networks. Under a community structure assumption on the truth, we derive an efficient method to estimate the noise levels and the original network, with theoretical guarantees on the convergence of our estimates. We show on synthetic networks that the performance of our method is close to an oracle method using the true parameter values, and apply our method to fMRI brain data, demonstrating that it constructs stable and plausible estimates of the population network.

In this paper, transformation formulas for a large class of Eisenstein series defined by \[ G(z,s;A_{\alpha},B_{\beta};r_{1},r_{2})=\sum\limits_{m,n=-\infty}^{\infty }\ \hspace{-0.19in}^{^{\prime}}\frac{f(\alpha m)f^{\ast}(\beta n)} {((m+r_{1})z+n+r_{2})^{s}},\text{ }\operatorname{Re}(s)>2,\text{ }\operatorname{Im}(z)>0 \] are investigated for $s=1-r$, $r\in\mathbb{N}$. Here $\left\{ f(n)\right\}$ and $\left\{ f^{\ast}(n)\right\}$, $-\infty0$, and $A_{\alpha}=\left\{ f(\alpha n)\right\} $ and $B_{\beta}=\left\{ f^{\ast}(\beta n)\right\}$, $\alpha,\beta\in\mathbb{Z}$. Appearing in the transformation formulas are generalizations of Dedekind sums involving the periodic Bernoulli function. Reciprocity law is proved for periodic Apostol-Dedekind sum outside of the context of the transformation formulas. Furthermore, transformation formulas are presented for $G(z,s;A_{\alpha},I;r_{1},r_{2})$ and $G(z,s;I,A_{\alpha };r_{1},r_{2})$, where $I=\left\{ 1\right\}$. As an application of these formulas, analogues of Ramanujan's formula for periodic zeta-functions are derived., Comment: arXiv admin note: text overlap with arXiv:1506.01809

Community detection is a fundamental problem in network analysis with many methods available to estimate communities. Most of these methods assume that the number of communities is known, which is often not the case in practice. We study a simple and very fast method for estimating the number of communities based on the spectral properties of certain graph operators, such as the non-backtracking matrix and the Bethe Hessian matrix. We show that the method performs well under several models and a wide range of parameters, and is guaranteed to be consistent under several asymptotic regimes. We compare this method to several existing methods for estimating the number of communities and show that it is both more accurate and more computationally efficient.

This paper studies how close random graphs are typically to their expectations. We interpret this question through the concentration of the adjacency and Laplacian matrices in the spectral norm. We study inhomogeneous Erd\"os-R\'enyi random graphs on $n$ vertices, where edges form independently and possibly with different probabilities $p_{ij}$. Sparse random graphs whose expected degrees are $o(\log n)$ fail to concentrate; the obstruction is caused by vertices with abnormally high and low degrees. We show that concentration can be restored if we regularize the degrees of such vertices, and one can do this in various ways. As an example, let us reweight or remove enough edges to make all degrees bounded above by $O(d)$ where $d=\max np_{ij}$. Then we show that the resulting adjacency matrix $A'$ concentrates with the optimal rate: $\|A' - \mathbb{E} A\| = O(\sqrt{d})$. Similarly, if we make all degrees bounded below by $d$ by adding weight $d/n$ to all edges, then the resulting Laplacian concentrates with the optimal rate: $\|L(A') - L(\mathbb{E} A')\| = O(1/\sqrt{d})$. Our approach is based on Grothendieck-Pietsch factorization, using which we construct a new decomposition of random graphs. We illustrate the concentration results with an application to the community detection problem in the analysis of networks., Comment: 21 pages. Elizaveta Levina is added as a co-author. Application to community detection of networks is expanded

We study random graphs with possibly different edge probabilities in the challenging sparse regime of bounded expected degrees. Unlike in the dense case, neither the graph adjacency matrix nor its Laplacian concentrate around their expectations due to the highly irregular distribution of node degrees. It has been empirically observed that simply adding a constant of order $1/n$ to each entry of the adjacency matrix substantially improves the behavior of Laplacian. Here we prove that this regularization indeed forces Laplacian to concentrate even in sparse graphs. As an immediate consequence in network analysis, we establish the validity of one of the simplest and fastest approaches to community detection -- regularized spectral clustering, under the stochastic block model. Our proof of concentration of regularized Laplacian is based on Grothendieck's inequality and factorization, combined with paving arguments., Comment: Added references

Community detection is one of the fundamental problems of network analysis, for which a number of methods have been proposed. Most model-based or criteria-based methods have to solve an optimization problem over a discrete set of labels to find communities, which is computationally infeasible. Some fast spectral algorithms have been proposed for specific methods or models, but only on a case-by-case basis. Here we propose a general approach for maximizing a function of a network adjacency matrix over discrete labels by projecting the set of labels onto a subspace approximating the leading eigenvectors of the expected adjacency matrix. This projection onto a low-dimensional space makes the feasible set of labels much smaller and the optimization problem much easier. We prove a general result about this method and show how to apply it to several previously proposed community detection criteria, establishing its consistency for label estimation in each case and demonstrating the fundamental connection between spectral properties of the network and various model-based approaches to community detection. Simulations and applications to real-world data are included to demonstrate our method performs well for multiple problems over a wide range of parameters., Comment: 45 pages, 7 figures; added discussions about computational complexity and extension to more than two communities