Statistical and dynamical physics of complex networks — graphs whose nodes and edges are governed by universal statistical laws rather than by a specific geometric or chemical lattice structure. Canonical ensembles: Erdős-Rényi 1959-60…
network-physics
Erdős-Rényi random graph G(N, p): giant component at ⟨k⟩ = 1
Erdős-Rényi 1959-60 (Publ. Math. Debrecen 6:290; Publ. Math. Inst. Hung. Acad. Sci. 5:17) defined the ensemble G(N, p) of undirected graphs…
Barabási-Albert 1999: preferential attachment → γ = 3
Barabási-Albert 1999 (Science 286:509) proposed that the 'scale-free' property (power-law P(k) ~ k^{-γ}) observed in the World-Wide-Web and…
Watts-Strogatz 1998 small-world: C(p) ≈ C(0)(1-p)³
Watts-Strogatz 1998 (Nature 393:440) introduced the small-world network model interpolating between regular lattices (high clustering C,…
ER giant-component threshold: ⟨k⟩_c = 1 exact (Poisson branching)
Exact derivation of the ER critical connectivity. Probability that a randomly chosen node is NOT in the giant connected component, q,…
BA exponent γ = 3 exact from P(k) = 2m(m+1)/[k(k+1)(k+2)]
Exact closed-form evaluation of the Barabási-Albert degree distribution and its large-k exponent. Master-equation solution with boundary…
WS clustering: C(0) = 1/2 at K=2, C(p=1/2)/C(0) = 1/8
Exact closed-form evaluation of the Watts-Strogatz clustering at two canonical points. Regular ring with K = 2 neighbours per side (degree…
Cycle graph C_N as planar graph: Euler formula V - E + F = 2 with V = N, E = N, F = 2
Planar-graph Euler-formula framework. Setup: a connected planar graph G embedded in the plane (or sphere) with V vertices, E edges, and F…
Cycle-graph Laplacian spectrum: eigenvalues 2 - 2 cos(2 pi k/N); trace equals 2N (Chebyshev sum identity)
Cycle-graph Laplacian framework via Chebyshev polynomials. Setup: the graph Laplacian L of the cycle C_N is the N x N matrix L = 2I - A…
Cycle chromatic polynomial: P(C_N, k) = (k-1)^N + (-1)^N (k-1) (deletion-contraction / Polya enumeration)
Cycle chromatic-polynomial framework via Polya enumeration / deletion-contraction. Setup: for a graph G, the chromatic polynomial P(G, k)…
Theorem: cycle graph C_N Euler characteristic V - E + F = N - N + 2 = 2
Theorem (cycle Euler-characteristic canonical): for a cycle graph C_N embedded in the plane with V = N vertices, E = N edges (the N cycle…
Theorem: trace of cycle-Laplacian for C_4 equals 8 (Chebyshev-sum / root-of-unity identity)
Theorem (C_4 Laplacian-trace canonical): for the cycle graph C_4 with Laplacian L = 2 I - A, the trace tr(L) = sum over k in {0, 1, 2, 3}…
Theorem: P(C_4, k) expanded = k^4 - 4 k^3 + 6 k^2 - 3 k (explicit polynomial identity)
Theorem (C_4 chromatic-polynomial-expansion canonical): the chromatic polynomial of the 4-cycle C_4 at k colours is P(C_4, k) = (k-1)^4 +…
Small world (Watts-Strogatz 1998)
D Watts-S Strogatz 1998 small-world: high clustering + low path-length; rewiring parameter p; pervasive in social/biological/tech networks.
Scale-free (Barabasi-Albert 1999)
A-L Barabasi-R Albert 1999 preferential-attachment power-law P(k) ~ k^-3; basis of WWW + protein-interaction + scientific-citation networks.
ER random graph (1959)
Erdos-Renyi 1959 G(n, p) random-graph; phase-transition at p_c=1/n; modern percolation + epidemic-threshold extensions.
Community detection (Newman-Girvan 2004)
Newman-Girvan 2004 modularity Q; modern Louvain Blondel 2008 + Leiden 2019; basis of network-clustering algorithms.
Controllability (Liu 2011)
Liu-Slotine-Barabasi 2011 minimum driver-nodes for controllability; basis of network-control framework; criticism of…
Temporal networks (Holme-Saramaki 2012)
Holme-Saramaki 2012 temporal-networks review; time-respecting paths; modern multi-layer + multiplex networks Kivela 2014.
Erdős-Rényi (1960)
P Erdős-A Rényi 1960 random-graph; modern modern foundational text + giant-component + 2024 modern ER-extensions weighted/dense.
Small world (Watts-Strogatz 1998)
D Watts-S Strogatz 1998 small-world-Nature; modern modern foundational text + 2024 brain-network small-world architecture.
BA scale-free (Barabási-Albert 1999)
A-L Barabási-R Albert 1999 preferential-attachment scale-free; modern modern foundational text + 2024 scale-free-vs-broad-degree…
Modularity (Newman-Girvan 2004)
M Newman-M Girvan 2004 modularity Q-metric community-detection; modern modern foundational text + Louvain + Leiden + 2024…
Network epidemic (Pastor-Satorras 2001)
R Pastor-Satorras-A Vespignani 2001 SIS-network-no-threshold scale-free; modern modern foundational text + 2024 covid network-mediated…
Multilayer (Boccaletti 2014)
S Boccaletti 2014 + Kivelä 2014 multilayer-networks-review; modern modern foundational text + 2024 multimodal-brain-network-multilayer.