生物医学网络科学Biomedical Network Science
Network FoundationsNetwork metrics and random graphs

网络结构指标与随机图

用度、路径、聚集、效率与中心性刻画网络结构，并以 Erdős–Rényi 随机图为零模型判断真实网络的特殊之处。

知识页面
19 页
阅读
约 37 分钟
讲解视频
1 段
代码示例
15 个
度分布密度最短路径直径广度优先搜索聚集系数全局效率局部效率加权网络中心性介数中心性特征向量中心性PageRankk 核

把一个系统写成图和邻接矩阵（见复杂系统与网络的数学表示）之后，下一步是描述它的结构。一张有上万个节点的网络画出来只是一团“毛线球”，肉眼看不出任何规律，需要定量的结构指标。本专题按“从局部到全局、从无权到加权、从描述到比较”的顺序整理这些指标：

  • 三把基本尺子：度分布（每个节点有多少连接、这些连接如何分配）、路径长度（信息或影响要走多远）、聚集系数（邻居之间是否彼此相连），以及与之相关的连通分支；
  • 效率：用距离的倒数刻画整合与局部容错，适用于不连通网络；
  • 加权网络：强度、加权聚集系数与加权路径，以及“权重如何转换为长度”这一常被忽视的步骤；
  • 中心性家族：度、接近、介数、特征向量、Katz、PageRank、HITS 与 k 核，各自隐含不同的“流动”假设；
  • 随机网络：Erdős–Rényi（ER）模型的度分布、最大与最小度、四个演化区间与临界现象、平均距离的对数律。

有了尺子还需要一个参照物，否则无法判断一个数值是“大”还是“小”。ER 随机网络就是最基本的参照物，即零模型。把真实网络与 ER 网络比较，会得到两个“反常”：聚集系数远高于随机预期，度分布的尾巴远比泊松分布长。这两个反常正是小世界与无标度网络模型要解释的对象；介于全局与局部之间的社团尺度在社团结构与社区发现中讨论；度–度相关（同配性）与富人俱乐部等高阶统计在度相关性与网络结构的高阶统计中讨论。

本专题的定义与 Barabási《Network Science》第 2–3 章、Newman《Networks》“Measures and metrics”一章以及 Brain Connectivity Toolbox（BCT）的指标文档保持一致；符号约定：NN 为节点数，MM 为边数，AA 为邻接矩阵。有向网络中 Aij=1A_{ij}=1 表示存在边 i→ji\to j。

Contents知识页面

