foundations-network-scienceNetwork-science primitives: centrality, influence seeding, communities, contagion vs homophily, GNN failures. Use when seeding a referral campaign or finding critical graph nodes.
Independent GitHub snapshot · Automated classification · Original documentation governs
Apply network-science when:
Skip and use simpler alternatives when:
Before reporting a graph statistic, name the target population, observation window, node/edge inclusion rule, sampling process, and estimand. Centrality and community results can reverse under missing nodes, projection choices, or edge weight definitions. Network size alone is never a validity threshold; compare the result across plausible graph constructions and report unstable ranks.
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.
Each primitive has a full playbook: Definition / When to use / Inputs / Outputs / Failure modes / Worked example / Sources.
| # | Primitive | Core Question | Typical Input | Failure Mode It Addresses |
|---|---|---|---|---|
| 1 | Centrality Measures | Which node matters most, and by what criterion? | Unweighted or weighted graph | Wrong centrality used — high degree ≠ high betweenness ≠ high influence |
| 2 | PageRank | Who is authoritative via inbound endorsements? | Directed graph with optional weights | Naive in-degree conflates volume with authority |
| 3 | Community Detection | Which nodes form cohesive clusters? | Undirected or directed graph | Arbitrary k-means on graph ignores topology |
| 4 | Small-World Networks | Is the graph navigable despite size? | Any graph | Assuming large graphs are either fully random or fully regular |
| 5 | Scale-Free Networks | Does degree follow a power law? | Degree sequence or full graph | Designing resilience for hubs that may not exist |
| 6 | Percolation | At what removal threshold does the graph fragment? | Graph + removal strategy | Ignoring phase transitions — small removals can catastrophically fragment |
| 7 | Contagion / SIR | How far and fast does influence or disease spread? | Graph + transmission probability | Linear spread assumptions on networked systems |
| 8 | Link Prediction | Which absent edges are likely to form? | Observed snapshot of graph | Random-guess recommendations miss structural proximity |
| 9 | Graph Clustering | How to partition nodes by structural similarity? | Graph with optional edge weights | Treating clustering as unstructured k-means; ignoring conductance |
| 10 | 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.) | One-hot node encodings lose all structural information |
| 11 | Temporal Networks | How does time ordering of edges change reachability? | Time-stamped edge list | Aggregating time-stamped edges loses causal ordering |
| 12 | 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 | Graph structure chosen implicitly at ingest, then frozen as technical debt |
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.
Primary sources: Newman 2010, Barabási 2016, Easley & Kleinberg 2010, Watts & Strogatz 1998, Barabási & Albert 1999, Fortunato 2010, Brin & Page 1998, Clauset et al. 2009, Broido & Clauset 2019. Power-law and small-world claims must be verified against statistical tests, not visual inspection.
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. Load references/identification-and-gnn-pitfalls.md before a causal peer-effect claim, statistics from a crawled or partial graph, or a GNN / link-prediction comparison: homophily vs contagion, the reflection problem, degree-biased sampling, over-smoothing vs over-squashing, heterophily and split leakage.
The "are scale-free networks rare?" question is contested, not settled: Broido & Clauset (2019) found only ~4% of nearly 1000 network data sets meet their strictest scale-free criterion (52% meet the weakest), but Holme (2019, Nat. Commun., companion piece) and Barabási's public rebuttal argue the result hinges on an unusually strict definitional threshold, and scale-freeness is only cleanly defined in the infinite-size limit. Report the fitted statistics and the tier of evidence, not a binary yes/no claim.
Tooling check: Before choosing a NetworkX Leiden implementation, look up leiden_communities() in the documentation for the installed version. Confirm native/backend requirements and the supported metric and resolution parameters. Select modularity or CPM deliberately and scan resolution under that objective; their resolution values are not interchangeable.
Numeric thresholds (PageRank damping, SIR β/γ, modularity resolution) are dataset-specific — calibrate on held-out snapshots. Community detection quality metrics (modularity, NMI, conductance) are complementary — no single metric is ground truth. Temporal-network results should be compared against static-graph baselines to quantify the timing effect.
| Anti-Pattern | Diagnosis | Fix |
|---|---|---|
| Degree centrality used for every importance question | Degree, shortest-path brokerage and diffusion impact are different objectives | Information brokers → betweenness; most-connected hub → degree; shortest average outward distance → outward closeness; fastest spreader → compare under the fitted diffusion process |
| 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 | Weak connectivity, strong connectivity and outward reachability answer different failure questions | Compute weak/strong components and directed reachability for the stated failure objective (Newman 2010) |
| Temporal-network paths confused with static-network paths | Time-respecting reachability is a subset of static reachability; it can be equal, and timestamps alone do not identify causal effects | Use time-respecting path algorithms; a static projection can overestimate reachable spread (Holme & Saramäki 2012) |
| PageRank damping copied without sensitivity analysis | Damping changes the balance between link following and teleportation; graph size alone does not determine it | Compare ranks across a justified damping range and personalization choices; report the choice and unstable ranks |
| Community inference justified by graph size alone | Neither a node-count cutoff nor a modularity score proves significance | Use a graph-specific null model, stability and decision relevance; small descriptive partitions are allowed |
| Correlated adoption among neighbours reported as contagion | Homophily and contagion are generically confounded in observational network data (Shalizi & Thomas 2011); similar people link and also adopt alike | Treat neighbour correlation as descriptive; hand peer-effect identification to foundations-causal-inference (Interference and SUTVA); use randomized seeding or exposure designs before sizing a contagion effect; reflection and sampling traps: identification reference |
| Greedy or IMM seed set reported as optimal | A model-specific approximation guarantee does not prove exact optimality, even when the diffusion model is correct | Fit and validate the model; report the applicable approximation guarantee and estimation error, and compare with simple seed sets on held-out spread (Kempe, Kleinberg & Tardos) |
| 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" is a second cause of over-smoothing, and long-range tasks also over-squash through bottleneck edges — the depth that would solve the task destroys the representation | Reduce the radius instead of adding depth (coarsening, global/virtual nodes, hierarchical message passing); per-architecture ordering in 10-graph-embeddings.md Failure Mode 3, diagnostics in the identification reference |
| 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?" | Expected avoided loss under an identified churn/diffusion model | Eigenvector/PageRank can propose candidates, but neither identifies peer effects nor incorporates retention cost, customer value and intervention response. |
| "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 has the shortest average broadcast distance?" | Outward closeness with declared unreachable-node handling | Closeness describes shortest-path distances, not realized diffusion speed; NetworkX's directed closeness uses incoming distances, so reverse the graph for outward distances (docs). |
| "Which service/package, if it breaks, takes down the most of the system?" | Directed reverse reachability plus operational dependency conditions | Enumerate exposed dependents and required/optional/version/fallback conditions; PageRank and betweenness are descriptive prioritization proxies, not outage-impact counts. |
| "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 | PageRank/degree are candidate heuristics, not optimality guarantees for either mechanism. Compare seed sets under the directed, weighted diffusion model and objective, including saturation and overlap; validate on held-out campaigns or simulations. |
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.
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:
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.
Defaulting to SIR for every spread question is a 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 may reduce novel exposure, but net spread depends on transmission rules, timing, topology and seeds |
| Technology adoption, norm change, health behaviour change, feature uptake | Requires multiple independent reinforcing exposures before adoption | Watts threshold model (complex contagion) | Clustering may facilitate reinforcement or restrict outward exposure; compare seed strategies under fitted thresholds and topology |
| Household/team/event-based transmission | Group exposure, not pairwise contact | Hypergraph/simplicial contagion model | Higher-order processes can exhibit thresholds/bistability in specified models; pairwise risk bias can have either direction and needs calibrated comparison |
| 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 one contact can suffice, evaluate a simple-contagion model; if reinforcement is documented, evaluate a threshold model. Choose seed sets by calibrated temporal simulations and held-out diffusion evidence under the task budget; neither hub nor clustered seeding is universally optimal.
An LLM multi-agent system is a graph whose nodes are agents and whose edges are permitted message paths: communication topology is 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:
Caveat before importing results: published agent-topology numbers are benchmark-specific (MMLU, HumanEval) and depend on the model, the task mix, and the prompt scaffold. Treat the structural argument as transferable and the percentages as not.
Full stacks, inputs, rules, outputs and the worked referral example are in references/composition-recipes.md:
ai-rag.foundations-causal-inference — peer-effect and interference identification (Interference and SUTVA); use it before claiming contagion over homophilyai-rag — GraphRAG pipelines; this skill supplies only the community-detection and PageRank primitivesfoundations-graph-theory — graph structure as a navigation surface (DAGs and cycles, reachability, fan-out and depth budgets, directed gates, orphans, table vs Mermaid); this skill keeps social and agent-network dynamicsConsumer skills that hold applied copies of these primitives (in their references/network-science-applied.md). This skill does not cross-link to them:
marketing-aeo-geo — citation-flow and topical-authority recipesmarketing-seo — PageRank and link-prediction recipes for backlink strategymarketing-social-media — seed selection and audience segmentation recipesdev-context-multi-repo — blast-radius and dependency-graph recipesagents-subagents — contagion and percolation recipes for agent-network robustness; agent communication topology as a sparsity/robustness tradeoffUse decision and validation worksheet for intake, model boundaries, uncertainty and checkable acceptance examples. Regression cases provide independent prompts and expected answers; these are fixtures, not executed agent results.
data/sources.jsonWhen prior decisions or pitfalls are relevant, consult learnings.consolidated.md if present; use learnings.md only for needed history or as the available fallback. Otherwise skip both.
After applying it, if you encountered a pattern worth remembering, a mistake worth preventing, or a domain fact that surprised you, append one dated bullet to learnings.md via agents-skills-feedback-loop/scripts/append_learning.py. Do not modify SKILL.md itself.