Return to Question

I have a graph G of N nodes and M edges. Graph G is a real-world graph, which could be connected or disconnected. Still, its largest component has small-world properties: High clustering coefficient and low average shortest length.

Many random subgraphs can be generated from the graph G as follows. I choose randomly (uniformly) n nodes (n < N), where two nodes are connected if they are connected in the original graph. The total number of edges in one subgraph is denoted by m.

I have two questions:

• Should I expect the subgraphs to have some properties of the Erdos-Ranyi graphs?
• And what is the expected number of edges of the subgraphs (m)? Thank you.

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.

I have a graph G of N nodes and M edges.

To create a random subgraph, I choose randomly (uniformly) n nodes (n < N), where two nodes are connected if they are connected in the original graph.

Should I expect the subgraph to have some properties of the Erdos-Ranyi graphs? And what is the expected number of edges of the subgraph? Thank you

I have a graph G of N nodes and M edges. Graph G is a real-world graph, which could be connected or disconnected. Still, its largest component has small-world properties: High clustering coefficient and low average shortest length.

Many random subgraphs can be generated from the graph G as follows. I choose randomly (uniformly) n nodes (n < N), where two nodes are connected if they are connected in the original graph. The total number of edges in one subgraph is denoted by m.

I have two questions:

• Should I expect the subgraphs to have some properties of the Erdos-Ranyi graphs?
• And what is the expected number of edges of the subgraphs (m)? Thank you.