For a finite graph $G$ on $n$ vertices, its graph bandwidth is the minimum of ${\max }_{uv\in E}|\ell (u)-\ell (v)|$ over all bijective labels $\ell :V\to \{1,\dots ,n\}$. It asks how close adjacent vertices can be placed in a line. For an edgeless graph the bandwidth is taken as zero.

A path has bandwidth one, while a complete graph has bandwidth $n-1$. With the same ordering of rows and columns, this is the smallest matrix bandwidth achievable for the adjacency matrix. It matters in storing sparse matrices and reducing the work or memory associated with interactions far from the diagonal.

The intersection graph of chords of a circle: each chord is a vertex, and two vertices are adjacent when their chords cross. Two chords with distinct endpoints cross exactly when their endpoints alternate around the circle.

An acyclic spanning subgraph containing a spanning tree of each connected component of the original graph. For a graph with $n$ vertices and $c$ components, a spanning forest has $n-c$ edges.

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.

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.

Small-worldness compares a network's clustering and average shortest-path length to reference values through $\sigma =(C/C_{\mathrm{rand}})/(L/L_{\mathrm{rand}})$. The common $\sigma >1$ classification is a ratio-based convention rather than a significance test; random-reference variability must be assessed separately.^[ref]

A degree distribution assigns the fraction or probability of vertices having each degree of a vertex. For an observed network, $P(k)=\#\{i:k_i=k\}/n$. Preserving every labelled degree preserves this distribution, but preserving only its mean does not.

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.

Degree-preserving edge rewiring replaces two edges $(u,v)$ and $(x,y)$ by $(u,y)$ and $(x,v)$, preserving every endpoint's degree of a vertex. On simple graphs, reject proposed self-loops and duplicate edges. Symmetric random proposals with rejected moves retained preserve a uniform distribution on the reachable realizations; adequate mixing remains a separate requirement. Connectivity can change unless explicitly constrained.

For a finite undirected graph with at least one edge, eigenvector centrality assigns nonnegative vertex scores proportional to the sum of neighbouring scores: $v_i={\lambda }_{\max }^{-1}{\sum }_j{A}_{ij}{v}_j$. It uses a nonnegative eigenvector of the adjacency matrix for its largest positive eigenvalue. State the normalization, such as Euclidean norm one. For a three-leaf star graph, hub and leaf scores have ratio $\sqrt{3}$.

The Louvain method is a greedy multilevel community detection algorithm maximizing network modularity. It alternates positive-gain single-vertex moves with contraction of communities into weighted vertices. Different vertex orders can produce different local optima; a result is not a certificate of globally maximum modularity.^[ref]

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 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.

Community detection partitions a network into groups according to a specified structural criterion, often excess internal connectivity. The output depends on the objective, so a partition inferred from topology need not by itself establish distinct biological functions.

Duncan J. Watts studies graphs and collective behavior using mathematical models, experiments, and large-scale data. His 1998 work with Steven H. Strogatz introduced the Watts-Strogatz model, showing how a few rewired connections can greatly shorten paths in an otherwise locally clustered graph.^[ref]

This gave a concrete explanation for how high clustering and short path lengths can coexist. His institutional biography describes research on social and organizational graphs, collective dynamics, and web-based experiments, alongside training in physics and theoretical and applied mechanics.^[ref]

Albert-László Barabási is a physicist known for work on complex networks. With Réka Albert, he introduced the Barabási-Albert model, in which a growing graph attaches new vertices preferentially to vertices with larger degree.^[ref]

The central scientific idea is a mechanism, rather than merely a fitted curve: growth and degree-dependent attachment can create a broad degree distribution. This encouraged testing network formation rules against data and helped connect graph theory with statistical mechanics. The mechanism does not imply that every heavy-tailed real network follows that model.

Laboratory website: www.barabasi.com/

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/

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.

Persistence of a specified network property under a specified class of perturbations. Robustness of connectivity and robustness of dynamical function are different questions.

The number of grafted chains per unit substrate area. For roughly uniform attachment spacing $D$, it scales as $D^{-2}$.