序贯网络设计中的嵌套分裂图最优性：基于中心性度量的动态形成路径分析

《Journal of Economic Theory》：Sequential network design

本文创新性地研究动态网络形成的中心化设计问题，提出前瞻性规划者在每期建立新连边的序贯决策框架。通过证明任意折现函数下嵌套分裂图（NSG）的每期最优性，以及短视规划者情形中准完全图（QC）的唯一最优性，为网络构造的贪婪算法提供了微观基础。研究进一步拓展至加权网络，验证了结论在卡茨-博纳奇中心性（KB centrality）等路径基础指标中的稳健性。

　　

模型构建

网络由节点集N={1,…,n}通过邻接矩阵G=(g_ij)_n×n表示，其中g_ij=g_ji=1表示连接存在。若网络?可通过向G新增单条连边获得（即?=G+E_ij），则称?继承于G。

最优形成过程

定理1

1. 1.
   存在最优路径s=(G(t))_t=1^T，使得每期网络G*(t)均为嵌套分裂图（NSG）；
2. 2.
   若第r期折现函数D(r)>0，则任何最优路径在r期必为NSG。
   该定理确立NSG在每期网络形成中的最优性，第二部分强调非零折现权重下的结构约束。

加权网络拓展

本节将分析延伸至加权网络场景。当规划者能分配连边权重（如交通网络中的车道数）时，核心技术工具（引理1）在加权情形下不再普适。研究得到两大结论：

1. 1.
   最大化KB中心性时，最优路径每期均产生未加权网络（命题1）；
2. 2.
   最大化平方KB中心性时，短视规划者会形成未加权准完全图（命题2），凸显权重分配的边界最优特性。

结论与讨论

本研究通过序贯网络设计框架，揭示NSG在多种效用函数（路径计数、谱半径等）与折现规则下的普适最优性。为准完全图作为贪婪算法输出提供理论依据，为基础设施渐进式建设（如电网扩展）提供动态设计范式。