5D Library › 五维灵商量化架构、先验条件化生成与检索增强认知体 · English

第六章 书库关联图:孤岛、菲德勒值与小世界

用关键词给书库建图

作者的提纲断言:书库各卷构成的知识图「没有孤岛」,并建议用图拉普拉斯矩阵的第二小特征值,即菲德勒值 λ2\lambda_2,来证明。菲德勒证明,λ2>0\lambda_2 > 0 当且仅当图是连通的,λ2\lambda_2 越大,图越难被切成两半,因此称为代数连通度 (Fiedler 1973; Chung 1997)。

要计算,先要有图。本章用最朴素、最可复核的办法:以每卷 book.yaml 中公开的英文关键词为准,两卷书有共同关键词就连一条边。书库全部 82 卷(第 001 卷至第 082 卷)都计入。只出现在一卷中的关键词不可能连边,所以程序中内嵌的表格只保留至少出现在两卷中的 204 个关键词,并为每卷列出它用到的编号;这张表由与程序一起保存的小脚本从 82 份 book.yaml 重新生成。规则 A 使用全部关键词;规则 B 去掉现已出现在 32 卷中的方法学关键词「预注册」(pre-registration),看图在多大程度上靠它维系。

推导

# Chapter 6. p11: The library as a graph: islands, Fiedler value, diameter.
# Nodes: all 82 volumes of the library (001 to 082). Data: each volume's
# English keywords from its book.yaml, lower-cased and turned into
# ASCII; only keywords that occur in at least two volumes can make an
# edge, so the table keeps those (VOCAB, most frequent first) and lists
# for each volume the numbers of the ones it uses (LINKS; "-" = none).
# The table is generated from the 82 book.yaml files by
# tools/extract_keywords.py and embedded so that this program stays
# self-contained. Rule A joins two volumes that share any keyword; rule
# B ignores "pre-registration", the method keyword found in the most
# volumes. Reported: components, isolated volumes, and for the largest
# component the algebraic connectivity lambda2 (second-smallest
# eigenvalue of the graph Laplacian, by Jacobi rotations), diameter,
# mean distance, mean clustering coefficient, the three best-connected
# volumes, and the largest component left after those three are removed.
VOCAB = (
    "pre-registration", "barnum effect", "base rates", "thompson sampling",
    "dihedral group", "guiguzi", "kuramoto model", "modular arithmetic",
    "multi-armed bandit", "mutual information", "optimal stopping",
    "a/b testing", "book of changes", "chinese remainder theorem",
    "incentive compatibility", "kelly criterion", "matching test",
    "optional stopping", "sample size", "sunzi", "absorbing markov chain",
    "adverse selection", "autophagy", "bone conduction", "bundling",
    "circadian rhythm", "critical slowing down", "crossover trial",
    "default mode network", "entropy", "ephemeris", "error propagation",
    "first-passage time", "gaussian copula", "golden ratio", "han feizi",
    "hawkes process", "heart rate variability", "incrementality",
    "kalman filter", "matthew effect", "ornstein-uhlenbeck process",
    "preferential attachment", "qimen dunjia", "replicator dynamics",
    "sexagenary cycle", "sha-256", "shao yong",
    "shifted-beta-geometric model", "shiji", "signalling", "solar terms",
    "survival analysis", "transaction costs", "winner's curse",
    "5-ht2a receptor", "a-weighting", "adler equation", "affine maps",
    "algebraic connectivity", "allostatic load", "ampk", "analects",
    "arnold tongue", "attention residue", "auditory feedback",
    "barbell strategy", "bayesian updating", "beta-hydroxybutyrate",
    "betweenness centrality", "bid-ask spread", "bifurcation",
    "binary numbers", "binaural beats", "birthday problem", "boolean cube",
    "branching ratio", "bregman divergence", "brier score", "calibration",
    "cannibalization", "cash flow", "chargebacks", "checkout design",
    "cohen's kappa", "complex contagion", "conditional entropy",
    "confounding", "controllability gramian", "convention sensitivity",
    "conversion funnel", "customer lifetime value", "cyclic groups",
    "daodejing", "dark patterns", "declination", "decoy effect",
    "default effect", "dendrobium officinale", "dynamic programming",
    "eigenvector centrality", "entropic brain", "equation of time",
    "escalation of commitment", "external focus of attention", "fat tails",
    "fisher information", "forer effect", "forgetting curve",
    "functional graph", "fundamental matrix", "garden of forking paths",
    "genetic nurture", "glucocorticoid receptor", "glucomannan",
    "goodhart's law", "graph laplacian", "hagen-poiseuille",
    "harmonics-to-noise ratio", "hazard rate", "heavy tails",
    "hick-hyman law", "hormesis", "hpa axis", "hysteresis",
    "identifiability", "implied volatility", "information cascades",
    "inverse effectiveness", "jump diffusion", "ketone bodies",
    "kleiber's law", "klein four-group", "leibniz", "lifetime value",
    "limit order book", "loss aversion", "luoshu", "magic square",
    "market microstructure", "markov chain", "mechanism design",
    "mengxi bitan", "modularity", "mtorc1", "mucosal wave",
    "multiple comparisons", "multiple testing", "mussa-rosen",
    "optimal error rate", "permutation group", "phase locking",
    "phonation threshold pressure", "pitch-shift reflex", "placebo",
    "power laws", "precision weighting", "predictive coding", "price ratio",
    "proper scoring rules", "refunds", "reputation", "resonance breathing",
    "retrieval-augmented generation", "revelation principle",
    "reward prediction error", "risk of ruin", "roc curve", "royal cubit",
    "saddle-node bifurcation", "salience network", "schumann resonance",
    "screening", "self-referral", "sequential probability ratio test",
    "shannon entropy", "shapley value", "singer's formant",
    "sleep fragmentation", "slow-wave sleep", "small-world networks",
    "sound masking", "source-filter theory", "spectral gap",
    "structural identifiability", "sybil attack", "tail latency",
    "time-restricted eating", "triple network model",
    "twelve-tone equal temperament", "two-sided markets", "ucb1", "upsell",
    "variance risk premium", "voice science", "volatility skew",
    "weibull distribution", "wenxin diaolong", "willingness to pay",
    "wisdom of crowds", "xor", "yogacara", "zi wei dou shu", "ziping",
)

