Network FoundationsDegree correlations and higher-order structure

度相关性与网络结构的高阶统计

度分布之外，谁和谁相连：联合度分布、同配与异配、结构截断、富人俱乐部、聚集谱与 k-核，以及它们对传播、渗流、同步与控制的影响。

知识页面: 13 页
阅读: 约 29 分钟
讲解视频: 1 段
代码示例: 9 个

度相关同配性异配性联合度分布邻居平均度度相关系数结构截断富人俱乐部聚集谱层次模块性k-核分解度保持随机化

度分布 $p_k$ 只告诉我们“每个节点有多少条边”，没有说明“这些边连向谁”。两张度序列完全相同的网络，可以一张让枢纽彼此相连，另一张让枢纽各自统领一群低度节点。区分这两种连接方式的统计量就是度相关性（degree correlations）：一条边两端节点的度是否相互依赖。枢纽倾向于连接枢纽的网络称为同配（assortative），枢纽倾向于连接低度节点的称为异配（disassortative），两者都不明显的称为中性（neutral）。

度相关是“度分布之后的下一层结构”。它最早由 Pastor-Satorras、Vázquez 与 Vespignani（2001, PRL）在互联网拓扑中通过邻居平均度函数 $k_{nn}(k)$ 提出；Maslov 与 Sneppen（2002, Science）用保度随机化比较了酵母蛋白质相互作用网络与转录调控网络中枢纽之间的连接；Newman（2002, PRL；2003, PRE）引入了度相关系数 $r$ ，并系统比较了社会、技术和生物网络。一个反复出现的经验规律是：社会网络多为同配，蛋白质相互作用、代谢、神经元等生物网络多为异配。但后续工作也表明，生物网络的异配有相当一部分可以由重尾度分布和“简单图不允许重边”这一约束解释，这就是结构截断问题。

本专题从两点相关推进到更高阶的结构统计：

联合度分布与条件度分布：度相关的完整描述；
邻居平均度函数 $k_{nn}(k)$ 与度相关系数 $r$ ：两种压缩描述及其局限；
结构截断与结构性异配、度保持随机化检验：怎样判断观测到的相关是否超出了度序列本身的约束；
生成具有度相关的网络：模型与重连算法；
更高阶的统计：富人俱乐部、聚集谱与层次模块性、k-核分解；
度相关对网络过程的影响：渗流、鲁棒性、传播、同步与可控性。

它建立在网络结构指标与随机图（度、度分布、聚集系数）和小世界与无标度网络模型（配置模型、BA 模型）之上；零模型的一般原理见网络构建与统计验证。本专题的全部代码示例见代码示例。

Contents知识页面

01联合度分布与条件度分布从“随机抽一个节点”到“随机抽一条边” 度相关的所有定义都以边为抽样单位。在无向网络中随机选一条边，再随机选它的一端，到达度为的节点的概率不是，而是因为度为的节点有条边可…02邻居平均度函数与相关指数定义节点的邻居平均度（average nearest-neighbor degree）。度相关函数：所有度为的节点的的平均， - 中性网络：，与无关（水平线）； …03度相关系数 r定义度相关系数（degree assortativity coefficient，Newman, 2002）：一条边两端节点度的 Pearson 相关系数，；同配，中性， …04结构截断与结构性异配简单图与度分布的冲突在配置模型中，度为与的两个节点之间的期望边数约为当两个节点的度都很大时，这个期望值可以超过 1。例如、的网络中，两个度为 55 与 46 的枢纽之间…05度保持随机化检验两种随机化度相关的检验问题是：观测到的或是否超出了“同一度序列的随机网络”能产生的范围。Barabási 书第 7 章区分两种保度随机化： - R-S（保持简单图）：双边交换…06生成具有度相关的网络常见模型的度相关模型度相关说明 --- --- --- ER 随机图中性没有枢纽，也没有结构截断问题配置模型（允许重边与自环）中性枢纽之间的“多余”边以重边形式存在…07富人俱乐部系数及其归一化定义富人俱乐部系数（rich-club coefficient; Zhou & Mondragón, 2004, IEEE Communications Letters）：度大于…08聚集谱 C(k) 与层次模块性三点相关是两点相关。更高一阶的统计是：度为的节点的两个邻居之间是否相连。聚集谱（clustering spectrum）是度为的节点局部聚集系数的平均。它对应条件概率与“…09k-核分解定义 -核（ -core; Seidman, 1983, Social Networks）：反复删除度小于的节点后剩下的最大子图；其中每个节点在子图内的度都至少为。核数（co…10度相关对网络过程的影响度相关改变的不只是一个描述性数字，它会改变发生在网络上的过程。下面的结论多来自模型网络，在真实生物网络中往往与模块、空间约束等因素同时存在。巨连通分支与鲁棒性 Newman（20…11数学推导与算法A. 细致平衡与中性网络的由的两种写法及，得细致平衡。把按加权求和：这一恒等式对任何相关结构都成立。若随发散，则必有某些的发散，矩阵的最大特征值也无界，…12生物医学应用蛋白质相互作用网络：枢纽回避及其解释酵母蛋白质相互作用网络是异配网络的典型例子：Newman（2003）报告；Maslov 与 Sneppen（2002）发现高度蛋白之间的连接…13适用范围与常见误用1. 把负的直接解释为“枢纽回避”的生物学机制。重尾度分布的简单图本身就偏异配；必须与同一度序列的保度随机网络（R-S）比较，并报告零分布。 2. 跨网络比较的绝对值。依赖…

