1.3 形态测量三把尺：度、路径与连通性

摘要：度、路径、连通性是网络形态测量的三把基础量尺。本节给出每把尺的定义、口径与计算方式：度与度分布刻画局部连接的多寡，平均路径长度与直径刻画全局距离的远近，连通分量刻画网络是一整块还是碎盘。三把尺配合 networkx 全部可一键计算，并引出「测量值必须对照随机基准」的方法论伏笔。

标本做好了，先量什么

标本瓶封好口，摆在测量台上，第一件事量什么？博物馆的形态学测量从最省事的指标开始：数条纹、量翼展、称体重。网络形态学也一样，第一把尺数连接，第二把尺量距离，第三把尺查整体性。三把尺都不需要任何模型假设，拿来就能量——它们是后续一切鉴定的原始读数：第 2 章拿它们鉴定随机图标本像不像真实网络，第 3 章拿它们登记真实网络的普适形态，第 5 章还要把其中两把尺升级成算法（中心性、社团检测）。

提醒一句分工：算最短路径用的是什么算法、复杂度多少，属于图论教程的地盘，本册直接引用结论——「用广度优先搜索求单源最短路」这句话之后不再解释。我们关心的是测出来之后怎么读数。

第一把尺：度与度分布

节点的度是与它相连的边数。有向图里度拆成两半：指向它的入度、从它出发的出度——微博账号的粉丝数是入度，关注数是出度，两者含义截然不同，混着读必然误判。加权图里还有点强度：把每条边的权重加总，回答「连接的总厚度」而非「连接的条数」。

单个节点的度只是体检单上的一项；真正有形态学意义的是度分布——整个网络里度为各种取值的节点各占多少。度分布是网络的第一张「侧脸照」：集中在平均值附近的分布说明节点彼此相仿；拖着长尾巴的分布说明少数节点连接极多。第 2 章的随机图会给出一个「泊松侧脸」，第 3 章的真实网络会亮出「幂律侧脸」，两者一对比，无标度的故事就开了头。

先把这把尺用到上一节的合作图上，并顺带完成第一次「手算校验」：


import networkx as nx
from collections import Counter

pairs = [("张三","李四"),("张三","王五"),("李四","王五"),
         ("王五","赵六"),("赵六","钱七"),("钱七","孙八")]
G = nx.Graph(pairs)

deg = dict(G.degree())
print("各节点度：", deg)
dist = Counter(deg.values())
print("度分布（度: 节点数）：", dict(sorted(dist.items())))

输出里王五的度最高——他一头连着张三李四的圈子、一头连着赵六，是两张关系网之间的「桥」。这个六节点小图的度分布手算即可复核：写下方程「所有节点的度之和等于边数的两倍」，任何测量结果违反这条守恒律，必定是建图环节出了错。这是三把尺中最常用的一致性检查。

第二把尺：路径、平均路径长度与直径

路径是从一个节点出发、沿边走到另一个节点所经过的序列，路径上的边数就是它的长度；最短路径是所有可行路径里最短的那条，习惯上直接把它的长度叫做两点间的距离。网络的全局距离读数有两个：平均路径长度把所有节点对的距离取平均，反映「随便挑两个人，中间隔几个人」；直径取距离的最大值，反映「最远的两个人隔多远」。

两个读数各有脾气。平均路径长度稳健、好比较，是「小世界」鉴定的主指标；直径却被一条极端路径绑架——网络里只要存在一条孤悬的长链，直径就会暴涨，因此实务里常用「有效直径」之类的分位数替代。还要注意有向图的口径：沿边方向走与忽略方向走，距离可以差得很远，引用网络里「A 引用 B」不代表「从 B 能走到 A」。


import networkx as nx

G = nx.karate_club_graph()
L = nx.average_shortest_path_length(G)      # 连通小图可直接整体计算
D = nx.diameter(G)
print("平均路径长度：", round(L, 3))        # 约 2.4
print("直径：", D)                          # 5
ecc = nx.eccentricity(G)                    # 每个节点到最远点的距离
print("离心率最大的会员：", max(ecc, key=ecc.get))

三十多个会员的俱乐部，任意两人之间平均只隔两人——小世界效应在最迷你的真实网络里已经显形。大图上整体求最短路代价高昂，实务改用随机抽样节点对或多点广度优先估计：读数略有抖动，量级判断不受影响。

第三把尺：连通性与连通分量

连通性问的是一票否决式的问题：网络是不是一整块？如果任意两节点之间都有路径，称网络连通；否则网络由若干个连通分量组成——分量内部互相可达、分量之间老死不相往来。数据建出来的图几乎总是不连通的：爬虫漏抓的网页、只收不发的账号，都会以孤立小分量的形式漂在图里。

有向图的连通性要分两档。强连通要求沿边方向互相可达；弱连通放宽为忽略方向后可达。航班网络是好例子：把航线图看成有向图，绝大多数机场之间都能往返（强连通分量很大），但总存在只出不进或只进不出的支线小机场，把它们算进「可达」靠的是弱连通口径。

处理真实网络的第一条守则由此而来：先看最大连通分量，把主块与碎渣分开报告。度分布、路径、社团这些测量通常只在主块上进行，碎渣单独立账。


import networkx as nx

G = nx.karate_club_graph()
comps = sorted(nx.connected_components(G), key=len, reverse=True)
print("连通分量个数：", len(comps), " 主块规模：", len(comps[0]))

DG = nx.gn_graph(60, seed=3)                # 生长型有向图：新节点指向老节点
sccs = sorted(nx.strongly_connected_components(DG), key=len, reverse=True)
print("强连通分量个数：", len(sccs),
      " 最大强连通块规模：", len(sccs[0]))
print("弱连通块个数：", nx.number_weakly_connected_components(DG))

这把尺揭示的现象有普遍性：增长型有向网络（如引用网络）往往由一大堆微小的强连通块挂在一条「主干链」上组成——文献引用里极少出现互相引用的环，绝大多数强连通块退化为单节点。连通性的读数，因此也是网络「生成方式」的第一条线索，第 4 章解剖生成机制时会回收这个伏笔。

图三把尺的读数仪表盘

三把尺合用：一次完整体检

三把尺各管一段，合在一起就是网络体检的标准流程：先查连通性确认主块，再在主块上量平均距离，最后登记度分布。体检报告的读法有一条隐藏守则——绝对值几乎没有意义，相对值才是信息。说「平均路径长度是二点四」并不能说明世界小不小；要说「同规模的随机图平均路径长度也在这个量级、而聚类却高得多」，读数才开始说话。

💡 关键直觉：测量值要放进参照系。第 2 章整章都在造这个参照系——随机图展室里两件理论标本，就是用来给真实网络当对照组的。

本节要点回顾

度：节点相连的边数，有向图分入度出度；度分布是网络的第一张侧脸照，度和守恒律是最便宜的正确性检查
路径：两点距离取最短路径长度；平均路径长度量全局远近，直径易受极值干扰，大图改用抽样估计
连通性：先分主块与碎渣，测量在主块上进行；有向图区分强连通与弱连通，读数本身就是生成机制的线索
方法论伏笔：三把尺的绝对读数无意义，与同规模随机对照比较才是鉴定的开始

带着体检报告，下一章推开随机图展室的门：先看统计学家在纯随机规则下培育的标本长什么样，再看加一点捷径的小世界标本，最后用真实报告给两件理论标本出鉴定书。

作者与出处

原作者：灏天文库

来源：灏天文库

整理：灏天文库整理

由灏天文库平台收录，内容或由平台用户上传，仅供学习交流

1.3 形态测量三把尺：度、路径与连通性