LINKS = """
001 93 | 002 0 23 65 | 003 0 46 168 | 004 26 29 165 175 | 005 22 68 130 187
006 42 90 127 155 190 | 007 98 114 | 008 6 28 55 73 101 | 009 0 27 171
010 65 104 118 145 152 153 177 182 194 | 011 1 9 86 201 | 012 98 114 117 179
013 85 97 124 169 | 014 25 37 60 113 123 162 165 | 015 3 8 191 201
016 10 53 161 | 017 22 61 68 130 131 144 187 | 018 5 6 95 118
019 15 32 49 66 105 | 020 12 26 41 93 126 129 155 195 | 021 12 | 022 112 113
023 62 108 149 | 024 27 50 64 149 | 025 42 69 85 100 127 180
026 19 67 78 79 159 167 199 | 027 14 50 115 141 164
028 12 26 41 124 143 167 169 | 029 23 39 71 145 152 153 177 182 194
030 22 61 122 144 | 031 25 27 56 181 | 032 3 8 40 | 033 0 17 54 111
034 128 | 035 44 | 036 19 52 131 143 196 | 037 4 13 45 92 147 175 189
038 10 15 70 105 126 193 195 | 039 36 39 41 76 135 | 040 33 66
041 40 88 112 176 | 042 3 8 10 19 35 103 174 191 | 043 39 104
044 6 183 199 | 045 21 36 70 76 135 139 | 046 34 121 | 047 96 97 136
048 3 8 11 17 38 48 91 176 | 049 77 106 | 050 14 141 164 185
051 28 37 60 123 128 154 156 157 162 170 188 | 052 88
053 0 28 37 117 156 157 170 184 188 | 054 0 55 101 122 184
055 0 10 15 20 99 166 | 056 0 15 53 125 129 166 193 | 057 0 25 84 140 178
058 0 11 48 52 71 81 87 91 | 059 0 53 77 78 79 139 159
060 0 30 34 44 51 102 106 | 061 0 20 31 54 110 163 186
062 0 6 32 43 57 63 99 119 125 137 138 147 150 151 | 063 0 1 5 14 24 96
064 0 4 7 16 47 72 75 132 133 140 183 202 | 065 0 1 7 13 16 29 200
066 0 7 13 16 31 45 51 58 84 102 203 | 067 0 4 16 43 45 51 75 89 137 200
068 0 14 24 33 44 46 49 74 80 120 148 172 173
069 0 1 2 5 20 35 67 80 94 103 107 110 134 158 174 192
070 0 2 9 29 33 43 89 109 202 203 | 071 0 1 2 59 69 100 116 146
072 0 1 2 4 7 13 30 47 72 132 133 | 073 0 1 2 7 30 32 109
074 21 62 108 134 161 190 | 075 3 10 46 74 173 185 186
076 0 1 9 12 47 59 86 116 163 180
077 0 1 11 17 18 35 54 82 83 94 121 136 160 197 198
078 0 3 8 9 18 24 38 49 82 83 158 160 192 198
079 0 5 9 19 36 38 48 50 148 172
080 0 6 18 23 56 57 63 73 111 142 146 151 154 171 178 179 181 189
081 0 5 11 17 18 21 40 42 52 64 81 90 115 119 120 196 197
082 0 1 2 4 31 34 58 87 92 95 107 138 142 150 168
"""