01度、平均度与密度度（degree）：节点 连接的边数， 。有向网络区分入度 和出度 ；加权网络中把边权相加得到强度（strength） （见加权网络的指标）。 由“每条边贡献两个度”（握手定理 ）…02度分布度分布（degree distribution） ：随机选一个节点，其度恰为 的概率。若 个节点的度为 ，则 。 度分布刻画了“连接是如何在节点之间分配的”。两类典型形状： - 均…03路径、距离与最短路径算法路径与最短路径 路径（path）是一串节点，相邻节点之间都有边相连；路径包含的边数称为路径长度。两个节点之间的距离（distance） 是它们之间最短路径的长度，也叫测地距离（ge…04连通分支与巨连通分支无向网络中，彼此可达的节点构成一个连通分支（connected component）。真实网络往往包含一个规模远大于其他分支的巨连通分支（giant component）以及许多小…05聚集系数局部聚集系数 “我的两个朋友之间是否也是朋友？”这个问题用聚集系数（clustering coefficient）来量化。 局部聚集系数：节点 的 个邻居之间实际存在的边数 ，与最…06全局效率与局部效率定义 Latora 与 Marchiori（2001）把“效率”定义为距离的倒数：两点越近，交换信息越“高效”；不可达时效率为 0。 全局效率（global efficiency）…07加权网络的指标生物医学网络大多带权：功能连接的相关系数、纤维束的条数或各向异性分数、共表达强度、STRING 的置信分数。二值化会丢失信息，并引入阈值选择问题；直接在加权网络上定义指标是另一条路…08中心性：度、接近与介数“哪个节点最重要？”没有唯一答案。中心性（centrality）是一族把节点按某种“重要性”排序的指标，每一种都对应一个关于网络上“流动什么、怎样流动”的隐含模型。本页介绍基于局部…09谱类中心性：特征向量、Katz、PageRank 与 HITS度中心性只数一步邻居。一个自然的推广是：被重要节点连接的节点更重要。这一递归思想把中心性写成邻接矩阵的特征向量或线性方程的解，统称谱类中心性。它们的共同数学基础是： 计数长度为 的…10k 核分解与核数k 核（k-core；Seidman 1983）：图中所有节点度都不小于 的极大子图。节点的核数（coreness，或 k-shell 指数） 是包含它的最大 k 核的 值；核数恰…11中心性的选择与解释一张对照表 指标 衡量什么 隐含的流动假设 计算代价 适用场景 --- --- --- --- --- 度 / 强度 直接连接数 / 强度 一步接触 几乎所有场合的基线；稠密加权网…12ER 随机网络模型定义 Erdős–Rényi 随机网络： 模型中， 个节点的每一对以概率 独立连边； 模型中，从所有可能的边中均匀随机地选出 条。 很大时两者性质相同。（ 也常归于 Gilbe…13ER 网络的演化与相变设想从 个孤立节点出发，不断随机加边（ 从 0 增大）。直觉上最大分支应该平滑长大；实际上它在 处突然“出现”。这是 Erdős 与 Rényi（1960）最著名的发现。 四个区间…14小世界性与平均距离推导： 从一个节点出发，在稀疏、局部近似为树的网络中：1 步可达约 个节点，2 步约 个， 步以内总共 可达节点数不能超过 。令 ，得 这个估计严格说是“搜索覆盖全网所需的步数”，…15真实网络与随机网络的比较以 2006 年微软即时通信网络为例（Leskovec 与 Horvitz 2008 的分析，约 1.8 亿用户、13 亿条边，两人有过对话即连边）： 指标 真实网络 同规模 ER…16数学推导与算法平均度与密度 由握手定理 立即得到 。无向简单图最多有 条边，故 。 ER 网络度分布的泊松极限 节点 的度是 次独立伯努利试验（成功概率 ）的成功次数，故 。令 固定、 ，对固定…17研究前沿与开放问题- 零模型的选择。ER 网络只保持节点数与边数。保持度序列、空间嵌入、模块结构等性质的零模型更严格，但不同零模型可能得出不同结论。对于一个具体的生物网络，什么才是“公平”的比较对象…18生物医学应用脑网络中的三把尺子。 在脑网络研究中，节点通常是按脑图谱划分的几十到几百个脑区。度高的脑区被称为枢纽脑区，常位于楔前叶、后扣带回、额顶联合皮层等；聚集系数和局部效率刻画局部“功能分…19适用范围与常见误用1. 误区：平均度相同的两个网络结构相似。→ 正解：平均度只是度分布的一阶矩，均匀分布与重尾分布可以有同样的平均度，但结构和功能（如鲁棒性、传播阈值）截然不同。 2. 误区：平均聚…

VIDEO讲解视频

三把尺子和一个参照物：度、路径、聚集系数与随机网络4 分 9 秒
文字稿

大家好，这一期我们来学习描述网络结构的基本指标。一张上万个节点的网络画出来只是一团毛线，我们需要用数字来描述它。

第一把尺子是度和度分布，看连接是怎样分配到各个节点上的。第二把尺子是路径长度，看信息从一个节点走到另一个节点要几步。第三把尺子是聚集系数，看一个节点的邻居之间是否彼此相连。最后我们需要一个参照物，那就是随机网络，用来判断数值是大是小。

