Search

The network data has attracted considerable attention in modern statistics. In research on complex network data, one key issue is finding its underlying connection structure given a network sample. The methods that have been proposed in literature usually assume that the underlying structure is a known model. In practice, however, the true model is usually unknown, and network learning procedures based on these methods may suffer from model misspecification. To handle this issue, based on the random matrix theory, we first give a spectral property of the normalized adjacency matrix under a mild condition. Further, we establish a general goodness-of-fit test procedure for the unweight and undirected network. We prove that the null distribution of the proposed statistic converges in distribution to the standard normal distribution. Theoretically, this testing procedure is suitable for nearly all popular network models, such as stochastic block models, and latent space models. Further, we apply the proposed method to the degree-corrected mixed membership model and give a sequential estimator of the number of communities. Both simulation studies and real-world data examples indicate that the proposed method works well.

The $\beta$-model has been extensively utilized to model degree heterogeneity in networks, wherein each node is assigned a unique parameter. In this article, we consider the hypothesis testing problem that two nodes $i$ and $j$ of a $\beta$-model have the same node parameter. We prove that the null distribution of the proposed statistic converges in distribution to the standard normal distribution. Further, we investigate the homogeneous test for $\beta$-model by combining individual $p$-values to aggregate small effects of multiple tests. Both simulation studies and real-world data examples indicate that the proposed method works well.

Let $\bm{x}_1,\cdots,\bm{x}_n$ be a random sample of size $n$ from a $p$-dimensional population distribution, where $p=p(n)\rightarrow\infty$. Consider a symmetric matrix $W=X^\top X$ with parameters $n$ and $p$, where $X=(\bm{x}_1,\cdots,\bm{x}_n)^\top$. In this paper, motivated by model selection theory in high-dimensional statistics, we mainly investigate the asymptotic behavior of the eigenvalues of the principal minors of the random matrix $W$. For the Gaussian case, under a simple condition that $m=o(n/\log p)$, we obtain the asymptotic results on maxima and minima of the eigenvalues of all $m\times m$ principal minors of $W$. We also extend our results to general distributions with some moment conditions. Moreover, we gain the asymptotic results of the extreme eigenvalues of the principal minors in the case of the real Wigner matrix. Finally, similar results for the maxima and minima of the eigenvalues of all the principal minors with a size smaller than or equal to $m$ are also given.

The stochastic block model is widely used for detecting community structures in network data. However, the research interest of much literature focuses on the study of one sample of stochastic block models. How to detect the difference of the community structures is a less studied issue for stochastic block models. In this article, we propose a novel test statistic based on the largest singular value of a residual matrix obtained by subtracting the geometric mean of two estimated block mean effects from the sum of two observed adjacency matrices. We prove that the null distribution of the proposed test statistic converges in distribution to the Tracy-Widom distribution with index 1, and we show the difference between the two samples for stochastic block models can be tested via the proposed method. Further, we show that the proposed test has asymptotic power guarantee against alternative models. Both simulation studies and real-world data examples indicate that the proposed method works well.

The stochastic block model is a popular tool for detecting community structures in network data. Detecting the difference between two community structures is an important issue for stochastic block models. However, the two-sample test has been a largely under-explored domain, and too little work has been devoted to it. In this article, based on the maximum entry--wise deviation of the two centered and rescaled adjacency matrices, we propose a novel test statistic to test two samples of stochastic block models. We prove that the null distribution of the proposed test statistic converges in distribution to a Gumbel distribution, and we show the change of the two samples from stochastic block models can be tested via the proposed method. Then, we show that the proposed test has an asymptotic power guarantee against alternative models. One noticeable advantage of the proposed test statistic is that the number of communities can be allowed to grow linearly up to a logarithmic factor. Further, we extend the proposed method to the degree-corrected stochastic block model. Both simulation studies and real-world data examples indicate that the proposed method works well.

Although the theoretical properties in the $p_0$ model based on a differentially private bi-degree sequence have been derived, it is still lack of a unified theory for a general class of directed network models with the $p_{0}$ model as a special case. We use the popular Laplace data releasing method to output the bi-degree sequence of directed networks, which satisfies the private standard--differential privacy. The method of moment is used to estimate unknown parameters. We prove that the differentially private estimator is uniformly consistent and asymptotically normal under some conditions. Our results are illustrated by the Probit model. We carry out simulation studies to illustrate theoretical results and provide a real data analysis., Comment: 21 pages,1figures

In this paper, we study limiting laws and consistent estimation criteria for the extreme eigenvalues in a spiked covariance model of dimension $p$. Firstly, for fixed $p$, we propose a generalized estimation criterion that can consistently estimate, $k$, the number of spiked eigenvalues. Compared with the existing literature, we show that consistency can be achieved under weaker conditions on the penalty term. Next, allowing both $p$ and $k$ to diverge, we derive limiting distributions of the spiked sample eigenvalues using random matrix theory techniques. Notably, our results do not require the spiked eigenvalues to be uniformly bounded from above or tending to infinity, as have been assumed in the existing literature. Based on the above derived results, we formulate a generalized estimation criterion and show that it can consistently estimate $k$, while $k$ can be fixed or grow at an order of $k=o(n^{1/3})$. We further show that the results in our work continue to hold under a general population distribution without assuming normality. The efficacy of the proposed estimation criteria is illustrated through comparative simulation studies.