def books():
    out = {}
    for part in LINKS.replace("\n", " | ").split("|"):
        part = part.split()
        if part:
            out[int(part[0])] = set() if part[1] == "-" else {
                int(x) for x in part[1:]}
    return out

def graph(bk, skip):
    adj = {n: set() for n in bk}
    for a in bk:
        for b in bk:
            if a < b and (bk[a] & bk[b]) - skip:
                adj[a].add(b)
                adj[b].add(a)
    return adj

def components(adj):
    seen, comps = set(), []
    for n in sorted(adj):
        if n in seen:
            continue
        stack, comp = [n], set()
        while stack:
            x = stack.pop()
            if x not in comp:
                comp.add(x)
                stack.extend(adj[x] - comp)
        seen |= comp
        comps.append(comp)
    return sorted(comps, key=len, reverse=True)

def jacobi_eigs(m, sweeps=60):
    n = len(m)
    a = [row[:] for row in m]
    for _ in range(sweeps):
        off = sum(a[i][j] ** 2 for i in range(n) for j in range(n) if i != j)
        if off < 1e-18:
            break
        for p in range(n - 1):
            for q in range(p + 1, n):
                if abs(a[p][q]) < 1e-14:
                    continue
                th = (a[q][q] - a[p][p]) / (2 * a[p][q])
                t = (1 if th >= 0 else -1) / (abs(th) + (th * th + 1) ** 0.5)
                c = 1 / (t * t + 1) ** 0.5
                s = t * c
                for k in range(n):
                    akp, akq = a[k][p], a[k][q]
                    a[k][p], a[k][q] = c * akp - s * akq, s * akp + c * akq
                for k in range(n):
                    apk, aqk = a[p][k], a[q][k]
                    a[p][k], a[q][k] = c * apk - s * aqk, s * apk + c * aqk
    return sorted(a[i][i] for i in range(n))