VIDEO讲解视频

谁和谁相连：度相关、富人俱乐部与 k-核6 分 30 秒

文字稿

大家好，这一期我们讨论度分布之后的下一层结构，度相关性。度分布告诉我们每个节点有多少条边，却没有说这些边连向谁。而谁和谁相连，会改变网络的鲁棒性、传播阈值和可同步性。

第一个问题，枢纽倾向于连接其他枢纽，还是连接低度节点。第二个问题，观测到的度相关，能不能仅用度序列本身来解释。第三个问题，度相关会怎样改变发生在网络上的过程。

先看度分布，左边是随机网络，右边是无标度网络。右边的网络有少数度特别大的枢纽，分布有一条长长的尾巴。但度序列相同的网络，可以让枢纽彼此相连，也可以让枢纽各自统领一群低度节点。枢纽倾向于连接枢纽的网络，称为同配网络。枢纽倾向于连接低度节点的称为异配，两者都不明显的称为中性。

度相关的定义都以边为抽样单位，沿一条边到达的往往是高度节点。所以平均而言，你的朋友的朋友数比你的多，这就是 Feld 描述的友谊悖论。第一种压缩是邻居平均度函数，把度为k的节点的邻居度取平均。中性网络里它是一条水平线，同配网络随k上升，异配网络随k下降。第二种压缩是 Newman 在2002年提出的度相关系数r。它就是一条边两端节点度的相关系数，取值在负1到1之间。星形图里中心只连叶子，是最极端的异配结构，r等于负1。

Newman 在2003年报告，物理学合作网络的r是0.363，明显同配。酵母蛋白质相互作用网络是负0.156，大肠杆菌代谢网络是负0.240。Newman 和 Park 提出，社会网络的同配性可以部分来自社团结构。但r不是与规模无关的相关强度，重尾的大网络里它会被压向0。删去一两个枢纽也可能明显改变r，所以比较时还要报告秩相关和整条曲线。

为什么生物网络常常是异配的？一个重要原因来自简单图的约束。在配置模型里，两个度都很大的节点之间，期望边数可能超过1。比如300个节点、450条边的网络里，度为55和46的两个枢纽应有约2.8条边。简单图不允许重边，多出的边只能连到低度节点上，网络就显得异配。这叫结构性异配，度指数在2到3之间时，最大度超过结构截断，冲突必然出现。代码示例中，同一度序列保留重边时r约为负0.01，变成简单图后约为负0.14。

检验的办法是反复交换两条边的端点，每个节点的度保持不变。关键是与同样是简单图的随机网络比较，看相关能否被度序列解释。报告时要给出零分布的均值和标准差，以及z分数和经验p值。保度随机化也会打乱模块和空间位置，差异可能来自这些被打乱的结构。Maslov 和 Sneppen 发现，酵母相互作用网络中枢纽之间的连接被系统性压低。但按 Barabási 书中的分析，蛋白相互作用网络和代谢网络的异配主要是结构性的。而合作网络等社会网络的同配性，不能被度分布解释。

富人俱乐部系数问的是，度大于k的那些节点之间连得有多密。但即使完全随机，高度节点也更容易彼此相连，这个系数会随k上升。所以 Colizza 等人提出要除以保度随机网络的值，显著大于1才算证据。他们发现科学合作网络有富人俱乐部，蛋白质相互作用网络则低于1。van den Heuvel 和 Sporns 在21名健康被试的结构脑网络中发现了富人俱乐部。富人俱乐部和同配性不是一回事，人脑结构网络常常r小于0，却仍有富人俱乐部。

