Random subgraph properties Consider a graph $G$ of $N$ vertices and $M$ edges, and assume $G$ has typical complex network properties: it is not necessarily connected, but it has a high clustering coefficient and a giant connected component with low average distance.
Now, consider a graph $G'$ defined as the sub-graph of $G$ induced by a randomly chosen set of $n$ vertices. Let us denote by $m$ its number of edges.

*

*Is $G'$ likely to have the typical properties of an Erdős–Rényi random graph?


*What is the expected value of $m$?
Thank you.
 A: I fear the question is difficult in its general form: the answer will strongly depends on the assumptions we make regarding the initial graph, and on how we choose $n$.
As noticed by @dodd, in particular, the sampling applied to a complete graph will lead to a complete sub-graph. Likewise, an initially empty graph will lead to an empty sub-graph.
But I guess we should assume a sparse graph with high clustering coefficient. The low average distance is not a very significant property.
If $n$ is large, close to $N$, then we only remove some nodes, and so we may expect a sub-graph with large clustering coefficient too.
If $n$ is low, far from $N$, then the nodes we choose have a high probability of not being linked together, since the graph is sparse, and we may end with an almost empty graph. It may then be similar to an ER graph with only few edges.
To go further, I think we have to study the probability to sample several neighbours of a same node, since they have a high probability to be linked together (clustering coefficient). To evaluate this, I suggest we look at the degree distribution of the initial graph, and at its degree-clustering correlations.
I think it's all I can say without additional information.