Estimating the number of principal components is one of the fundamental problems in many scientific fields such as signal processing (or the spiked covariance model). In this paper, we first demonstrate that, for fixed $p$, any penalty term of the form $k'(p-k'/2+1/2)C_n$ may lead to an asymptotically consistent estimator under the condition that $C_n\to\infty$ and $C_n/n\to0$. We also extend our results to the case $n,p\to\infty$, with $p/n\to c>0$. In this case, for $k=o(n^{\frac{1}{3}})$, we first investigate the limiting laws for the leading eigenvalues of the sample covariance matrix $S_n$ under the condition that $\lambda_k>1+\sqrt{c}$. At low SNR, since the AIC tends to underestimate the number of signals $k$, the AIC should be re-defined in this case. As a natural extension of the AIC for fixed $p$, we propose the extended AIC (EAIC), i.e., the AIC-type method with tuning parameter $\gamma=\varphi(c)=1/2+\sqrt{1/c}-\log(1+\sqrt{c})/c$, and demonstrate that the EAIC-type method, i.e., the AIC-type method with tuning parameter $\gamma>\varphi(c)$, can select the number of signals $k$ consistently. In the following two cases, (1) $p$ fixed, $n\to\infty$, (2) $n,p\to\infty$ with $p/n\to 0$, if the AIC is defined as the degeneration of the EAIC in the case $n,p\to\infty$ with $p/n\to c>0$, i.e., $\gamma=\lim_{c\rightarrow 0+0}\varphi(c)=1$, then we have essentially demonstrated that, to achieve the consistency of the AIC-type method in the above two cases, $\gamma>1$ is required. Moreover, we show that the EAIC-type method is essentially tuning-free and outperforms the well-known KN estimator proposed in Kritchman and Nadler (2008) and the BCF estimator proposed in Bai, Choi and Fujikoshi (2018). Numerical studies indicate that the proposed method works well., Comment: 56 pages; AIC is re-defined; for $k=o(n^{\frac{1}{3}})$, we investigate the limiting laws for the leading eigenvalues of the sample covariance matrix $S_n$ under the condition that $\lambda_k>1+\sqrt{c}$

The stochastic block model is widely used for detecting community structures in network data. How to test the goodness-of-fit of the model is one of the fundamental problems and has gained growing interests in recent years. In this article, we propose a novel goodness-of-fit test based on the maximum entry of the centered and re-scaled adjacency matrix for the stochastic block model. One noticeable advantage of the proposed test is that the number of communities can be allowed to grow linearly with the number of nodes ignoring a logarithmic factor. We prove that the null distribution of the test statistic converges in distribution to a Gumbel distribution, and we show that both the number of communities and the membership vector can be tested via the proposed method. Further, we show that the proposed test has asymptotic power guarantee against a class of alternatives. We also demonstrate that the proposed method can be extended to the degree-corrected stochastic block model. Both simulation studies and real-world data examples indicate that the proposed method works well., Comment: 31 pages

Estimating the number of communities is one of the fundamental problems in community detection. We re-examine the Bayesian paradigm for stochastic block models and propose a "corrected Bayesian information criterion",to determine the number of communities and show that the proposed estimator is consistent under mild conditions. The proposed criterion improves those used in Wang and Bickel (2016) and Saldana et al. (2017) which tend to underestimate and overestimate the number of communities, respectively. Along the way, we establish the Wilks theorem for stochastic block models. Moreover, we show that, to obtain the consistency of model selection for stochastic block models, we need a so-called "consistency condition". We also provide sufficient conditions for both homogenous networks and non-homogenous networks. The results are further extended to degree corrected stochastic block models. Numerical studies demonstrate our theoretical results., Comment: 42 pages, major revision. Change the title to "Corrected Bayesian information criterion for stochastic block models"

Naming game simulates the process of naming an object by a single word, in which a population of communicating agents can reach global consensus asymptotically through iteratively pair-wise conversations. We propose an extension of the single-word model to a multi-word naming game (MWNG), simulating the case of describing a complex object by a sentence (multiple words). Words are defined in categories, and then organized as sentences by combining them from different categories. We refer to a formatted combination of several words as a pattern. In such an MWNG, through a pair-wise conversation, it requires the hearer to achieve consensus with the speaker with respect to both every single word in the sentence as well as the sentence pattern, so as to guarantee the correct meaning of the saying, otherwise, they fail reaching consensus in the interaction. We validate the model in three typical topologies as the underlying communication network, and employ both conventional and man-designed patterns in performing the MWNG., Comment: 19 pagesa, 11 figures, Physica A (2017)