Show that a giant strongly connected component exists

Assignment Help Basic Computer Science

Reference no: EM131313028

Consider a directed random graph of the kind discussed in Section 13.11.

a) If the in- and out-degrees of vertices are uncorre1ated, i.e., if the joint in/outdegree distribution P_jk is a product of separate functions of j and k, show that a giant strongly connected component exists in the graph if and only if c(c -1) > a, where c is the mean degree, either in or out.

b) In real directed graphs the degrees are usually correlated (or anti-correlated). The correlation can be quantified by the covariance ρ of in- and out-degrees. Show that in the presence of correlations, the condition above for the existence of a giant strongly connected component generalizes to c(c - 1) + ρ >O.

c) In the World Wide Web the in- and out-degrees of the vertices have a measured covariance of about ρ = 180. The mean degree is around c = 4.6. On the basis of these numbers, do we expect the Web to have a giant strongly connected component?

Reference no: EM131313028

Questions Cloud

Calculating the mean degree : What is the time complexity, as a function of the number n of vertices and m of edges, of the following network operations if the network in question is stored in adjacency list format?

The stocks and their expected returns and standard deviation : Consider the following stocks and their expected returns and standard deviations:- Between Stock A and Stock B, which would a risk-averse investor prefer? Explain.

Calculate the reciprocity of the network : For a directed network in which in- and out-degrees are uncorrelated, show that it takes time 0(/m2 / n) to calculate the reciprocity of the network. Why is the restriction to uncorrelated degrees necessary? What could happen if they were correlate..

What observations about stores customers does angelou make : What observations about the Stores customers does Angelou make?

Show that a giant strongly connected component exists : In the World Wide Web the in- and out-degrees of the vertices have a measured covariance of about ρ = 180. The mean degree is around c = 4.6. On the basis of these numbers, do we expect the Web to have a giant strongly connected component?

Difference between linear and non-linear accident models : 1. What is the difference between linear and non-linear accident models? Why are non-linear accident models not used more often in workplace accident investigations?

What is the expected return on stock x for next year : If there is a 40% chance that the economy will recover and a 60% that it will not, what is:- The expected return on Stock X for next year?

Derive a rough expression for the diameter of the network : Hence derive a rough expression for the diameter of the network in terms of C1 and C2, and so argue that configuration model networks display the small-world effect in the sense that typical geodesic distances between vertices are O(log n).

Analyze data to learn more about business and customers : You want to analyze data to learn more about your business and customers. Toward this goal, provide one (and only one) specific example question that you might want to address using each of the data analysis techniques below and provide an example ..

User Account

All Pages