# 图算法与结果解读

从分析问题选择算法，明确边权、方向和结果范围，并把工具输出转化为可以验证的结论。

## 从问题到工具调用

一次图分析通常由数据确认、实体定位、算法计算和结果呈现四步组成。先用 get_graph_info 确认活动图版本、方向和属性；再用精确节点名称或实体检索解析输入；随后执行算法；最后把完整计算结果交给可视化或报告工具。模型负责组织分析过程，数值结果来自 Graph Engine 的实际执行。

| 分析问题 | 优先工具 | 需要先确认 |
| --- | --- | --- |
| 哪些节点直接连接最多？ | degree_analysis / node_centrality(degree) | 区分入度、出度、关系条数和不同邻居数。 |
| 哪些节点控制重要路径？ | node_centrality(betweenness) | 边权是距离或代价，且满足权重约束。 |
| 两个实体如何联系？ | shortest_path / path_analysis | 明确方向，以及要找最少跳数还是最低成本。 |
| 网络有哪些紧密群体？ | community_detection | 确认无向投影与边权表示的连接强度。 |
| 哪里是网络瓶颈？ | maximum_flow / minimum_cut | 容量的单位、源点、汇点和并行关系。 |
| 哪些关系值得进一步验证？ | link_prediction_score | 结构相似度只是候选得分，不是已存在关系。 |

同一轮模型响应中的独立算法可以并行，但依赖真实结果的下一步需要等结果返回。例如，不能在 search_node 尚未返回时猜测节点 ID 再调用 shortest_path。准备清空、覆盖或保存子图时，还应检查工具是否会改变当前活动图。

- [完整工具参考](/zh/graph-tools/): 查询 72 个业务工具的参数、返回字段及具体约束。

> **平行关系会限制可用算法**
> 存在平行关系时，社区发现仅支持 louvain 与 greedy_modularity。VoteRank、percolation、maximum_cycle、link_prediction_score、k_core/k_truss/k_corona，以及 transitivity、average_clustering、degree_assortativity 会返回 UNSUPPORTED_MULTIGRAPH_OPERATION。应先检查图结构，再选择支持的方法；不要未经说明就删除关系来绕过限制。

## 最短路径与路径枚举

shortest_path 的 use_weight=true 按边权总和寻找最低成本路径；false 按跳数计算。两者优化目标不同。默认加权路径使用 NetworkX 的最短路径实现，单源到所有节点的请求使用 Dijkstra；无权路径按跳数遍历。不存在路径是一次有效查询的结果，应读取 found=false，而不是把它当成服务故障。

```text
A -> B : 2
A -> C : 5
B -> C : 1
B -> D : 4
C -> D : 1

Weighted minimum: A -> B -> C -> D, cost = 4, hops = 3
Minimum hops:     A -> B -> D or A -> C -> D, hops = 2
```

algorithm=yen_k_shortest 返回按成本排序的若干简单路径，路径之间的成本可以不同；all_shortest_paths 返回相同最优成本的路径。path_analysis(method=all_simple_paths) 则枚举满足 cutoff 的简单路径，可能包含大量非最短路径。简单路径不重复经过节点，因此它与允许绕圈的步行序列不同。

target="all" 会执行单源可达路径计算，默认只展示最近的 10 条路径，并同时返回 reachable_count 和距离统计。all_shortest_paths 也默认最多展示 10 条。展示条数不能当作可达节点总数或最短路径总数；必须同时读取 truncated、count_returned 等字段。

属性图中的平行边按最小权重投影后参与路径计算，路径按节点序列区分。同一节点序列上存在多条等价关系，不会自动变成多条不同结果。NebulaGraph 上的部分路径工具只加载有限跳数邻域，此时未找到路径仅说明当前查询范围内未找到。

## 中心性：不同意义上的重要节点

