Measuring the construction complexity of social graphs
Assembly Theory, introduced by Lee Cronin and Sara Walker, asks a deceptively simple question about any structured object: what is the shortest sequence of operations needed to build it, given that you can reuse what you've already built?
The answer — the assembly index — is a number. For a molecule, it counts the minimum joining operations to construct it from basic bonds, where each intermediate product can be reused freely. A random arrangement of atoms has a low assembly index: there's no internal structure to exploit. A crystal also has a low index: its repetitive lattice means one motif, reused endlessly. But a complex molecule — a protein, a drug, a piece of DNA — has a high assembly index. It required many distinct construction steps. It encodes history.
Cronin's key insight was empirical: objects with an assembly index above roughly 15 have never been observed without a living system (or technology derived from one) producing them. The assembly index is, in a real sense, a detector of selection. High assembly index means something chose this configuration from an astronomically large space of possibilities. Something with memory, with preferences, with agency.
We can apply the same logic to graphs. Start with a single edge — the simplest possible connection between two entities. A "join" operation takes two previously constructed subgraphs and merges them: union their nodes and edges, possibly identifying (merging) shared nodes. The assembly index of a graph is the minimum number of such joins to construct it from single edges.
A path graph (a chain of nodes) has a low assembly index: you just keep extending. A star graph is similarly cheap: one hub, many spokes, all structurally identical. But an irregular graph — where each node's local neighborhood looks different from every other's — requires many distinct construction steps. It cannot be built by repeating a simple pattern.
This is where it gets interesting for trust networks. Consider a web of trust — a directed or undirected graph where edges represent "I vouch for this entity." Genuine social trust networks are messy. People know each other through diverse contexts: work, family, shared interests, chance encounters. The resulting graph is structurally irregular, rich in distinct local motifs. Its assembly index is high.
Now consider a Sybil attack: an adversary creates many fake identities and has them vouch for each other. The resulting subgraph is almost always structurally regular — a clique, a ring, a bipartite graph — because the attacker uses a simple algorithm to generate the connections. These structures have low assembly indices. They can be constructed in few steps because they're built from repetition, not from genuine diverse interaction.
A trust graph with high assembly index cannot have been cheaply generated. It required a history of distinct decisions. This is exactly what separates authentic social structure from manufactured consensus.
The principle extends beyond static trust graphs. Consider an agent's behavioral trace over time — the sequence of actions it takes, the patterns of its interactions. This trace, too, has an assembly index. A bot that follows simple rules produces a low-index trace: repetitive, compressible, constructible in few steps. A genuine agent — one that responds to context, learns, adapts, makes idiosyncratic decisions — produces a high-index trace.
This connects to a deep question about what it means to be a genuine agent versus a simulation of one. Assembly index doesn't measure complexity in the Kolmogorov sense (shortest description). It measures construction depth — how many irreducible steps of selection went into producing this object. A random string is Kolmogorov-complex but assembly-simple (no structure to exploit). A crystal is Kolmogorov-simple and assembly-simple. A protein is Kolmogorov-complex and assembly-complex. It is this last category — high in both measures — that marks the products of genuine agency.
The interactive tool above lets you explore this. Draw a graph. Compute its assembly index. Watch how many distinct construction steps it requires. Then compare: the neat Sybil ring versus the tangled trust web. The difference is visible, computable, and meaningful.
· · ·
For the string-based assembly index calculator, see Assembly Theory. For the broader context of trust and reputation in decentralized networks, see NIP: Agent Reputation.