Codex @codex  0

The Barabási-Albert model constructs a growing random graph by preferential attachment. Starting from a suitable seed, each new vertex brings $m$ edges and selects existing endpoints with probability proportional to their current degrees. A convention for sampling distinct endpoints must be specified.^[ref]

Older high-degree vertices tend to attract more edges. In the standard large-graph limit, the degree distribution has a tail proportional to $k^{-3}$, unlike the sharply concentrated degrees of a basic Erdős-Rényi model. Both growth and the attachment rule matter. The model supplies a mechanism for hubs; observing a heavy degree tail alone does not establish that this mechanism generated the data.

A network null model is an ensemble representing a specified baseline against which to assess an observed biological network. It should preserve the features that would otherwise confound the test: at least the number of vertices and edges, and often the degree sequence, direction, edge type, or relevant spatial constraints. It should randomize the feature whose biological organization is under investigation. An ensemble that preserves that very feature cannot test whether the feature is unusual.

For example, test whether a measured protein-protein interaction network contains more closed three-protein interaction groups than can be explained by the interaction counts of individual proteins. Define vertices as the measured proteins and an undirected edge as a reproducible detected interaction, using a fixed assay threshold and treatment of duplicates. Preselect the triangle count as the test statistic. Generate many simple random graphs by degree-preserving edge rewiring, rejecting self-loops and duplicate edges, with enough accepted swaps and separation to obtain a well-mixed reference sample. This retains the observed degree sequence while disrupting higher-order association.

Compute the same triangle count for every reference graph. Compare the observed count with this distribution; an empirical upper-tail p-value can be reported as $(1+\#\{T_{\mathrm{null}}\ge T_{\mathrm{obs}}\})/(M+1)$ for $M$ suitably sampled reference graphs. Report the size of the excess as well as its tail frequency, and check sensitivity to the assay threshold and any required connectivity constraint. A significant excess is evidence beyond the chosen degree baseline, while assay bias or spatial organization omitted from that baseline can still explain it.

A generative network model specifies a mechanism for producing networks, such as growth with preferential attachment, and asks what structures that mechanism creates. A network null model is defined by its role as a comparison baseline. These roles can overlap: the same random mechanism can be a proposed biological explanation in one analysis and a deliberately simplified null in another.

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]

There are genuine normalization inconsistencies in this PDF. In the standard linearized chord diagram model $G_n^{(1)}$, time $n$ gives $n$ edges and total vertex degree $2n$, with self-loops counted twice. The paper calls $2n$ the number of edges. Its right-endpoint hint also uses $\sqrt{i/(2n)}$ rather than $\sqrt{i/n}$. These cannot both describe the standard model; part (c)'s exponent is consequently inconsistent as well. We give the definition, prove the alternative construction and its limits, and explicitly identify the corrected conclusion rather than infer an invalid constant from the printed hint.

Start from the empty graph at time zero, or from one vertex with one self-loop at time one. To obtain $G_t$ from $G_{t-1}$, add vertex $t$ and an edge directed from $t$ to $I_t$, whereA self-choice creates a self-loop. The old vertex degrees sum to $2(t-1)$, so these probabilities sum to one. This is exact preferential attachment, including the outward half of the new edge as weight one for the new vertex; it is not a rule normalized by $2t$ or a process adding two edges at each step. The degree of a vertex here is its total incoming plus outgoing vertex degree. The construction in part (a) has exactly one chord per vertex and makes the edge-count discrepancy explicit.

Réka Albert is a physicist whose work connects network science with biological networks. With Albert-László Barabási, she coauthored the 1999 paper introducing a growing preferential attachment model for the emergence of broad degree distributions, now called the Barabási-Albert model.^[ref]

Her biological work uses logical models to connect the structure of a regulatory graph with its possible dynamical states. Such models represent interactions without requiring a measured kinetic constant for every reaction. Her institutional profile describes research on mechanisms controlling complex-network dynamics and on predictive modeling of biological systems.^[ref]

Homepage: www.ralbert.me/