def stats(adj, comp):
    nodes = sorted(comp)
    ix = {v: i for i, v in enumerate(nodes)}
    lap = [[0.0] * len(nodes) for _ in nodes]
    for v in nodes:
        lap[ix[v]][ix[v]] = len(adj[v] & comp)
        for w in adj[v] & comp:
            lap[ix[v]][ix[w]] = -1.0
    lam2 = jacobi_eigs(lap)[1]
    dist_all, diam = [], 0
    for s in nodes:
        dist, frontier = {s: 0}, [s]
        while frontier:
            nxt = []
            for x in frontier:
                for y in adj[x] & comp:
                    if y not in dist:
                        dist[y] = dist[x] + 1
                        nxt.append(y)
            frontier = nxt
        diam = max(diam, max(dist.values()))
        dist_all += [d for d in dist.values() if d]
    cl = []
    for v in nodes:
        nb = list(adj[v] & comp)
        k = len(nb)
        if k < 2:
            cl.append(0.0)
            continue
        e = sum(1 for i in range(k) for j in range(i + 1, k)
                if nb[j] in adj[nb[i]])
        cl.append(2 * e / (k * (k - 1)))
    return lam2, diam, sum(dist_all) / len(dist_all), sum(cl) / len(cl)

FORMER = (3, 9, 24, 31)   # isolated in the 73-volume edition

if __name__ == "__main__":
    bk = books()
    print("   table: {} volumes, {} shared keywords;"
          " pre-registration in {}".format(
              len(bk), len(VOCAB), sum(1 for v in bk.values() if 0 in v)))
    for name, skip in (("A all keywords", set()),
                       ("B without pre-registration", {0})):
        adj = graph(bk, skip)
        comps = components(adj)
        m = sum(len(v) for v in adj.values()) // 2
        iso = [n for n in sorted(adj) if not adj[n]]
        print("   rule {}: {} volumes, {} edges".format(name, len(adj), m))
        print("     components {}; isolated: {}".format(
            [len(c) for c in comps][:6], " ".join(
                "{:03d}".format(n) for n in iso) or "none"))
        share = len(comps[0]) / len(adj)
        print("     largest component holds {:.0%} of volumes".format(share))
        lam2, diam, mean_d, clus = stats(adj, comps[0])
        print("     largest: lambda2 {:.4f}, diameter {}".format(lam2, diam))
        print("     mean distance {:.2f}, clustering {:.3f}".format(
            mean_d, clus))
        hubs = sorted(adj, key=lambda v: -len(adj[v]))[:3]
        print("     hubs: " + ", ".join("{:03d} ({})".format(
            h, len(adj[h])) for h in hubs))
        rest = {v: adj[v] - set(hubs) for v in adj if v not in hubs}
        print("     without hubs, largest component: {}".format(
            len(components(rest)[0])))
        print("     former islands, degree: " + ", ".join(
            "{:03d} ({})".format(v, len(adj[v])) for v in FORMER))
    print("\nReading: 'no islands' holds for all 82 volumes under both")
    print("rules. Volumes 003, 009, 024 and 031 now carry keywords their")
    print("own text supports, and volumes 080 to 082 add links to them")
    print("through shared topics. Connected is not woven: without")
    print("pre-registration the former islands hang on three to six")
    print("edges each, and the core meets the fringe through few")
    print("bridges.")
#    table: 82 volumes, 204 shared keywords; pre-registration in 32
#    rule A all keywords: 82 volumes, 691 edges
#      components [82]; isolated: none
#      largest component holds 100% of volumes
#      largest: lambda2 0.5475, diameter 5
#      mean distance 2.23, clustering 0.591
#      hubs: 081 (42), 079 (41), 080 (39)
#      without hubs, largest component: 79
#      former islands, degree: 003 (32), 009 (33), 024 (6), 031 (5)
#    rule B without pre-registration: 82 volumes, 321 edges
#      components [82]; isolated: none
#      largest component holds 100% of volumes
#      largest: lambda2 0.4161, diameter 6
#      mean distance 2.69, clustering 0.383
#      hubs: 082 (22), 081 (21), 069 (20)
#      without hubs, largest component: 79
#      former islands, degree: 003 (3), 009 (3), 024 (6), 031 (5)
#
# Reading: 'no islands' holds for all 82 volumes under both
# rules. Volumes 003, 009, 024 and 031 now carry keywords their
# own text supports, and volumes 080 to 082 add links to them
# through shared topics. Connected is not woven: without
# pre-registration the former islands hang on three to six
# edges each, and the core meets the fringe through few
# bridges.
书库关联图(规则 A)。金色为第 080 卷至第 082 卷,紫色为 73 卷版本中的四个孤岛:第 3、9、24、31 卷。

