AssemblingGraphs.jl

A Julia library for generating graphs through a stochastic process inspired by assembly theory. This approach models graph growth by iteratively merging components from a seed set, simulating generative histories of complex structures.

Build docs

$ julia --project docs/make.jl

View by opening the html file.

Quick Start

Suppose you want to generate a random simple graph, one way you can do this is via a generative process inpsired by assembly theory. This involves starting with an initial collection of graphs (seeds), such as

using Graphs
seeds = [path_graph(2), path_graph(3)];

Then you can randomly select pairs of graphs from seeds and join them following the principles of assembly theory; selecting nodes from each graph, combining such that nodes are identified in the new graph. This is explained in our manuscript, and in previous work on assembly theory. This package automates this task. The key functions are join_iteratively() and join_until().

join_iteratively()

The more general function, join_iteratively(), will perform a specified number of joinning operations and return the ensemble of generated graphs.

    join_iteratively(gs, iterations::Integer, p_force_largest=0; kwargs...)

Join graphs iteratively by merging nodes based on specified criteria.

Arguments

• gs: An array of graphs to be joined
• iterations: Number of iterations to perform join operations
• p_force_largest::Real=0: Probability (0-1) of forcing one of the selected graphs to be a largest graph. NOTE: At 0, all graphs, including the largest, have an equal chance to be chosen.
• n_nodes_to_merge: Number of nodes to merge from selected graphs. Can be:
  • Integer: Fixed number of nodes to merge
  • Vector{Integer}: Random selection from these values
  • UnitRange : Range to randomly sample from
  • nothing: Random selection based on graph constraints (default)
• rng: Random number generator for reproducibility
• collect_data: Whether to collect and return detailed metrics about the joining process

Returns

If collect_data=false (default):

• Vector of accumulated graphs from the join iterations

If collect_data=true: Named tuple containing:

• gs_joined: Vector of all accumulated graphs
• gs_largest_by_iteration: Vector of largest graphs at each iteration
• parents_by_iteration: Vector of tuples containing the parent graphs for each join
• n_edges_lost_by_iteration: Vector tracking edges lost in each join
• n_nodes_to_merge_by_iteration: Vector tracking number of nodes merged in each join

Example usage

gs = [path_graph(i) for i in 2:4]

result = join_iteratively(gs, 5)

data_result = join_iteratively(gs, 5, collect_data=true)

largest_graphs = data_result.gs_largest_by_iteration

edges_lost = data_result.n_edges_lost_by_iteration

join_until()

Meanwhile, join_until() allows the user to specify the final size of a graph they desire and the algorithm will run until a graph of that size is generated.

    join_until(
        gs, # Seed graphs
        g_joined_size_limit; # desired final graph size
        p_force_largest::Real=0, # chance of forcing the joinning operation to include one of the largest graphs (see manuscript for more details)
        rng::AbstractRNG = Random.default_rng()
        )

Arguments

• gs: A vector of graphs to be joined.
• g_joined_size_limit: An Integer representing the maximum number of nodes in the final graph
• p_force_largest::Real=0: Probability (0-1) of forcing one of the selected graphs to be a largest graph. NOTE: At 0, all graphs, including the largest, have an equal chance to be chosen.
• rng: The random number generator to use. Default is Random.default_rng().

Returns

An array of graphs after performing the iterative joining.

References

For more details on the theoretical motivation behind this approach, refer to the accompanying manuscript and prior work on assembly theory.

Reproducing the results of Mathis & Smith 2025

The results from Historical Contingencies Steer the Topology of Randomly Assembled Graphs, Mathis & Smith 2025 can be generated using the files in scripts and the corresponding figures can be generated with the assocaited jupyter notebooks.