Graphical & Network Models of Dependence

← Back to Domain-Specific Families

Abstractions that represent probabilistic, physical, or computational dependence as a graph or network — Bayesian networks, factor graphs, ancestral graphs, and signal-flow graphs — including self-organizing network models like the Bak–Sneppen and shortcut models, and graph-based algorithms for flow, connectivity, and pointer analysis.

16 abstractions in this family — domain-specific abstractions that sit near one another in structural-signature space (k-means over structural-signature embeddings). Each is shown with its short description.

• Ancestral graph — A mixed graph using directed, bidirected and undirected edges to encode conditional independences left by latent-variable marginalization and selection conditioning in a DAG.
• Bak–Sneppen model — An extremal coevolution model that repeatedly replaces the least-fit species and its neighbors, self-organizing toward a critical fitness threshold and avalanche dynamics.
• Blockmodeling — A social-network analysis framework that partitions actors into position classes whose tie patterns form an interpretable reduced block structure.
• Cavity method — A statistical-physics technique for disordered mean-field systems that removes one variable, characterizes the effective field from the remainder and imposes self-consistency when the variable is restored.
• Dying percolation conjecture — The conjecture that critical Bernoulli bond percolation on every integer lattice of dimension at least two has no infinite cluster.
• Dynamic Bayesian network — A Bayesian network template replicated across time slices to represent probabilistic dependencies within and between successive states of a stochastic process.
• Factor graph — A bipartite graph whose variable nodes and factor nodes expose how a multivariate function decomposes into local functions.
• Graph reduction — Evaluation of a functional program by rewriting a shared expression graph so lazy subexpressions are computed at most once.
• Minimum-cost flow problem — The optimization problem of routing a required amount of flow through a capacitated network while satisfying conservation and minimizing total edge cost.
• Power graph analysis — Lossless graph compression and visualization by grouping repeated clique, biclique, and star connection patterns.
• Shortcut model — A random-network model that interpolates between regular lattices of neighboring integer dimensions by adding structured long-range shortcut layers.
• Signal-flow graph — A directed weighted graph whose nodes denote system variables and whose branches denote functional dependence or gain from one variable to another.
• Steensgaard's algorithm — A near-linear, flow-insensitive pointer analysis that models assignments as equality constraints and merges points-to equivalence classes with union–find.
• Strong connectivity augmentation — Add the fewest or least-cost directed edges to a digraph so every vertex can reach every other, with the unweighted optimum governed by source and sink components of the condensation DAG.
• Structural Network Controllability — Structural network controllability is generic full-state reachability of a specified directed linear network and input pattern; matching can identify minimum driver placements under a stated convention.
• Variable-order Bayesian network — A Bayesian-network model whose parent set for a variable can change according to the realized context of preceding variables.