I recently want to test my network estimation algorithms and need to sample some data from undirected graphs.

The natural way I think of was:

  1. Generate a sparse symmetric Precision matrix $P$.
  2. Calculate SVD: $P=USV^T$
  3. adding a constant $\hat{S}=S+c$ to make sure min$(\hat{S})\geq 0$. (So $c$ can be determined very with constant time since it will be 0 if min$(S)\geq 0$ and will be $|$min$(S)$$|$ otherwise.)
  4. $\Sigma=(U\hat{S}V^T)^{-1}$ and sample data with $\Sigma$ as covariance.

However, I found that $U\hat{S}V^T$ is always quite dense, which is not ideal.

Alternatively, it seems a better way is to use $\hat{P}=P+\lambda I$ for the minimum positive $\lambda$ for $\hat{P}$ to be p.s.d. But how should I find the optimal $\lambda$?

Actually, I am not sure I understand why these two methods are different. Can someone please also explain that?

  • $\begingroup$ Can you explain how you are going from a precision matrix to an edge list? $\endgroup$ – Cliff AB Nov 25 '17 at 21:21
  • $\begingroup$ Also note that one of the standards for generating test data is a stochastic block model, although it's acknowledged to be an overly naive model for a variety of reasons. $\endgroup$ – Cliff AB Nov 25 '17 at 21:23
  • $\begingroup$ @CliffAB Isn't that the non-zero coefficient of Precision matrix means an edge in the graph? $\endgroup$ – Haohan Wang Nov 25 '17 at 21:32
  • $\begingroup$ How about using spectral decomposition instead? The eigenvalues and vectors of real symmetric matrix are real. This way will provide you the minimal $\lambda$ you need. $\endgroup$ – tmrlvi Nov 25 '17 at 22:18

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.