再往上一阶，我们问一个节点的两个邻居之间是否相连。画面上的节点i有5个邻居，邻居之间最多可以有10条边。红色三角形每出现一个，就说明有一对邻居彼此相连。把度为k的所有节点的聚集系数取平均，就得到聚集谱。这里最终有3对邻居相连，3除以10，局部聚集系数是0.3。Ravasz 等人分析了43种生物的代谢网络，发现聚集谱随度按幂律下降。这提示层次模块性，但它只是必要条件，度相关和空间约束也能让聚集谱下降。

k核分解反复删除度小于k的节点，剩下的最大子图就是k核。Kitsak 等人发现，单个起点的传播范围，由核数比由度预测得更好。度相关也会改变渗流，同配网络在稀疏时就能更早形成巨连通分支。异配网络在删除枢纽时更脆弱，每个枢纽会带走一批只连向它的节点。在流行病模型里，同配让高度节点形成相互感染的储库，通常降低阈值。不过只要度的二阶矩发散，无论同配还是异配，无标度网络的阈值都趋于0。

好，小结一下，度相关描述的是一条边两端节点的度是否相互依赖。度相关系数依赖网络规模和少数枢纽，比较时要同时报告曲线和秩相关。重尾度分布加上简单图约束本身就会产生异配，要与保度随机网络比较。富人俱乐部系数必须用随机网络归一化，而且节点数不能太少。聚集谱和k核都是有用的高阶统计，但都需要合适的零模型来解读。建议在代码示例里亲手重连一张网络，看看同配和异配怎样改变它的行为。

INTERACTIVE交互可视化

CODE计算实现

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

按定义手算度相关系数 r 与 k_nn(k)，并与 NetworkX 对照

结构截断与“伪异配”——简单图约束本身就会产生负的 r

度保持随机化检验——观测到的 r 是否超出度序列本身能解释的范围

富人俱乐部系数 phi(k) 及其保度归一化 rho(k)

聚集谱 C(k) 与层次模块网络（Ravasz–Barabási 型确定性模型）

k-核分解——手写剥离算法并与 NetworkX 对照，比较核数与度

度相关如何改变巨连通分支、传播阈值与可同步性

阈值化相关网络中的同配性——模块大小如何制造正的 r

References核心文献

度相关的定义与测量

Pastor-Satorras R, Vázquez A, Vespignani A. Dynamical and correlation properties of the Internet. Physical Review Letters, 2001, 87: 258701. DOI: 10.1103/PhysRevLett.87.258701
Vázquez A, Pastor-Satorras R, Vespignani A. Large-scale topological and dynamical properties of the Internet. Physical Review E, 2002, 65: 066130. DOI: 10.1103/PhysRevE.65.066130
Newman MEJ. Assortative mixing in networks. Physical Review Letters, 2002, 89: 208701. DOI: 10.1103/PhysRevLett.89.208701
Newman MEJ. Mixing patterns in networks. Physical Review E, 2003, 67: 026126. DOI: 10.1103/PhysRevE.67.026126
Newman MEJ, Park J. Why social networks are different from other types of networks. Physical Review E, 2003, 68: 036122. DOI: 10.1103/PhysRevE.68.036122
Foster JG, Foster DV, Grassberger P, Paczuski M. Edge direction and the structure of networks. PNAS, 2010, 107: 10815–10820. DOI: 10.1073/pnas.0912671107
Litvak N, van der Hofstad R. Uncovering disassortativity in large scale-free networks. Physical Review E, 2013, 87: 022801. DOI: 10.1103/PhysRevE.87.022801
Barrat A, Barthélemy M, Pastor-Satorras R, Vespignani A. The architecture of complex weighted networks. PNAS, 2004, 101: 3747–3752. DOI: 10.1073/pnas.0400087101
Feld SL. Why your friends have more friends than you do. American Journal of Sociology, 1991, 96: 1464–1477. DOI: 10.1086/229693

结构截断、零模型与生成模型

