InfraAnalysis

[LLM Generated]
Calculus on directed graphs: the real line is an idealization of a DAG, integration an idealization of accumulation. Different treatments of branching give different integrals, each paired with a derivative for which a fundamental theorem holds, and blow-ups provide a renormalization group.

Setup

Install the paclet from the Wolfram Cloud. The substrates below follow the shared example-graphs notebook: a directed path, a cone, and an acyclically oriented grid.
PacletInstall["https://www.wolframcloud.com/obj/hajek_pavel/InfraAnalysis.paclet",ForceVersionInstall->True];​​Needs["WolframInstitute`InfraAnalysis`"]
ambientGraphStyles=<|​​"Default"->{},​​"GrayFaint"->{EdgeStyle->Directive[StandardGray,Opacity[0.15]],VertexStyle->Directive[StandardGray,Opacity[0.3]]},​​"GrayOpaque"->{EdgeStyle->Directive[StandardGray,Opacity[0.4]],VertexStyle->Directive[StandardGray,Opacity[0.6]]},​​"Gray"->{EdgeStyle->StandardGray,VertexStyle->StandardGray}|>;​​dag=ConeGraph[DirectedPath[4]];​​gridDag=DirectedGraph[GridGraph[{4,4}],"Acyclic",Sequence@@ambientGraphStyles["GrayOpaque"]];

Function reference

Domains and utilities

Function
Description
DirectedPath[n]
the directed path graph on n vertices
ConeGraph[g]
adds a cone vertex connected to all vertices of g
GraphSources[g]
the source vertices (in-degree 0) of g
GraphSinks[g]
the sink vertices (out-degree 0) of g

Integration and differentiation

Function
Description
GraphIntegrate[g, f]
g annotated with the integral of f; Method "Ordered", "Cumulative", "Conservative", or "Laminar"
GraphIntegral[g, f, v]
the total of f over all predecessors of v; four-argument form integrates over the subdag between sources and sinks
GraphDerivative[g, f]
g annotated with the derivative of f, the inverse of GraphIntegrate

Finite differences and vector fields

Function
Description
GraphFiniteDifference[g, f]
f(v) minus the sum of f over in-neighbors of v
GraphVectorFields[g]
enumerates all vector fields on g
GraphVectorFieldQ[g, X]
tests that each X(v) is a neighbor of v
GraphDirectionalDifference[g, X, f]
f(X(v)) - f(v) along the vector field X
GraphVectorFieldEndomorphism[g, X]
the pullback endomorphism sending f to the function v -> f(X(v))
GraphTwistedProduct[g, X, f, h]
the shifted product f(X(v)) h(v)
GraphWeightedDerivation[g, X, f, eps]
(f(X(v)) - f(v)) / eps with scalar or per-vertex eps
GraphWeightedLeibnizQ[g, X, f, h, eps]
tests the weighted Leibniz rule for the directional difference

Renormalization

Function
Description
GraphBlowUp[g, n]
replaces each vertex with an n-vertex fiber and each edge with a complete bipartite block; three-argument form also diffuses a function
GraphContract[g]
collapses a blown-up graph back, summing functions over fibers
RadialExpansion[g, layers]
grows g by concentric vertex rings outside the sources

Decomposition

Function
Description
LaminarDecomposition[g]
decomposes a directed graph into laminar layers (a DAG of layers plus per-layer subgraphs)

Domains

◼
  • The simplest integration domains: the directed path (the discrete half-line), the cone over it, and the acyclically oriented grid (a causal diamond).
    • Row[{Graph[DirectedPath[6],ImageSize->100],Graph[dag,ImageSize->200],Graph[gridDag,ImageSize->200]}]
    {GraphSources[gridDag],GraphSinks[gridDag]}
    {{1},{16}}

    Integration is accumulation

    ◼
  • The integral of a vertex function accumulates its values along the causal order; the result annotates the graph.
    • ◼
  • The scalar integral at a sink totals the function over the sink's predecessors.
    • f=AssociationThread[VertexList[dag],1];​​GraphIntegrate[dag,f]
    GraphIntegral[gridDag,AssociationThread[VertexList[gridDag],1],First[GraphSinks[gridDag]]]
    16

    Derivative and the fundamental theorem

    ◼
  • The paired derivative differences accumulated values back along the order, recovering the integrand: the fundamental theorem of graph calculus.
    • ◼
  • The finite difference is its non-annotated companion.
    • GraphDerivative[GraphIntegrate[dag,f]]
    GraphFiniteDifference[dag,f]

    Vector fields and directional differences

    ◼
  • A vector field assigns to each vertex one of its neighbors; directional differences differentiate along it.
    • ◼
  • The weighted derivation satisfies a weighted Leibniz rule.

    • Blow-up as renormalization

    ◼
  • Blowing up replaces each vertex with a fiber and each edge with a complete bipartite block; contraction collapses it back.
    • ◼
  • Integration and differentiation commute with this coarse-graining, giving a renormalization group.
    • ◼
  • Radial expansion grows a domain outward by concentric rings.

    • Laminar decomposition

    ◼
  • The laminar decomposition splits a directed graph into layers whose flow is unbranched, organized as a DAG of layers.

    • Learn more

    The paclet lives at github.com/WolframInstitute/InfraAnalysis. It is actively developed, experimental research code. Ready-made substrates: the example-graphs notebook.