完全图中新增节点的缺失边权重（步行时长）估算方法问询

基础零额外成本方案：三角不等式约束法 #

路网步行时长天然满足三角不等式规则：对任意三个节点a、b、c，有d(a,c) ≤ d(a,b) + d(b,c)，同时满足d(a,c) ≥ |d(a,b) - d(b,c)|，你可以直接用现有已有的全量数据计算：

• 对每个需要估算的目标原有节点u，遍历所有你已经测得新节点v到其步行时长的样本节点s
  • 计算所有下界候选值|d(v,s) - d(s,u)|，取最大值作为新节点到u的步行时长下界
  • 计算所有上界候选值d(v,s) + d(s,u)，取最小值作为新节点到u的步行时长上界
• 普通场景下直接取上下界的平均值即可作为最终估算值，精度由你选择的样本节点分布决定，样本节点在空间/路网中覆盖越均匀，估算误差越小。

有坐标数据的优化方案：空间插值法 #

如果所有地理位置节点都带有经纬度坐标，可以进一步提升精度：

• 逆距离加权插值：以新节点到各样本节点的步行时长为基础，按样本节点和待估算节点的空间距离倒数加权计算，公式为d(v,u) = Σ (w_s * d(v,s)) / Σ w_s，其中权重w_s = 1 / d(s,u)^k，k默认取2即可
• 特征回归：拟合步行时长和球面距离、区域路网密度、道路交叉口数量等空间特征的回归模型，代入待估算节点的对应特征即可得到预测值。

复杂路网高精度方案：图嵌入法 #

如果原有节点数量足够多，可以先对原有全连通图做节点嵌入：

• 用Node2Vec、DeepWalk等图嵌入算法把所有原有节点映射为低维向量，向量会隐含节点在路网中的相对位置、连通性等特征
• 用样本节点的嵌入向量和对应的新节点步行时长训练简单回归模型，输入待估算节点的嵌入向量即可得到预测结果，该方案在路网结构复杂、弯道/隔断多的场景下精度远高于前两种。

内容的提问来源于stack exchange，提问作者Raphael Schumann