5D Library

第五章 特征向量中心性与 PageRank

5D Library › 社会网络拓扑、结构洞与复杂传染的数学模型 · English

第五章 特征向量中心性与 PageRank

不只看有多少连接，也看连接的是谁

度中心性只数一个人有多少联系人。但认识十个同样只认识你的人，和认识十个各自认识上百人的人，位置显然不同。博纳西奇在 1972 年提出一个自洽的定义：一个人的地位与他的联系人的地位之和成正比 (Bonacich 1972)。

推导

特征向量中心性。 设 AA 是网络的邻接矩阵（ii 与 jj 相连时 aij=1a_{ij} = 1），要求

λxi=∑jaijxj\lambda\, x_i = \sum_j a_{ij}\, x_j

即 Ax=λxA x = \lambda x：xx 是 AA 的特征向量。对连通的网络，取最大特征值 λmax\lambda_{\max} 对应的特征向量，它的各分量都为正（佩龙—弗罗贝尼乌斯定理）。最简单的求法是幂迭代：从任意正向量出发，反复乘以 AA 并归一化，向量就会收敛到这个特征向量；收敛速度由第二大特征值与最大特征值之比决定。

博纳西奇的 β 中心性：被依赖的权力

博纳西奇在 1987 年把这一思路推广为一族指标：

c(β)=α∑k=0∞βkAk+1𝟏c(\beta) = \alpha \sum_{k=0}^{\infty} \beta^k A^{k+1} \mathbf{1}

Ak+1𝟏A^{k+1}\mathbf{1} 数的是从每个人出发、长度为 k+1k+1 的路径，β\beta 决定远处的路径有多大权重，级数在 |β|<1/λmax|\beta| < 1/\lambda_{\max} 时收敛；β=0\beta = 0 时 cc 就是度，β\beta 趋于 1/λmax1/\lambda_{\max} 时 cc 趋于特征向量中心性。他指出，当 β\beta 为负时，这个指标衡量的是另一种东西：在交换与谈判的网络中，与那些没有其他选择的人相连，才意味着权力，因为他们只能依赖你；而与那些自己就有很多选择的人相连，反而削弱你的议价地位 (Bonacich 1987)。

推导

一个虚构的网络。X 有四位联系人 x1–x4，他们除了 X 不认识任何人；Y 有四位联系人 y1–y4，他们彼此全都相识；X 与 Y 相连。X 与 Y 的度相同（都是 5）。所有列都以同样的方式缩放（平方和等于节点数）。

# Eigenvector centrality (Bonacich 1972) and Bonacich's (1987) beta-centrality
#   c(beta) = alpha * sum_{k>=0} beta^k R^(k+1) 1,  scaled so that sum c^2 = n,
# computed as a series (valid for |beta| < 1/lambda_max). beta > 0: being tied
# to well-connected people counts; beta < 0: being tied to people who have
# FEW other options counts (bargaining power in exchange networks).
# Invented network: X has four contacts x1-x4 with no other ties; Y has four
# contacts y1-y4 who are all tied to each other; X and Y are tied.
# All columns are scaled the same way (beta = 0 gives degree).
import math
from itertools import combinations
ties = [("X", f"x{i}") for i in range(1, 5)] + [("Y", f"y{i}") for i in range(1, 5)]
ties += list(combinations([f"y{i}" for i in range(1, 5)], 2)) + [("X", "Y")]
nodes = sorted({v for e in ties for v in e})
nb = {v: set() for v in nodes}
for a, b in ties:
    nb[a].add(b); nb[b].add(a)

def mult(x):                       # R x
    return {v: sum(x[w] for w in nb[v]) for v in nodes}

def scale(x):
    s = math.sqrt(sum(val * val for val in x.values()) / len(x))
    return {v: x[v] / s for v in nodes}

x = {v: 1.0 for v in nodes}        # power iteration for the leading eigenvector
for _ in range(500):
    y = mult(x)
    lam = math.sqrt(sum(v * v for v in y.values()) / sum(v * v for v in x.values()))
    x = scale(y)
print(f"lambda_max = {lam:.3f}, so |beta| must stay below {1 / lam:.3f}")

def beta_centrality(beta, terms=400):
    total, walk = {v: 0.0 for v in nodes}, mult({v: 1.0 for v in nodes})
    for k in range(terms):
        for v in nodes:
            total[v] += beta ** k * walk[v]
        walk = mult(walk)
    return scale(total)

deg = scale({v: float(len(nb[v])) for v in nodes})
cols = [("degree", deg), ("eigenvector", x)]
cols += [(f"beta {b:+.2f}", beta_centrality(b)) for b in (0.2, -0.2)]
print("node  " + "".join(f"{name:>13s}" for name, _ in cols))
for v in ("X", "Y", "x1", "y1"):
    print(f" {v:4s}" + "".join(f"{c[v]:13.2f}" for _, c in cols))
# lambda_max = 4.068, so |beta| must stay below 0.246
# node         degree  eigenvector   beta +0.20   beta -0.20
#  X            1.46         0.48         0.75         2.10
#  Y            1.46         1.47         1.50         1.11
#  x1           0.29         0.12         0.21         0.05
#  y1           1.16         1.37         1.32         1.04

X 与 Y 的度完全相同，但特征向量中心性相差三倍（0.48 对 1.47）：Y 的联系人彼此相连、各自也有很多连接，X 的联系人只认识 X。β=+0.2\beta = +0.2 时排序相同（0.75 对 1.50）。但当 β=−0.2\beta = -0.2 时排序反转：X 为 2.10，Y 为 1.11。在博纳西奇的意义上，X 的联系人只能通过 X 与外界往来，X 处在一个「被依赖」的位置。这与第二章的结构洞相通：X 的四位联系人之间全是结构洞，X 的网络约束很低。

哪一种中心性「正确」，取决于问的是什么。如果关心的是信息能多快地从一个人传遍网络，连接到连接广泛的人（正的 β\beta、特征向量中心性）更重要；如果关心的是谈判与交换中的议价能力，被依赖（负的 β\beta）可能更重要。用一个指标给所有人排名，而不说明问题是什么，往往没有意义。

PageRank

证据

随机冲浪者。 布林与佩奇在 1998 年描述了谷歌搜索引擎的原型，其中给网页排序的方法称为 PageRank：一个网页的分数由所有链接到它的网页的分数决定，每个网页把自己的分数平均分给它链接出去的网页；再加上一个阻尼系数 dd，他们写道通常取 d=0.85d = 0.85 (Brin and Page 1998)。佩奇等人在 1999 年的技术报告中用「随机冲浪者」解释它：一个上网者以概率 dd 点击当前网页上的一个随机链接，以概率 1−d1-d 厌倦了，跳到一个完全随机的网页；PageRank 就是这个随机游走的长期停留比例 (Page et al. 1999)。

有向网络带来两个在无向网络中不存在的问题。一是悬挂节点：没有任何出链的网页，随机冲浪者走到这里就无路可走。常见的处理办法是让它以均等的概率跳到任何网页。二是陷阱：一组只互相链接、不链接到外面的网页，随机冲浪者一旦进入就出不来，分数会全部积聚到那里。阻尼系数的随机跳转同时解决了这两个问题，也保证了幂迭代收敛：误差每一步大约缩小为原来的 dd 倍。朗维尔与迈耶对这些处理办法与收敛性质做了系统的综述 (Langville and Meyer 2004)。

推导

一个虚构的 8 页「网络」。F 没有出链（悬挂节点），它的分数平均分给所有页面；G 与 H 只互相链接，B 有一条链接通向 G（一个「陷阱」）。DD 为悬挂节点的集合。用幂迭代计算 PageRank，直到前后两次的差（各页差的绝对值之和）小于 10−1210^{-12}。

PRi=1−dn+d(∑j→iPRjoutj+1n∑j∈DPRj)PR_i = \frac{1-d}{n} + d\Big(\sum_{j \to i} \frac{PR_j}{\mathrm{out}_j} + \frac{1}{n}\sum_{j \in D} PR_j\Big)

# PageRank by power iteration, standard library only (Brin & Page 1998;
# Page et al. 1999). An invented web of 8 pages. F has no out-links (a
# dangling page): its rank is spread evenly over all pages. G and H link only
# to each other (a "rank sink" that B feeds). With damping d, the surfer
# follows a link with probability d and jumps to a random page otherwise:
#   PR = (1 - d)/n + d * (sum over in-links PR(j)/out(j) + dangling mass/n)
links = {"A": "BC", "B": "CG", "C": "A", "D": "CE", "E": "CF", "F": "",
         "G": "H", "H": "G"}
pages = sorted(links)
n = len(pages)

def pagerank(d, tol=1e-12, max_it=20000):
    pr = {p: 1 / n for p in pages}
    errs = []
    for it in range(1, max_it + 1):
        dangling = sum(pr[p] for p in pages if not links[p])
        new = {p: (1 - d) / n + d * dangling / n for p in pages}
        for p in pages:
            for q in links[p]:
                new[q] += d * pr[p] / len(links[p])
        err = sum(abs(new[p] - pr[p]) for p in pages)
        errs.append(err); pr = new
        if err < tol:
            return pr, it, errs
    return pr, max_it, errs

pr, it, errs = pagerank(0.85)
order = sorted(pages, key=lambda p: -pr[p])
print("d = 0.85: " + "  ".join(f"{p} {pr[p]:.3f}" for p in order))
print(f"  converged in {it} iterations; error ratio per step about"
      f" {errs[30] / errs[29]:.3f} (close to d)")
print("damping   iterations   G + H share   top page")
for d in (0.5, 0.85, 0.95, 0.99, 1.0):
    pr_d, it_d, _ = pagerank(d)
    top = max(pages, key=lambda p: pr_d[p])
    its = f"{it_d:9d}" if it_d < 20000 else "    never"
    print(f"  {d:4.2f}   {its}     {pr_d['G'] + pr_d['H']:8.3f}       {top}")