先看度分布，也就是随机抽一个节点，它的度等于某个值的概率。左边这种分布集中在平均值附近，几乎所有节点的连接数都差不多。右边这种分布尾巴拖得很长，多数节点连接很少，少数枢纽连接极多。我们把前者叫做均匀分布，后者叫做重尾分布。两个网络平均度完全一样，结构却可能截然不同，所以要看完整的分布。比如两个平均度都是8的蛋白网络，一个人人均等，另一个却有几百度的枢纽。

再看路径，两个节点之间的距离，就是连接它们的最短路径包含的边数。怎么求距离呢？我们从源点出发，做广度优先搜索。第一步找到所有邻居，标为距离1，第二步找到邻居的邻居，标为距离2。就像水波一样一层一层向外扩散，直到所有节点都被标记。它的计算量和节点数加边数成正比，在稀疏网络上非常快。所有距离的最大值叫做直径，所有距离的平均值叫做平均路径长度。

第三把尺子是聚集系数，我们选中一个节点，看它的邻居。邻居之间实际存在的边，除以邻居之间最多可能有的边，就是局部聚集系数。每一条邻居之间的边，都和中心节点组成一个三角形。所以聚集系数衡量的，其实是网络里三角形有多丰富。

有了尺子，还需要一个参照物，这就是 Erdős 和 Rényi 的随机网络。规则很简单，每一对节点都以同样的概率独立地连一条边。在随机网络里，聚集系数约等于连边概率，网络越大就越接近0。大家看，连边概率很小时，网络是一堆零散的小碎片。当平均度超过1，一个包含大量节点的巨连通分支突然出现。这种突然的转变叫做相变，后面讲传播和鲁棒性时还会遇到它。

随机网络的路径很短，只随节点数的对数增长，这一点和真实网络一致。但随机网络的聚集系数很低，真实网络往往高出好几个数量级。随机网络的度分布集中，没有枢纽，而真实网络常常存在枢纽。

在脑网络中，聚集系数反映局部分工，路径长度反映全脑整合。要注意，功能网络需要先选阈值，阈值一变，度和聚集系数都会跟着变。在蛋白网络中，热门基因被研究得多，测到的连接也多，度会被抬高。

小结一下，度分布告诉我们连接是怎样在节点之间分配的。路径长度告诉我们信息在网络中传递有多快。聚集系数告诉我们网络的局部有多抱团。随机网络是零模型，真实网络偏离它的地方，才是值得解释的结构。

请打开页面上的随机网络演示，拖动连边概率，看巨连通分支何时出现。然后在代码示例中自己写一遍广度优先搜索。下一期，我们来看小世界和无标度这两个模型怎样解释这些反常。

INTERACTIVE交互可视化

CODE计算实现

15 个完整可运行的 Python 示例，每个都给出代码、输出图和解读；可在浏览器中直接运行，或下载 Jupyter Notebook · Python 脚本。

度、平均度、密度与度分布用广度优先搜索（BFS）求最短路径距离局部聚集系数、平均聚集系数与传递性全局效率与局部效率加权网络的强度、加权聚集系数与加权最短路径中心性家族在同一网络上的比较用 Brandes 算法手工计算介数中心性特征向量、Katz、PageRank 与 HITS 的幂迭代实现k 核分解（逐层剥离）ER 网络的最大度与最小度（自然截断）ER 随机网络中巨连通分支的涌现ER 网络演化的四个区间临界点处的分支大小分布 p_s ~ s^{-3/2}ER 网络平均距离随 N 的对数增长真实网络与同规模 ER 网络的比较

Papers论文精读

研究论文脑网络与连接组网络基础理论▶ 视频在投稿件 · 2026

共同接收者中的突触组织预测输入神经元之间的连接

Synaptic organization in shared receivers predicts connectivity between input neurons
Zhang X

在两个成年果蝇连接组中，相连输入源的突触在共同接收神经元上靠得更近，这种空间信息可帮助预测未见过的输入神经元之间的连接。

相关专题：脑连接组：结构与功能连接 网络结构指标与随机图 生物分子网络与拓扑特征

References核心文献

Erdős & Rényi 1960：On the evolution of random graphs

  • 出处：Publications of the Mathematical Institute of the Hungarian Academy of Sciences 5: 17–61。（原刊无 DOI，可在网上找到公开的重排版）论文精读：Erdős 1960
  • 背景：图论此前主要研究具体的、确定的图。Erdős 与 Rényi 系统研究了“随机地加边，图会如何演化”。
  • 核心发现：随着边数增加，图的许多性质（是否含有某种子图、是否存在大连通分支、是否连通）会在某个临界边数附近突然出现，即阈值现象；巨连通分支在平均度为 1 时出现。
  • 阅读提示：这是一篇纯数学论文，不必逐条读证明。重点读引言和关于“巨分支”出现的部分，体会“相变”这一思想，网络上的传播与免疫（传播阈值）和网络鲁棒性、渗流与级联失效都会再次用到它。
  • 思考题：为什么巨连通分支恰好在平均度等于 1 时出现？试用“沿着边向外探索，每一步平均能找到几个新节点”的思路解释。

Freeman 1977：A set of measures of centrality based on betweenness

  • 出处：Sociometry 40: 35–41。DOI：10.2307/3033543。论文精读：Freeman 1977
  • 背景：社会网络分析中，“中心”的直觉含义有多种，此前的指标多基于度或距离。
  • 核心内容：提出以“处在多少对节点的最短路径之间”度量节点对交流的控制力，即介数中心性，并给出网络层面的中心化指标。次年的 Freeman（1978, Social Networks）进一步把度、接近、介数三类中心性放在统一框架下比较。
  • 阅读提示：注意介数隐含的假设——交流沿最短路径进行、各条最短路径等可能。思考它在 PPI、调控网络和功能连接网络中是否成立。

Rubinov & Sporns 2010：Complex network measures of brain connectivity: uses and interpretations

  • 出处：NeuroImage 52: 1059–1069。DOI：10.1016/j.neuroimage.2009.10.003。论文精读：Rubinov 2010
  • 背景：图论指标在脑影像研究中快速普及，但不同研究使用的定义、计算方法和解释各不相同。
  • 核心内容：把脑网络指标分为功能分离（聚集系数、局部效率、模块度）、功能整合（路径长度、全局效率）、中心性与枢纽、网络韧性等几类，给出二值/加权、有向/无向情形下的统一定义，并讨论各指标的神经生物学解释与局限。
  • 阅读提示：文末附有各指标数学定义的汇总，可作为“速查表”；特别留意作者对“路径长度是否真正反映信息传递”的谨慎态度。Rubinov 与 Sporns 提供的 Brain Connectivity Toolbox 是脑网络分析的常用工具。
  • 思考题：在功能连接网络中，两个脑区之间的“最短路径”有没有明确的生理含义？如果没有，平均路径长度还能解释为“整合能力”吗？

