Skip to main content
added 17 characters in body
Source Link
feire
  • 101
  • 1

Consider a random directed graph with $n$ nodes. Each node has on average $x$ number of incoming edges.

How many nodes are not part of a cycle? Alternatively phrased, how many strongly connected components are a singleton?

I would think that this question has been answered in the literature. Versions of it have been answered on this site (see here for a solution for bipartite graphs in which each node has a unique incoming edge expected number of cycles in a "random" bipartite directed graph).

I would be very grateful if anyone could provide me with a reference.

Simulations with $x=\log(n)$ show that the fraction of such nodes becomes smaller as $n$ grows, dropping from 68% with $n=25$ to 40% with $n=500$.

Consider a random directed graph with $n$ nodes. Each node has on average $x$ number of incoming edges.

How many nodes are not part of a cycle? Alternatively phrased, how many strongly connected components are a singleton?

I would think that this question has been answered in the literature. Versions of it have been answered on this site (see here for a solution for bipartite graphs in which each node has a unique incoming edge expected number of cycles in a "random" bipartite directed graph).

I would be very grateful if anyone could provide me with a reference.

Simulations show that the fraction of such nodes becomes smaller as $n$ grows, dropping from 68% with $n=25$ to 40% with $n=500$.

Consider a random directed graph with $n$ nodes. Each node has on average $x$ number of incoming edges.

How many nodes are not part of a cycle? Alternatively phrased, how many strongly connected components are a singleton?

I would think that this question has been answered in the literature. Versions of it have been answered on this site (see here for a solution for bipartite graphs in which each node has a unique incoming edge expected number of cycles in a "random" bipartite directed graph).

I would be very grateful if anyone could provide me with a reference.

Simulations with $x=\log(n)$ show that the fraction of such nodes becomes smaller as $n$ grows, dropping from 68% with $n=25$ to 40% with $n=500$.

Source Link
feire
  • 101
  • 1

Expected number of nodes not involved in a cycle

Consider a random directed graph with $n$ nodes. Each node has on average $x$ number of incoming edges.

How many nodes are not part of a cycle? Alternatively phrased, how many strongly connected components are a singleton?

I would think that this question has been answered in the literature. Versions of it have been answered on this site (see here for a solution for bipartite graphs in which each node has a unique incoming edge expected number of cycles in a "random" bipartite directed graph).

I would be very grateful if anyone could provide me with a reference.

Simulations show that the fraction of such nodes becomes smaller as $n$ grows, dropping from 68% with $n=25$ to 40% with $n=500$.