本章在 73 卷版本中的结论是否定的:第 3、9、24、31 卷与其他任何一卷都没有共同关键词,「没有孤岛」不成立,整个图的 λ2\lambda_2 为 0。此后这四卷各自补充了正文本身支持的关键词:第 3 卷事先写明测量预测,并用 SHA-256 为原始数据文件留存指纹;第 9 卷以一项预注册的交叉试验收尾;第 24 卷有一个贝叶斯信号模型和一个按最优错误率调节难度的学习者模型;第 31 卷有交叉试验方案,并专节讨论光照与昼夜节律。

以全部 82 卷计,两条规则下的图都只有一个分量,没有任何孤立的卷:最大分量包含 100% 的卷。规则 A 下有 691 条边,菲德勒值 0.5475,直径 5,平均距离 2.23,平均聚类系数 0.591;连接最多的是第 81、79、80 卷,去掉这三个枢纽,其余 79 卷仍连成一个分量。第 080 卷至第 082 卷还以真实的共同主题与原来的孤岛相连:第 3 卷与第 082 卷共享「王室腕尺」,第 9 卷与第 080 卷共享「舒曼共振」,第 31 卷与第 080 卷共享「A 计权」与「声音掩蔽」,第 24 卷与第 081 卷共享「注意力残留」。

规则 B 去掉「预注册」之后,边数从 691 降到 321,菲德勒值降到 0.4161,直径增至 6,平均距离增至 2.69,但图仍然连成一体。原来的孤岛显示了边缘有多薄:规则 A 下第 3、9 卷分别有 32 和 33 个邻居,几乎全靠「预注册」;规则 B 下只各剩 3 个,第 24、31 卷则保有 6 个和 5 个。书库是连通的,但它是一个「有核心、有边缘」的结构,而不是均匀交织的网。

与随机图比较

一个图「很连通」还是「很聚集」,要与同样规模的随机图比较。程序为每条规则生成 30 个节点数、边数相同的 Erdős-Rényi 随机图 (Erdős and Rényi 1959),比较聚类系数、平均距离与菲德勒值,并计算小世界指数 σ=(C/Crand)/(L/Lrand)\sigma = (C/C_{\mathrm{rand}})/(L/L_{\mathrm{rand}}) (Watts and Strogatz 1998)。

推导

# Chapter 6. p12: Is the library graph more than chance? Random baselines.
# The library graph of p11 is one component of 82 volumes with 691
# edges (rule A) or 321 edges (rule B), mean clustering 0.591 / 0.383,
# mean distance 2.23 / 2.69 and Fiedler value 0.5475 / 0.4161 (values
# printed by p11). For each rule the program draws 30 Erdos-Renyi
# graphs with the same numbers of nodes and edges (fixed seed), keeps
# their largest component, and reports their mean clustering, mean
# distance and lambda2. The small-world index is
# sigma = (C / C_rand) / (L / L_rand).
import random

N = 82
OBS = {"A": (691, 0.591, 2.23, 0.5475), "B": (321, 0.383, 2.69, 0.4161)}

def jacobi_eigs(m, sweeps=60):
    n = len(m)
    a = [row[:] for row in m]
    for _ in range(sweeps):
        off = sum(a[i][j] ** 2 for i in range(n) for j in range(n) if i != j)
        if off < 1e-18:
            break
        for p in range(n - 1):
            for q in range(p + 1, n):
                if abs(a[p][q]) < 1e-14:
                    continue
                th = (a[q][q] - a[p][p]) / (2 * a[p][q])
                t = (1 if th >= 0 else -1) / (abs(th) + (th * th + 1) ** 0.5)
                c = 1 / (t * t + 1) ** 0.5
                s = t * c
                for k in range(n):
                    akp, akq = a[k][p], a[k][q]
                    a[k][p], a[k][q] = c * akp - s * akq, s * akp + c * akq
                for k in range(n):
                    apk, aqk = a[p][k], a[q][k]
                    a[p][k], a[q][k] = c * apk - s * aqk, s * apk + c * aqk
    return sorted(a[i][i] for i in range(n))

