2
$\begingroup$

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.

Improve this question
$\endgroup$
10
  • $\begingroup$ If the graph is complete then any random subgraph is complete. If the graph is a cycle (path) and $n$ is small enough then the subgraph will be empty with positive probability. $\endgroup$
    – markvs
    Commented Dec 15, 2020 at 0:55
  • $\begingroup$ I didn't mention, but the graph G is in fact a real-world graph (citation graph), which is not connected, so it is not complete. $\endgroup$
    – lenhhoxung
    Commented Dec 15, 2020 at 1:16
  • 1
    $\begingroup$ My intention was to show that, as formulated, the question does not make sense. $\endgroup$
    – markvs
    Commented Dec 15, 2020 at 1:36
  • 1
    $\begingroup$ It is now less understandable. There is no such thing as real world graph. The other properties hold in a complete graph. $\endgroup$
    – markvs
    Commented Dec 15, 2020 at 21:28
  • 1
    $\begingroup$ It would be interesting to know examples of non-real world graphs. $\endgroup$
    – markvs
    Commented Dec 18, 2020 at 4:39

1 Answer 1

Reset to default
2
$\begingroup$

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.

Improve this answer
$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .