Network Science Foundations

12 canonical network-science primitives, each solving a distinct structural or dynamic analysis problem. Primitives are domain-agnostic: the same PageRank that ranks web pages ranks citation authority, package influence, and audience amplification. The same percolation threshold that governs epidemic spread governs cascading failure in dependency graphs.

When to Apply

Apply network-science when:

• The data IS a graph — citations, dependencies, follower graphs, supply chains, knowledge graphs
• The system is a graph even if the data is not — LLM multi-agent communication topology, agent memory graphs, tool-call graphs (see Agent Topology as a Graph Problem)
• Spread/contagion question — viral coefficient, R₀, percolation threshold
• Centrality question — "which nodes are critical?" (PageRank, betweenness, eigenvector)
• Community detection — clustering nodes by structural similarity (Louvain, Leiden)
• Blast-radius / dependency-impact analysis on services or modules

Skip and use simpler alternatives when:

• Data is tabular and relationships aren't structural — standard analytics suffices
• Graph has < 50 nodes — visual inspection beats algorithmic centrality
• Question is about strategic interaction at the node level — use foundations-game-theory
• Question is about queue or flow through a single bottleneck — use foundations-queueing-theory or theory-of-constraints
• Edges are weak proxies (e.g. "users who viewed both products") — centrality is unreliable; validate edge semantics first
• "Network effects" is a marketing claim, not a measured viral coefficient — quantify R first or skip the analysis

The data is tabular but might still be a graph problem. Three criteria (Broadwater & Stillman 2025, §1.4) — any one is grounds to reframe: implicit relationships and interdependencies (entities connected by undocumented influence, co-investment, or co-occurrence rather than a recorded relation); high dimensionality and sparsity (many entities, few direct interactions — recommender interaction data, molecules; also the cold-start motivation); complex nonlocal interactions (an entity's outcome depends on entities reachable only through intermediaries — supply-chain cascades, propagation through a network over time). Key indicators and the closing self-test questions are in 10-graph-embeddings.md. If a criterion holds, design the structure explicitly with #12 before ingest, and establish a tabular (non-GNN) baseline before attributing anything to the graph.

Contents

• Quick Reference
• Primitive Index
• Formal Supporting Theory
• Misuse Boundaries
• Decision Checklist
• Anti-Patterns
• Expert Judgment
• Composition Recipes
• Related Skills
• Workflow
• ASCII Flow
• Fact-Checking

---

Quick Reference

Primitive	Core Question	Typical Input
Centrality Measures	Which node matters most, and by what criterion?	Unweighted or weighted graph
PageRank	Who is authoritative via inbound endorsements?	Directed graph with optional weights
Community Detection	Which nodes form cohesive clusters?	Undirected or directed graph
Small-World Networks	Is the graph navigable despite size?	Any graph
Scale-Free Networks	Does degree follow a power law?	Degree sequence or full graph
Percolation	At what removal threshold does the graph fragment?	Graph + removal strategy
Contagion / SIR	How far and fast does influence or disease spread?	Graph + transmission probability
Link Prediction	Which absent edges are likely to form?	Observed snapshot of graph
Graph Clustering	How to partition nodes by structural similarity?	Graph with optional edge weights
Graph Embeddings	How to represent nodes as dense vectors?	Graph structure + optional node features (For cross-domain transfer with zero labels, see Graph Foundation Models: Liu et al. TPAMI 2025.)
Temporal Networks	How does time ordering of edges change reachability?	Time-stamped edge list
Graph Schema Design	What should be a node, an edge, or a property — and is that choice testable?	Non-graph source data + use-case queries

---

Primitive Index

Each primitive has a full playbook: Definition / When to use / Inputs / Outputs / Failure modes / Worked example / Sources.

#	Primitive	Failure Mode It Addresses
1	Centrality Measures	Wrong centrality used — high degree ≠ high betweenness ≠ high influence
2	PageRank	Naive in-degree conflates volume with authority
3	Community Detection	Arbitrary k-means on graph ignores topology
4	Small-World Networks	Assuming large graphs are either fully random or fully regular
5	Scale-Free Networks	Designing resilience for hubs that may not exist
6	Percolation	Ignoring phase transitions — small removals can catastrophically fragment
7	Contagion / SIR	Linear spread assumptions on networked systems
8	Link Prediction	Random-guess recommendations miss structural proximity
9	Graph Clustering	Treating clustering as unstructured k-means; ignoring conductance
10	Graph Embeddings	One-hot node encodings lose all structural information
11	Temporal Networks	Aggregating time-stamped edges loses causal ordering
12	Graph Schema Design	Graph structure chosen implicitly at ingest, then frozen as technical debt

---

Formal Supporting Theory

Load references/formal-theory-map.md when the analysis depends on graph assumptions: directed vs. undirected edges, weighted vs. unweighted measures, random-walk stationarity, modularity limits, power-law testing, percolation thresholds, epidemic dynamics, link-prediction leakage, embedding validity, or temporal reachability.

Misuse Boundaries

Load references/patterns-scenarios-traps.md before publishing graph rankings, communities, scale-free claims, diffusion forecasts, dependency blast-radius scores, or embedding explanations. It contains scenario playbooks, anti-patterns, known traps, and validation checks.

---

Decision Checklist

• Structure not yet fixed: Is the source data non-graph, or does more than one node/edge/property split look plausible? → graph schema design (#12) first — write a conceptual schema, build an instance model on real data, and test the constraints before any algorithm runs. Tabular layout is unambiguous; graph layout is not, and the choice becomes technical debt once a pipeline sits on it.
• Influence / importance ranking: Which single node matters most? → choose the right centrality (#1); if endorsement-weighted → PageRank (#2)
• Cluster structure: Do nodes group into cohesive communities? → community detection (#3) — use Louvain/Leiden for descriptive partitioning; if the question is "does community structure exist?" or requires statistical model comparison → inferential SBM (#3, Failure Mode 7); if cut-minimization is the goal → graph clustering (#9)
• Navigation / reachability: Is average path length short despite size? → small-world test (#4)
• Degree distribution: Does degree follow a power law? Test before claiming scale-free (#5)
• Robustness / fragility: How many nodes must be removed to break connectivity? → percolation (#6)
• Spread / contagion: How far does a signal reach from a seed? → SIR model (#7); if spread requires social reinforcement or multiple exposures (technology adoption, norm diffusion, behaviour change) → threshold / complex contagion model (#7, Failure Mode 7), not SIR
• Missing edge inference: Which edges are likely to form next? → link prediction (#8)
• Node similarity / downstream ML: Need node vectors for classification or recommendation? → graph embeddings (#10)
• Temporal causality: Do edge timestamps change what is reachable? → temporal networks (#11)
• Higher-order structure test: Before applying community detection (#3) or temporal-network analysis (#11) to a hypergraph dataset, run a reducibility test (Lucas et al. 2026) — if degree heterogeneity is low, pairwise methods remain valid; if high, use higher-order methods to avoid underfitting.

---

Anti-Patterns

Anti-Pattern	Diagnosis	Fix
Degree centrality used when betweenness is the right measure	High-degree nodes are not always the best bridges; bridges have high betweenness regardless of degree	Clarify the question: information brokers → betweenness; most-connected hub → degree; fastest spreader → closeness
Modularity treated as ground truth (resolution limit ignored)	Modularity optimization misses small communities and merges large ones at scale	Pair modularity with resolution parameter scan; verify with NMI against ground truth if available (Fortunato 2010)
Scale-free claimed without statistical test	Visual inspection of log-log degree plots is unreliable — Gaussian and log-normal distributions look similar in log-log	Run a maximum-likelihood power-law fit and report the p-value and xmin (Clauset, Shalizi & Newman 2009)
Percolation reasoning on directed networks treated as undirected	Directed graphs have separate in-component and out-component; removing a node in-component does not break out-component reachability	Compute giant weakly connected component and giant strongly connected component separately (Newman 2010)
Temporal-network paths confused with static-network paths	An edge at t=5 cannot precede an edge at t=3 even if it would on a static graph; temporal reachability is strictly smaller	Use time-respecting path algorithms; static-graph reachability overestimates spread (Holme & Saramäki 2012)
PageRank used on sparse undirected graphs without damping tuning	Default damping d=0.85 was calibrated for the web graph; sparse or small graphs need different d	Sensitivity-test d ∈ [0.5, 0.95]; report the chosen value and its effect on rank stability
Community detection applied to graphs with < 50 nodes	Modularity gains are trivially achievable on small graphs; results are statistically meaningless	Use visualisation and domain knowledge for small graphs; reserve community detection for N ≥ 100
SIR model run on a group-interaction network (e.g. household spread, team transmission) without higher-order correction	Group interaction models produce a dual epidemic threshold and potential bistable regime absent in pairwise SIR (Ferraz de Arruda 2024, Nat. Rev. Phys.); pairwise SIR systematically understates outbreak risk	If the dataset has documented group events, use a hypergraph contagion model; check for bistability before setting intervention thresholds
Applying pairwise community detection to a high-degree-heterogeneity hypergraph	Reducibility analysis (Lucas 2026) shows co-authorship-style networks cannot be collapsed to pairwise edges without dynamical information loss	Run the reducibility test first; if degree heterogeneity is high (e.g. χ > 0.5 for the dataset's irreducibility score), use a higher-order community detection method
GNN shipped without a non-GNN baseline	With no tabular baseline (logistic regression / gradient-boosted trees / MLP on the same node features) there is no counterfactual, so any claimed benefit of graph structure is unfalsifiable	Train non-GNN baselines first, then a GCN to isolate what graph structure adds, then any attention architecture (Broadwater & Stillman 2025, §4.3–4.4)
GNN architecture selected on published Big-O complexity	GNNs mix heterogeneous operations with different complexities and do not all use the same operations; the literature typically compares one major operation, not whole algorithms, and implementation and hardware shift the result	Treat Big-O as an ordering hint only; benchmark candidate architectures on your own data and hardware (§7.6.1)
Layers added to reach a distant influencing node	A large "problem radius" (long-range dependency task) is a second, distinct cause of over-smoothing — the depth that would solve the task is the depth that destroys the representation	Reduce the radius instead of adding depth: coarsening, global/virtual nodes, hierarchical message passing. Note the architecture ordering: GraphSAGE's fixed-size neighbour sampling mitigates; GCN is more at risk; GAT's attention only partially lowers it since aggregation stays local (§4.5.2)
Assuming pairwise edges are sufficient for temporal network inference	>60% of real EEG dynamics are non-pairwise; pairwise temporal models can systematically underfit	Before committing to standard temporal edges, test higher-order fit using THIS (Arnaudon 2025) if time-series data is available

---

Expert Judgment

The failure modes above are mechanical — wrong formula, missing test, unnormalised score. This section is about the judgment calls a mechanical checklist cannot make for you: which question is actually being asked, whether the data supports answering it, and whether "network" is even the right frame.

Which centrality answers which business question

Centrality choice is usually presented as a technical decision. In practice it is a translation problem: someone asks "who matters most?" in business language, and that phrase maps to different math depending on what they mean by "matters." Get the translation wrong and the analysis is precise but irrelevant.

Business question	Right measure	Why the obvious choice is often wrong
"Who do we lose the most by losing?" (churn/attrition risk)	Betweenness, or articulation-point test	Degree picks the loudest node, not the one holding two subgraphs together. A quiet node with low degree can be a single point of failure.
"Who should get the retention budget to prevent contagion-style churn?"	Eigenvector / PageRank	Losing a customer connected to other high-value customers has second-order costs that raw connection count misses.
"Whose endorsement carries the most weight?" (authority, credibility)	PageRank / eigenvector	Volume of inbound links or mentions rewards spam and popularity contests; authority requires weighting by the endorser's own standing.
"Who can broadcast a message fastest?"	Closeness	High degree does not imply short average distance to everyone else if the high-degree node sits in a peripheral cluster.
"Which service/package, if it breaks, takes down the most of the system?"	Reverse PageRank (transitive dependents) + betweenness (bridges)	Direct dependents undercount blast radius; betweenness alone misses volume of downstream impact. Use both, not either.
"Who has the biggest raw audience?"	Degree	This is the one case where degree is usually the right answer — but confirm the question is really about raw reach, not influence or bridging.
"Where should we seed a marketing campaign?"	Depends on the contagion mechanism — see diffusion-model choice below	Seeding by PageRank/degree is correct for simple (single-exposure) contagion but actively wrong for complex (reinforcement-needed) contagion.

The recurring error is treating "importance" as one thing. Before computing anything, restate the business question as "a node such that removing/promoting/notifying it does X" — that sentence usually reveals which centrality is implied.

Sampling bias: the network you measure is not the network that exists

Almost no analyst works with the true underlying graph. API rate limits, crawl depth limits, consent/opt-in populations, and snowball sampling all produce a subnet, not the network. This matters more than most failure-mode checklists suggest, because the bias is not random noise — it is systematic and direction-specific:

• Degree-biased discovery: high-degree nodes are easier to find (more paths lead to them), so crawls and snowball samples over-represent hubs and under-represent the long tail. This inflates apparent centralization and can manufacture the appearance of a heavy-tailed degree distribution from a true distribution that is not heavy-tailed at all.
• The subnet is not the same distribution family as the parent: Stumpf, Wiuf & May (2005, PNAS) prove that random subsampling of a scale-free network does not, in general, yield a scale-free subnet — and the reverse inference (subnet looks scale-free ⇒ population is scale-free) is equally unsafe. This is a structural reason, independent of the Broido–Clauset debate, to distrust degree-distribution claims made from partial crawls.
• Survivorship bias compounds it: inactive, deleted, or churned nodes are typically missing from the snapshot, which further skews measured centrality and community structure toward currently-active, currently-visible entities.
• What to do: before reporting a degree distribution, centrality ranking, or community structure, state explicitly how the graph was collected (full census, API crawl to depth d, snowball from k seeds, opt-in panel) and treat any claim about the shape of the distribution as conditional on that collection method. If the collection method is degree-biased, prefer rank-based or relative comparisons within the sample over absolute claims about the population.

When the network frame itself misleads

Not every relational dataset should be analyzed as a network, and not every network metric on a valid graph means what it appears to mean.

• Near-complete / dense graphs: centrality and community detection are diagnostic tools for structure — variation in connectivity across the graph. On a graph where most nodes connect to most other nodes (density approaching 1), every centrality measure converges toward the same ranking and modularity cannot find meaningful cuts, because there is no structural variation to detect. If average degree is within an order of magnitude of n−1, run centrality/community detection with the expectation that the output may reflect edge-collection noise more than real structure — check density before, not after, running the analysis.
• Bipartite projection inflates clustering artificially: converting a two-mode graph (users × products, authors × papers) into a one-mode projection (users connected if they bought the same product) manufactures cliques by construction — any two users of the same popular product become "connected," and any three users of the same product form a "triangle." The resulting clustering coefficient is an artifact of the projection, not evidence of real triadic closure or community structure in user behavior. If a bipartite projection is unavoidable, weight edges by co-occurrence strength and compare against a projected-random-bipartite null model before interpreting clustering or community results — never take the raw projected clustering coefficient at face value.
• Weak-proxy edges break centrality semantics: an edge meaning "viewed the same page" or "mentioned in the same document" is not the same kind of relationship as "follows" or "cites," and centrality measures assume a consistent edge semantic across the whole graph. Mixing strong ties (explicit follow) and weak proxies (co-occurrence) in one adjacency matrix produces a centrality score that answers no coherent question. Validate that all edges mean approximately the same thing before computing centrality, and if they don't, build separate graphs per edge type rather than merging them into one weighted graph.

Diffusion-model choice by phenomenon, not by default

Defaulting to SIR for every spread question is the single most common judgment error in applied contagion modelling. The right model depends on the exposure mechanism, not on which model is best known:

Phenomenon	Exposure mechanism	Right model	Signature that distinguishes it
Biological disease, forwarded messages, software vulnerability propagation	Single contact is sufficient to transmit	SIR / SIS (simple contagion)	Clustering slows spread (redundant ties waste exposure opportunities on already-infected neighbours)
Technology adoption, norm change, health behaviour change, feature uptake	Requires multiple independent reinforcing exposures before adoption	Watts threshold model (complex contagion)	Clustering accelerates spread (repeated exposure from the same tight-knit group reinforces the decision); cascades come from clustered seed sets, not high-degree seed sets
Household/team/event-based transmission	Group exposure, not pairwise contact	Hypergraph/simplicial contagion model	Dual epidemic threshold and possible bistability — pairwise SIR systematically understates risk (Ferraz de Arruda et al. 2024)
Rumour/misinformation with source credibility effects	Mixture of single-exposure and reinforcement, credibility-weighted	Neither pure SIR nor pure threshold — hybrid or empirically fit model	Neither pure signature holds cleanly; validate against held-out spread data rather than assuming

The practical test: ask "would one credible contact be enough, or does this require seeing it from more than one direction first?" If the answer is "one is enough," use SIR and seed by PageRank/degree/betweenness as appropriate. If the answer is "it takes social proof," use the threshold model and seed clustered, not high-degree, nodes — seeding a threshold-model cascade with the highest-degree hub is a common and costly mistake, because a single hub cannot supply the repeated exposure a threshold model requires.

Agent topology as a graph problem

An LLM multi-agent system is a graph whose nodes are agents and whose edges are permitted message paths. Since 2024–2025 this has stopped being a metaphor: communication topology is now designed and learned rather than hand-picked, and the primitives above apply directly to it (Liu et al. 2025, survey; Zhang et al. 2025, G-Designer).

The graph-science content is that topology is a cost/robustness tradeoff, not a style choice: