1import numpy as np
 2
 3
 4def cyclic_triangle_incidence(n):
 5    A = np.zeros((n, n), dtype=float)
 6    for j in range(n):
 7        A[j % n, j] = 1.0
 8        A[(j + 1) % n, j] = 1.0
 9        A[(j + 2) % n, j] = 1.0
10    return A
11
12
13def local_operator(A, self_loop=0.0):
14    up = A.sum(axis=1)
15    down = A.sum(axis=0)
16    P = (A / up[:, None]) @ np.diag(1.0 / down) @ A.T
17    if self_loop:
18        P = (1.0 - self_loop) * P + self_loop * np.eye(P.shape[0])
19    return P
20
21
22def teleport(P, alpha):
23    n = P.shape[0]
24    return (1.0 - alpha) * P + alpha * np.ones((n, n)) / n
25
26
27def nonprincipal_radius(P):
28    vals = np.linalg.eigvals(P)
29    k = np.argmin(np.abs(vals - 1.0))
30    return float(np.max(np.abs(np.delete(vals, k))))
31
32
33def mfpt_to_target(P, target):
34    n = P.shape[0]
35    keep = [i for i in range(n) if i != target]
36    Q = P[np.ix_(keep, keep)]
37    t = np.linalg.solve(np.eye(n - 1) - Q, np.ones(n - 1))
38    out = np.zeros(n)
39    out[keep] = t
40    return out
41
42
43def ridge_accuracy(X, y, train, reg=1e-2):
44    Xtr = X[train]
45    Y = np.eye(2)[y[train]]
46    W = np.linalg.solve(Xtr.T @ Xtr + reg * np.eye(X.shape[1]), Xtr.T @ Y)
47    pred = np.argmax(X @ W, axis=1)
48    return float(np.mean(pred == y)), pred
49
50
51def run_experiment(seed=7):
52    rng = np.random.default_rng(seed)
53    n = 60
54    A = cyclic_triangle_incidence(n)
55    P0 = local_operator(A, self_loop=0.1)
56    alphas = np.array([0.0, 0.01, 0.03, 0.1, 0.3, 0.6])
57
58    # Prediction 1: uniform teleportation contracts every nonprincipal eigenvalue
59    # by exactly 1-alpha on the regular complex.
60    rho0 = nonprincipal_radius(P0)
61    spectral = []
62    for a in alphas:
63        rho = nonprincipal_radius(teleport(P0, a))
64        spectral.append((float(a), rho, rho / rho0, 1.0 - a))
65
66    # Prediction 2: first-passage times decrease as global jumps become more likely.
67    target = n // 2
68    mfpt = []
69    for a in alphas:
70        t = mfpt_to_target(teleport(P0, a), target)
71        mfpt.append((float(a), float(np.mean(t))))
72
73    # Small node classification test: two noisy community signals on the cycle.
74    y = np.zeros(n, dtype=int)
75    y[n // 2:] = 1
76    X = np.zeros((n, 8))
77    X[:, 0] = 2 * y - 1
78    X[:, 1] = np.cos(2 * np.pi * np.arange(n) / n)
79    X[:, 2:] = rng.normal(0, 0.8, size=(n, 6))
80    train = np.r_[np.arange(0, 8), np.arange(n // 2, n // 2 + 8)]
81    # Repeated propagation isolates the oversmoothing/mixing tradeoff.
82    cls = []
83    for a in alphas:
84        P = teleport(P0, a)
85        H = X.copy()
86        for _ in range(8):
87            H = P @ H
88        acc, _ = ridge_accuracy(H, y, train)
89        cls.append((float(a), acc, float(np.std(H[:, 0]))))
90
91    return {"n": n, "rho0": rho0, "spectral": spectral, "mfpt": mfpt,
92            "classification": cls}
93
94
95if __name__ == '__main__':
96    import json
97    print(json.dumps(run_experiment(), indent=2))