Abstract
Scatter many points and join randomly chosen pairs with edges, and connected clusters form. This paper sets the mean number of neighbours per point $c$ to $0.5$, $1$ and $2$, increases the number of points from $1000$ to $64000$ fourfold at a time, measures how the largest cluster grows, and compares the second cluster and the mean size of small clusters for each $c$. No new theorem or law is claimed.
First, with c below 1 the largest cluster grows only like the logarithm of the number of points: at $c=0.5$ the mean largest cluster was $11.025$, $16.450$, $20.500$ and $26.200$; the overall power over a $64$-fold increase was $\mathbf{0.208131}$, and the differences from the logarithmic formula values $10.749$, $15.559$, $20.736$ and $26.181$ were within twice the standard error (Section 2).
Second, with c above 1 the largest cluster is proportional to the number of points: at $c=2$ the overall power was $\mathbf{1.000894}$ and the cluster’s share at $64000$ points was $0.797359$, close to $0.796812$, the solution of $s=1-\exp(-cs)$ (Section 2).
Third, at exactly c equal to 1 it grows with a power in between: at $c=1$ the mean largest cluster was $90.290$, $226.305$, $590.260$ and $1643.225$, with an overall power of $\mathbf{0.697637}$ (Section 2).
Fourth, the second cluster and small clusters are large near the boundary: at $16000$ points the second cluster was largest at $c=1.1$, $277.200$, and $11.200$ at $c=2$. Away from the boundary, at $c=0.6$, $0.8$, $1.5$ and $2$, the mean size of small clusters matched the formula within a relative $0.037917$ (Section 3).
Fifth, the separator is whether a cluster is seen as a share of the points or by the power with which it grows as points are added: as shares, all clusters with c at or below 1 approach $0$ and cannot be told apart, but as powers they split into logarithmic, in-between and proportional (Section 4).
Keywords: random graph, giant cluster, Erdős–Rényi, connected components, finite number of points, measured power.
Scope (what is not claimed)
No new theorem or law is claimed: that in a graph with randomly drawn edges a largest cluster appears across a mean of $1$ neighbour (Erdős and Rényi), the formula $s=1-\exp(-cs)$ for its share, and that below the boundary clusters are of logarithmic size and at the boundary of about the $2/3$ power of the number of points are all known. Measured with finite points: points go up to $64000$ and the powers are values for finite numbers of points. The power $0.697637$ at $c=1$ is not claimed to equal the limiting value. How edges are drawn: $cn/2$ edges were drawn by choosing two points independently at random, allowing the same pair or the same point twice. No real network is treated: human ties, communication networks and the spread of infection are not mapped onto it. Relation to earlier papers: Paper 264 showed that inside one phenomenon live a number that moves with the lattice and a number that does not. Here, in a graph without a lattice, it is counted that the growth power of the cluster splits into three by the mean number of neighbours. Paper 271 showed that mean field does not see the dimension, yet the dimension alone settles how far it errs. Here, in a graph without dimension, growth is measured as a power of the number of points. Paper 511 showed that the epidemic threshold and final size both come from $R_{0}$ and obtained the final size from $z=1-e^{-R_{0}z}$. Here the share of the largest cluster appears as a value of the same form of equation ($0.796812$ at $c=2$). What is added: finding the growth powers over a $64$-fold increase in points for three values of $c$, checking clusters below the boundary against the logarithmic formula, listing the $c$ at which the second cluster is largest and the mean size of small clusters, and placing the separator on “share, or power”.
1. Notation and the Question
Setting: place $n$ points and draw $cn/2$ edges between randomly chosen pairs. $c$ is the mean number of neighbours per point. A set of connected points is a cluster. For mean number of neighbours $c>1$, the share $s$ of the largest cluster is known to approach the solution of the following equation.
$$s=1-e^{-cs}$$The solutions are $0.582812$, $0.796812$ and $0.940480$ at $c=1.5$, $2$ and $3$, and $0$ for $c\le1$.
Measurement: at $n=1000$, $4000$, $16000$ and $64000$, the mean and standard error of the largest cluster size are found ($400$, $200$, $100$ and $40$ runs at $c=1$). $\log(\text{size ratio})/\log4$ for a fourfold increase in points is the “power per fourfold”, and from $1000$ to $64000$ the “overall power”.
Question: how does the largest cluster grow as points are added, and how does that change with the mean number of neighbours?
2. How the Largest Cluster Grows
Computation 2.1: mean largest cluster (standard error in parentheses).
| $c$ | $n=1000$ | $n=4000$ | $n=16000$ | $n=64000$ | overall power |
|---|---|---|---|---|---|
| $0.5$ | $11.025$ ($0.388$) | $16.450$ ($1.070$) | $20.500$ ($1.416$) | $26.200$ ($1.772$) | $\mathbf{0.208131}$ |
| $1$ | $90.290$ ($2.024$) | $226.305$ ($7.848$) | $590.260$ ($27.244$) | $1643.225$ ($147.650$) | $\mathbf{0.697637}$ |
| $2$ | $794.400$ ($2.337$) | $3184.200$ ($5.848$) | $12744.600$ ($16.452$) | $51031.000$ ($36.474$) | $\mathbf{1.000894}$ |
The powers per fourfold were $0.288654$, $0.158768$ and $0.176971$ at $c=0.5$; $0.662815$, $0.691541$ and $0.738554$ at $c=1$; and $1.001497$, $1.000442$ and $1.000744$ at $c=2$.
Computation 2.2: the comparison formula at $c=0.5$, $(\ln n-2.5\ln\ln n)/(c-1-\ln c)$ with $c-1-\ln c=0.193147$, gave $10.749$, $15.559$, $20.736$ and $26.181$, and for all four $n$ the difference from the mean was within twice the standard error. The share at $c=2$, $n=64000$ was $0.797359$ (formula $0.796812$).
Observation 2.3 the same “largest cluster” splits into three by its growth power. At $c=2$, multiplying the points by $4$ makes the cluster nearly $4$ times larger, a power close to $1$: at $c=0.5$ the power shrinks from $0.288654$ to $0.176971$, following the logarithmic formula. $c=1$ lies between, with an overall power of $0.697637$ (a value for finite $n$; even with more runs the standard error at $n=64000$ is $147.650$).
3. The Second Cluster and Small Clusters
Computation 3.1: $n=16000$, $10$ runs each. The mean size of small clusters is the mean size of the cluster containing a randomly chosen point outside the largest cluster (formula $1/(1-c)$ for $c<1$ and $1/(1-c(1-s))$ for $c>1$).
| $c$ | second cluster | mean size of small clusters | formula |
|---|---|---|---|
| $0.6$ | $23.800$ | $2.493888$ | $2.500000$ |
| $0.8$ | $58.600$ | $5.189587$ | $5.000000$ |
| $0.9$ | $103.500$ | $9.214250$ | $10.000000$ |
| $1.0$ | $240.500$ | $40.196050$ | diverges |
| $1.1$ | $\mathbf{277.200}$ | $19.585278$ | $10.666945$ |
| $1.2$ | $108.300$ | $6.707084$ | $5.667713$ |
| $1.5$ | $27.400$ | $2.628430$ | $2.672243$ |
| $2.0$ | $11.200$ | $1.684342$ | $1.684567$ |
Away from the boundary, at $c=0.6$, $0.8$, $1.5$ and $2$, the relative differences from the formula were $0.002445$, $0.037917$, $0.016396$ and $0.000134$.
Observation 3.2 near the boundary both the second cluster and small clusters are large. The second cluster was largest at $1.1$ among the eight values of $c$: away from the boundary the mean size of small clusters matches the formula, but at $c=0.9$, $1.1$ and $1.2$ it departed from the formula (the source of the departure was not checked by changing the number of points). Whether the second cluster peaks exactly at $c=1$ is not claimed with this number of points and runs.
4. The Separator
Observation 4.1 the separator is whether a cluster is seen as a share of the points or by the power with which it grows as points are added. As shares, both $26.200/64000$ at $c=0.5$ and $1643.225/64000$ at $c=1$ approach $0$ as points are added, and only $c=2$ remains at $0.797359$: as powers, the two that approach $0$ split into $0.208131$ and $0.697637$, and with $1.000894$ at $c=2$ they make three ways of growing.
Observation 4.2 what is not said. Limiting values of the powers, the exact $c$ at which the second cluster peaks, real networks and percolation on lattices are not treated. What is shown is that in random graphs of up to $64000$ points the growth power of the largest cluster split into three by the mean number of neighbours.
5. Roll Call and Closing
- graph with $cn/2$ edges and the formula $s=1-e^{-cs}$ (Section 1): boundary at $c=1$.
- overall power $\mathbf{0.208131}$ at $c=0.5$ (Computations 2.1 and 2.2): logarithmic.
- overall power $\mathbf{1.000894}$ at $c=2$ (Computation 2.1): proportional, share $0.797359$.
- overall power $\mathbf{0.697637}$ at $c=1$ (Computation 2.1): in between.
- second cluster $\mathbf{277.200}$ at $c=1.1$ (Computation 3.1): large near the boundary.
- share, or power (Observation 4.1): the separator; Papers 264, 271 and 511.
Closing: The largest cluster of a random graph grows by three different powers depending on the mean number of neighbours. Increasing the points from $1000$ to $64000$, with a mean of $0.5$ neighbours the overall power was $0.208131$ following the logarithmic formula, with $2$ it was $1.000894$ and the share stayed at $0.797359$, and with $1$ it was $0.697637$: the second cluster peaked at $c=1.1$ at $277.200$, and at four values of $c$ away from the boundary the mean size of small clusters matched the formula. The separator is whether a cluster is seen as a share of the points or by the power with which it grows as points are added. Placed among the earlier papers: the boundary that Papers 264 and 271 viewed through lattice and dimension was measured as a power of the number of points in a graph with neither, and the value of the same form of equation as the final size in Paper 511 was seen as a cluster share. To be honest: limiting values are not given. That with finite points the same largest cluster appears to split into three by its power, and no further.
References
- Bollobás, B. (2001). Random Graphs (2nd ed.). Cambridge University Press.
- Erdős, P., & Rényi, A. (1960). On the evolution of random graphs. Publications of the Mathematical Institute of the Hungarian Academy of Sciences.
- Yamagishi, Y. (2026). Inside One Phenomenon Live a Number That Moves with the Lattice and a Number That Does Not [Paper 264]. YOI: https://www.yamagishiyuuki.com/yoi/264; DOI: 10.5281/zenodo.22169720
- Yamagishi, Y. (2026). Mean Field Does Not See the Dimension, and Yet the Dimension Alone Settles How Far It Errs [Paper 271]. YOI: https://www.yamagishiyuuki.com/yoi/271; DOI: 10.5281/zenodo.22169925
- Yamagishi, Y. (2026). The Threshold and the Final Size Both Come from $R_{0}$, and Their Ratio Is Not Constant [Paper 511]. YOI: https://www.yamagishiyuuki.com/yoi/511; DOI: 10.5281/zenodo.22862074
Reference
Yamagishi, Y. (2026). The Largest Cluster of a Random Graph Grows by Three Different Powers Depending on the Mean Number of Neighbours [Paper 946]. YOI: https://www.yamagishiyuuki.com/yoi/946
ORCID: 0009-0006-8587-3450
PDF (English) · PDF (Japanese) · Date proof of the English PDF (OpenTimestamps .ots) · SHA256SUMS
The record page for this paper (in Japanese, with the PDFs in each language and the date proof): YOI 946. This paper is a preprint and has not been peer reviewed.