Model / graph · All operations

Analyse a network

Network or graph analysis.

Status

In arcform

Runs as a SQL step

arcform carries it as a sql: step today.

Shape of the result
a new grain: each row stands for a group of input rows
Level
several clauses of SQL, or a window

The DuckDB step

Reachability by a recursive query

SQL
CREATE TEMP TABLE result AS
WITH RECURSIVE edges(src, dst) AS (VALUES ('a','b'),('b','c'),('c','d'),('x','y')),
reach(node, depth) AS (SELECT 'a', 0 UNION SELECT e.dst, r.depth + 1 FROM reach r JOIN edges e ON e.src = r.node)
SELECT * FROM reach ORDER BY depth;
SELECT * FROM result;
SELECT CASE WHEN ((SELECT map_from_entries(list((node, depth) ORDER BY node)) = MAP {'a': 0, 'b': 1, 'c': 2, 'd': 3} FROM result)) THEN 'as expected' ELSE error('the nodes reached from a are not b, c and d at depths 1 to 3') END AS verdict;
  • The statement builds its own data.
  • It needs nothing installed beyond DuckDB itself.
  • The statement checks its own result and raises an error when it is wrong: “the nodes reached from a are not b, c and d at depths 1 to 3”.
  • It passed on DuckDB v2.0.0 (Cyanoptera) d54cbbe3df.

Variants

  • Walk a parent-child hierarchy

    Follow parent-child links to build ancestor paths, a closure table of every ancestor and descendant, or totals rolled up each level.

Analyse nodes and edges

Build a network from edge rows and compute statistics, partitions or views of its nodes and edges.

Find a minimum spanning tree

Connect a set of points with the shortest total length of edges.

What other tools call it

Meridian's classification; an independent blind rating agreed on 86.2% of 312 rows (exact class, version 2).

Alteryx Designer (1)
  • Network Analysisread 2026-09-27

    Build an interactive network view with summary statistics for nodes and edges

Apache Hop (1)
  • Closureread 2026-09-27

    Build a reflexive transitive closure table with distances from parent-child pairs

EasyMorph (2)
  • Hierarchy pathread 2026-09-27

    Build a pipe-delimited ancestor path for each row of a parent-child table

  • Roll upread 2026-09-27

    Sum amounts upward through each level of a parent-child hierarchy

KNIME Analytics Platform (2)
mlpack (1)
  • mlpack_emstread 2026-09-27

    Euclidean minimum spanning tree of a point set by dual-tree Boruvka

Pentaho Data Integration (1)
  • Closure Generatorread 2026-09-27

    Build a closure table from parent-child relationships

RapidMiner Studio (1)
  • Transition Graphread 2026-09-27

    Build a graph of transitions from source and target columns with optional strength

Background

Network science studies networks such as computer, biological and social networks, treating their elements as nodes and the connections between them as edges.[1] A graph is a mathematical structure that models pairwise relations between objects, as vertices, also called nodes, connected by edges.[2] Indicators of centrality assign numbers or rankings to the nodes of a graph according to their position in the network.[3]

When to use it

Centrality is used to identify the most influential people in a social network, key infrastructure nodes in the Internet or urban networks, and super-spreaders of disease.[3] The shortest path problem is finding a path between two vertices of a graph that minimises the sum of the weights of its edges, as when finding a route between two intersections on a road map.[4] The components of an undirected graph partition its vertices into disjoint sets, each a connected subgraph that is not part of any larger connected subgraph.[5] In computer science, a transitive closure can be thought of as a data structure for answering reachability questions, such as whether one node can be reached from another in one or more hops.[6] A minimum spanning tree is a subset of the edges of a connected, edge-weighted undirected graph that connects all the vertices, without any cycles and with the minimum possible total edge weight.[7] One use of a minimum spanning tree is a telecommunications company laying cable in a new neighbourhood, choosing the least expensive set of paths that still connects every house.[7]

