We consider an undirected, static,Sampling dynamic graphs is currently an active research area [1]}, [2]}, [3]}, but out of the scope of this paper.
graph \(G=(V,E)\) , with \(N\!=\!|V|\)  nodes and \(|E|\)  edges.
For a node \(v\in V\) , denote by \(\deg (v)\)  its degree, and by \(\mathcal {N}(v)\subset V\)  the list of neighbors of \(v\) .
A graph \(G\)  can be weighted.
We denote by \(\textrm {w}(u,v)\)  the weight of edge \(\lbrace u,v\rbrace \in E\) , and by
\(\textrm {w}(u) = \sum _{v\in \mathcal {N}(u)} \textrm {w}(u,v)\) 
