# How to sample undirected graph/network data?

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?

• Can you explain how you are going from a precision matrix to an edge list? – Cliff AB Nov 25 '17 at 21:21
• 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. – Cliff AB Nov 25 '17 at 21:23
• @CliffAB Isn't that the non-zero coefficient of Precision matrix means an edge in the graph? – Haohan Wang Nov 25 '17 at 21:32
• 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. – tmrlvi Nov 25 '17 at 22:18