做了几年的图算法和图神经网络我发现一个特别有意思的现象节点的度degree这个图论里最简单的基础概念反而是生产环境中让我栽过最多跟头的点。群里大家聊到degree第一反应都是不就是邻居数量吗但真到了写代码、做特征、跑模型、查异常的时候各种关于有向还是无向、权重算不算、自环计几次、稀疏矩阵怎么处理的问题全冒出来了。这篇我会把degree从定义、计算、图分布一直到GNN和网络健壮性的应用完整过一遍也把我在实际项目里踩过的坑一并整理出来。无论你是刚学图论的学生、正在做社交网络分析的分析师还是准备上手Graph Neural Network的工程师这篇应该都能帮你在度这个最小的单元上少走点弯路。1. 度的定义拆解它到底在数什么先别急着往下跳我建议把度的定义本身摆到桌面上仔细看一遍。因为这个概念在不同场景下有不同的变体每个变体背后对应着完全不同的工程实现和业务含义。如果不先把定义这层关系理清楚后面在代码里十有八九要出错。1.1 无向图里的度最简单的邻居计数在无向图 G (V, E) 中一个顶点 v 的度记作 deg(v)定义是与 v 直接相连的边的条数。从邻居的角度理解更直观它等于 v 在一跳范围内能到达的节点数量。这个定义有两点容易模糊的地方。第一自环self-loop算不算一条边。在很多标准图论教材里一条自环会被计数两次因为一条自环在顶点的关联矩阵里对应两列。但是在实际工程库中行为并不统一NetworkX 的G.degree()对自环会返回 2如果 graph 对象里以(u, u)形式存在会按两次计而 Spark GraphX 默认则把自环算作 1。这个差异在节点不多、自环不多的时候看不出来一旦在超大规模图中做统计误差就会实实在在影响后面的归一化和模型训练。第二多重边multi-edge算几条。如果两个节点之间存在多条边大多数简单图的上下文里会将度合并为 1但实践中比如电商的用户-商品交互图用户和一个商品可能下单了 5 次这时用多重边建模时每条交互记录都应该计入累积度。我在做购物行为网络特征时就发现用简单度还是多重度做特征购买力强的用户群体完全不一样。1.2 有向图里的入度、出度信息流向的账本到了有向图度被劈成两个方向入度in-degree和出度out-degree。入度是从其他节点指向该节点的边的数量出度是从该节点指向其他节点的边的数量。也就是说对任意有向图的顶点 v[ deg_{in}(v) deg_{out}(v) deg(v) ]如果算上自环自环既计入入度也计入出度。千万不要小看这个方向分裂。我做过一个网页链接网络的分析某个网站的入度极高、出度极低意味着大量外部资源引用它而不外跳这种节点的语义是权威信息源反向的出度高、入度低则更像是分发型节点或者搜索引擎爬虫。在异常检测场景里一个有高入度但零出度的账号往往对应垃圾邮件接收器或者粉丝聚集地而高出度低入度的账号更像是刷消息机器人。所以只算一个合并后的度等于把方向信息全丢了。1.3 带权图与强度当每条边不是等量时当边上带有权重 w通常定义节点强度strengths(v) 来代替原始度[ s(v) \sum_{u \in N(v)} w_{uv} ]如果所有权重都是 1强度等于度但现实中边权很少都是 1。拿社交网络举例A 和 B 互发了 10 条私信A 和 C 只发了 1 条如果只统计度A 对 B 和 C 一视同仁如果统计强度A 跟 B 的交互强度是 C 的 10 倍。这个差异在很多真实场景里足够改变结论。在航空网络中一个机场连接了 50 条航线度50但其中 45 条是每日一班、5 条是每周一班强度就能更精准地反映机场实际吞吐能力。在交易网络里一个账户转出 100 万到另一个账户和转出 1 块钱到 1 万个账户强度也完全不同。我把度在不同图类型下的各种表现整理成一张表图类型指标名称核心计数对象自环处理常见库行为典型业务含义无向简单图degree邻居节点数NetworkX 计 2多数自研按 1社交好友数、处理器直连数量有向简单图in-degree / out-degree指向/指出的边数单独各计 1粉丝数 / 关注数、引用 / 外链数带权无向图strength邻接边的权重求和权重加一次消息总量、资金流动总量带权有向图in-strength / out-strength方向 权重累计各方向按权重加一次收入 / 支出、上行 / 下行流量实际用的时候建议在特征命名和表结构里就带上in_deg、out_deg、weighted_in_strength这类后缀否则建模做到后面连自己都容易搞混。2. 从数据表示到代码算一个度有哪些选择理论上算度很简单但在工程里算一个度的时间和空间开销完全取决于你用什么数据结构存图。我见过有人拿邻接矩阵去算 1 亿节点的图跑了两小时直接内存爆炸也见过有人用 Spark 聚合边表几分钟就把度分布算完了。这部分的差距比大多数人想象中大得多。2.1 三种常用图存储结构下的计算复杂度目前主流存图方式有四种邻接矩阵、邻接表、边列表Edge List、CSR/CSC 压缩稀疏矩阵。不同结构下算度的复杂度差异非常明显。邻接矩阵用 A[i][j] 表示 i 到 j 是否有边算某个点的度直接对行求和单点复杂度 O(n)全部节点度数都算一遍复杂度 O(n²)空间复杂度 O(n²)。对于一万个节点这还好对于百万级节点那就是一万亿个单元完全不现实。所以邻接矩阵只适合小规模稠密图。邻接表为每个顶点维护一个邻居列表。算度数时直接 len(adj[v])单点 O(1)全图 O(m)其中 m 是边数空间 O(n m)。这是绝大多数内存图算法库的标准做法。边列表则把每条边存成一行(src, dst)要算度最常见的做法是分组聚合——先对 src 做 group by 得到出度再对 dst 做 group by 得到入度。单机可以用字典分布式可以用 MapReduce/Spark/SQL 的 GROUP BY。复杂度同样是 O(m)不需要额外维护索引但每次查询都需要扫描边表。CSRCompressed Sparse Row是工业级图计算系统的标准格式它把邻居数组连续存储通过indptr数组记录每个节点的起始偏移量。算每个节点的度数只需要一次diff(indptr)就行复杂度 O(n)——这是所有方式里最漂亮的。我把它们做个对比存储结构单点度数复杂度全图度数复杂度空间复杂度适用场景备注邻接矩阵O(n)O(n²)O(n²)稠密小图大图空间爆炸邻接表O(1)O(n m)O(n m)内存内单机图非压缩缓存友好度一般边列表O(m)需扫描O(m)聚合一次O(m)分布式海量数据聚合后得到全局度数CSRO(1)O(n)O(n m)工业/图计算引擎不可变、查询极快顺带提一句CSR 格式下如果要更新度数——插入一条新边——通常成本很高因为它需要重排邻居数组。所以如果你的图是动态更新的要仔细衡量查询性能和更新性能的取舍。2.2 Python 实现从邻接表到稀疏矩阵的一行代码提到 Python 里的度计算绕不开 NetworkX 和 NumPy/SciPy。NetworkX 适合中小规模最多几十万节点级别实验代码非常直观import networkx as nx G nx.Graph() G.add_edges_from([ (1, 2), (1, 3), (2, 4), (3, 4), (4, 5), (5, 1) ]) # 单个节点度数 print(G.degree(1)) # 输出 3邻居是 2, 3, 5 # 所有节点度数 degrees dict(G.degree()) print(degrees) # {1: 3, 2: 2, 3: 2, 4: 3, 5: 2}如果图太大放不进 NetworkX 的内存模型用 scipy.sparse 处理 CSR 格式是更好的方案比如常见的 CSC/CSR 稀疏矩阵存图统计度数只需要一句代码import scipy.sparse as sp # 假设 adj 是一个 scipy.sparse.csr_matrix形状 n x n degrees np.diff(adj.indptr) # 无向图矩阵的每行非零个数说下原理在 CSR 矩阵里indptr数组的第 i 个元素和第 i1 个元素之间的差值正好是第 i 行的非零元素数量也就是该节点的度数。这比遍历所有行要快得多。遇到有向图要同时算出度、入度就分别取行和列out_deg np.diff(adj.indptr) in_deg np.diff(adj.T.indptr) # 转置后行非零个数 原矩阵列非零个数如果你用的是 PyTorch Geometric 或 DGL 这类图神经网络库度数往往直接内置在消息传递里了。比如 GCN 需要归一化的邻接矩阵或者度矩阵 D^{-1/2} A D^{-1/2}PyG 里用torch_geometric.utils.degree(index, num_nodes)一行拿到from torch_geometric.utils import degree # edge_index shape: [2, num_edges] # 无向图出度直接统计merge both directions deg degree(edge_index[0], num_nodesN)DGL 就更本土化了g.in_degrees()、g.out_degrees()直接给出张量在做 GNN 的邻接归一化时非常方便。2.3 SQL 与分布式环境下的度数统计生产环境里的图规模通常超过单机内存边表躺在数据仓库里。这时候度数计算本质上就是一个 GROUP BY 问题——我从边表里统计每个端点出现的次数。假设有一张边表edges(src, dst)无向图的度数等价于SELECT node, COUNT(*) AS degree FROM ( SELECT src AS node FROM edges UNION ALL SELECT dst AS node FROM edges ) t GROUP BY node;有向图则拆开-- 出度 SELECT src, COUNT(*) AS out_deg FROM edges GROUP BY src; -- 入度 SELECT dst, COUNT(*) AS in_deg FROM edges GROUP BY dst;在 Spark 环境里写 Scala 或者 PySpark 的方式几乎一样用flatMap把每条边拆成两个端点然后reduceByKey相加。Spark GraphX 则更有现成 APIimport org.apache.spark.graphx.GraphLoader val graph GraphLoader.edgeListFile(sc, hdfs://.../edges.txt) val degrees graph.degrees // VertexRDD[Int]这里面要注意的点是如果边表有方向性你用graph.degrees拿到的是无向度graph.inDegrees和graph.outDegrees才是方向版本。之前有同事在度特征里混用了两种口径最后模型线上效果一直上不去查了好久才定位到是这里的口径问题。3. 度分布一眼看穿网络底层逻辑单个节点的度意义有限但整张图所有节点的度构成一个分布之后它几乎能告诉你这张图的所有关键结构信息是社交网络还是交通网络是均匀连接还是少数枢纽节点主导网络面对故障和攻击时的反应是完全不一样的两套剧本。3.1 度分布函数与真实网络的幂律尾巴度分布 P(k) 定义为随机选中一个节点其度恰好等于 k 的概率。计算方法很简单统计每个度值 k 对应的节点数 n_k然后除以总节点数 N[ P(k) \frac{n_k}{N} ]现实世界里两类图拥有完全不同的度分布。一类是随机图Erdős–Rényi 模型P(k) 大致呈泊松分布绝大多数节点度数在均值附近没有特别突出的超级节点。这种图在现实中有对应吗部分传感器网络、同质化程度特别高的区域人际网络在某些局部会稍微接近但整体来看现实世界很少存在纯粹的泊松度分布网络。另一类是无标度网络scale-free network它的度分布服从幂律 P(k) ∝ k^{-γ}大多数节点的度很小极少数节点度数特别大形成很长的尾巴。我实际看过的社交网络关注关系、论文引用网络、互联网路由器拓扑、金融交易网络几乎都是这种形态。幂律最反直觉的地方是平均度这个指标会严重欺骗你。比如一个 1000 节点的网络平均度算出来可能只有 2.3可里面有 3 个节点度是 200 多。你说这个网络平均每节点 2.3 个连接对吧但实际感觉完全是另一个世界。所以在看度分布的时候一定要画 log-log 图横纵轴都取对数如果大致是一条直线就说明存在幂律关系。而且 log-log 图上那些偏离直线很远的右上角点恰恰是你最需要关注的 hub 节点。3.2 无标度网络里 Hubs 的作用为什么少数节点撑起整个网络无标度网络里面那些少数高连接节点通常被称为 hubs。它们的出现并非偶然而是富者愈富机制优先连接偏好的产物新加入的节点更倾向于连接那些已经拥有很多连接的节点。这个机制放在社交网络上就是新用户注册后平台会给他推荐那些已经几百万粉丝的大 V于是大 V 用户数的增长速度远快于普通用户。最终少数 hubs 承担了不成比例的连接量整张网络的整体性强依赖于它们。从网络健壮性的角度看这是一个非常经典的双刃剑。面对随机故障比如随机关掉 10% 的节点无标度网络表现得极其顽强——因为绝大多数节点度小、作用有限删掉它们对整体连通性几乎没影响。但面对蓄意攻击比如专挑度最高的节点依次删网络会迅速碎裂。我把两种情况下的关键差异列成表格场景随机图泊松分布无标度网络幂律分布随机移除 10% 节点连通性下滑可能分裂几乎不受影响蓄意攻击最高度节点连通性缓慢下降但整体仍可工作快速崩溃成碎片关键原因度分布均匀每节点承担的角色差不多少数 hubs 承担着桥梁枢纽核心角色以前做电力网络相关分析时这个性质是评估抗毁性的基本出发点。电网节点的度数线路数同样不是均匀的重视枢纽变电站的保护策略本质上就是在利用蓄意攻击风险的镜像逻辑。3.3 用度分布做冷启动异常检测实际业务场景里度分布还有一个特别实用的价值异常检测。在我做过的一个社交网络反欺诈项目里首先对全量用户做了入度分布。正常用户入度被关注数落在低度区间虚假账号则有截然不同的形态一种僵尸粉丝群每个机器号入度非常小甚至为 0出度却奇高另一种水军大号用软件刷了几十万粉丝入度严重偏离主分布直接落在 log-log 图的右上角尾巴之外。这两种情况都不需要训练模型单纯从度分布的离群点就能识别。还有一类异常是孤岛 超大连通分量的组合。正常的交易图中绝大多数节点应该能连入一个巨大的主连通分量如果你发现大量中等度数的节点形成了互不相通的碎片往往意味着刷单团伙在自建闭环网络。这种网络内部节点度数差距不大但和主网络的连接度几乎为 0度分布图形会呈现双峰特征——主群体一个峰值刷单群体另一个峰值——非常有识别度。因此在我经手的任何图数据项目里做数据探索的第一步永远是算一遍度分布画 log-log 图看看有没有离群的节点。这个习惯救过我很多次与其直接上复杂模型不如先让度告诉你图中有什么异常。4. 度中心性、PageRank 和图神经网络度在哪里被反复使用度这个指标不只是用来描述和探索的很多经典算法和现代图模型都在更深层面反复消耗它。理解这些算法里度所扮演的角色有助于你在实际调参和实现时做出更合理的决策而不是停留在调用现成函数的黑盒层面。4.1 度中心性最直观的影响力度量度中心性degree centrality是所有中心性度量里最简单的一种它把节点的度除以理论上最大可能的度n-1[ C_D(v) \frac{deg(v)}{n-1} ]除以 n-1 是为了归一化到 [0, 1] 区间方便在不同规模的图之间比较。比如一个 100 节点的图中度为 50 的节点度中心性是 50/99 ≈ 0.505同样的度放 1000 节点图中中心性就只有约 0.05。这个指标衡量的是节点在局部范围内能直接影响多少其他节点。它不关心这些邻居质量如何、在网络里的位置如何。在选举社区、寻找意见领袖这类场景中度中心性常作为 baseline 特征虽然粗糙但非常稳健。但也正因为只数邻居数量它忽略了邻居本身的地位——一个认识 100 个普通人的节点和一个认识 10 个行业大佬的节点度中心性会认为前者更重要这在很多场景里并不准确。真正需要考虑邻居质量的算法就是 PageRank 这类递归方法。4.2 PageRank度的高阶递归版本PageRank 的核心思想是一个节点的重要性不仅取决于谁指向它还取决于指向它的人自身的重要性。公式简化版[ PR(v) (1 - d) d \sum_{u \in N_{in}(v)} \frac{PR(u)}{deg_{out}(u)} ]注意看这个式子分母是出度。在随机游走视角下一个投票节点 u 把自己的权值除以出度均匀分配给所有它指向的节点。所以一个节点被赋予的 PageRank等于所有入邻居对他们自己出度的摊薄投票之和。这里的度出现了两次第一次是入度决定谁给我投票第二次是出度决定我的每一票被稀释成多少。这样就让有很多高质量入链的节点胜过有很多低质量入链的节点。动手做过 PageRank 的人应该都知道在超大图上实现的关键就是迭代地让每个节点把自己的 PR 值按出度均分给邻居然后不断收敛。这里的度和迭代更新天然绑定在一起。如果图里的节点出度为 0页面没有任何外链这些节点通常被称为 dangling nodes如果不做处理就会吸收掉所有 PR 值需要做特殊重分配。我记得第一次实现 PageRank 时忽视了 dangling nodes结果迭代几十轮后 PR 值全部跑到几个出度为 0 的节点上前几次收敛曲线完全没法看。4.3 图神经网络消息传递中度的归一化作用到了 GNN 时代度变得更加核心。图神经网络的基本操作是消息传递message passing每个节点从邻居那里聚合特征然后更新自己的表示。几乎所有经典 GCN 的层定义里度都直接出现在归一化项中。以单层 GCN 为例[ H^{(l1)} \sigma\left( \hat{D}^{-1/2} \hat{A} \hat{D}^{-1/2} H^{(l)} W^{(l)} \right) ]其中 \hat{A} A I 是加了自环的邻接矩阵\hat{D} 是对应的度矩阵。这里的 \hat{D}^{-1/2} 做的是对称归一化。为什么需要它逻辑很简单如果不做归一化一个高度数节点聚合了大量邻居特征它的 embedding 更新幅度远大于低度数节点数值尺度差异会严重影响训练稳定性。而对称归一化的做法是把特征张量在传播前先除以源的出度平方根、传播后再除以目标入度平方根这样能让不同度数节点的特征分布保持在相近的尺度上。我训练 GCN 的时候观察到一个规律当图中存在严重幂律分布——极少数 hub 连了巨量节点而大量节点只有 1~2 个邻居——即便做了归一化hub 节点依然容易出现特征过度平滑具体表现为它们最终学到的 embedding 在向量空间中向中心区域收敛彼此之间难以区分。这是因为消息传递迭代多次后hub 节点和它们的邻居们的特征被反复混合特征趋于一致。这种过平滑现象是 GNN 加深网络层数时的一个核心障碍度的分布是理解它的第一把钥匙。还有更深一层在 Link Prediction 任务里很多启发式方法如 CN、AA、RA本质上也是在利用路径两端的度。比如资源分配指标 RA 定义为两端节点的邻居集合中中间节点的 1/度 之和。这里度大就意味着这个公共邻居和太多人都有连接那么它对某一条特定边关系的贡献权重应该被稀释。换句话说公共服务节点的度直接决定了它对每条边的资源分配密度。如果完全不考虑度两个节点仅仅因为共同认识一个万人迷就被判断成强关联那就太不靠谱了。5. 实战踩坑我整理的几个和度有关的经典问题最后把我在实际项目里遇到过的、和度直接相关的几个坑总结出来。这些坑在教科书里通常不会提到但工程里几乎人人都撞过。5.1 自环算几次不同库行为不一致这个前面提过NetworkX 无向图自环 degree 计数为 2Spark GraphX 的degrees对自环默认算 1。如果你的图存在大量自环比如用户给自己点赞、系统内部节点给自己发心跳两边统计结果会系统性差出一个常数倍数。建议在数据管道的入口就明确自环的清洗策略要么全部剔除大多数业务图可以直接剔除要么全部保留并规定计数口径。给个具体例子我处理过一份用户行为数据里面有大约 3% 的自环边主要是用户收藏自己的内容。单看 3% 好像不大但因为这些自环大多集中在几个活跃度高的大号上这几个大号的度数直接被放大了将近 40%对后续的 PageRank 排序造成了相当大的扰动。5.2 有向图度数口径不统一统计有向图时默认很多库给的是出度入度合并的degree比如 igraph 里degree(modeall)。但业务里影响力或者活跃度往往只跟你关心的方向有关。如果你把入度和出度混在一个特征里拿去训练模型模型很难学出关注数少但发消息多这类用户画像。我的建议是任何有向图特征至少拆成三个独立字段in_deg、out_deg、total_deg不要嫌字段多。还有一个踩过的细节在 PyTorch Geometric 统计无向图度数时如果边表是通过to_undirected()把有向图转成的无向图每条原始边都会变出两条反向边直接在扩增后的edge_index上统计会把度数翻倍。应该用原始边表统计或者在转无向图之前先统计好再通过对称化后的数据结构做消息传递。5.3 幂律长尾下的数值稳定性度数分布是幂律时数据里会出现极端大值和大量小值并存的情况。如果你直接用原始度数作为特征喂给机器学习模型尤其是 LR 这种线性模型那少数超大度数节点会主导整个特征的尺度模型很难学习其他维度的信号。常用的处理手段有两个一是做对数变换取 log(1 degree)把长尾压平二是做归一化用 (degree - min) / (max - min) 缩放到 [0, 1]但要注意如果 max 是极端离群值大部分节点都会被压到接近 0效果不如对数变换。更稳妥的做法是先可视化度分布、初步用箱线图看上下四分位数再决定用哪种变换。我在做社交关系特征时几乎无脑选择 log1p 变换效果一直比较稳。另一个数值稳定的隐患是计算1 / degree时节点度为零会导致除以零。这在很多图算法里是真实存在的一个孤立节点没有任何边分母就是 0。务必备好 protectionsafe_deg torch.where(deg 0, deg, torch.ones_like(deg))。5.4 动态图中度的延迟更新问题如果图是动态变化的边的增删非常频繁那么度作为一个静态快照指标可能严重滞后。比如社交平台里用户取关非常快如果你昨晚计算的特征显示某用户有 100 万粉丝但今天早上他已经掉到 80 万那么基于旧特征训练的模型很可能高估该用户的影响力。解决办法可以落地三种以 T1 的批处理方式重算度数适用于业务容忍一天延迟的场景用时间衰减因子维护一个滚动度对近期新增边赋予更高权重在流式计算环节增量更新每次新增一条边时对源节点和目标节点的度数各做一次原子加 1有向图只更新对应方向需要注意自环不能重复累加。我之前在实时推荐系统里用第三种方式用 Redis 存每个节点的入度/出度每次事件进来做一个INCR一度数秒级延迟就能看到度数的更新。但这里也有坑Redis 的 key 数量等于节点数量百万级节点没问题上亿节点就要考虑分片策略了。5.5 从度再往前一步二级邻居与效率权衡最后讲一个我常用来给团队的建议——当你想计算二阶度比如朋友的度之和或共同邻居数时要非常小心复杂度。直接枚举一个高度数节点的二阶邻居可能瞬间产生几十万甚至上千万次中间结果。如果你的图里存在超级 hubs做一个 naive 的二阶邻居枚举就能把集群资源耗干。更稳妥的做法是先裁剪掉度超过某个阈值比如 500的超级节点或者在计算邻居交集中利用稀疏矩阵的乘法代替显式枚举。在处理社交网络的共同好友指标时用A A.T这种矩阵乘法的稀疏版本往往比显式遍历快几个数量级。但也要记住矩阵乘法产生的中间矩阵可能并不稀疏两者之间需要根据图的密度做实际测试和取舍。这个取舍没有标准答案只能靠实验数据说话。说到底度是图分析里最基础的一道门槛但它延伸出的处理和优化问题其实贯穿了图存储、图计算、网络科学和图机器学习的所有环节。把每一个细节都想透往往能让下游模型和算法的效果提升一个台阶。 节点的度：从基础定义到图神经网络应用的完全指南
做了几年的图算法和图神经网络我发现一个特别有意思的现象节点的度degree这个图论里最简单的基础概念反而是生产环境中让我栽过最多跟头的点。群里大家聊到degree第一反应都是不就是邻居数量吗但真到了写代码、做特征、跑模型、查异常的时候各种关于有向还是无向、权重算不算、自环计几次、稀疏矩阵怎么处理的问题全冒出来了。这篇我会把degree从定义、计算、图分布一直到GNN和网络健壮性的应用完整过一遍也把我在实际项目里踩过的坑一并整理出来。无论你是刚学图论的学生、正在做社交网络分析的分析师还是准备上手Graph Neural Network的工程师这篇应该都能帮你在度这个最小的单元上少走点弯路。1. 度的定义拆解它到底在数什么先别急着往下跳我建议把度的定义本身摆到桌面上仔细看一遍。因为这个概念在不同场景下有不同的变体每个变体背后对应着完全不同的工程实现和业务含义。如果不先把定义这层关系理清楚后面在代码里十有八九要出错。1.1 无向图里的度最简单的邻居计数在无向图 G (V, E) 中一个顶点 v 的度记作 deg(v)定义是与 v 直接相连的边的条数。从邻居的角度理解更直观它等于 v 在一跳范围内能到达的节点数量。这个定义有两点容易模糊的地方。第一自环self-loop算不算一条边。在很多标准图论教材里一条自环会被计数两次因为一条自环在顶点的关联矩阵里对应两列。但是在实际工程库中行为并不统一NetworkX 的G.degree()对自环会返回 2如果 graph 对象里以(u, u)形式存在会按两次计而 Spark GraphX 默认则把自环算作 1。这个差异在节点不多、自环不多的时候看不出来一旦在超大规模图中做统计误差就会实实在在影响后面的归一化和模型训练。第二多重边multi-edge算几条。如果两个节点之间存在多条边大多数简单图的上下文里会将度合并为 1但实践中比如电商的用户-商品交互图用户和一个商品可能下单了 5 次这时用多重边建模时每条交互记录都应该计入累积度。我在做购物行为网络特征时就发现用简单度还是多重度做特征购买力强的用户群体完全不一样。1.2 有向图里的入度、出度信息流向的账本到了有向图度被劈成两个方向入度in-degree和出度out-degree。入度是从其他节点指向该节点的边的数量出度是从该节点指向其他节点的边的数量。也就是说对任意有向图的顶点 v[ deg_{in}(v) deg_{out}(v) deg(v) ]如果算上自环自环既计入入度也计入出度。千万不要小看这个方向分裂。我做过一个网页链接网络的分析某个网站的入度极高、出度极低意味着大量外部资源引用它而不外跳这种节点的语义是权威信息源反向的出度高、入度低则更像是分发型节点或者搜索引擎爬虫。在异常检测场景里一个有高入度但零出度的账号往往对应垃圾邮件接收器或者粉丝聚集地而高出度低入度的账号更像是刷消息机器人。所以只算一个合并后的度等于把方向信息全丢了。1.3 带权图与强度当每条边不是等量时当边上带有权重 w通常定义节点强度strengths(v) 来代替原始度[ s(v) \sum_{u \in N(v)} w_{uv} ]如果所有权重都是 1强度等于度但现实中边权很少都是 1。拿社交网络举例A 和 B 互发了 10 条私信A 和 C 只发了 1 条如果只统计度A 对 B 和 C 一视同仁如果统计强度A 跟 B 的交互强度是 C 的 10 倍。这个差异在很多真实场景里足够改变结论。在航空网络中一个机场连接了 50 条航线度50但其中 45 条是每日一班、5 条是每周一班强度就能更精准地反映机场实际吞吐能力。在交易网络里一个账户转出 100 万到另一个账户和转出 1 块钱到 1 万个账户强度也完全不同。我把度在不同图类型下的各种表现整理成一张表图类型指标名称核心计数对象自环处理常见库行为典型业务含义无向简单图degree邻居节点数NetworkX 计 2多数自研按 1社交好友数、处理器直连数量有向简单图in-degree / out-degree指向/指出的边数单独各计 1粉丝数 / 关注数、引用 / 外链数带权无向图strength邻接边的权重求和权重加一次消息总量、资金流动总量带权有向图in-strength / out-strength方向 权重累计各方向按权重加一次收入 / 支出、上行 / 下行流量实际用的时候建议在特征命名和表结构里就带上in_deg、out_deg、weighted_in_strength这类后缀否则建模做到后面连自己都容易搞混。2. 从数据表示到代码算一个度有哪些选择理论上算度很简单但在工程里算一个度的时间和空间开销完全取决于你用什么数据结构存图。我见过有人拿邻接矩阵去算 1 亿节点的图跑了两小时直接内存爆炸也见过有人用 Spark 聚合边表几分钟就把度分布算完了。这部分的差距比大多数人想象中大得多。2.1 三种常用图存储结构下的计算复杂度目前主流存图方式有四种邻接矩阵、邻接表、边列表Edge List、CSR/CSC 压缩稀疏矩阵。不同结构下算度的复杂度差异非常明显。邻接矩阵用 A[i][j] 表示 i 到 j 是否有边算某个点的度直接对行求和单点复杂度 O(n)全部节点度数都算一遍复杂度 O(n²)空间复杂度 O(n²)。对于一万个节点这还好对于百万级节点那就是一万亿个单元完全不现实。所以邻接矩阵只适合小规模稠密图。邻接表为每个顶点维护一个邻居列表。算度数时直接 len(adj[v])单点 O(1)全图 O(m)其中 m 是边数空间 O(n m)。这是绝大多数内存图算法库的标准做法。边列表则把每条边存成一行(src, dst)要算度最常见的做法是分组聚合——先对 src 做 group by 得到出度再对 dst 做 group by 得到入度。单机可以用字典分布式可以用 MapReduce/Spark/SQL 的 GROUP BY。复杂度同样是 O(m)不需要额外维护索引但每次查询都需要扫描边表。CSRCompressed Sparse Row是工业级图计算系统的标准格式它把邻居数组连续存储通过indptr数组记录每个节点的起始偏移量。算每个节点的度数只需要一次diff(indptr)就行复杂度 O(n)——这是所有方式里最漂亮的。我把它们做个对比存储结构单点度数复杂度全图度数复杂度空间复杂度适用场景备注邻接矩阵O(n)O(n²)O(n²)稠密小图大图空间爆炸邻接表O(1)O(n m)O(n m)内存内单机图非压缩缓存友好度一般边列表O(m)需扫描O(m)聚合一次O(m)分布式海量数据聚合后得到全局度数CSRO(1)O(n)O(n m)工业/图计算引擎不可变、查询极快顺带提一句CSR 格式下如果要更新度数——插入一条新边——通常成本很高因为它需要重排邻居数组。所以如果你的图是动态更新的要仔细衡量查询性能和更新性能的取舍。2.2 Python 实现从邻接表到稀疏矩阵的一行代码提到 Python 里的度计算绕不开 NetworkX 和 NumPy/SciPy。NetworkX 适合中小规模最多几十万节点级别实验代码非常直观import networkx as nx G nx.Graph() G.add_edges_from([ (1, 2), (1, 3), (2, 4), (3, 4), (4, 5), (5, 1) ]) # 单个节点度数 print(G.degree(1)) # 输出 3邻居是 2, 3, 5 # 所有节点度数 degrees dict(G.degree()) print(degrees) # {1: 3, 2: 2, 3: 2, 4: 3, 5: 2}如果图太大放不进 NetworkX 的内存模型用 scipy.sparse 处理 CSR 格式是更好的方案比如常见的 CSC/CSR 稀疏矩阵存图统计度数只需要一句代码import scipy.sparse as sp # 假设 adj 是一个 scipy.sparse.csr_matrix形状 n x n degrees np.diff(adj.indptr) # 无向图矩阵的每行非零个数说下原理在 CSR 矩阵里indptr数组的第 i 个元素和第 i1 个元素之间的差值正好是第 i 行的非零元素数量也就是该节点的度数。这比遍历所有行要快得多。遇到有向图要同时算出度、入度就分别取行和列out_deg np.diff(adj.indptr) in_deg np.diff(adj.T.indptr) # 转置后行非零个数 原矩阵列非零个数如果你用的是 PyTorch Geometric 或 DGL 这类图神经网络库度数往往直接内置在消息传递里了。比如 GCN 需要归一化的邻接矩阵或者度矩阵 D^{-1/2} A D^{-1/2}PyG 里用torch_geometric.utils.degree(index, num_nodes)一行拿到from torch_geometric.utils import degree # edge_index shape: [2, num_edges] # 无向图出度直接统计merge both directions deg degree(edge_index[0], num_nodesN)DGL 就更本土化了g.in_degrees()、g.out_degrees()直接给出张量在做 GNN 的邻接归一化时非常方便。2.3 SQL 与分布式环境下的度数统计生产环境里的图规模通常超过单机内存边表躺在数据仓库里。这时候度数计算本质上就是一个 GROUP BY 问题——我从边表里统计每个端点出现的次数。假设有一张边表edges(src, dst)无向图的度数等价于SELECT node, COUNT(*) AS degree FROM ( SELECT src AS node FROM edges UNION ALL SELECT dst AS node FROM edges ) t GROUP BY node;有向图则拆开-- 出度 SELECT src, COUNT(*) AS out_deg FROM edges GROUP BY src; -- 入度 SELECT dst, COUNT(*) AS in_deg FROM edges GROUP BY dst;在 Spark 环境里写 Scala 或者 PySpark 的方式几乎一样用flatMap把每条边拆成两个端点然后reduceByKey相加。Spark GraphX 则更有现成 APIimport org.apache.spark.graphx.GraphLoader val graph GraphLoader.edgeListFile(sc, hdfs://.../edges.txt) val degrees graph.degrees // VertexRDD[Int]这里面要注意的点是如果边表有方向性你用graph.degrees拿到的是无向度graph.inDegrees和graph.outDegrees才是方向版本。之前有同事在度特征里混用了两种口径最后模型线上效果一直上不去查了好久才定位到是这里的口径问题。3. 度分布一眼看穿网络底层逻辑单个节点的度意义有限但整张图所有节点的度构成一个分布之后它几乎能告诉你这张图的所有关键结构信息是社交网络还是交通网络是均匀连接还是少数枢纽节点主导网络面对故障和攻击时的反应是完全不一样的两套剧本。3.1 度分布函数与真实网络的幂律尾巴度分布 P(k) 定义为随机选中一个节点其度恰好等于 k 的概率。计算方法很简单统计每个度值 k 对应的节点数 n_k然后除以总节点数 N[ P(k) \frac{n_k}{N} ]现实世界里两类图拥有完全不同的度分布。一类是随机图Erdős–Rényi 模型P(k) 大致呈泊松分布绝大多数节点度数在均值附近没有特别突出的超级节点。这种图在现实中有对应吗部分传感器网络、同质化程度特别高的区域人际网络在某些局部会稍微接近但整体来看现实世界很少存在纯粹的泊松度分布网络。另一类是无标度网络scale-free network它的度分布服从幂律 P(k) ∝ k^{-γ}大多数节点的度很小极少数节点度数特别大形成很长的尾巴。我实际看过的社交网络关注关系、论文引用网络、互联网路由器拓扑、金融交易网络几乎都是这种形态。幂律最反直觉的地方是平均度这个指标会严重欺骗你。比如一个 1000 节点的网络平均度算出来可能只有 2.3可里面有 3 个节点度是 200 多。你说这个网络平均每节点 2.3 个连接对吧但实际感觉完全是另一个世界。所以在看度分布的时候一定要画 log-log 图横纵轴都取对数如果大致是一条直线就说明存在幂律关系。而且 log-log 图上那些偏离直线很远的右上角点恰恰是你最需要关注的 hub 节点。3.2 无标度网络里 Hubs 的作用为什么少数节点撑起整个网络无标度网络里面那些少数高连接节点通常被称为 hubs。它们的出现并非偶然而是富者愈富机制优先连接偏好的产物新加入的节点更倾向于连接那些已经拥有很多连接的节点。这个机制放在社交网络上就是新用户注册后平台会给他推荐那些已经几百万粉丝的大 V于是大 V 用户数的增长速度远快于普通用户。最终少数 hubs 承担了不成比例的连接量整张网络的整体性强依赖于它们。从网络健壮性的角度看这是一个非常经典的双刃剑。面对随机故障比如随机关掉 10% 的节点无标度网络表现得极其顽强——因为绝大多数节点度小、作用有限删掉它们对整体连通性几乎没影响。但面对蓄意攻击比如专挑度最高的节点依次删网络会迅速碎裂。我把两种情况下的关键差异列成表格场景随机图泊松分布无标度网络幂律分布随机移除 10% 节点连通性下滑可能分裂几乎不受影响蓄意攻击最高度节点连通性缓慢下降但整体仍可工作快速崩溃成碎片关键原因度分布均匀每节点承担的角色差不多少数 hubs 承担着桥梁枢纽核心角色以前做电力网络相关分析时这个性质是评估抗毁性的基本出发点。电网节点的度数线路数同样不是均匀的重视枢纽变电站的保护策略本质上就是在利用蓄意攻击风险的镜像逻辑。3.3 用度分布做冷启动异常检测实际业务场景里度分布还有一个特别实用的价值异常检测。在我做过的一个社交网络反欺诈项目里首先对全量用户做了入度分布。正常用户入度被关注数落在低度区间虚假账号则有截然不同的形态一种僵尸粉丝群每个机器号入度非常小甚至为 0出度却奇高另一种水军大号用软件刷了几十万粉丝入度严重偏离主分布直接落在 log-log 图的右上角尾巴之外。这两种情况都不需要训练模型单纯从度分布的离群点就能识别。还有一类异常是孤岛 超大连通分量的组合。正常的交易图中绝大多数节点应该能连入一个巨大的主连通分量如果你发现大量中等度数的节点形成了互不相通的碎片往往意味着刷单团伙在自建闭环网络。这种网络内部节点度数差距不大但和主网络的连接度几乎为 0度分布图形会呈现双峰特征——主群体一个峰值刷单群体另一个峰值——非常有识别度。因此在我经手的任何图数据项目里做数据探索的第一步永远是算一遍度分布画 log-log 图看看有没有离群的节点。这个习惯救过我很多次与其直接上复杂模型不如先让度告诉你图中有什么异常。4. 度中心性、PageRank 和图神经网络度在哪里被反复使用度这个指标不只是用来描述和探索的很多经典算法和现代图模型都在更深层面反复消耗它。理解这些算法里度所扮演的角色有助于你在实际调参和实现时做出更合理的决策而不是停留在调用现成函数的黑盒层面。4.1 度中心性最直观的影响力度量度中心性degree centrality是所有中心性度量里最简单的一种它把节点的度除以理论上最大可能的度n-1[ C_D(v) \frac{deg(v)}{n-1} ]除以 n-1 是为了归一化到 [0, 1] 区间方便在不同规模的图之间比较。比如一个 100 节点的图中度为 50 的节点度中心性是 50/99 ≈ 0.505同样的度放 1000 节点图中中心性就只有约 0.05。这个指标衡量的是节点在局部范围内能直接影响多少其他节点。它不关心这些邻居质量如何、在网络里的位置如何。在选举社区、寻找意见领袖这类场景中度中心性常作为 baseline 特征虽然粗糙但非常稳健。但也正因为只数邻居数量它忽略了邻居本身的地位——一个认识 100 个普通人的节点和一个认识 10 个行业大佬的节点度中心性会认为前者更重要这在很多场景里并不准确。真正需要考虑邻居质量的算法就是 PageRank 这类递归方法。4.2 PageRank度的高阶递归版本PageRank 的核心思想是一个节点的重要性不仅取决于谁指向它还取决于指向它的人自身的重要性。公式简化版[ PR(v) (1 - d) d \sum_{u \in N_{in}(v)} \frac{PR(u)}{deg_{out}(u)} ]注意看这个式子分母是出度。在随机游走视角下一个投票节点 u 把自己的权值除以出度均匀分配给所有它指向的节点。所以一个节点被赋予的 PageRank等于所有入邻居对他们自己出度的摊薄投票之和。这里的度出现了两次第一次是入度决定谁给我投票第二次是出度决定我的每一票被稀释成多少。这样就让有很多高质量入链的节点胜过有很多低质量入链的节点。动手做过 PageRank 的人应该都知道在超大图上实现的关键就是迭代地让每个节点把自己的 PR 值按出度均分给邻居然后不断收敛。这里的度和迭代更新天然绑定在一起。如果图里的节点出度为 0页面没有任何外链这些节点通常被称为 dangling nodes如果不做处理就会吸收掉所有 PR 值需要做特殊重分配。我记得第一次实现 PageRank 时忽视了 dangling nodes结果迭代几十轮后 PR 值全部跑到几个出度为 0 的节点上前几次收敛曲线完全没法看。4.3 图神经网络消息传递中度的归一化作用到了 GNN 时代度变得更加核心。图神经网络的基本操作是消息传递message passing每个节点从邻居那里聚合特征然后更新自己的表示。几乎所有经典 GCN 的层定义里度都直接出现在归一化项中。以单层 GCN 为例[ H^{(l1)} \sigma\left( \hat{D}^{-1/2} \hat{A} \hat{D}^{-1/2} H^{(l)} W^{(l)} \right) ]其中 \hat{A} A I 是加了自环的邻接矩阵\hat{D} 是对应的度矩阵。这里的 \hat{D}^{-1/2} 做的是对称归一化。为什么需要它逻辑很简单如果不做归一化一个高度数节点聚合了大量邻居特征它的 embedding 更新幅度远大于低度数节点数值尺度差异会严重影响训练稳定性。而对称归一化的做法是把特征张量在传播前先除以源的出度平方根、传播后再除以目标入度平方根这样能让不同度数节点的特征分布保持在相近的尺度上。我训练 GCN 的时候观察到一个规律当图中存在严重幂律分布——极少数 hub 连了巨量节点而大量节点只有 1~2 个邻居——即便做了归一化hub 节点依然容易出现特征过度平滑具体表现为它们最终学到的 embedding 在向量空间中向中心区域收敛彼此之间难以区分。这是因为消息传递迭代多次后hub 节点和它们的邻居们的特征被反复混合特征趋于一致。这种过平滑现象是 GNN 加深网络层数时的一个核心障碍度的分布是理解它的第一把钥匙。还有更深一层在 Link Prediction 任务里很多启发式方法如 CN、AA、RA本质上也是在利用路径两端的度。比如资源分配指标 RA 定义为两端节点的邻居集合中中间节点的 1/度 之和。这里度大就意味着这个公共邻居和太多人都有连接那么它对某一条特定边关系的贡献权重应该被稀释。换句话说公共服务节点的度直接决定了它对每条边的资源分配密度。如果完全不考虑度两个节点仅仅因为共同认识一个万人迷就被判断成强关联那就太不靠谱了。5. 实战踩坑我整理的几个和度有关的经典问题最后把我在实际项目里遇到过的、和度直接相关的几个坑总结出来。这些坑在教科书里通常不会提到但工程里几乎人人都撞过。5.1 自环算几次不同库行为不一致这个前面提过NetworkX 无向图自环 degree 计数为 2Spark GraphX 的degrees对自环默认算 1。如果你的图存在大量自环比如用户给自己点赞、系统内部节点给自己发心跳两边统计结果会系统性差出一个常数倍数。建议在数据管道的入口就明确自环的清洗策略要么全部剔除大多数业务图可以直接剔除要么全部保留并规定计数口径。给个具体例子我处理过一份用户行为数据里面有大约 3% 的自环边主要是用户收藏自己的内容。单看 3% 好像不大但因为这些自环大多集中在几个活跃度高的大号上这几个大号的度数直接被放大了将近 40%对后续的 PageRank 排序造成了相当大的扰动。5.2 有向图度数口径不统一统计有向图时默认很多库给的是出度入度合并的degree比如 igraph 里degree(modeall)。但业务里影响力或者活跃度往往只跟你关心的方向有关。如果你把入度和出度混在一个特征里拿去训练模型模型很难学出关注数少但发消息多这类用户画像。我的建议是任何有向图特征至少拆成三个独立字段in_deg、out_deg、total_deg不要嫌字段多。还有一个踩过的细节在 PyTorch Geometric 统计无向图度数时如果边表是通过to_undirected()把有向图转成的无向图每条原始边都会变出两条反向边直接在扩增后的edge_index上统计会把度数翻倍。应该用原始边表统计或者在转无向图之前先统计好再通过对称化后的数据结构做消息传递。5.3 幂律长尾下的数值稳定性度数分布是幂律时数据里会出现极端大值和大量小值并存的情况。如果你直接用原始度数作为特征喂给机器学习模型尤其是 LR 这种线性模型那少数超大度数节点会主导整个特征的尺度模型很难学习其他维度的信号。常用的处理手段有两个一是做对数变换取 log(1 degree)把长尾压平二是做归一化用 (degree - min) / (max - min) 缩放到 [0, 1]但要注意如果 max 是极端离群值大部分节点都会被压到接近 0效果不如对数变换。更稳妥的做法是先可视化度分布、初步用箱线图看上下四分位数再决定用哪种变换。我在做社交关系特征时几乎无脑选择 log1p 变换效果一直比较稳。另一个数值稳定的隐患是计算1 / degree时节点度为零会导致除以零。这在很多图算法里是真实存在的一个孤立节点没有任何边分母就是 0。务必备好 protectionsafe_deg torch.where(deg 0, deg, torch.ones_like(deg))。5.4 动态图中度的延迟更新问题如果图是动态变化的边的增删非常频繁那么度作为一个静态快照指标可能严重滞后。比如社交平台里用户取关非常快如果你昨晚计算的特征显示某用户有 100 万粉丝但今天早上他已经掉到 80 万那么基于旧特征训练的模型很可能高估该用户的影响力。解决办法可以落地三种以 T1 的批处理方式重算度数适用于业务容忍一天延迟的场景用时间衰减因子维护一个滚动度对近期新增边赋予更高权重在流式计算环节增量更新每次新增一条边时对源节点和目标节点的度数各做一次原子加 1有向图只更新对应方向需要注意自环不能重复累加。我之前在实时推荐系统里用第三种方式用 Redis 存每个节点的入度/出度每次事件进来做一个INCR一度数秒级延迟就能看到度数的更新。但这里也有坑Redis 的 key 数量等于节点数量百万级节点没问题上亿节点就要考虑分片策略了。5.5 从度再往前一步二级邻居与效率权衡最后讲一个我常用来给团队的建议——当你想计算二阶度比如朋友的度之和或共同邻居数时要非常小心复杂度。直接枚举一个高度数节点的二阶邻居可能瞬间产生几十万甚至上千万次中间结果。如果你的图里存在超级 hubs做一个 naive 的二阶邻居枚举就能把集群资源耗干。更稳妥的做法是先裁剪掉度超过某个阈值比如 500的超级节点或者在计算邻居交集中利用稀疏矩阵的乘法代替显式枚举。在处理社交网络的共同好友指标时用A A.T这种矩阵乘法的稀疏版本往往比显式遍历快几个数量级。但也要记住矩阵乘法产生的中间矩阵可能并不稀疏两者之间需要根据图的密度做实际测试和取舍。这个取舍没有标准答案只能靠实验数据说话。说到底度是图分析里最基础的一道门槛但它延伸出的处理和优化问题其实贯穿了图存储、图计算、网络科学和图机器学习的所有环节。把每一个细节都想透往往能让下游模型和算法的效果提升一个台阶。