We can make a directed equivalent of the random graph by taking n nodes and placing...

  

Transcribed Image Text:

We can make a directed equivalent of the random graph by taking n nodes and placing directed edges with probability p between every pair of distinct nodes. We explicitly and separately consider placing an edge in each direction between every node pair, so a given pair could end up connected by zero edges, one edge, or two edges in opposite directions. a.) What is the average number m of directed edges in the network in terms of n and p? Hence, what is the average degree c (either in or out) of a node? b.) If we were to discard the directions of the edges, making an undirected network, what would the average degree be? Show that the fraction W of the network occupied by the giant weakly connected component is a solution of W - 1-e-2cW in the limit of large n. c.) Let S be the fraction of the network occupied by the giant strongly connected compo- nent. In order to belong to the giant strongly connected component, a node must have at least one outgoing edge leading to another node in the giant strongly connected component and at least one incoming edge leading from a node in the giant strongly connected component. Hence, derive an equation analogous to that for W above that must be satisfied by S in the limit of large n. We can make a directed equivalent of the random graph by taking n nodes and placing directed edges with probability p between every pair of distinct nodes. We explicitly and separately consider placing an edge in each direction between every node pair, so a given pair could end up connected by zero edges, one edge, or two edges in opposite directions. a.) What is the average number m of directed edges in the network in terms of n and p? Hence, what is the average degree c (either in or out) of a node? b.) If we were to discard the directions of the edges, making an undirected network, what would the average degree be? Show that the fraction W of the network occupied by the giant weakly connected component is a solution of W - 1-e-2cW in the limit of large n. c.) Let S be the fraction of the network occupied by the giant strongly connected compo- nent. In order to belong to the giant strongly connected component, a node must have at least one outgoing edge leading to another node in the giant strongly connected component and at least one incoming edge leading from a node in the giant strongly connected component. Hence, derive an equation analogous to that for W above that must be satisfied by S in the limit of large n.