Maslov S, Sneppen K. Specificity and stability in topology of protein networks. Science, 2002, 296: 910–913. DOI: 10.1126/science.1065103
Boguñá M, Pastor-Satorras R, Vespignani A. Cut-offs and finite size effects in scale-free networks. European Physical Journal B, 2004, 38: 205–209. DOI: 10.1140/epjb/e2004-00038-8
Park J, Newman MEJ. Origin of degree correlations in the Internet and other networks. Physical Review E, 2003, 68: 026112. DOI: 10.1103/PhysRevE.68.026112
Johnson S, Torres JJ, Marro J, Muñoz MA. Entropic origin of disassortativity in complex networks. Physical Review Letters, 2010, 104: 108702. DOI: 10.1103/PhysRevLett.104.108702
Boguñá M, Pastor-Satorras R. Class of correlated random networks with hidden variables. Physical Review E, 2003, 68: 036112. DOI: 10.1103/PhysRevE.68.036112
Barrat A, Pastor-Satorras R. Rate equation approach for correlations in growing network models. Physical Review E, 2005, 71: 036127. DOI: 10.1103/PhysRevE.71.036127
Xulvi-Brunet R, Sokolov IM. Reshuffling scale-free networks: from random to assortative. Physical Review E, 2004, 70: 066102. DOI: 10.1103/PhysRevE.70.066102
Mahadevan P, Krioukov D, Fall K, Vahdat A. Systematic topology analysis and generation using degree correlations. Proceedings of ACM SIGCOMM, 2006: 135–146. DOI: 10.1145/1159913.1159930
Orsini C, Dankulov MM, Colomer-de-Simón P, et al. Quantifying randomness in real networks. Nature Communications, 2015, 6: 8627. DOI: 10.1038/ncomms9627
Fosdick BK, Larremore DB, Nishimura J, Ugander J. Configuring random graph models with fixed degree sequences. SIAM Review, 2018, 60: 315–355. DOI: 10.1137/16M1087175

富人俱乐部、聚集谱与 k-核

Zhou S, Mondragón RJ. The rich-club phenomenon in the Internet topology. IEEE Communications Letters, 2004, 8: 180–182. DOI: 10.1109/LCOMM.2004.823426
Colizza V, Flammini A, Serrano MA, Vespignani A. Detecting rich-club ordering in complex networks. Nature Physics, 2006, 2: 110–115. DOI: 10.1038/nphys209
Opsahl T, Colizza V, Panzarasa P, Ramasco JJ. Prominence and control: the weighted rich-club effect. Physical Review Letters, 2008, 101: 168702. DOI: 10.1103/PhysRevLett.101.168702
Ravasz E, Somera AL, Mongru DA, Oltvai ZN, Barabási AL. Hierarchical organization of modularity in metabolic networks. Science, 2002, 297: 1551–1555. DOI: 10.1126/science.1073374
Ravasz E, Barabási AL. Hierarchical organization in complex networks. Physical Review E, 2003, 67: 026112. DOI: 10.1103/PhysRevE.67.026112
Soffer SN, Vázquez A. Network clustering coefficient without degree-correlation biases. Physical Review E, 2005, 71: 057101. DOI: 10.1103/PhysRevE.71.057101
Seidman SB. Network structure and minimum degree. Social Networks, 1983, 5: 269–287. DOI: 10.1016/0378-8733(83)90028-X
Batagelj V, Zaveršnik M. Fast algorithms for determining (generalized) core groups in social networks. Advances in Data Analysis and Classification, 2011, 5: 129–145. DOI: 10.1007/s11634-010-0079-y
Dorogovtsev SN, Goltsev AV, Mendes JFF. k-core organization of complex networks. Physical Review Letters, 2006, 96: 040601. DOI: 10.1103/PhysRevLett.96.040601
Kitsak M, Gallos LK, Havlin S, et al. Identification of influential spreaders in complex networks. Nature Physics, 2010, 6: 888–893. DOI: 10.1038/nphys1746

对网络过程的影响

Boguñá M, Pastor-Satorras R. Epidemic spreading in correlated complex networks. Physical Review E, 2002, 66: 047104. DOI: 10.1103/PhysRevE.66.047104
Boguñá M, Pastor-Satorras R, Vespignani A. Absence of epidemic threshold in scale-free networks with degree correlations. Physical Review Letters, 2003, 90: 028701. DOI: 10.1103/PhysRevLett.90.028701
Vázquez A, Moreno Y. Resilience to damage of graphs with degree correlations. Physical Review E, 2003, 67: 015101. DOI: 10.1103/PhysRevE.67.015101
di Bernardo M, Garofalo F, Sorrentino F. Effects of degree correlation on the synchronization of networks of oscillators. International Journal of Bifurcation and Chaos, 2007, 17: 3499–3506. DOI: 10.1142/S0218127407019263
Pósfai M, Liu YY, Slotine JJ, Barabási AL. Effect of correlations on network controllability. Scientific Reports, 2013, 3: 1067. DOI: 10.1038/srep01067

生物医学应用

