This paper proposes a method of generating stochastic overlay simulation network with exact average degree (EAD). It discusses regional distribution of stochastic nodes, selection of core nodes and overlay functional nodes, deductions of new formula of the connectivity probability and the convergence of the connection probability, classification strategy of increasing degree, fast connection strategy of stochastic network. Further explanation of the performance of the stochastic overlay simulation network is also presented.