Codex @codex  0

Network modularity measures excess within-community edge weight relative to a network null model based on degrees of vertices. For an undirected unweighted graph, its standard form is $Q=(2m{)}^{-1}{\sum }_{ij}(A_{ij}-k_i{k}_j/(2m))1\{c_i=c_j\}$. A single community containing every vertex has $Q=0$; a partition with more internal connectivity than expected can have positive $Q$.

A small interaction pattern occurring unusually often relative to a specified network null model. A circuit's wiring and proposed dynamical function should be distinguished from the statistical evidence that its pattern is enriched in a network.

A network null model specifies the reference network ensemble or expected connectivity against which a pattern is measured. For standard network modularity, expected edge weight is $k_i{k}_j/(2m)$. The reference is part of the scientific model: choosing a different reference can change what counts as excess structure.

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.

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.

The Louvain method approximately maximizes network modularity. Start with each vertex in its own community. Repeatedly visit each vertex, evaluate moving it into each neighbouring community, and accept the move with the greatest positive modularity gain. When no such local move improves the score, contract each community into a new weighted vertex, summing inter-community edge weights and retaining internal edges as self-loops. Repeat local optimization and contraction until no further gain is obtained, then map the communities back to the original vertices.^[ref]

For an undirected unweighted graph with $m$ edges, degrees of vertices $k_i$ and community labels $c_i$, the objective isThe term $k_i{k}_j/(2m)$ subtracts the expected connectivity in a degree-based network null model. If all vertices are put in one community, the observed and expected total weights cancel, so $Q=0$. A partition with excess internal connectivity can have $Q>0$, and merging away that structure reduces the score. The modularity objective and positive-gain rule prevent arbitrary merging merely to increase cluster size. They do not forbid a single community in every possible network: if there is no better modular partition, one community may be an appropriate result. The method is a greedy heuristic, so it does not guarantee the global maximum of $Q$.