The Spectral Distribution of Random Mixed Graphs

Round 1

Reviewer 1 Report

Authors consider the random mixed graph model and study the spectrum of the Hermitean adjacency matrix with the aim to extend Erdos-Renyi's result onto the wider class of models.  The article contains the necessary proof and also supporting numerics. Unfortunately, there is no conclusion section, where the main result and its importance would be described. 

I would like to pay the author's attention to the article "Two conjectures about spectral density of diluted sparse Bernoulli random matrices"  by S. Nechaev (https://arxiv.org/abs/1409.7650), where he studies the spectra of sparse random graphs. As I can see, this case can explain deviations from the semicircle law at small p and q. Am I right?

To this end, one more question arises. It is not reflected in the definitions whether you put restrictions that the graphs are connected? Or you study an ensemble of graphs, which can be disconnected but are described by the same adjacency matrix?

Remark.

Line 59: absents bracket after q

Author Response

On behalf of all the contributing authors, I would like to express our sincere appreciations of your constructive comments concerning our article. These comments are all valuable and helpful for improving our article. According to your comments, we have made modifications to our manuscript as follows.

 

1. Authors consider the random mixed graph model and study the spectrum of the Hermitian adjacency matrix with the aim to extend Erdos-Renyi's result onto the wider class of models.  The article contains the necessary proof and also supporting numerics. Unfortunately, there is no conclusion section, where the main result and its importance would be described. 

RESPOND: We add a conclusion section to emphasize  the importance of the main result. We also add a note that our condition in Theorem 1.1 is may be necessary according to the simulation.

2. I would like to pay the author's attention to the article "Two conjectures about spectral density of diluted sparse Bernoulli random matrices"  by S. Nechaev (https://arxiv.org/abs/1409.7650), where he studies the spectra of sparse random graphs. As I can see, this case can explain deviations from the semicircle law at small p and q. Am I right?

RESPOND: Yes, you are right. If the p,q tends to zeroes ( such that n\sigma^2 < \infty), the random mixed graph would tend to sparse graph with very few edges, consider the extreme example: the trivial empty graph with n vertices. We can see that all its eigenvalues are zeroes, the corresponding ESD deviates far away from the semicircle law.  And we can see that if p tends to one (such that n\sigma^2 < \infty),  the deviations would occur too. 

The two conjectures in the article "Two conjectures about spectral density of diluted sparse Bernoulli random matrices" consider the cases when q=0, p=1/N + \epsilon, where 0<\epsilon<<1/N, from which we can see that the corresponding  of N \sigma^2 is approximate 1. Thus it’s not strange to see that the corresponding ESD is deviates from the semicircle law.

3. To this end, one more question arises. It is not reflected in the definitions whether you put restrictions that the graphs are connected? Or you study an ensemble of graphs, which can be disconnected but are described by the same adjacency matrix?

Remark.    RESPOND: You are right, the graphs are not necessarily connected. We consider an ensemble of random mixed graphs, which can be disconnected, but are described by the same adjacency matrix. We add a sentence “Note that the above result consider an ensemble of random Hermitian matrices, which the corresponding random mixed graphs are not necessarily connected.” in Line 113.

4. Line 59: absents bracket after q.   

    RESPOND: corrected.

Once again, thank you for  your valuable comments, which are valuable in improving the quality of our manuscript.

Reviewer 2 Report

The main aim of this paper is to give  a new random mixed graph model $G_n(p(n),q(n))$ including the classical Erd\H{o}s-R\'enyi{'}s random graph model and the random oriented graph model, but in my opinion, that intention has not been achieved successfully. To increase some readability, I suggest the following improvements:

\item There are missing middle names in the references, e.g.,  Joel E. Cohen and Eugene P. Wigner. I also recommend to use some spelling for others misspellings as "stimulation", "ganrantee". 

\item In line~26, notation $\overline{\Gamma}(G)$ is not obvious to me. Is there some relationship between $W$ and $G$?   

\item In line~32, I think that instead of "there is not any", should be "there is no any".

\item In lines~37 and~38, "Hu et al's" sounds very strange.

\item In line~59, parentheses are not written correctly. 

