For a finite graph on vertices, its graph bandwidth is the minimum of over all bijective labels . 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 . 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.
An acyclic spanning subgraph containing a spanning tree of each connected component of the original graph. For a graph with vertices and components, a spanning forest has edges.
For a vertex with neighbours in a simple graph, its local clustering coefficient is , where 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.
A degree distribution assigns the fraction or probability of vertices having each degree of a vertex. For an observed network, . 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 and by and , 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: . 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 .
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 . A single community containing every vertex has ; a partition with more internal connectivity than expected can have positive .
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 . 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]
Collective dynamics of small-world networks by Duncan J. Watts and Steven H. Strogatz. model construction and small-world regime
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]
Emergence of scaling in random networks by Albert-László Barabási and Réka Albert. 1999, growth and preferential-attachment mechanism
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.
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/
Réka Albert, portrait on her institutional homepage
. Persistence of a specified network property under a specified class of perturbations. Robustness of connectivity and robustness of dynamical function are different questions.
There are unlisted articles, also show them or only show them.

