Question Graph structure 2 points possible (graded) An Erdos-Renyi model, G (n,p), displays, in the large node limit of n +o, a phase transition in the global graph structure at two points. For p < , there are many small components. The size of these components tends to be bounded above: P(Smax > clnn) → as n + where Smax is the size of the largest component in the graph, and c = 2m/n is the average node degree. Note that this is strictly only a bound as n +, for any finite n there is a non-zero probability of all nodes being connected. 12 Between 1 <p < Inn, a giant component emerges. This giant component has a size that is a significant fraction of n, around (C – 1)n for c = 1 (the relation is not linear for larger c). There will only be one of these giant components; other components will exist, but they will observe the S<cln n bound discussed above. Inn Above p > the giant component includes all nodes in the graph and the graph becomes connected. 12 Although these phase transitions are only defined in the n → limit, you can observe them even for n as small as 100. When n is small, the phase transition points become "fuzzy" in that the transition may not occur at exactly the points described above, but close to them. Suppose that you are given a graph with n=1 x 106 and m = 200 x 103. What would you expect to see if the process that created this graph can be described by an Erdos-Renyi model? Many small connected components. Some small components along with a giant connected component. A single connected component. If you are given a graph with n=1 x 106 and m = 20 x 106, what would you expect to see if the graph came from an Erdos-Renyi model? Many small connected components. Some small components along with a giant connected component. A single connected component.
the giant component includes all nodes in the graph and the graph becomes connected. 12 Although these phase transitions are only defined in the n → limit, you can observe them even for n as small as 100. When n is small, the phase transition points become "fuzzy" in that the transition may not occur at exactly the points described above, but close to them. Suppose that you are given a graph with n=1 x 106 and m = 200 x 103. What would you expect to see if the process that created this graph can be described by an Erdos-Renyi model? Many small connected components. Some small components along with a giant connected component. A single connected component. If you are given a graph with n=1 x 106 and m = 20 x 106, what would you expect to see if the graph came from an Erdos-Renyi model? Many small connected components. Some small components along with a giant connected component. A single connected component.
the giant component includes all nodes in the graph and the graph becomes connected. 12 Although these phase transitions are only defined in the n → limit, you can observe them even for n as small as 100. When n is small, the phase transition points become "fuzzy" in that the transition may not occur at exactly the points described above, but close to them. Suppose that you are given a graph with n=1 x 106 and m = 200 x 103. What would you expect to see if the process that created this graph can be described by an Erdos-Renyi model? Many small connected components. Some small components along with a giant connected component. A single connected component. If you are given a graph with n=1 x 106 and m = 20 x 106, what would you expect to see if the graph came from an Erdos-Renyi model? Many small connected components. Some small components along with a giant connected component. A single connected component.
  Graph structure2 points possible (graded)An Erdos-Renyi model, G(n,p), displays, in the large node limit of n rarr oo, a phase transition in the global graph structure at two points.For p < (1)/(n), there are many small components. The size of these components tends to be bounded above:P(S_(max) > c ln n)rarr0quad" as "n rarr oowhere S_(max) is the size of the largest component in the graph, and c=2m//n is the average node degree. Note that this is strictly only a bound as n rarr oo, for any finite n there is a non-zero probability of all nodes being connected.Between (1)/(n) < p < (ln n)/(n), a giant component emerges. This giant component has a size that is a significant fraction of n, around (c-1)n for c~~1 (the relation is not linear for larger c ). There will only be one of these giant components; other components will exist, but they will observe the S < c ln n bound discussed above.Above p > (ln n)/(n), the giant component includes all nodes in the graph and the gra ... See the full answer