Extracted main text — title through conclusion, appendix excluded. This is what our citation measures are computed over, published so the extraction can be checked by eye.
34,063 characters · 9 sections · 39 citation commands
\footnotetext[3]{$^*$Correspondence author. Email: [email removed] (Haoyu Wei). Luo's research is partially supported by the Fundamental Research Funds for the Central Universities of South-Central Minzu University(Grant Number:CZQ22003) and by National Statistical Science Research of China (2022LY051) and by the Open Research Fund of Key Laboratory of Nonlinear Analysis & Applications (Central China Normal University), Ministry of Education, P.R. China. \\ Jing Luo and Haoyu Wei are co-first authors. Email:[email removed] (Jing Luo), {[email removed]} (Xiaoyu Lei), [email removed] (Jiaxin Guo).} \vskip 1.5mm
\vskip 5 pt
In network data analysis, the privacy of network data has received wide attention as the disclosed data is likely to contain sensitive information about individuals and their social relationships (sexual relationships, email exchanges, money transfers, etc). Analyzing this type of data can uncover valuable information that can be used to address many important social concerns, such as disease transmission, fraud detection, precision marketing, and more. In recent years, the urgent need to solve the problem of network privacy protection has led to the rapid development of algorithms for securely publishing network data or aggregating network data (see Zhou2008A, Yuan2011Personalized, Cutillo2010Privacy, and Lu2014Exponential). However, the unstructured characteristics of network data bring great challenges to the statistical inference (see fienberg2012brief, Mosler2015) . Data privacy protection is usually achieved by adding some noise to the data. The most typical method is differential privacy[Dwork2006]. Due to the unstructured characteristics of network data and the data with noise, there are relatively few theoretical studies on statistical asymptotic behavior of noise-based network data.
The Erd\"{o}s-R\'{e}nyi model (see Erd1959On) is generally acknowledged as one of the earliest random binary graph models, in which each edge occurs with the same probability independent of any other edge. However, it lacks the ability to capture the extent of degree heterogeneity commonly associated with network data in practice. To capture the heterozygous of nodes' degree, a class of models have come into use for analyzing binary undirected networks network data. The simplest network model is the binary network model, which mainly uses the degree sequence to capture the real network [albert2002]. The $\beta$-model has undirected binary weighted, which is known for binary arrays whose distribution only depends on the row and column totals (see degree1britton2006generating,degree3bickel2011method,degree4zhao2012consistency,hillar2013maximum). When the number of network nodes tends to infinity, many literature have studied the Maximum Likelihood Estimator (MLE) of the $\beta$-model(see chatterjee2011random; degree2blitzstein2011sequential; rinaldo2013maximum). The asymptotic normality of the MLE of the $\beta$-model is further studied by yanxu2013. Fan2002Connected proposes another type of binary network model. This model is called log-linear model, where the edge probability $p_{ij}$ between vertices $i$ and $j$ is $w_{i}w_{j}/(\sum_{k=1}^{n} w_{k})$ under the normalization constraint $w_{i}^{2}\leq (\sum_{k=1}^{n} w_{k}) $($i=1,...,n$), where $w_{i}$ is referred to as the weight of vertex $i$. Moreover, Olhede and Wolfe (2012) obtained the approximate value of the parameter estimation of a class of binary network in the case of limited sample network nodes. Until recent years, Karwa2016 has given research on the asymptotic theory of adding discrete Laplace noise to network data. However, when the general noise is added to a class of this network model, the asymptotic theory of parameter estimators is still unknown.
In this paper, we mainly study the asymptotic theory of a class of network models with sub-Gamma degree sequences. It is different from the method of adding noise to network data in Karwa2016, luo2022asymptotic and luo2021Ordered. Therefore, they only considered the asymptotic theory of the parameters for the $\beta-$model in the case of Laplace noise. Here, we consider the general distribution of noise variables, and Laplace distribution is only a special case. And then, our method does not need to deal with the degree sequence of noise, so we can directly use the degree sequence with noise to study the statistical inference of the network model. Furthermore, the probability-mass or density function of the edge $a_{ij}$ only depends on the sum of $\alpha_i^{*}$ and $\alpha_j^{*}$, where $\alpha_i^{*}$ denotes the strength parameter of vertex $i$. These are the main contributions of this paper.
For the rest of this article, we state as follows. In Section 2, we give null models for undirected network data and sub-Gamma degree sequences. In Section 3, we give a uniform asymptotic result. In Section 4, we illustrate several applications of our main results. Summary and discussion are given in Section 5. Proofs are given in the Appendix.
Notation: For $0< q\leq\infty$, we write $\| \beta\|_{q}:=(\sum_{i=1}^{p}|\beta_{i}|^{q})^{1/q}$ as the $\ell_{q}$-norm of a $p-$dimensional vector $\beta$. If $q=\infty$, we have $\| \beta\|_{\infty}:=\max\limits_{i=1,...,p}|\beta_{i}|$. For a subset $C\subset \mathbb{R}^n$, let $C^0$ and $\overline{C}$ denote the interior and closure of $C$ in $\mathbb{R}^n$, respectively. Let $\Omega(\mathbf{x}, r)$ denote the open ball $\{\mathbf{y}: \|\mathbf{x}-\mathbf{y}\|< r \}$, and $\overline{\Omega(\mathbf{x}, r)}$ be its closure.
Following yanxu2013, we consider an undirected graph $\mathcal{G}_{n}$ on n ( $n \geq 2$ ) agents labeled by $1,...,n$. Let $a_{ij}\in\{0,1\}$ be the weight of the undirected edge between $i$ and $j$. That is, if there is a link between $i$ and $j$, then $a_{ij}=1$; otherwise, $a_{ij}=0$. Denote $A=(a_{ij})_{n \times n}$ as the symmetric adjacency matrix of $\mathcal{G}_{n}$. We assume that there are no self-loops, i.e., $a_{ii}=0$. Define $d_{i}=\sum_{j\neq i}^{n}a_{ij}$ as the degree of vertex $i$ and $\mathbf{d}=(d_{1},\dots,d_{n})^{\top}$ as the degree sequence of the graph $\mathcal{G}$. We suppose that the adjacency matrix $A$ has independent Bernoulli elements such that $\mathrm{P} (a_{ij}=1) = p_{ij}$ and specify the corresponding family of probability null models for $A$. Here $\boldsymbol{\alpha}^{*}=(\alpha_{1}^{*},\alpha_{2}^{*},...,\alpha_{n}^{*})^{\top}$ is a parameter vector. The parameter $\alpha_i^*$ quantifies the effect of the vertex $i$. To this end, let $\varepsilon(\cdot,\cdot): \mathbb{R}^2 \mapsto \mathbb{R}$ be a smooth bivariate function satisfying $ \varepsilon(x,y) = \varepsilon(y,x)$. Consider the model $\emph{M}_{\varepsilon}$ specified $p_{ij}$ as
so that we obtain a class of log-linear models indexed by $\varepsilon$. In fact, this class encompasses three common choices of link functions:
To see this, set $\varepsilon(\alpha_{i}^{*},\alpha_{j}^{*}) = -\log\{1+ \exp(\alpha_{i}^{*}+ \alpha_{j}^{*})\}$ for the model $\emph{M}_{logit}$. As we have seen, the logit-link model $\emph{M}_{logit}$ is an undirected version of Holland1981An exponential family random graph model without reciprocal parameter. As noted by yanxu2013, the degree sequence of $\mathcal{G}$ is sufficient for $\alpha$ in this case, and they derived its asymptotic normality. The log-link model $\emph{M}_{\log}$ can be considered as an undirected version of expected degree model with $\varepsilon(\alpha_{i}^{*},\alpha_{i}^{*}) = 0$ constructed by Fan2002Connected. Setting $\varepsilon(\alpha_{i}^{*},\alpha_{j}^{*}) = \log\{1- \exp(\alpha_{i}^{*}+ \alpha_{j}^{*})\}-(\alpha_{i}^{*}+ \alpha_{j}^{*})$, we get the complementary log-log link model $\emph{M}_{\rm cloglog}$ (see Mccullagh1989Generalized).
In this section, we will prepare the probability and distribution preliminary for later network analysis. This section can be divided into two parts. In the first part, we are going to recap the definition of a specific type of distributions and state their basic properties.
Similarly, we define that a random variable is called sub-exponential if its survival function is bounded by that of a particular exponential distribution.
Obviously, sub-Gaussian random variables are sub-exponential but not vice verse. And there are some equivalent definitions of sub-exponential distributions, see Rigollet2019, which can lead to sub-exponential norm used in concentration inequalities. The equivalent definitions and other details can be seen in the Appendix.
The above norm provides us with a useful tool to connect MGF and the defined norm, and hence makes it possible to give concentrations for the sub-exponential variables. The following lemma confirms Definition (ref) would give a concise form of concentrations.
Lemma (ref)(c) implies that the following user-friendly concentration inequality would contain all known constant. One should note that Theorem 2.8.1 of Vershynin2018 includes an unspecific constant, so it is inefficacious when constructing non-asymptotic confident interval for sub-exponential sample mean.
Hay2009 and Karwa2016 used the Laplace mechanism to provide privacy protection in which independent and identically distributed Laplace random variables are added into the input data. Here, we consider a general distribution for the noisy variables with the Laplace distribution as a special case.
In statistical applications, we sometimes do not expect the bounded assumption in Hoeffding's inequality, the following Bernstein's inequality for a sum of independent random variables allows us to estimate the tail probability by a weaker version of exponential condition on the growth of the $k$-moment (like a condition of the exponential MGF) without any assumption of boundedness.
The proof Bernstein's inequality for the sum of independent random variables can be founded in p119 of Gin2015Mathematical.
Like the sub-Gaussian, boucheron2013concentration defines the sub-Gamma r.v. based on the right tail and left tail with variance factor $v$ and scale factor $b$.
The sub-exponential moment condition (ref) would imply that Bernstein's moment condition (ref) is observed as $$\log (\mathrm{{E}}{e^{s{X}}}) \le {\frac{s^{2}\lambda ^{2}}{2}} \le \frac{s^{2}\lambda ^{2}}{ {2(1 - \lambda|s|)}},~\forall~|s| <\frac{1}{\lambda}.$$
The concentration inequalities introduced in above only concerns the linear combinations of independent random variables. For lots of applications in high-dimensional statistics, we have to control the maximum of the n r.vs when deriving error bounds for the proposed estimator. In our proof of Theorem (ref), the following maximum inequality is crucial.
In this section, we will derive the asymptotic results for the estimator with an increasing sub-Gamma degree sequence. Note that $\mathrm{E}(a_{ij})$ only depends on the $e^{\alpha_{i}^{*}+ \alpha_{j}^{*}+\varepsilon_{ij}(\alpha_{i}^{*}+\alpha_{j}^{*})}$. Let $\mathbf{d}=(d_{1}, \ldots, d_{n})^{\top}$ be the degree sequence of graph $\mathcal{G}_{n}$. We assume that random variables $\{ e_{i}\}_{i=1}^n$ are mutually independent and distributed in sub-gamma distributions $\{{\rm{sub}}\Gamma(\upsilon_i,c_i)\} _{i = 1}^n$ with respective parameters $\{(\upsilon_i,c_i)\} _{i = 1}^n$. Then we observe the noisy sequence $\tilde{d}$ instead of $d$, where
We use moment equations to estimate the degree parameter with the noisy sequence $\tilde{d}$ instead of $d$. Define a system of functions:
Now, we define our estimator $\widehat{\boldsymbol{\alpha}}$ as the solution to the equation $F(\boldsymbol{\alpha})=0$, i.e.,
It is not hard to see that the estimator is actually induced by the moment equation $\mathbf{\tilde{d}} = \mathrm{E} (\mathbf{d})$.
These asymptotic results of $\widehat{\boldsymbol{\alpha}}$ hold for all $\varepsilon$ satisfying the following condition.
Note that the solution to the equation $F({\boldsymbol{\alpha}})=0$ is precisely the moment estimator. Here, we consider the symmetric parameter space \[D = \{ {\boldsymbol{\alpha}} \in \mathbb{R}^{n}: -Q_{n}\leq \alpha_{i} + \alpha_{j} \leq Q_{n}, \ Q_{n} >0, \ 1\leq i<j \leq n\}.\] The uniform consistency of $\widehat{\boldsymbol{\alpha}}$ and asymptotic distribution of the parameter estimator are stated as follows, and the proofs are given in Appendix.
We use the Newton-Kantovorich theorem to prove the consistency of the estimators by constructing the Newton iterative sequence. This technical step is different from Chatterjee et al. (2011) and provides a simple proof. The proof of the theorem is in Appendix.
The proof of the theorem is in Appendix.
In this section, we will evaluate the asymptotic result in Theorems (ref) through numerical simulations and a real data example. The simulation will be conducted using Hermite distributions which we have introduced and proved its properties under the framework of Section 2.
For the simulation study of all models $M_{\varepsilon}$, we set $\alpha_{i}^{*} = i*L/n$ for $i=1,...,n$. Other parameter settings in simulation studies are listed as follows. We consider three different values $-\log(\log(n))^{1/3}$, $ -\log(\log(n))^{1/2}$, and $-\log(\log(n))$ for $L$ in case of model $M_{log}$. For model $M_{logit}$, we consider three different values $L=0$, $\log(\log(n))$ and $\log(n)^{1/2}$. In case of model $M_{cloglog}$, we set three different values $L=\log(\log(\log(n)))^{3/2}, \log(\log(\log(n)))^{5/4}$ and $\log(\log(\log(n)))$. The noise $e_{i}(i=1,...,n)$ is the difference between two independent and identically distributed Hermite distributions (see Definition (ref)). We consider three cases of Hermite distribution where parameters $a_1=0.01$, $a_2=(\Lambda-0.01)/4, m=2$; $a_1=\Lambda-0.01$, $a_2=0.025$, $m=2$ and $a_1=4*\Lambda/5$, $a_2=\Lambda/5$, $m=2$. Here, we set $\Lambda = 2*\exp(-\lambda_{0}/2)/(1-\exp(-\lambda_{0}/2))^{2}$ and $\lambda_{0}=2$. We consider two values for $n=100$ and $n=200$. Note that by Theorems (ref), $\widehat{\xi}_{ij} =(\widehat{\alpha}_i + \widehat{\alpha}_j-(\alpha_{i}^{*} + \alpha_{j}^{*}))/(1/\widehat{v}_{ii}+1/\widehat{v}_{ii})^{1/2}$ is an asymptotically normal distribution, where $\hat{v}_{ii}$ is the estimator of $v_{ii}$ by replacing $\alpha_i$ with $\hat{\alpha}_i$. The quantile-quantile(QQ) plots of $\xi_{ij}$ are drawn. We ran $10000$ simulations for each scenario.
We simulate with $n=100$, $n=200$, three values for $L$ and three cases of Hermite distribution to find that the QQ-plots for each combination are similar. In order to save the place, we only present the QQ plots of three model in Figure (ref), Figure (ref) and Figure (ref) when $n=200$, $a_1=4*\Lambda/5$, $a_2=\Lambda/5$, and $m=2$ for each case. The horizontal and vertical axes are the theoretical and empirical quantiles respectively, and the straight lines correspond to the reference line $y=x$. In Figure (ref), we first observe that the empirical quantiles agree well with the ones of the standard normality of $\widehat{\xi_{ij}}$, expect for pair $(n/2, n/2+1)$ and $(n-1, n)$ when $L=-\log(\log(n))$ in the case of model $M_{log}$. For the case of model $M_{logit}$, there are no notable derivations from the standard normality for each scenario in Figure (ref). We also observe that the empirical quantiles agree well with the ones of the standard normality of $\widehat{\xi}_{ij}$, expect for pair $(n/2, n/2+1)$ and $(n-1, n)$ when $L=\log(\log(\log(n)))$ in Figure (ref).
The coverage probability of the $95\%$ confidence interval for $\alpha_i-\alpha_j$, the length of the confidence interval and the frequency that the MLE did not exist are reported in Table (ref), Table (ref) and Table (ref). We can see that the length of estimated confidence interval increases as $L$ increases for fixed $n$, and decreases as $n$ increases for fixed $L$.
We use the KAPFERER TAILOR SHOP network dataset created by Bruce Kapferer which is downloaded from \url{http://vlado.fmf.uni-lj.si/pub/networks/data/ucinet/ucidata.htm}. In each study they obtain measures of social interaction among all actors. In this network data, $``1''$ represents they have a friend relationship between two actors, otherwise, it is denoted as $``0''$. Because the estimate $\hat{\alpha}$ does not exist when the degree is zero, we remove the vertex 17 and 22 whose degree is zero before analysis, so the network with the left 37 vertices in each table remains. When the parameters of three kinds of noise distribution function $e_{i}(i=1,...,n)$ are set, the parameter estimation is similar in case of model $M_{logit}$, $M_{log}$ and $M_{cloglog}$. Thus we here only show the parameter estimation under the case of noise distribution function parameter for $a_1=4*\Lambda/5$, $a_2=\Lambda/5$ and $m=2$. From Figure (ref), we first observe the scatter plots of the noisy degree sequence $\tilde{d}$ corresponding to the parameter estimation $\hat{\alpha}$ under model $M_{\varepsilon}$ and the value of $\hat{\alpha}$ increases as the number of $\tilde{d}$ climbs. The larger the estimated parameters $\hat{\alpha}$, the actors have more friends. For these three cases of model $M_{\varepsilon}$, the estimated parameters and their standard errors as well as the $95\%$ confidence intervals and the size of noisy degree sequences are reported in Table (ref), Table (ref) and Table (ref) respectively. The value of estimated parameters reflects the corresponding size of noisy degrees. For example, the large five degrees are $26,17,16,15,14$ for vertices $16,18,32,11,12$ which also have the top five influence parameters at $0.36,-0.05,-0.12,-0.18,-0.25$. On the other hand, the five vertices with smallest parameters $-2.89,-2.19,-1.79,-1.28,-1.10$ have degrees at $1,2,3,5,6$. In Table (ref) and Table (ref), the larger the parameter $\hat{\alpha}$, the greater the degree $\tilde{d}$ of the node. This is the same as the conclusion in Table (ref).
In this paper, we release the degree sequences of the class of binary networks under the sub-Gamma noisy mechanism. We establish the asymptotic result including the consistency and asymptotically normality of the parameter estimator when the number of parameters goes to infinity. By using the Newton-Kantorovich theorem, we try to ignore adding noisy process and obtain the existence and consistency of the parameter estimator satisfying equation $\mathbf{\tilde{d}} = \mathrm{E} (\mathbf{d})$. Furthermore, we give some simulation results to illustrate that the asymptotic normality behaves well under model $\emph{M}_{\log}$, $\emph{M}_{logit}$ and $ \emph{M}_{cloglog}$. However, an edge in networks takes not only binary values but also weighted edges in many scenarios. We will investigate null models for these directed weighted networks in the future. It is worth noting that the conditions imposed on $Q_{n}$,$a_1$, $a_2$, and $m=2$ may not be the most possible. In particular, the conditions guaranteeing the asymptotic normality are stronger than those guaranteeing the consistency. Simulation studies suggest that the conditions on $Q_{n}$ might be relaxed. It can be noted that the asymptotic behavior of the parameter estimator depends not only on $Q_{n}$ $a_1$, $a_2$, and $m=2$, but also on the configuration of all the parameters, We will investigate this in future studies.
In this paper we derived individual parameter asymptotic properties, and we can also study on a linear combination of all the parameter estimation in binary networks with noisy degree sequence in the future work. In our paper, we only consider the model heterogeneity parameter. In network data, the second distinctive feature inherent in most natural networks is the homophily phenomenon. Yan2019 established the uniform consistency and asymptotic normality of the heterogeneity parameter and homophily parameter estimators. On the other hand, sub-Weibull variables, as an extension of sub-Gamma variables, enable variables have heavier tails, which may also be consider in networks models. Fortunately, there have been some articles investigating concentration of sub-Weibull variables, see zhang2021sharper for instance. And we further investigate a central limit theorem for a linear combination of all the maximum likelihood estimators of degree parameter when the number of nodes goes to infinity[luo2020asymptotic]. And the asymptotic theory of the affiliation network model with noise sequence is also worth further study[luo2021affiliation]. We will investigate these aspects in future studies.