Example05 / 11

邻接矩阵的乘方——游走、共同邻居与三角形

所属专题: 复杂系统与网络的数学表示
下载: Notebook · .py

对正文中的 4 蛋白例子（a–b、a–c、b–c、c–d）计算 A^2 与 A^3。 (A^r)_ij 是从 i 到 j 的长度为 r 的游走条数：A^2 的对角元等于度，非对角元等于共同邻居数； tr(A^3)/6 是三角形数。最后用 NetworkX 的 common_neighbors 与 triangles 核对。输出：A^2 对角元 [2 2 3 1]；a 与 d 的共同邻居数 1；三角形数 1（a–b–c）。

Output输出图

Output文字输出

A^2 =
 [[2 1 1 1]
 [1 2 1 1]
 [1 1 3 0]
 [1 1 0 1]]
A^3 =
 [[2 3 4 1]
 [3 2 4 1]
 [4 4 2 3]
 [1 1 3 0]]
A^2 的对角元: [2 2 3 1]  度: [2, 2, 3, 1]
a 与 d 的共同邻居数 (A^2)_ad = 1 ；NetworkX: 1
三角形数 tr(A^3)/6 = 1 ；NetworkX: 1
有向图中 TF1 经两步到达 g 的路径数 = 1 （TF1→TF2→g，前馈环的间接支路）

Code代码

# 对正文中的 4 蛋白例子（a–b、a–c、b–c、c–d）计算 A^2 与 A^3。
# (A^r)_ij 是从 i 到 j 的长度为 r 的游走条数：A^2 的对角元等于度，非对角元等于共同邻居数；
# tr(A^3)/6 是三角形数。最后用 NetworkX 的 common_neighbors 与 triangles 核对。
# 输出：A^2 对角元 [2 2 3 1]；a 与 d 的共同邻居数 1；三角形数 1（a–b–c）。
import networkx as nx
import numpy as np

nodes = ["a", "b", "c", "d"]
G = nx.Graph([("a", "b"), ("a", "c"), ("b", "c"), ("c", "d")])
A = nx.to_numpy_array(G, nodelist=nodes, dtype=int)
A2 = A @ A
A3 = A2 @ A
print("A^2 =\n", A2)
print("A^3 =\n", A3)
print("A^2 的对角元:", np.diag(A2), " 度:", [G.degree(v) for v in nodes])
print("a 与 d 的共同邻居数 (A^2)_ad =", A2[0, 3],
      "；NetworkX:", len(list(nx.common_neighbors(G, "a", "d"))))
print("三角形数 tr(A^3)/6 =", np.trace(A3) // 6,
      "；NetworkX:", sum(nx.triangles(G).values()) // 3)

# 有向情形：(A^r)_ij 只计沿箭头方向的游走
D = nx.DiGraph([("TF1", "TF2"), ("TF2", "g"), ("TF1", "g")])
order = ["TF1", "TF2", "g"]
Ad = nx.to_numpy_array(D, nodelist=order, dtype=int)   # NetworkX 约定：行 = 起点，列 = 终点
print("有向图中 TF1 经两步到达 g 的路径数 =", (Ad @ Ad)[0, 2], "（TF1→TF2→g，前馈环的间接支路）")

# 作图：A、A^2、A^3 三个热图，格子里标出游走条数
import matplotlib.pyplot as plt

fig, axes = plt.subplots(1, 3, figsize=(10, 3.6))
for ax, (name, Mx) in zip(axes, [("A", A), ("A^2 (diag = degree)", A2), ("A^3 (tr/6 = %d triangle)" % (np.trace(A3) // 6), A3)]):
    ax.imshow(Mx, cmap="Blues")
    for i in range(4):
        for j in range(4):
            ax.text(j, i, Mx[i, j], ha="center", va="center",
                    color="white" if Mx[i, j] > Mx.max() / 2 else "black")
    ax.set_xticks(range(4)); ax.set_xticklabels(nodes); ax.set_yticks(range(4)); ax.set_yticklabels(nodes)
    ax.set_title(name, fontsize=10)
plt.tight_layout(); plt.show()

Run在浏览器中运行

首次加载 Python 环境约需 20–40 秒；可以修改参数后重新运行。

邻接矩阵的乘方——游走、共同邻居与三角形

# 对正文中的 4 蛋白例子（a–b、a–c、b–c、c–d）计算 A^2 与 A^3。
# (A^r)_ij 是从 i 到 j 的长度为 r 的游走条数：A^2 的对角元等于度，非对角元等于共同邻居数；
# tr(A^3)/6 是三角形数。最后用 NetworkX 的 common_neighbors 与 triangles 核对。
# 输出：A^2 对角元 [2 2 3 1]；a 与 d 的共同邻居数 1；三角形数 1（a–b–c）。
import networkx as nx
import numpy as np

nodes = ["a", "b", "c", "d"]
G = nx.Graph([("a", "b"), ("a", "c"), ("b", "c"), ("c", "d")])
A = nx.to_numpy_array(G, nodelist=nodes, dtype=int)
A2 = A @ A
A3 = A2 @ A
print("A^2 =\n", A2)
print("A^3 =\n", A3)
print("A^2 的对角元:", np.diag(A2), " 度:", [G.degree(v) for v in nodes])
print("a 与 d 的共同邻居数 (A^2)_ad =", A2[0, 3],
      "；NetworkX:", len(list(nx.common_neighbors(G, "a", "d"))))
print("三角形数 tr(A^3)/6 =", np.trace(A3) // 6,
      "；NetworkX:", sum(nx.triangles(G).values()) // 3)

# 有向情形：(A^r)_ij 只计沿箭头方向的游走
D = nx.DiGraph([("TF1", "TF2"), ("TF2", "g"), ("TF1", "g")])
order = ["TF1", "TF2", "g"]
Ad = nx.to_numpy_array(D, nodelist=order, dtype=int)   # NetworkX 约定：行 = 起点，列 = 终点
print("有向图中 TF1 经两步到达 g 的路径数 =", (Ad @ Ad)[0, 2], "（TF1→TF2→g，前馈环的间接支路）")

# 作图：A、A^2、A^3 三个热图，格子里标出游走条数
import matplotlib.pyplot as plt

fig, axes = plt.subplots(1, 3, figsize=(10, 3.6))
for ax, (name, Mx) in zip(axes, [("A", A), ("A^2 (diag = degree)", A2), ("A^3 (tr/6 = %d triangle)" % (np.trace(A3) // 6), A3)]):
    ax.imshow(Mx, cmap="Blues")
    for i in range(4):
        for j in range(4):
            ax.text(j, i, Mx[i, j], ha="center", va="center",
                    color="white" if Mx[i, j] > Mx.max() / 2 else "black")
    ax.set_xticks(range(4)); ax.set_xticklabels(nodes); ax.set_yticks(range(4)); ax.set_yticklabels(nodes)
    ax.set_title(name, fontsize=10)
plt.tight_layout(); plt.show()