Calculate subgraph density distribution? Let $G=(E,V)$ be an undirected graph, and let $S=(E_S,V_S)$ be a subgraph of $G$.
Also let the density of $S$ to be defined as $d(S)=\frac{|E_S|}{|V_S|}$.
What is the probability distribution of $d(S)$ of all subgraphs with $k$ edges ($k=|E_S|$)?
I am particularly interested in a sort of shortcut for the calculation of this distribution as enumerating all subgraphs becomes computationally very expensive.
 A: It should be easy enough to estimate these probabilities in almost any programming language. Here is one in R (when I have time later today I'll do it in Python as well to confirm the numbers):
# In the following functions a graph/subgraph is represented as
# a matrix in which edges are stored in rows
# it is assumed that no edge is stored twice

randSubgraph <- function(graph,k){
  graph[sample(1:nrow(graph),k),]
}

subgraphDensity <- function(edges){
  nrow(edges)/length(unique(as.vector(edges)))
}

# For testing purposes:

completeGraph <- function(n){
  G <- expand.grid(1:(n-1),2:n)
  G <- as.matrix(G[G[,1]<G[,2],])
  dimnames(G) <- NULL
  G
}

G <- completeGraph(500)
subGraphDensities <- replicate(1000,subgraphDensity(randSubgraph(G,100)))
print(mean(subGraphDensities))
hist(subGraphDensities)

The program generates 1000 100-edge random subgraphs of the complete graph on 500 vertices, calculates the subgraph densities of them, and returns the mean of them, as well as making a histogram. I've run it several times an gotten consistent results (which suggests that the sample size of 1000 is more than enough). The last time I ran it I got a mean density of 0.605863, with the flowing histogram:
 
On Edit: Here is a simple Python version, which represents graphs as simply a list of 2-element sets:
def estimateDensity(G,k,n = 1000):
    total = 0
    for i in range(n):
        S = random.sample(G,k)
        total += k/len(set.union(*S))
    return total/n

def completeGraph(n):
    return [{i,j} for i in range(1,n) for j in range(i+1,n+1)]

For example, 
>>> estimateDensity(completeGraph(500),100)

0.6056279747464909

which meshes with the R output.