中心性没有统一的“重要程度”定义。度中心性描述直接连接数量，介数中心性关注最短路径经过的中介位置，PageRank 关注来自其他重要节点的连接。解释排名前，先说明研究问题及边的方向含义；不要把所有中心性值放在一个量纲下比较。

| 枚举值 / 名称 | 计算含义 | 实现要点 |
| --- | --- | --- |
| degree | 度中心性：连接数量的归一化统计。 | 不按权重强度求和；度分布的原始计数用 degree_analysis。 |
| betweenness | 介数中心性：最短路径经过该节点的比例之和。 | 使用 weight 作为距离；属性图要求严格正权重，不暴露抽样 k 参数。 |
| closeness | 接近中心性：其他节点到该节点的平均最短距离的倒数。 | 有向图使用入向距离，并采用 NetworkX 的连通范围修正。 |
| harmonic | 调和中心性：可达节点距离倒数之和。 | 使用加权距离，不能把无法到达的节点当作零距离。 |
| pagerank | PageRank：沿连接传播的稳态重要度。 | weight 表示连接强度，平行关系的权重累加。 |
| eigenvector | 特征向量中心性：与高中心性节点相连会提高得分。 | 幂迭代上限为 1,000；不收敛时尝试 NumPy 求解。 |
| katz | Katz 中心性：考虑不同长度的连接路径并衰减远距离影响。 | 固定 alpha=0.1、beta=1.0、max_iter=1000，仍可能不收敛。 |
| load | 负载中心性：按最短路径分配负载。 | 使用 weight 作为距离，属性图要求严格正权重。 |
| voterank | VoteRank：用投票过程选择影响节点。 | 返回的是选中节点的顺序评分，不是全部节点的概率。 |
| percolation | 渗流中心性：考虑节点渗流状态的路径指标。 | 读取节点 percolation 属性，缺失时按 1.0 处理。 |

node_centrality 返回 top_nodes、bottom_nodes、value_stats 和 total_nodes，数值通常保留 6 位小数。top_nodes 默认最多 20 项；bottom_nodes 只补充不与前列重叠的末尾节点。total_nodes 表示该算法实际生成的得分数量，VoteRank 等方法不能据此推断完整图规模。

