当生成一个包含 n 个节点的随机图时，我们开始通过随机选择节点对来添加边。当我们添加边时，最大连通子图（组件）的直径会不断增长，直到平均节点度 c=

When generating a random graph with n nodes, we start adding edges by randomly selecting pairs of nodes. As we adding the edges, the diameter of the largest connected subgraph (component) grows till the average node degree c =

Question

当生成一个包含 n 个节点的随机图时，我们开始通过随机选择节点对来添加边。当我们添加边时，最大连通子图（组件）的直径会不断增长，直到平均节点度 c=

When generating a random graph with n nodes, we start adding edges by randomly selecting pairs of nodes. As we adding the edges, the diameter of the largest connected subgraph (component) grows till the average node degree c =

BlackTom AI · Accepted Answer

The Erdős–Rényi random graph exhibits a sharp phase transition at average degree c = 1. Relevant concepts: - Two common models: G(n,m) (m random edges) and G(n,p) (each edge present with probability p). The average degree c equals 2m/n in G(n,m) and c = np in G(n,p). - The growth and structure of connected components can be analyzed by approximating component exploration with a Galton–Watson branching process whose mean offspring (expected new neighbors) is c. - A branching process with mean < 1 dies out quickly (subcritical), at = 1 is critical, and > 1 is supercritical leading to a giant component. Step-by-step reasoning and intermediate calculations: 1. Express average degree in terms of added edges. After m edges: c = 2m/n. In the probabilistic model p = expected edges/(number of possible edges) and c = np. 2. Set c = 1 to find the threshold in G(n,m): 1 = 2m/n ⇒ m = n/2. In G(n,p): 1 = np ⇒ p = 1/n. 3. For c < 1 (subcritical), components are small (typical size O(log n) or bounded), and the largest component diameter increases with added edges but remains relatively small. At c = 1 (critical) component sizes and diameters peak (largest component size scales ~ n^{2/3}), and beyond c > 1 a single giant component of Θ(n) nodes appears. 4. The branching-process intuition: when the expected new neighbors per explored vertex (c) exceeds 1, exploration typically does not die out and a giant component emerges. Thus the diameter growth of the largest component culminates at the critical point c = 1. Why the correct answer is 1 and why others are wrong: - 1 is the classical phase-transition threshold where the giant component emerges and diameters reach their maximum scale. - 0 is trivial (no edges), so diameter does not grow to that value. - 2/n is negligible (for large n) and not a known threshold. - n − 1 is the complete graph degree, far beyond the emergence threshold. Conclusion: The diameter grows until the average node degree c = 1, which matches the provided correct answer.

类似问题

在随机图 G(n, p) 中，边的数量的期望值是 m = In a random graph G(n, p), the expected number of edge m =

For stock A, we have 𝛽 𝑖 = 0.70. Suppose the expected market risk premium next year is 9% and the risk-free rate is 3%. What is the expected return of this stock based on the CAPM? (Please answer in % and round to 2 decimal places. If the answer is 8.057%, then in the box, write 8.06)

The following graph shows the Security Market Line in the current economy. If a stock has a β of 1.2, what is the expected return of this stock based on the CAPM? (Please answer in % and round to 2 decimal places. If the answer is 8.057%, then in the box, write 8.06)

Suppose Apple publicly announces earnings today and the announcement is above market expectations. If markets are semistrong-form efficient, then:

更多留学生实用工具

智能学习助手

风格化写作助手

论文查重助手

文献引用助手

课堂转译助手

课堂笔记助手

Quiz搜索助手

学校历年真题

智能刷题助手

智能匹配练习

希望你的学习变得更简单