Graph theory distinguishes undirected graphs, whose edges link two vertices symmetrically, from directed graphs, whose edges link two vertices asymmetrically.[2] Settle whether an edge row means a one-way or a two-way link before computing anything on the network, and write the choice down. (Meridian's view) Because importance has a wide number of meanings there are many definitions of centrality, and a centrality appropriate for one category will often get it wrong when applied to a different category.[3] A centrality ranking only orders vertices by importance; the ranking does not quantify the difference in importance between its levels.[3] Choose a centrality by what moves through the network and what being central should mean there, and read its scores as an order rather than as sizes. (Meridian's view) In DuckDB, a recursive common table expression (CTE), written WITH RECURSIVE, can traverse an arbitrary graph, but if the graph has cycles the query must detect them to prevent infinite loops.[8] In DuckDB, enumerating all paths with WITH RECURSIVE is in most cases not practical or feasible, and only the unweighted shortest paths are usually of interest.[8]

The method

The earliest known paper in network science is the Seven Bridges of Königsberg, written by Leonhard Euler in 1736, whose description of vertices and edges was the foundation of graph theory.[1] The term graph was introduced by James Joseph Sylvester in a paper published in 1878 in Nature.[2] Centrality concepts were first developed in social network analysis, and many of the terms used to measure centrality reflect their sociological origin.[3] Jacob Moreno developed the sociogram, a representation of the social structure of a group of elementary school students, and presented it in April 1933 at a convention of medical scholars.[1]

Many, though not all, centrality measures count the paths, also called walks, of some type going through a vertex, from walks of length one in degree centrality to infinite walks in eigenvector centrality.[3] Freeman's betweenness centrality is the number of shortest paths that pass through a given vertex.[3] Eigenvector centrality was introduced in 1895 by Edmund Landau for matrices representing chess tournaments, and Google's PageRank is a variant of it.[3] Dijkstra's algorithm, conceived by Edsger W. Dijkstra in 1956 and published three years later, finds the shortest path from a given source node to every other node in a weighted graph.[9] Dijkstra's algorithm is commonly used on graphs where the edge weights are non-negative integers or real numbers.[9] The components of a graph can be constructed in linear time.[5] The transitive closure of a graph can be computed by the Floyd–Warshall algorithm, or by repeated breadth-first or depth-first search starting from each node.[6] The first algorithm for finding a minimum spanning tree was developed by the Czech scientist Otakar Borůvka in 1926, for an efficient electrical coverage of Moravia.[7]

The SQL 3 standard of 1999 added a WITH RECURSIVE construct that allows transitive closures to be computed inside the query processor.[6] In DuckDB, one way to detect cycles is to store the path of a traversal in a list and, before extending the path with a new edge, check whether its endpoint has been visited before.[8]

Compared with the alternatives

A hierarchical query in SQL is a special case of the more general recursive fixed-point queries, which compute transitive closures.[10] DuckPGQ, a DuckDB community extension, supports the SQL/PGQ syntax of the SQL:2023 standard and introduces visual graph pattern matching and a more concise syntax for path-finding.[11] DuckPGQ's ANY SHORTEST path search is non-deterministic: when several shortest paths exist, any one of them is returned.[12] In DuckDB, a WITH RECURSIVE query can instead return all the unweighted shortest paths between two nodes.[8] A recursive CTE is enough for one reachability or path question over an edge table; a graph pattern syntax repays itself when the same network is asked many questions. (Meridian's view)

Sources

  1. [1]Network science - Wikipediasecondary source
  2. [2]Graph theory - Wikipediasecondary source
  3. [3]Centrality - Wikipediasecondary source
  4. [4]Shortest path problem - Wikipediasecondary source
  5. [5]Component (graph theory) - Wikipediasecondary source
  6. [6]Transitive closure - Wikipediasecondary source
  7. [7]Minimum spanning tree - Wikipediasecondary source
  8. [8]WITH Clause – DuckDBdocumentation
  9. [9]Dijkstra's algorithm - Wikipediasecondary source
  10. [10]Hierarchical and recursive queries in SQL - Wikipediasecondary source
  11. [11]duckpgq – DuckDB Community Extensionsdocumentation
  12. [12]SQL/PGQ - DuckPGQdocumentation