\item On page~2, by my opinion, $\sigma^2$ as $\hbox{Var}(\zeta)$ is not correctly established. I obtained the value $\sigma^2=\hbox{Var}(\zeta)=p-2q-p^2$ after recalculating in two different ways, but I didn't use absolute value. Authors mention it, can you explain why? I think that your $\sigma^2=p+2q-p^2$ is probably $\hbox{Var}(|\zeta|)$, and therefore, it should be correctly clarified. Moreover, if $\sigma^2=\hbox{Var}(|\zeta|)=p+2q-p^2$, then $\hbox{E}(\zeta)=p$ and $\hbox{E}(|\zeta|)\neq p$ should also be distinguished, which yields that a random variable $\eta$ will have completely different values on page~4.  

Note that the case of $\sigma^2=\hbox{Var}(\zeta)=p-2q-p^2$ also enforces some negative values, e.g.,  $\sigma^2=-0.16$ for $q=\sqrt{p}-p$ and $p=0.5$. In addition, it will force several discrepancies in the description of $M_n$ and also in the properties of $\hbox{E}(|\eta|^s)$ for some positive odd integer $s$ on page~4. 

\item In line~74, notation $\hbox{E}(|x_{11}|^r)$ and $\hbox{E}(|x_{12}|^r)$ need to be explained. 

Due to the limited readability in Introduction, it was unfortunately not possible for me to observe the correctness of the described results in the following sections. The work is written in an unclear style and the paper is not suitable for publication in the journal Axioms in this form. 

Comments for author File: Comments.pdf

Author Response

On behalf of all the contributing authors, I would like to express our sincere appreciations of your constructive comments concerning our article. These comments are all valuable and helpful for improving our article. According to your comments, we have made modifications to our manuscript as follows.

\item There are missing middle names in the references, e.g.,  Joel E. Cohen and Eugene P. Wigner. I also recommend to use some spelling for others misspellings as "stimulation", "ganrantee". 

Respond: Corrected.

\item In line~26, notation $\overline{\Gamma}(G)$ is not obvious to me. Is there some relationship between $W$ and $G$?   

Respond:  Sorry for the confusion. we corrected the sentences as follows:

Let $W$ be a mixed walk of a mixed graph $G$, its underlying graph $\Gamma(W)$ (the undirected graph spanned by $W$ in $G$) may contain parallel edges since $W$ may go through an edge or arcs (no matter in which direction) several of times and thus not necessarily simple. If we take the edge set of $\Gamma(W)$ without multiplicities, this edge set can span a simple undirected graph which we denote it by $\overline{\Gamma}(W)$. For undefined terminology and notation, we refer the reader to \cite{Cvetkovic1995spectra}.

\item In line~32, I think that instead of "there is not any", should be "there is no any".

Respond： Corrected.

\item In lines~37 and~38, "Hu et al's" sounds very strange.

Respond：We rephrase the sentence as “if we set $q=\sqrt{p}-p$, then $G_{n}{(p,\sqrt{p}-p)}$ is the random mixed graph model in \cite{hu2017spectral}”.

\item In line~59, parentheses are not written correctly. 

Respond: Corrected.

\item On page~2, by my opinion, $\sigma^2$ as $\hbox{Var}(\zeta)$ is not correctly established. I obtained the value $\sigma^2=\hbox{Var}(\zeta)=p-2q-p^2$ after recalculating in two different ways, but I didn't use absolute value. Authors mention it, can you explain why? I think that your $\sigma^2=p+2q-p^2$ is probably $\hbox{Var}(|\zeta|)$, and therefore, it should be correctly clarified. Moreover, if $\sigma^2=\hbox{Var}(|\zeta|)=p+2q-p^2$, then $\hbox{E}(\zeta)=p$ and $\hbox{E}(|\zeta|)\neq p$ should also be distinguished, which yields that a random variable $\eta$ will have completely different values on page~4.  

Respond:  Since the $\zeta$ is a random variable with complex value, its variance is defined as the $E [(\zeta - E(\zeta) \overline{\zeta - E(\zeta)})] $, see Eq.3 in https://en.wikipedia.org/wiki/Complex_random_variable for example. 

 Thus , it is ok that $\sigma^2=p+2q-p^2$ and $\sigma^2$ is non-negative.

We make this Definition more clearly in the following: 

\begin{equation*}

\begin{split}

  \sigma^{2}

  :&=\Var(\xi)=\E[(\xi-\E(\xi))\overline{(\xi-\E(\xi))}]:=\E(\abs{\xi}^2)-\abs{\E(\xi)}^2\\

&=1\cdot [p+2q]+0\cdot(1-p-2q)-p^2\\

&=p+2q-p^2.

\end{split}

\end{equation*}

Thus $\hbox{E}(\zeta)=p$ is different from $\hbox{E}(|\zeta|)\neq p$. So for formulas between line 95 and line 96 in page 4,  where we consider the expectation of the power of the absolute value of $\eta$.