def er(rng, m):
    pairs = [(i, j) for i in range(N) for j in range(i + 1, N)]
    adj = {i: set() for i in range(N)}
    for i, j in rng.sample(pairs, m):
        adj[i].add(j)
        adj[j].add(i)
    return adj

def largest(adj):
    best, seen = set(), set()
    for s in adj:
        if s in seen:
            continue
        comp, stack = set(), [s]
        while stack:
            x = stack.pop()
            if x not in comp:
                comp.add(x)
                stack.extend(adj[x] - comp)
        seen |= comp
        best = max(best, comp, key=len)
    return best

def measures(adj, comp):
    nodes = sorted(comp)
    ix = {v: i for i, v in enumerate(nodes)}
    lap = [[0.0] * len(nodes) for _ in nodes]
    dsum = dcnt = 0
    cl = []
    for v in nodes:
        nb = adj[v] & comp
        lap[ix[v]][ix[v]] = len(nb)
        for w in nb:
            lap[ix[v]][ix[w]] = -1.0
        k = len(nb)
        nbl = list(nb)
        e = sum(1 for i in range(k) for j in range(i + 1, k)
                if nbl[j] in adj[nbl[i]])
        cl.append(2 * e / (k * (k - 1)) if k > 1 else 0.0)
        dist, fr = {v: 0}, [v]
        while fr:
            nx = []
            for x in fr:
                for y in adj[x] & comp:
                    if y not in dist:
                        dist[y] = dist[x] + 1
                        nx.append(y)
            fr = nx
        dsum += sum(dist.values())
        dcnt += len(dist) - 1
    return sum(cl) / len(cl), dsum / dcnt, jacobi_eigs(lap)[1]

if __name__ == "__main__":
    rng = random.Random(76012)
    print("   rule   C obs  C rand   L obs  L rand   lam2 obs  lam2 rand"
          "  sigma")
    for rule, (m, c, l, lam) in OBS.items():
        res = []
        for _ in range(30):
            adj = er(rng, m)
            res.append(measures(adj, largest(adj)))
        cr = sum(r[0] for r in res) / 30
        lr = sum(r[1] for r in res) / 30
        qr = sum(r[2] for r in res) / 30
        print("   {:4s} {:7.3f} {:7.3f} {:7.2f} {:7.2f} {:10.4f} {:10.4f}"
              " {:6.2f}".format(rule, c, cr, l, lr, lam, qr,
                                (c / cr) / (l / lr)))
    print("\nReading: the library is far more clustered than a random")
    print("graph of the same size, with paths nearly as short: a small")
    print("world. But its Fiedler value is lower than chance: books")
    print("cluster into themes joined by few bridges, which is exactly")
    print("where a cross-book agent must plan its route.")
#    rule   C obs  C rand   L obs  L rand   lam2 obs  lam2 rand  sigma
#    A      0.591   0.208    2.23    1.82     0.5475     7.0987   2.31
#    B      0.383   0.096    2.69    2.35     0.4161     1.5205   3.47
#
# Reading: the library is far more clustered than a random
# graph of the same size, with paths nearly as short: a small
# world. But its Fiedler value is lower than chance: books
# cluster into themes joined by few bridges, which is exactly
# where a cross-book agent must plan its route.

书库图的聚类系数远高于随机图(规则 A:0.591 对 0.208;规则 B:0.383 对 0.096),平均距离只略长(2.23 对 1.82),小世界指数分别为 2.31 与 3.47:这是一个典型的小世界。但它的菲德勒值远低于随机图(0.5475 对 7.0987):书库由几个主题团块构成,团块之间的桥不多。跨书综合的智能体正是要在这些桥上规划路线。

