Link-level Vulnerability Indicators for Real-World Networks Abstract Methodology

Link-level Vulnerability Indicators
Victor Knoop
for
Real-World
Networks
Maaike Snelder
Henk van Zuylen
Serge Hoogendoorn
Abstract
Methodology
Literature proposes link-based indicators as predictors of
the delay caused by a blockade on a particular link. This
paper cross-compares these indicators and compares them
with the result of a full simulation. The indicators predict
different links to be vulnerable. Furthermore, the
indicators do not provide a good indication of the delay of
a blockade, partly because traffic dynamics (including
spillback or blocking back) are not well included in the
indicators. A linear combination of different indicators
does not increase the performance either. Once more than
one indicator is included in the fit, the predictive value of
the combination of the indicators is lower than the
predictive value of one indicator due to over fitting.
Correlation C2 and full calculation
Correlation C3 and full calculation
Correlation C5 and full calculation
Correlation C4 and full calculation
1
0.8
0.8
0.8
0.8
0.8
0.6
0.4
0
0
0.6
0.4
0.2
0
0
1
2
3
4
5
Vulnerability by full calculation (vah h lost)
x 10
0.6
0.4
0.2
0
0
1
2
3
4
5
Vulnerability by full calculation (vah h lost)
x 10
C5(scaled value)
1
C4(scaled value)
1
C3(scaled value)
1
0.2
0.6
0.4
1
2
3
4
5
Vulnerability by full calculation (vah h lost)
x 10
0.4
0.2
0.2
0
0
0.6
0
0
1
2
3
4
5
Vulnerability by full calculation (vah h lost)
x 10
500
500
400
400
400
400
400
300
200
100
0
0
100
200
300
400
Position according to full calculation
1
I
500
= q /(1 − q/C)
300
200
100
0
0
100
200
300
400
−
Position according to full calculation
I 2 = 1/Tb
500
300
200
100
0
0
100
200
300
400
Position according
b to full calculation
500
300
200
100
0
0
I 3 = Ii1 · ϑ (q − 2500)
4
Position according to I5
500
Position according to I4
500
Position according to I3
500
Position according to I2
Position according to I1
• 468-link network: also dynamic traffic simulation
=> 468 values for the delay caused by blockades at
different sites
=> Fit these delays with the values of the indicators.
1
C2(scaled value)
C1(scaled value)
Correlation C1 and full calculation
In literature: 9 link-based criteria predicting
impact of a blockade
=> Calculate for 3 networks (11, 150 and 468 links)
=> Cross-compare values
•
1
100
200
300
400
· calculation
Position according to full
4
1
I
= I ·q
500
1
2
3
4
5
Vulnerability by full calculation (vah h lost)
x 10
300
200
100
0
0
Ii5 =
100
200
300
400
·
Position according to full calculation
X
2
Ii · qi ·
upstream links j of i
X
The correlation between the indicator values and the full calculation (top row) and between the predicted ranks and the calculated ranks (bottom row)
Results
Different indicators indicate different links a
vulnerable.
=> complementary?
• Also combination of indicators does not
indicate the most vulnerable links
• Alternative: include the most vulnerable links
according to each of the indicators
• Result: include many links since all indicators
differ
•
Transport & Planning
500
The considered networks
Delft University of Technology
Ij1
Victor L. Knoop PhD.
TRAIL Research School fellow
Delft University of Technology
Transport & Planning
[email protected]
Transportation Research Board
89th Annual Meeting, January 10-14, 2010
Paper number: 10-1231
indicator i
Tried for all possible combinations of indicators
9
9 indicators, so 2 =512 combinations
Coefficients ai optimized on a calibration set (2/3)
Combination tested on validation set (1/3)
Combining hardly reduces the residual error
Including more than one indicator increases the error
=> over fitted
1
1
0.4
0.6
0.4
0.2
0
0
0.6
0.4
0
0
1
2
3
4
5
Vulnerability full calculation (vah h lost)x 10
0
0
1
2
3
4
5
Vulnerability full calculation (vah h lost)x 10
400
400
100
X
0
0
Ii6
=
100
200
300
400
Position according to full calculation
X
3
Ii · qi ·
500
100
0
0
Ij1
upstream links j of i
X
100
200
300
400
Position according to full calculation
I
7
X
=
upstream links j of i
Ij1
500
Position according to I9
400
Position according to I8
400
Position according to I7
500
200
300
200
100
0
0
100
Number of required links in each critirion 0.2
Total number of unique links
Overlap
0
200
300
400
500
Links to be included
100
0.2
500
200
0.4
0.4
500
300
200
0.6
500
300
0.6
0.8
0.2
0
0
1
2
3
4
5
Vulnerability full calculation (vah h lost)x 10
300
1
0.8
I8(scaled value)
0.6
0.2
Position according to I6
1
0.8
I7(scaled value)
I6(scaled value)
0.8
0.8
0
0
I9(scaled value)
•
•
•
•
=>
=>
400
100
200
300
400
Position according to full calculation
I
8
q
=
C
500
1
2
3
4
5
Vulnerability full calculation (vah h lost)x 10
300
200
100
0
0
100
200
300
400
Position accordingC
to full calculation
I 9 = qi − Cib
500
q
Stdev error predicted delay / Stdev delay
•
Number of Links
468 values of the impact calculated with a dynamic traffic
simulation program (large network).
X
f=
D
ai Ci
Delay is estimated by
•
1
Stdev error in predicted delay / Stdev delay
Combinations
500
Overlap fraction
Number of links found
Error in multi−lineair regression fit
1.06
1 indicator
1.04
1.02
1
0.98
0.96
1
2
3
4
5
6
7
8
Indicator i included in multi−regression analysis
Error for different model complexities
9
1
2
9
1.06
1.04
1.02
1
0.98
0.96
3
4
5
6
7
8
Number of indicators in prediction model
Results of fits of combinations
Discussion
Conclusions
The influence of a blockade stretches further than the
link where the blockade occurs. Network dynamics
should therefore taken into account. In practice, also
alternative routes play a role. This is insufficiently
captured in the current indicators. Link-level
indicators are therefore unable to indicate the
vulnerable links. Possible alternatives are indicators
which include alternative routes, or otherwise a
complete simulation of the network.
Current link-based indicators do not provide an
insight into the vulnerability of blockades in a
network. Moreover, they cannot be used to select
a subset of possible vulnerable links. Network effects play an important role in the real
vulnerability. Therefore, if one looks for an
indicator for vulnerability, it needs to include
these effects.
Transport & Planning
Delft University of Technology