其他引用文献

  • Achard S, Salvador R, Whitcher B, Suckling J, Bullmore E (2006). A resilient, low-frequency, small-world human brain functional network with highly connected association cortical hubs. Journal of Neuroscience 26: 63–72. DOI：10.1523/JNEUROSCI.3874-05.2006
  • Barrat A, Barthélemy M, Pastor-Satorras R, Vespignani A (2004). The architecture of complex weighted networks. PNAS 101: 3747–3752. DOI：10.1073/pnas.0400087101
  • Batagelj V, Zaversnik M (2003). An O(m) algorithm for cores decomposition of networks. arXiv:cs/0310049
  • Boldi P, Vigna S (2014). Axioms for centrality. Internet Mathematics 10: 222–262. DOI：10.1080/15427951.2013.865686
  • Bonacich P (1987). Power and centrality: a family of measures. American Journal of Sociology 92: 1170–1182. DOI：10.1086/228631
  • Borgatti SP (2005). Centrality and network flow. Social Networks 27: 55–71. DOI：10.1016/j.socnet.2004.11.008
  • Brandes U (2001). A faster algorithm for betweenness centrality. Journal of Mathematical Sociology 25: 163–177. DOI：10.1080/0022250X.2001.9990249
  • Bringmann LF, Elmer T, Epskamp S, et al. (2019). What do centrality measures measure in psychological networks? Journal of Abnormal Psychology 128: 892–903. DOI：10.1037/abn0000446
  • Brin S, Page L (1998). The anatomy of a large-scale hypertextual Web search engine. Computer Networks and ISDN Systems 30: 107–117. DOI：10.1016/S0169-7552(98)00110-X
  • Dorogovtsev SN, Goltsev AV, Mendes JFF (2006). k-core organization of complex networks. Physical Review Letters 96: 040601. DOI：10.1103/PhysRevLett.96.040601
  • Estrada E, Rodríguez-Velázquez JA (2005). Subgraph centrality in complex networks. Physical Review E 71: 056103. DOI：10.1103/PhysRevE.71.056103
  • Freeman LC (1978). Centrality in social networks: conceptual clarification. Social Networks 1: 215–239. DOI：10.1016/0378-8733(78)90021-7
  • Fronczak A, Fronczak P, Hołyst JA (2004). Average path length in random networks. Physical Review E 70: 056110. DOI：10.1103/PhysRevE.70.056110
  • Katz L (1953). A new status index derived from sociometric analysis. Psychometrika 18: 39–43. DOI：10.1007/BF02289026
  • Kitsak M, Gallos LK, Havlin S, et al. (2010). Identification of influential spreaders in complex networks. Nature Physics 6: 888–893. DOI：10.1038/nphys1746
  • Kleinberg JM (1999). Authoritative sources in a hyperlinked environment. Journal of the ACM 46: 604–632. DOI：10.1145/324133.324140
  • Latora V, Marchiori M (2001). Efficient behavior of small-world networks. Physical Review Letters 87: 198701. DOI：10.1103/PhysRevLett.87.198701
  • Martin T, Zhang X, Newman MEJ (2014). Localization and centrality in networks. Physical Review E 90: 052808. DOI：10.1103/PhysRevE.90.052808
  • Morrison JL, Breitling R, Higham DJ, Gilbert DR (2005). GeneRank: using search engine technology for the analysis of microarray experiments. BMC Bioinformatics 6: 233. DOI：10.1186/1471-2105-6-233
  • Newman MEJ, Strogatz SH, Watts DJ (2001). Random graphs with arbitrary degree distributions and their applications. Physical Review E 64: 026118. DOI：10.1103/PhysRevE.64.026118
  • Onnela JP, Saramäki J, Kertész J, Kaski K (2005). Intensity and coherence of motifs in weighted complex networks. Physical Review E 71: 065103. DOI：10.1103/PhysRevE.71.065103
  • Opsahl T, Agneessens F, Skvoretz J (2010). Node centrality in weighted networks: generalizing degree and shortest paths. Social Networks 32: 245–251. DOI：10.1016/j.socnet.2010.03.006
  • Pittel B, Spencer J, Wormald N (1996). Sudden emergence of a giant k-core in a random graph. Journal of Combinatorial Theory, Series B 67: 111–151. DOI：10.1006/jctb.1996.0036
  • Seidman SB (1983). Network structure and minimum degree. Social Networks 5: 269–287. DOI：10.1016/0378-8733(83)90028-X
  • van den Heuvel MP, Sporns O (2013). Network hubs in the human brain. Trends in Cognitive Sciences 17: 683–696. DOI：10.1016/j.tics.2013.09.012
  • Wuchty S, Almaas E (2005). Peeling the yeast protein network. Proteomics 5: 444–449. DOI：10.1002/pmic.200400962
  • Yu H, Kim PM, Sprecher E, Trifonov V, Gerstein M (2007). The importance of bottlenecks in protein networks: correlation with gene essentiality and expression dynamics. PLoS Computational Biology 3: e59. DOI：10.1371/journal.pcbi.0030059