菲德勒值究竟量什么

为了让 λ2\lambda_2 不只是一个数字,程序在 12 个节点的小图上计算它,并用穷举所有切分的方法求出边扩张 hh(从一个不超过半数节点的集合流出的边数除以集合大小)。谱图论保证 λ2/2≤h≤2dmaxλ2\lambda_2/2 \le h \le \sqrt{2 d_{\max} \lambda_2} (Chung 1997)。

推导

# Chapter 6. p13: What the Fiedler value measures: twelve-node examples.
# For six graphs on 12 nodes the program computes lambda2 of the
# Laplacian (Jacobi rotations) and, by checking all 2^12 cuts, the
# edge expansion h = min over sets S with |S| <= 6 of (edges leaving
# S) / |S|. Fiedler's theory bounds it: lambda2 / 2 <= h <=
# sqrt(2 d_max lambda2). Graphs: a path, a ring, a star, the complete
# graph, two 6-cliques joined by one edge, and by three. Last, an
# island: a 6-clique plus 6 isolated nodes (lambda2 = 0), then the same
# with one edge from each isolated node into the clique.
import itertools
import math

def jacobi_eigs(m, sweeps=60):
    n = len(m)
    a = [row[:] for row in m]
    for _ in range(sweeps):
        off = sum(a[i][j] ** 2 for i in range(n) for j in range(n) if i != j)
        if off < 1e-20:
            break
        for p in range(n - 1):
            for q in range(p + 1, n):
                if abs(a[p][q]) < 1e-15:
                    continue
                th = (a[q][q] - a[p][p]) / (2 * a[p][q])
                t = (1 if th >= 0 else -1) / (abs(th) + (th * th + 1) ** 0.5)
                c = 1 / (t * t + 1) ** 0.5
                s = t * c
                for k in range(n):
                    akp, akq = a[k][p], a[k][q]
                    a[k][p], a[k][q] = c * akp - s * akq, s * akp + c * akq
                for k in range(n):
                    apk, aqk = a[p][k], a[q][k]
                    a[p][k], a[q][k] = c * apk - s * aqk, s * apk + c * aqk
    return sorted(a[i][i] for i in range(n))

def lam2(edges, n=12):
    lap = [[0.0] * n for _ in range(n)]
    for i, j in edges:
        lap[i][i] += 1
        lap[j][j] += 1
        lap[i][j] -= 1
        lap[j][i] -= 1
    return max(0.0, jacobi_eigs(lap)[1])