# d = 0.85: G 0.279  H 0.260  A 0.144  C 0.143  B 0.084  F 0.036  E 0.032  D 0.023
#   converged in 146 iterations; error ratio per step about 0.827 (close to d)
# damping   iterations   G + H share   top page
#   0.50          35        0.326       G
#   0.85         146        0.539       G
#   0.95         462        0.759       G
#   0.99        2356        0.938       G
#   1.00       never        1.000       H

在 d=0.85d = 0.85 时，排名最高的是 G（0.279）与 H（0.260），因为 B 的一半分数流进这个陷阱后只能在两者之间循环，只有随机跳转才能把它带出来。C 有四条入链（来自 A、B、D、E），比任何页面都多，但它的分数（0.143）略低于只有一条入链的 A（0.144）：C 把全部分数都给了 A。这说明 PageRank 衡量的不是入链的数量，而是入链的来源。误差每一步缩小约 0.827 倍，接近 dd。

阻尼系数越大，排名越接近「纯粹」的链接结构，但代价有两个：收敛变慢（d=0.5d = 0.5 时 35 次迭代，d=0.85d = 0.85 时 146 次，d=0.99d = 0.99 时 2,356 次），陷阱吸走的分数也越多（G 与 H 合计从 0.33 升到 0.94）；d=1d = 1 时，迭代在 G 与 H 之间来回振荡，永远不收敛，全部分数都被困在陷阱里。d=0.85d = 0.85 是在「尊重链接结构」与「稳定、快速、不被陷阱劫持」之间的折中，并没有理论上的最优性。

注

两种写法。 布林与佩奇 1998 年论文中的公式写作 PR(A)=(1−d)+d∑PR(Ti)/C(Ti)PR(A) = (1-d) + d\sum PR(T_i)/C(T_i)，各页分数之和等于页面总数而不是 1，同时文中又说这些分数构成一个概率分布；后来的文献通常采用上面除以 nn 的写法。对于排序，两种写法在同样处理悬挂节点时是等价的。

中心性用在人身上

在社会网络中，各种中心性常被当作「影响力」的指标，用来寻找传播的起点。第三章已经说明，对于复杂传染，基于最短路径的中心性可能选错人；本章的例子又说明，不同的中心性回答的是不同的问题。还有一层限制：网络中的中心性只描述结构上的位置，不说明一个人是否愿意传播、他的话是否被信任。

假说 · 尚未验证

求教网络中的 PageRank（尚未确立）。在一个组织中，以「你遇到技术问题时会向谁求教」构建有向网络。假说：一个人在这个网络中的 PageRank，比他的入度（被多少人求教）更能预测同事在匿名评价中对其专业水平的评分，因为被「被求教者」求教比被许多新手求教更能说明专业水平。可以检验的预测：在控制入度之后，PageRank 与专业评分仍然显著正相关。如果在控制入度之后相关消失，这一假说就被削弱。

本章小结

特征向量中心性把「连接的是谁」纳入地位的计算，可以用幂迭代求得。博纳西奇的 β 中心性把度与特征向量中心性连成一族指标，负的 β 衡量「被依赖」的议价权力，与结构洞相通。PageRank 是有向网络上带随机跳转的随机游走：阻尼系数处理了悬挂节点与陷阱，保证收敛，d=0.85d = 0.85 是一种折中而不是最优。下一章讨论，当每个人都在观察前面的人怎么做时，群体会怎样一起走向同一个方向，而那个方向未必正确。

参考文献

Bonacich, Phillip. 1972. “Factoring and Weighting Approaches to Status Scores and Clique Identification.” Journal of Mathematical Sociology 2 (1): 113–20.
———. 1987. “Power and Centrality: A Family of Measures.” American Journal of Sociology 92 (5): 1170–82. https://doi.org/10.1086/228631.
Brin, Sergey, and Lawrence Page. 1998. “The Anatomy of a Large-Scale Hypertextual Web Search Engine.” Computer Networks and ISDN Systems 30 (1–7): 107–17. https://doi.org/10.1016/S0169-7552(98)00110-X.
Langville, Amy N., and Carl D. Meyer. 2004. “Deeper Inside PageRank.” Internet Mathematics 1 (3): 335–80.
Page, Lawrence, Sergey Brin, Rajeev Motwani, and Terry Winograd. 1999. “The PageRank Citation Ranking: Bringing Order to the Web.” 1999-66. Stanford InfoLab.

Fan, Y. (2026). Social Network Topology, Structural Holes and Complex Contagion: From the Strength of Weak Ties and Preferential Attachment to Information Cascades, Read Beside Classical Chinese Diplomacy [社会网络拓扑、结构洞与复杂传染的数学模型] (Version 1.0.0). 5D Library. https://doi.org/10.5281/zenodo.23764990 · Licensed under Creative Commons Attribution-NonCommercial-NoDerivatives 4.0 International (CC BY-NC-ND 4.0).