What does Spectral Gaps and Bottleneck Cuts conclude, in numbers, about “Opposing Evidence and Boundaries: Where the Algebraic Connectivity Misleads”?

Answer: Chapter 6 sets out the opposing evidence: the preferential-attachment graph with the highest algebraic connectivity keeps only 0.300 of its nodes connected after a fifth of its hubs are removed on purpose.

Scope of the numbers: The parameters are illustrative; all calculations are generated by the book's programs; the book is not individual business advice, and any change to a production system or a real supply chain must be reviewed and released by hand by the person in charge. Marked boxes separate published evidence, runnable Python calculations (18 programs), classical sources and the author's hypotheses.

中文版

Data table

The numbers below are printed verbatim by the chapter's Python program and can be reproduced by running it. standard-library Python onlyprinted values that match the answer: 0.300

graphedges dmax lambda2rand10rand20hub10hub20
pref. attachment77140.72010.8970.7820.7500.300
uniform random7780.35140.8840.7710.8250.675
ring C40(1,2)8040.12250.9000.7140.9000.800
Show the full program
# Chapter 6. p61: the opposing evidence. Random failures against a
# targeted attack on hubs (Albert, Jeong and Barabasi 2000) for three
# 40-node graphs of about the same size, set beside lambda2.
# Model: a preferential-attachment graph (each new node links to 2
# existing nodes with probability proportional to degree), a uniform
# random graph with the same number of edges, and the ring lattice
# C40(1,2). Remove 10 or 20 percent of nodes at random (mean of 300
# draws) or by highest initial degree; report the share of the 40 nodes
# left in the largest connected piece. Seeds fixed; graphs illustrative.
import math
import random


def laplacian(n, edges):
    lap = [[0.0] * n for _ in range(n)]
    for i, j in edges:
        lap[i][j] -= 1.0
        lap[j][i] -= 1.0
        lap[i][i] += 1.0
        lap[j][j] += 1.0
    return lap


def jacobi(mat, tol=1e-22):
    n = len(mat)
    a = [row[:] for row in mat]
    v = [[1.0 if i == j else 0.0 for j in range(n)] for i in range(n)]
    sweeps = 0
    while True:
        off = math.fsum(a[i][j] ** 2 for i in range(n)
                        for j in range(i + 1, n))
        if off < tol or sweeps > 60:
            break
        sweeps += 1
        for p in range(n - 1):
            for q in range(p + 1, n):
                if abs(a[p][q]) < 1e-300:
                    continue
                th = (a[q][q] - a[p][p]) / (2.0 * a[p][q])
                t = math.copysign(1.0, th) / (abs(th) + math.hypot(th, 1.0))
                c = 1.0 / math.sqrt(t * t + 1.0)
                s = t * c
                for k in range(n):
                    akp, akq = a[k][p], a[k][q]
                    a[k][p] = c * akp - s * akq
                    a[k][q] = s * akp + c * akq
                for k in range(n):
                    apk, aqk = a[p][k], a[q][k]
                    a[p][k] = c * apk - s * aqk
                    a[q][k] = s * apk + c * aqk
                for k in range(n):
                    vkp, vkq = v[k][p], v[k][q]
                    v[k][p] = c * vkp - s * vkq
                    v[k][q] = s * vkp + c * vkq
    order = sorted(range(n), key=lambda i: a[i][i])
    vals = [a[i][i] for i in order]
    vecs = [[v[k][i] for k in range(n)] for i in order]
    return vals, vecs, sweeps


def pref_attach(n, m, rng):
    edges, targets = set(), []
    for i in range(m + 1):
        for j in range(i):
            edges.add((j, i))
            targets += [i, j]
    for v in range(m + 1, n):
        chosen = set()
        while len(chosen) < m:
            chosen.add(rng.choice(targets))
        for u in sorted(chosen):
            edges.add((u, v))
            targets += [u, v]
    return sorted(edges)


def uniform(n, m, rng):
    allp = [(i, j) for i in range(n) for j in range(i + 1, n)]
    while True:
        es = sorted(rng.sample(allp, m))
        if giant(n, es, set()) == n:
            return es


def giant(n, es, gone):
    adj = {v: [] for v in range(n) if v not in gone}
    for i, j in es:
        if i in adj and j in adj:
            adj[i].append(j)
            adj[j].append(i)
    best, seen = 0, set()
    for s in sorted(adj):
        if s in seen:
            continue
        comp, stack = 1, [s]
        seen.add(s)
        while stack:
            u = stack.pop()
            for w in adj[u]:
                if w not in seen:
                    seen.add(w)
                    stack.append(w)
                    comp += 1
        best = max(best, comp)
    return best


n = 40
rng = random.Random(20261113)
ba = pref_attach(n, 2, rng)
graphs = [("pref. attachment", ba), ("uniform random", uniform(n, len(ba),
                                                                rng)),
          ("ring C40(1,2)", sorted({(min(i, (i + d) % n),
                                     max(i, (i + d) % n))
                                    for i in range(n) for d in (1, 2)}))]
print("graph             edges dmax lambda2  rand10  rand20  hub10  hub20")
for name, es in graphs:
    deg = [0] * n
    for i, j in es:
        deg[i] += 1
        deg[j] += 1
    lam = jacobi(laplacian(n, es))[0][1]
    order = sorted(range(n), key=lambda v: (-deg[v], v))
    cells = []
    for frac in (0.1, 0.2):
        k = int(round(frac * n))
        vals = [giant(n, es, set(rng.sample(range(n), k))) / n
                for _ in range(300)]
        cells.append(math.fsum(vals) / len(vals))
    for frac in (0.1, 0.2):
        k = int(round(frac * n))
        cells.append(giant(n, es, set(order[:k])) / n)
    print("%-17s %5d %4d %7.4f  %s"
          % (name, len(es), max(deg), lam,
             "  ".join("%6.3f" % c for c in cells)))

Single source and citation

Fan, Y. (2026). Graph-Laplacian Spectral Gaps and Cheeger Constants: Single-Point Bottleneck Cuts in Multi-Agent Workflows and Cross-Border Supply Chains (Version 1.0.0), Chapter 6: Opposing Evidence and Boundaries: Where the Algebraic Connectivity Misleads. 5D Library. DOI pending

DOI pending · monograph page goes live after publication · 5DL-B-243 · v1.0.0 · CC-BY-NC-ND-4.0

BibTeX
@book{fan2026243,
  author    = {Fan, Yafu},
  title     = {Graph-Laplacian Spectral Gaps and Cheeger Constants: Single-Point Bottleneck Cuts in Multi-Agent Workflows and Cross-Border Supply Chains},
  year      = {2026},
  publisher = {5D Library},
  edition   = {1.0.0},
  note      = {DOI pending}
}

Other chapter answers in this book