Substrate · NP-Hard Complexity Scaling

Social Clique Networks Complexity Profile

The algorithmic boundary of social clique networks modeled via graph theory.

Community detection and influence inference on a social graph are parameterized by its treewidth; dense overlapping cliques drive it up. Every profile below reads the same substrate through a different graph invariant and structural regime, and prices it with Ross’s Law.

Read the volume (PDF, 895 pp)

A social graph wears its structure on the surface: people are vertices, ties are edges, and the interesting questions — who forms a community, how influence spreads, where the cliques overlap — are all questions about how separable the graph is. Sparse, tribal networks come apart into clean communities. Densely overlapping cliques refuse to. The number that says which you have, and what it will cost to analyze, is treewidth.

Many of these tasks are NP-hard in general, yet routine on real networks — and the reason is exactly Ross’s Law: the algorithms run in time exponential in treewidth and linear in size, so a low-width social graph is tractable no matter how many nodes it has. The five invariants below each locate a network on the axis from a shadow regime (modular, partitionable) to a mirror regime (one overlapping tangle), with the equilibrium band — the small-world structure most real social networks show — between them.

analysis cost ≈ exp(Θ(tw(G)))Ross’s Law for social graphs: community detection, influence maximization, and clique analysis cost the exponential of the treewidth. Tribal structure keeps you tractable; pervasive overlap pushes you into the hard regime.

Treewidth bounds

Treewidth measures how far the network is from a set of separable communities — the width of the densest overlap any partition must cut through.

Shadow
tw(G) = O(1) — well-separated groups with sparse bridges. Community detection is clean and cheap.
Equilibrium
tw(G) = Θ(log N) — the small-world regime: communities plus a few connectors. Still tractable, the common shape of real networks.
Mirror
tw(G) = Ω(N) — pervasive overlapping cliques with no clean boundaries. Community structure dissolves and the analysis goes exponential.

Graph degeneracy

Degeneracy is the workhorse here — the k-core decomposition is a degeneracy ordering, so this invariant is already how analysts find the dense heart of a social graph. It lower-bounds the treewidth for free.

Shadow
d(G) = O(1) — no dense core; the graph peels to nothing. Tree-like, trivially partitioned.
Equilibrium
d(G) = Θ(log N) — a modest k-core, an influential center forming.
Mirror
d(G) = Ω(N) — a giant dense core no peeling removes. Large treewidth certified; the network is one mass.

Community entropy

The entropy-across-a-cut invariant, for a social graph, is how much the two halves of a partition still depend on each other — how much community structure is lost when you split it. Low across-cut entropy is shadow; high is mirror.

Shadow
S ∝ ∂A — ties across a partition live on a thin boundary. The split barely severs anything; communities are real.
Equilibrium
S ∝ log N — meaningful but bounded cross-community ties. Partitions are good, not perfect.
Mirror
S ∝ |A| — ties saturate every cut. No partition captures the structure; “community” stops meaning anything.

Fiedler-value connectivity

The Fiedler value is the classic spectral test for a social graph’s natural division — it powers spectral community detection precisely because it finds the weakest cut.

Shadow
λ₂ → 0 — nearly disconnected factions. An obvious split.
Equilibrium
λ₂ = Θ(1/N) — loosely joined groups, a detectable but soft division.
Mirror
λ₂ = Ω(1) — an expander. The network mixes too well to cut; no faction structure survives.

Bipartite treewidth

The bipartite cut is the worst-case partition test: split the population in two and measure how many ties the densest overlapping cliques force across the divide.

Shadow
twᵇ(G) = O(1) — the two sides touch along a constant-size interface. Cleanly separable.
Equilibrium
twᵇ(G) = Θ(√N) — a perimeter-shaped interface, the signature of a geographically or topically embedded network.
Mirror
twᵇ(G) = Ω(N) — every bisection cuts a linear number of ties. The network is irreducibly one community.

The same meter, four other substrates

A social graph is one instance of the universal meter. The same five invariants read these too:

Tensor-Network ContractionVector Databases & RAGNeural-Network Quantum StatesBiological Connectomes
The full matrix