Data & tools相关数据与软件

软件/工具包Brain Connectivity Toolbox（MATLAB）脑网络图论指标的标准 MATLAB 函数集。软件/工具包bctpy（Brain Connectivity Toolbox for Python）Brain Connectivity Toolbox 的 Python 移植版。软件/工具包GRETNA基于 MATLAB 的图形界面脑网络构建与图论分析工具箱。软件/工具包NetworkXPython 中最常用的通用网络创建、分析与可视化库。软件/工具包igraph以 C 为核心、提供 R 与 Python 接口的高效网络分析库。数据集SNAP 大型网络数据集斯坦福大学整理的大型真实网络数据集合。数据集WormWiring线虫神经连接组数据与可视化网站。

Further延伸资源

类型 资源 说明
教材 Barabási, Network Science, Ch. 2 Graph Theory（networksciencebook.com/chapter/2） 度、邻接矩阵、加权与二分网络、路径与距离、BFS、连通性、聚集系数；进阶专题 2.A 讨论全局聚集系数
教材 Barabási, Network Science, Ch. 3 Random Networks（networksciencebook.com/chapter/3） 随机网络模型、泊松度分布、演化的四个区间、小世界、聚集系数；进阶专题 3.A–3.G 给出泊松推导、最大最小度、巨分支、分支大小、完全连通区、相变与小世界修正
教材 Newman, Networks（第 2 版, Oxford University Press, 2018），Ch. 7 Measures and metrics；随机图各章 中心性家族（度、特征向量、Katz、PageRank、枢纽与权威、接近、介数）、群组与 k 核、传递性与相似性的系统处理
工具 Brain Connectivity Toolbox（sites.google.com/site/bctnet） 二值/加权、有向/无向的聚集、效率、路径、中心性、核结构函数清单，含权重–长度转换的说明；Python 版为 bctpy
软件 NetworkX 算法文档（networkx.org） 查阅 clustering、transitivity、global_efficiency、betweenness_centrality、pagerank、core_number 等函数的精确定义与约定
公开课 Stanford CS224W（主页） 英文公开课；“网络性质与随机图模型”部分与本专题对应，视频在 YouTube（需境外网络）
综述 Newman 2003, “The structure and function of complex networks”, SIAM Review（DOI） 网络指标与模型的经典长综述，第 III 节（真实网络的性质）与本专题对应；论文精读见 Newman 2003
脑网络 Rubinov & Sporns 2010, NeuroImage（DOI） 脑网络指标的定义与解释，可作为脑网络分析的工具书
经典数据 Zachary 1977, 空手道俱乐部网络（DOI） 本专题代码示例所用数据的原始论文；NetworkX 内置为 karate_club_graph()

Open questions开放问题

  1. 你的研究数据如果构建成网络（例如基因共表达网络或脑功能网络），你认为它的度分布更可能是均匀型还是重尾型？如果是重尾型，度最高的那些节点在生物学上可能是什么？你会如何排除“研究偏倚”等技术性原因？
  2. 本专题把 ER 随机网络作为零模型。对于你的数据，ER 网络是否是一个“公平”的比较对象？你认为还应该保持哪些性质不变（例如度序列、空间距离、模块结构），比较才有意义？
  3. 在你的网络里，“重要节点”应该按哪种流动模型来定义？如果度、介数和 PageRank 给出的前十名不一致，你会怎样决定报告哪一个，又如何检验它的生物学意义？
  4. 一个功能连接网络的平均度为 10、节点数为 300。按 ER 理论它处于哪个演化区间？如果实际网络有若干孤立脑区，这更可能反映拓扑规律，还是阈值选择与测量噪声？