\item Note that the case of $\sigma^2=\hbox{Var}(\zeta)=p-2q-p^2$ also enforces some negative values, e.g.,  $\sigma^2=-0.16$ for $q=\sqrt{p}-p$ and $p=0.5$. In addition, it will force several discrepancies in the description of $M_n$ and also in the properties of $\hbox{E}(|\eta|^s)$ for some positive odd integer $s$ on page~4. 

Respond: As we mentioned above,  $\sigma^2=p+2q-p^2$ and $\sigma^2$ is non-negative. We believe it is ok so far for the rest of the paper.

\item In line~74, notation $\hbox{E}(|x_{11}|^r)$ and $\hbox{E}(|x_{12}|^r)$ need to be explained. 

Respond: Since we have mentioned in Line 70 page 2 that “The upper-triangular entries x_{kl} (1 ≤ k < l ≤ n) are i.i.d. complex random variables with zero mean and unit variance; if we restrict $\hbox{E}(|x_{12}|^r)$ to be finite, so will be all upper-triangular entries x_{kl} (1 ≤ k < l ≤ n); same as $\hbox{E}(|x_{11}|^r)$. We think this expression is more concise.

Once again, we thank you for your constructive comments, which are valuable in improving the quality of our manuscript.

Round 2

Reviewer 2 Report

All my comments were corrected or sufficiently explained. I still found a few small shortcomings:

In line 2, a new typo as "the ccccc"

In line 69, instead of "Wigner matrices", should be "Wigner matrix".

All helpful statements should be better cited. E.g: Lemma1(See [2] Lemma 2.4)

In the definition of the matrix $M_n$ on page 4, it is worth recalling what the symbols $p$ and $\sigma$ mean.

In line 121, should be "$p$ increasingly from 0.001 to 0.1"

In Remark 2, the terms $\mathcal{F}$ and $c$ must be explained.

On page 11,  $e(\overline{W})=x$ doesn't make sense to me.

 

Author Response

On behalf of all the contributing authors, I would like to express our sincere appreciations of your constructive comments concerning our article. These comments are all valuable and helpful for improving our article. According to your comments, we have made modifications to our manuscript as follows.

 

In line 2, a new typo as "the ccccc”. Respond: corrected.

In line 69, instead of "Wigner matrices", should be "Wigner matrix". Respond: corrected.

All helpful statements should be better cited. E.g: Lemma1(See [2] Lemma 2.4)

Respond: we add citations for Lemma 1 —Lemma 7.

In the definition of the matrix $M_n$ on page 4, it is worth recalling what the symbols $p$ and $\sigma$ mean.

Respond: we add “where $p:=p(n)$ is the parameter from $G_n(p,q)$, $\sigma=\sqrt{p(1-p)+2q}$” after the definition of M_n on page 4.

In line 121, should be "$p$ increasingly from 0.001 to 0.1”. Respond: Corrected. 

In Remark 2, the terms $\mathcal{F}$ and $c$ must be explained.

Respond. $\mathcal{F}$ is a $\sigma$-algebra of the probability space $(\Omega,\mathcal{F},\Pro)$ and $c$ means complementation of sets. A probability space is a triple $(\Omega,\mathcal{F},\Pro)$, where $\Omega$ is a nonempty set, $\mathcal{F}$ is a $\sigma$-algebra of $\Omega$ (i.e., a nonempty collection of subsets of $\Omega$ that is closed under countable unions and intersections as well as under complementation), and $\Pro$ is a probability measure on the $\sigma$-algebra $\mathcal{F}$ (i.e., a countably additive non-negative set function normalized by the condition $\Pro(\Omega)=1$). See e.g., \cite{kallenberg2006foundations} for more references.

 

For brevity, we rephrase the paragraph to the following:

\begin{Remark}\label{rem2}

The result of the theorem means that if $\sigma^2 =\omega(\frac{1}{n})$, then for any bounded continuous function $f$, we have

      \begin{equation*}

        \int f(x)dF^{\frac{1}{\sigma\sqrt{n}}H_n(\alpha)}(x)\rightarrow\int f(x)dF(x) \quad a.s.

      \end{equation*}

 

On page 11,  $e(\overline{W})=x$ doesn't make sense to me.    Respond: we corrected the “e(\overline{W})=x$” to ‘ \abs{E(\overline\Gamma(\overline{W})}=x’.

Author Response File: Author Response.pdf