Quantifying how network components affect overall performance is key for resilience and design. We revisit vertex- and edge-importance in nonatomic selfish-routing games, comparing classical topological centralities and demand-based metrics: Latora–Marchiori global efficiency, Zhu average disutility, Jenelius–Mattsson unsatisfied demand, and the Nagurney–Qiang unified measure. Analytical and empirical tests on the Sioux Falls network and smaller examples reveal key weaknesses: (i) topological scores neglect flow; (ii) most demand-weighted measures become unbounded when removals improve travel times; and (iii) many collapse entirely when disconnections occur. To address this, we introduce a bounded, sign-aware importance index that preserves scale invariance and remains well-defined under disconnection. Experiments demonstrate rank correlation with total travel time and correct identification of paradoxical cases where removals improve outcomes. Our work identifies where these existing measures fall short and cautions against using a single measure to assess both efficiency and connectivity.

错误:搜索内容不能为空,请输入英文关键词
错误:关键词超出字数限制,请精简
高级检索

Classical and Novel Measures for Component Criticality in Selfish-Routing Networks

  • Sam O’Neill,
  • Ovidiu Bagdasar

摘要

Quantifying how network components affect overall performance is key for resilience and design. We revisit vertex- and edge-importance in nonatomic selfish-routing games, comparing classical topological centralities and demand-based metrics: Latora–Marchiori global efficiency, Zhu average disutility, Jenelius–Mattsson unsatisfied demand, and the Nagurney–Qiang unified measure. Analytical and empirical tests on the Sioux Falls network and smaller examples reveal key weaknesses: (i) topological scores neglect flow; (ii) most demand-weighted measures become unbounded when removals improve travel times; and (iii) many collapse entirely when disconnections occur. To address this, we introduce a bounded, sign-aware importance index that preserves scale invariance and remains well-defined under disconnection. Experiments demonstrate rank correlation with total travel time and correct identification of paradoxical cases where removals improve outcomes. Our work identifies where these existing measures fall short and cautions against using a single measure to assess both efficiency and connectivity.