- [NetworkX：接近中心性与有向距离](https://networkx.org/documentation/stable/reference/algorithms/generated/networkx.algorithms.centrality.closeness_centrality.html)
- [NetworkX：介数中心性的定义](https://networkx.org/documentation/stable/reference/algorithms/generated/networkx.algorithms.centrality.betweenness_centrality.html)

## 社区发现与模块度

社区发现把连接较密集的节点分为组。Graph Engine 先按当前算法规则构造无向分析图，再计算社区及模块度。模块度衡量分组中的内部连接相对于随机基线是否更集中；它用于比较同一图和同一权重语义下的划分，不能直接当作预测准确率。

| 算法 | 策略与边权 | 结果范围 |
| --- | --- | --- |
| louvain | 基于加权模块度优化；固定 seed=42。 | 给出一次层次聚合后的分组。 |
| greedy_modularity | 贪心合并以提高加权模块度。 | 在当前无向分析图上分组。 |
| label_propagation | 标签传播，当前分支不向算法传入边权。 | 分组依据邻接结构。 |
| label_propagation_asyn | 异步加权标签传播，固定 seed=42。 | 随机过程由该固定种子控制。 |
| girvan_newman | 按边介数逐步拆分网络。 | 当前只取生成器的第一次划分。 |
| asyn_fluidc | 异步流体社区算法，目标组数至多 3。 | 图不连通时只处理最大连通分量。 |
| leiden | 通过 python-igraph 与 leidenalg 计算；当前转换未传入边权。 | 发生异常时回退到加权 Louvain；返回的 algorithm 仍为请求值。 |

默认返回最大的 5 个社区，每组只预览 10 个节点。num_communities、communities_shown、communities_truncated 与 nodes_truncated 分别说明总组数、已展示组数以及两层截断。community_id 来自本次计算，不是跨图版本稳定的业务标识。

比较算法时应记录图版本、是否使用权重、是否进行了无向投影和实际覆盖节点。对于 Leiden，需要额外注意回退和权重传递的实现限制；对于 asyn_fluidc，需要检查遗漏的其他连通分量。这些条件会改变结果含义。

focus_nodes 最多接受 200 个真实节点名，用于把指定节点关联到同一次社区划分，避免另一次调用产生不同编号。普通活动图与大图路径的同名算法不能混为一谈：大图社区入口当前将七个名称映射到可扩展的加权同步标签传播近似，max_iterations 默认 5；要求原算法语义时先查能力目录，并考虑 strict_semantics=true 拒绝近似映射。

## 网络流、最小割与生成树

最大流把边权解释为容量。对给定源点和汇点，求满足容量约束和中间节点流量守恒的最大流量。指定 source/sink 的 minimum_cut 寻找把它们分开的最小容量割；在相同网络和容量约定下，最大流值应等于最小割值，可据此检查分析是否使用了一致的输入。

```text
s -> a : 3
s -> b : 2
a -> b : 1
a -> t : 2
b -> t : 3

Feasible flow: s-a-t = 2, s-a-b-t = 1, s-b-t = 2
Maximum flow = 5; a minimum cut is {s} | {a,b,t}, capacity = 5
```

这是按容量手工计算的说明例子。maximum_flow 返回 max_flow_value 与非零流边预览，minimum_cut 返回 min_cut_value、分区规模和割边预览。具体流量分配或最小割分区可能不唯一，因此不应把单次返回的边集合解释为唯一瓶颈方案。

global_minimum_cut 不指定源汇，当前使用无向 Stoer–Wagner 算法。有向输入需要 treat_as_undirected=true，成对连接的权重会合并，自环不参与割；图已不连通时割值为 0。它回答的是全局最易分离的位置，与两点间的最小割问题不同。

minimum_spanning_tree 寻找连接所有节点且总权重最小的无环边集。图不连通时返回最小生成森林摘要。它优化整张网络的总连接成本，不保证每个节点到源点的路径最短；路径规划应使用 shortest_path。

最小生成树基于无向分析图。构图属性图按无向端点对选择最小权重关系；普通有向图则直接通过 NetworkX 转为无向图，不能假定相反方向边自动取较小权重。需要比较生成树结果时，应明确采用哪一种输入与投影规则。

## 结构分析、子图与候选关系

有向图的强连通分量要求组内节点沿方向互相可达；弱连通分量忽略方向后判断连通。graph_connectivity 会分别报告两者。topological_sort 只适用于有向无环图，如果业务依赖含环，应先用 find_cycles 定位冲突，再决定是否修改关系。

find_cycles 采用有限展示上限时，会流式读取“上限加一”个环来判断是否截断；请求全部结果时，会枚举并保存全部简单环。maximum_cycle 在 max_cycles 范围内寻找最长或权重最大的简单环，默认最多枚举 10,000 个；search_exhausted=false 表示搜索未穷尽，返回的只是已搜索候选中的最好结果。

| 子图方法 | 含义 | 使用提示 |
| --- | --- | --- |
| node_subset | 给定节点集合的诱导子图。 | 保留这些节点之间已有的关系。 |
| ego_graph | 围绕中心节点按指定半径扩展。 | 确认方向与范围参数。 |
| k_core | 递归去除度不足 k 的节点。 | 强调整体上维持至少 k 度的结构。 |
| k_truss | 保留至少参与 k−2 个三角形的边所形成的子图。 | 用于分析三角关系密集的区域。 |
| k_corona | k-core 中度恰好为 k 的节点诱导子图。 | 不是所有原图度等于 k 的节点。 |

subgraph_extraction 默认 create_version=true，会把提取结果保存为当前活动图。仅为了解释结果或预览结构时，应显式传 false。后续中心性、社区或训练会读取活动图，因此保存子图会改变分析输入；需要记录新 graph_version。

结构链接预测不需要训练模型。Jaccard 衡量共同邻居占并集的比例；Adamic–Adar 与资源分配指数降低高度数共同邻居的贡献；优先连接使用两端节点度数的乘积。未指定两个端点时，工具遍历不存在边的节点对并保留最高分候选，top_k 限制结果保存量，但不把候选评分工作变成常数时间。

- [NetworkX：k-core、k-truss 与 k-corona 定义](https://networkx.org/documentation/stable/_modules/networkx/algorithms/core.html)

| 扩展工具 | 问题与范围 |
| --- | --- |
| graph_structure_analysis | 树、森林、DAG、二部图和平面性等判定，BFS/DFS 树、拓扑序和 WL 哈希。遍历必须指定 source；不会保存为新的活动图。 |
| connectivity_analysis | 点/边连通度、割集、割点、桥和分量；局部连通度与割集成对提供 source/target。condensation 要求有向图。 |
| tree_dag_analysis | 最大/随机生成树、最近公共祖先、支配关系、DAG 最长路与反链。LCA 需要 node1/node2，支配关系需要 source；有向无环类方法会检查前提。 |
| matching_coloring_analysis | 无向视图上的匹配、边覆盖与着色。极大匹配不等于最大匹配；均衡着色要求 num_colors 大于最大度，最小边覆盖拒绝孤立节点。 |
| distance_measures | 中心、边缘、离心率、Wiener 指数、效率、互惠性等。中心、边缘、离心率、Wiener 指数与重心只在最大无向连通分量计算；无环图的围长为 null 并标记 acyclic=true。 |

这五组扩展工具目前拒绝多重图。普通路径的列表预览默认 20，正整数上限钳制为 200；all 的含义要看具体方法。全部拓扑序、反链、collider 与 v-structure 枚举仍受 200 条硬上限约束。读取 truncated、hard_limit、count_is_exact 等字段，不能把预览条数当作全体数量。大图路径另有能力、预算和结果文件约束；本页描述源码契约，不表示所有算法和参数组合都已在当前部署逐项运行。

## 统计口径与输出范围

| 指标 | 当前计算口径 |
| --- | --- |
| density | 在当前方向语义下计算图密度。自环或多重关系会影响对“密度”的解释。 |
| diameter / radius | 先转为无向图，再取最大连通分量，使用无权距离。 |
| transitivity | 在无向分析图上计算全局三角闭合程度。 |
| average_clustering | 在无向图上计算加权平均聚类系数。 |
| degree_assortativity | 在无向图上衡量两端度数的相关性。 |

直径和半径的有限数值不代表原始有向图完全连通；它们可能只描述最大无向连通分量。部分指标在空图或度数无变化的图上无定义。global_metrics 用 defined=false、value=null 表示非有限结果；度同配系数还返回 undefined_reason_code 与 undefined_reason，区分无边和端点度数方差为零。无定义不是数值 0，也不等于引擎不支持这个指标；其他参数或图结构错误仍可能返回 success=false。

输出中的 summary、preview、top_nodes、truncated 表达不同层次的信息。全局指标可能基于完整输入图计算，而列表只展示其中一部分；远端有限范围查询则连计算输入本身也可能被限定。写报告时应同时标明“计算范围”和“展示范围”。

visualize_subgraph 的目录默认值为 max_nodes=800、include_community=true；引擎的省略值和边数上限可由 VISUALIZE_MAX_NODES、VISUALIZE_MAX_EDGES 配置，默认分别为 800 和 2,000。超出范围时使用确定性的概览选择，结合高亮、节点类型、社区代表、高度数节点和连接路径。高亮本身过多也可能截断，需检查 overview.required_nodes_truncated。total_nodes/total_edges 表示请求范围内的原始规模，num_nodes/num_edges 是实际展示规模。视图不能证明范围外没有路径；报告同样应使用真实 source_results，并单独说明计算与展示范围。