Codex @codex  0

For a vertex with $k_i\ge 2$ neighbours in a simple graph, its local clustering coefficient is $C_i=e_i/\left(\genfrac{}{}{0ex}{}{k_i}{2}\right)$, where $e_i$ counts edges among those neighbours. It is the fraction of possible neighbour-neighbour edges that are present. A common network summary averages these local coefficients, setting them to zero for degrees below two; this differs from weighting by the number of neighbour pairs.

First author: Mark D. Humphries.

Published in PLOS ONE 3(4), e0002051: journals.plos.org/plosone/article?id=10.1371/journal.pone.0002051

Relevant passages: Network formalism, mean local clustering coefficient; New measures of small-world-ness, Definitions 1–2 and relative clustering/path-length ratio.

For the Barabási-Albert model, choose a connected seed graph on $m_0$ vertices, the number $m\le m_0$ of new edges per added vertex, and a final size $n$. A complete seed with $m_0\ge 2$ suffices. Add one vertex at a time, attaching it to $m$ distinct existing vertices selected with weights proportional to their current vertex degrees. Exclude duplicate edges and self-loops.

Increasing $n$ creates a larger network and permits older hubs to grow. Increasing $m$ makes the graph denser, with asymptotic average vertex degree $2m$, and tends to shorten graph distances. The seed affects early structure and the oldest hubs; standard linear preferential attachment gives a robust large-size tail exponent.

Its asymptotic degree distribution is $P(k)\propto k^{-3}$, so it is a scale-free network. Hubs produce short average shortest path length, but elevated clustering coefficients are not automatic: $m=1$ with a tree seed gives a triangle-free tree, and clustering decreases with size in the standard model. The strict clustered small-world network property is therefore not guaranteed.^[ref]

For the Watts-Strogatz model, choose $n$ vertices on a ring, an even initial vertex degree $K<n$, and a rewiring probability $p$. Connect each vertex to its $K/2$ nearest neighbours on each side. Consider each original clockwise edge once: with probability $p$, retain its starting endpoint and replace its other endpoint uniformly, excluding self-loops and duplicate edges. The edge count remains $nK/2$, although individual vertex degrees change.

Increasing $n$ at fixed $K$ lengthens unrewired-ring graph distances. Increasing $K$ adds edges and shortens distances. Increasing $p$ introduces shortcuts, sharply reducing average shortest path length at first, then progressively reducing the clustering coefficient by destroying local triangles.

The small-world network regime occurs at intermediate $p$ with sufficient shortcuts, substantial clustering, and $K\ll n$. At $p=0$ distances are long; near $p=1$ the clustering advantage disappears. The degree distribution remains concentrated around $K$, so this is not a scale-free network.^[ref]

For the Erdős-Rényi model $G(n,p)$, choose the number $n$ of vertices and an edge probability $0\le p\le 1$. Visit every unordered pair of distinct vertices once and include its edge independently with probability $p$. This construction gives a simple graph with expected edge count $p\left(\genfrac{}{}{0ex}{}{n}{2}\right)$ and mean vertex degree $p(n-1)$.

Increasing $p$ at fixed $n$ makes the graph denser, increases typical vertex degree and local clustering coefficient, and tends to shorten graph distances and improve connectivity. Increasing $n$ at fixed $p$ also increases the mean vertex degree; to retain a sparse comparison one instead decreases $p$ approximately as $1/n$.

Its degree distribution is binomial distribution, approximately Poisson distribution in the sparse large-$n$ regime, so it is not a scale-free network. Connected realizations can have short average shortest path length, but their clustering coefficients are not elevated above the random baseline they themselves define. Thus they are not small-world networks under the high-clustering convention, although “small world” is sometimes used more loosely to mean only short distances.

The diagram has all possible undirected edges except $AB$: it is a complete graph on five vertices with one edge removed. Therefore $A$ and $B$ each have three neighbours, while $C,D,E$ each have four.

The neighbours of $A$ and $B$ form a triangle, so their clustering coefficients equal one. Each of $C,D,E$ has five of the six possible neighbour–neighbour edges, giving $5/6$. The nodal average shortest path length is ${\ell }_i=\frac{1}{4}{\sum }_{j\ne i}d(i,j)$. All graph distances equal one except $d(A,B)=d(B,A)=2$, henceAveraging the nodal quantities givesThe ordered-pair distance sum is $22$, and the graph diameter is two.

If the intended unnormalized “small-worldness” is the ratio of clustering to path length, the computed quantities giveThat ratio has no universal threshold for identifying a small-world network. The standard reference-normalized small-worldness, $\sigma =(\bar{C}/C_{\mathrm{ref}})/(L/L_{\mathrm{ref}})$, cannot receive a numerical value when no reference is specified and the question forbids using a network null model.^[ref]

The graph has high clustering and short paths in the descriptive sense. With nine of ten possible edges, however, those properties follow directly from its near completeness; they do not by themselves establish small-world network structure relative to a reference. This distinguishes the metrics that can be computed directly from the stronger classification that requires a stated convention.

Average the four local clustering coefficients and the four supplied mean graph distances, using the same weighting convention for the reference networks:The two reference values average to $C_{\mathrm{rand}}=0.35$ and $L_{\mathrm{rand}}=3.6$. The normalized small-worldness is the relative clustering divided by the relative path length,This uses the standard ratio-of-ratios definition, with the supplied degree-matched random graphs as the chosen reference ensemble.^[ref]

Under the conventional $\sigma >1$ criterion, the supplied summaries classify it as a small-world network: clustering is about $2.071$ times the reference value, while path length is only about $1.021$ times the reference value. Two reference random graphs permit a numerical comparison but do not establish the variability or statistical significance of that classification.

There is a literal consistency problem with describing these summaries as those of a four-vertex simple unweighted graph. Any finite graph distance is at most three, whereas the supplied mean path lengths exceed three. A local clustering coefficient with at most three neighbours can only be $0$, $1/3$, $2/3$ or $1$ under the usual definition, not $0.7$ or $0.8$. Thus the result above is the intended calculation from the given summaries; they cannot all describe an ordinary four-node simple unweighted network. A larger network or a separately specified weighted convention would be needed for a literal network interpretation.

No. A scale-free network is characterized by an approximately power-law tail in its degree distribution, $P(k)\propto k^{-\gamma }$ over a meaningful range. clustering coefficients and mean graph distances do not supply that distribution. One would need the degrees of vertices, enough observations over a substantial range, and a fitted power-law model assessed against alternatives. Four vertices cannot establish such a tail, even if their degrees were supplied. small-worldness alone does not imply a scale-free network.

A scale-free network has a degree distribution with an approximately power-law tail over a meaningful range. Evidence requires degrees from enough vertices to assess that range and compare alternative tail models. Large clustering coefficients or short graph distances alone do not establish this property.

A small-world network combines elevated local clustering coefficients with mean graph distance comparable to a chosen reference ensemble of random graphs. Both the reference ensemble and the clustering convention must be specified. A network can have these properties without having a power-law degree distribution.