def expansion(edges, n=12):
    best = math.inf
    for size in range(1, n // 2 + 1):
        for s in itertools.combinations(range(n), size):
            s = set(s)
            cut = sum((i in s) != (j in s) for i, j in edges)
            best = min(best, cut / size)
    return best

def clique(nodes):
    return list(itertools.combinations(nodes, 2))

if __name__ == "__main__":
    two = clique(range(6)) + clique(range(6, 12))
    graphs = [
        ("path", [(i, i + 1) for i in range(11)]),
        ("ring", [(i, (i + 1) % 12) for i in range(12)]),
        ("star", [(0, i) for i in range(1, 12)]),
        ("complete", clique(range(12))),
        ("2 cliques, 1 bridge", two + [(5, 6)]),
        ("2 cliques, 3 bridges", two + [(5, 6), (4, 7), (3, 8)]),
        ("clique + 6 islands", clique(range(6))),
        ("islands linked", clique(range(6)) + [(i - 6, i)
                                               for i in range(6, 12)]),
    ]
    print("   graph                  lambda2       h   lam2/2  upper")
    for name, e in graphs:
        l2 = lam2(e)
        d = max(sum(v in p for p in e) for v in range(12))
        print("   {:21s} {:8.4f} {:7.3f} {:8.4f} {:6.3f}".format(
            name, l2, expansion(e), l2 / 2, math.sqrt(2 * d * l2)))
    print("\nReading: lambda2 is zero exactly when the graph falls apart")
    print("and small when it hangs on a few bridges, as the cut value h")
    print("confirms: one bridge between two dense halves gives less than")
    print("a ring. One link per island lifts lambda2 from zero, but each")
    print("island then hangs on one edge, and losing it isolates it.")
#    graph                  lambda2       h   lam2/2  upper
#    path                    0.0681   0.167   0.0341  0.522
#    ring                    0.2679   0.333   0.1340  1.035
#    star                    1.0000   1.000   0.5000  4.690
#    complete               12.0000   6.000   6.0000 16.248
#    2 cliques, 1 bridge     0.2583   0.167   0.1292  1.761
#    2 cliques, 3 bridges    0.8377   0.500   0.4189  3.171
#    clique + 6 islands      0.0000   0.000   0.0000  0.000
#    islands linked          0.8377   1.000   0.4189  3.171
#
# Reading: lambda2 is zero exactly when the graph falls apart
# and small when it hangs on a few bridges, as the cut value h
# confirms: one bridge between two dense halves gives less than
# a ring. One link per island lifts lambda2 from zero, but each
# island then hangs on one edge, and losing it isolates it.

路径图的 λ2\lambda_2 只有 0.0681,环为 0.2679;两个各 6 个节点的完全图之间只有一座桥时为 0.2583,比环还小;三座桥时升到 0.8377。完全图加 6 个孤立点时 λ2=0\lambda_2 = 0;每个孤立点各连一条边后升到 0.8377,但这时每个原来的孤岛都只靠一条边挂着,断了就又成孤岛。

这正是四个原孤岛在规则 B 下的处境:第 3、9 卷各自只靠三条边挂着,其中一条来自第 080 卷至第 082 卷。把它们连进书库已经做到;要把它们织进书库,还需要在内容上建立更多联系,这可以由后续各卷补上。

假说 · 尚未验证

作者的诠释(尚未验证): 为第 3、9、24、31 卷补充的关键词反映了内容上的真实联系,所以若以全文内容建图,例如以段落嵌入的相似度连边,这四卷同样会与主体相连。什么会证明这一判断错:若用预先登记的全文相似度阈值建图后,第 3、9、24、31 卷中仍有任何一卷不与其他卷相连,那么这些关键词联系就只是标签,背后没有内容。

小结

以全部 82 卷的关键词建图,书库没有孤岛:两条规则下都只有一个分量,菲德勒值为 0.5475(规则 A)或 0.4161(规则 B)。73 卷版本中的四个孤岛,已通过各自正文支持的关键词以及第 080 卷至第 082 卷的共同主题接入主体。这个图是一个聚类系数远高于随机图的小世界,但团块之间的桥比随机图少;在规则 B 下,原来的孤岛只靠少数几条边挂着:连通了,还没有织密。

参考文献

Chung, Fan R. K. 1997. Spectral Graph Theory. CBMS Regional Conference Series in Mathematics 92. American Mathematical Society.
Erdős, Paul, and Alfréd Rényi. 1959. “On Random Graphs i.” Publicationes Mathematicae Debrecen 6: 290–97.
Fiedler, Miroslav. 1973. “Algebraic Connectivity of Graphs.” Czechoslovak Mathematical Journal 23 (2): 298–305.
Watts, Duncan J., and Steven H. Strogatz. 1998. “Collective Dynamics of ‘Small-World’ Networks.” Nature 393: 440–42.

Fan, Y. (2026). Spiritual Quotient Quantification, Prior-Conditioned Generation and Retrieval-Augmented Cognitive Agents: Multidimensional State Vectors, Personalized Prompt Conditioning and Cross-Corpus Synthesis [五维灵商量化架构、先验条件化生成与检索增强认知体] (Version 1.0.0). 5D Library. https://doi.org/10.5281/zenodo.24090203 · Licensed under Creative Commons Attribution-NonCommercial-NoDerivatives 4.0 International (CC BY-NC-ND 4.0).