Jeong H, Mason SP, Barabási AL, Oltvai ZN. Lethality and centrality in protein networks. Nature, 2001, 411: 41–42. DOI: 10.1038/35075138
Han JDJ, Bertin N, Hao T, et al. Evidence for dynamically organized modularity in the yeast protein–protein interaction network. Nature, 2004, 430: 88–93. DOI: 10.1038/nature02555
Wuchty S, Almaas E. Peeling the yeast protein network. Proteomics, 2005, 5: 444–449. DOI: 10.1002/pmic.200400962
Piraveenan M, Prokopenko M, Zomaya A. Assortative mixing in directed biological networks. IEEE/ACM Transactions on Computational Biology and Bioinformatics, 2012, 9: 66–78. DOI: 10.1109/TCBB.2010.80
Hagmann P, Cammoun L, Gigandet X, et al. Mapping the structural core of human cerebral cortex. PLoS Biology, 2008, 6: e159. DOI: 10.1371/journal.pbio.0060159
van den Heuvel MP, Sporns O. Rich-club organization of the human connectome. Journal of Neuroscience, 2011, 31: 15775–15786. DOI: 10.1523/JNEUROSCI.3539-11.2011
van den Heuvel MP, Kahn RS, Goñi J, Sporns O. High-cost, high-capacity backbone for global brain communication. PNAS, 2012, 109: 11372–11377. DOI: 10.1073/pnas.1203593109
Harriger L, van den Heuvel MP, Sporns O. Rich club organization of macaque cerebral cortex and its role in network communication. PLoS ONE, 2012, 7: e46497. DOI: 10.1371/journal.pone.0046497
Towlson EK, Vértes PE, Ahnert SE, Schafer WR, Bullmore ET. The rich club of the C. elegans neuronal connectome. Journal of Neuroscience, 2013, 33: 6380–6387. DOI: 10.1523/JNEUROSCI.3784-12.2013
van den Heuvel MP, Sporns O, Collin G, et al. Abnormal rich club organization and functional brain dynamics in schizophrenia. JAMA Psychiatry, 2013, 70: 783. DOI: 10.1001/jamapsychiatry.2013.1328

Further延伸资源

类型	资源	说明
教材	Barabási, Network Science, Ch. 7 Degree Correlations，networksciencebook.com/chapter/7（CC BY-NC-SA 2.0）	$e_{ij}$ 、 $k_{nn}(k)$ 、相关指数、结构截断、R-S/R-M 随机化、Xulvi-Brunet–Sokolov 算法；进阶专题 7.A（ $r$ 与 $\mu$ 的关系）与 7.B（结构截断推导）
教材	Newman, Networks（第 2 版, Oxford University Press, 2018），同配混合与度相关相关章节	类别与标量同配系数、相关网络上的渗流与传播的生成函数处理
综述	Newman 2003, SIAM Review（精读见 Newman 2003）	同配混合在复杂网络结构统计中的位置
工具	NetworkX：`degree_assortativity_coefficient`、`average_degree_connectivity`、`rich_club_coefficient`、`core_number`、`double_edge_swap`、`attribute_assortativity_coefficient`	本专题代码示例全部基于这些函数，并给出与定义的手算对照
工具	Brain Connectivity Toolbox / bctpy	加权与有向的同配系数、富人俱乐部系数（`rich_club_bu`、`rich_club_wu` 等）、核分解与多种零模型；指标说明见 Rubinov & Sporns（2010, NeuroImage，DOI: 10.1016/j.neuroimage.2009.10.003）
工具	igraph（R / Python）	`assortativity_degree`、`knn`、`coreness`，适合大规模网络
数据	BioGRID	可按实验类型（双杂交、亲和纯化）筛选相互作用，比较不同证据类型对度相关的影响

Open questions开放问题

对你熟悉的一个生物网络，度相关有多少可以由度序列和简单图约束解释（R-S 随机化），多少需要额外的机制？如果再控制模块结构或空间距离，剩余的相关还存在吗？
相互作用组的研究偏倚使被研究得多的蛋白既度高又更可能互相有记录。你预期这种偏倚使观测的度相关偏向同配还是异配？可以用系统性筛选数据（如人类二元相互作用参考图谱）做什么样的对照？
富人俱乐部的归一化依赖零模型：保度、保持空间距离、保持权重分布的零模型可能给出不同结论。对一个具体的脑网络问题，你会预先规定哪一种，为什么？
两点相关（ $k_{nn}$ ）、三点相关（ $C(k)$ ）和更高阶统计（ $k$ -核、dK 序列）之间是什么关系？在什么条件下，掌握到 2K 或 2.5K 就足以预测传播阈值或可控性，什么时候还需要更高阶的结构？
在患者与对照的网络比较中，如果患者组 $r$ 或 $\rho_{\text{ran}}(k)$ 不同，怎样区分“度相关结构改变”与“度分布、网络密度或模块大小改变”的间接效应？