Introduction
Related work
Robustness management through link perturbations
Evolutionary methods improving robustness
Effective graph resistance \(R_{G}\)
Incremental computation of \(R_{G}\)
- Edge addition
- Edge removal
Optimising the effective graph resistance through link addition or link protection
RobGA{\(L^{+}\)}
RobLPGA{\(L^{+}\)}
Experimental setup
Datasets
Network | ID | n | m | <k> | <C> | D |
---|---|---|---|---|---|---|
Bell South | BS | 51 | 66 | 1.294 | 0.081 | 0.052 |
ASNET-AM | AA | 65 | 77 | 1.184 | 0.063 | 0.037 |
ITC Deltacom | ITC | 113 | 161 | 1.425 | 0.053 | 0.025 |
ION | ION | 125 | 146 | 1.168 | 0.006 | 0.019 |
US Carrier | USC | 158 | 189 | 1.196 | 0.002 | 0.015 |
Ego 3980 | 3980 | 44 | 138 | 3.136 | 0.227 | 0.072 |
Ego 686 | 686 | 168 | 1656 | 9.8572 | 0.266 | 0.059 |
Ego 3437 | 3437 | 532 | 4812 | 9.045 | 0.272 | 0.017 |
US Power Grid | USPG | 4941 | 6594 | 2.669 | 0.103 | 5.403e−04 |
Network type | Network ID | n | m | <k> | <C> | D |
---|---|---|---|---|---|---|
Erdős–Rényi | ER_128 | 128 | 627.3 | 5.23 | 0.054 | 0.041 |
ER_256 | 256 | 1423.2 | 11.117 | 0.064 | 0.043 | |
ER_512 | 512 | 3240.2 | 12.64 | 0.01 | 0.024 | |
ER_1024 | 1024 | 6310.2 | 12.222 | 0.004 | 0.011 | |
Watts–Strogatz | WS_128 | 128 | 384 | 6 | 0.109 | 0.047 |
WS_256 | 256 | 768 | 6 | 0.104 | 0.023 | |
WS_512 | 512 | 2560 | 10 | 0.036 | 0.019 | |
WS_1024 | 1024 | 5120 | 10 | 0.039 | 0.009 | |
Bárabasi–Albert | BA_128 | 128 | 253.4 | 3.954 | 0.132 | 0.031 |
BA_256 | 256 | 510.2 | 3.984 | 0.129 | 0.015 | |
BA_512 | 512 | 1529.7 | 5.996 | 0.017 | 0.011 | |
BA_1024 | 1024 | 3065.2 | 5.986 | 0.012 | 0.005 |
Strategies for selecting a link
-
\(S_{1}\): node i has the lowest degree and node j is picked at random. The computational cost is \(O(n^{2}-n+m_{c}+1)\), with \(O(n(n-1))\) the cost for computing the node degrees, \(O(m_{c})\) the cost for searching the node with the minimum degree and O(1) is required for selecting a random node.
-
\(S_{2}\): the product of the degrees \(d_{i}d_{j}\) between two nodes is the minimum. The complexity for \(S_{2}\) is \(O(n^{2} - n +2m_{c})\), with \(O(n(n-1))\) for computing node degrees, \(O(m_{c})\) for their product and \(O(m_{c})\) for searching the minimum value of degree product.
-
\(S_3\): differently from the previous two strategies based on graph topology, this strategy analyzes the graph spectrum. Nodes i and j have the maximum difference \(|y_{i} -y_{j}|\), where \(y_{i}\) and \(y_{j}\) are the i-th and j-th elements of the Fiedler vector y. The complexity of \(S_3\) is \(O(n^{3}+2m_{c})\), where \(O(n^{3})\) is required for the Fiedler vector computation, \(O(m_{c})\) for the difference \(|y_{i} -y_{j}|\) of the \(m_{c}\) links, and \(O(m_{c})\) for searching the maximum of the difference.
-
\(S_{4}\): the nodes i and j have the maximum effective resistance \(R_{ij}\), computed as in Eq. (1). The complexity of \(S_{4}\) is \(O(n^{3}+4m_{c})\), where \(O(n^{3})\) is needed for computing the Moore–Penrose pseudoinverse \(L^{+}\), \(O(3m_{c})\) for \(R_{ij}\) for the \(m_{c}\) links, and \(O(m_{c})\) for finding the highest effective resistance value.
Performance indexes
-
Percentage Error the percentage relative error between strategy \(S_{x}\) and the exhaustive search (*) in terms of effective graph resistance measured on the graph G modified with the addition or the removal of a link.$$\begin{aligned} \Delta {R_{G}}=\left| \frac{R_{G}^{S_{x}}-R_{G}^*}{R_{G}^*} \right| *100 \end{aligned}$$(10)
-
Speedup the ratio between the time required to run the strategy \(S_{x}\) and the strategy \(S_{y}\).$$\begin{aligned} Speedup=\frac{t_{sim}^{S_{x}}}{t_{sim}^{S_{y}}} \end{aligned}$$(11)
Results
Link addition
ID | \(\Delta R_{G+\{e\}}^{S_{1}}\) | \(\Delta R_{G+\{e\}}^{S_{2}}\) | \(\Delta R_{G+\{e\}}^{S_3}\) | \(\Delta R_{G+\{e\}}^{S_{4}}\) | \(\Delta R_{G+\{e\}}^{RobGA}\) | \(\Delta R_{G+\{e\}}^{RobGA}\{L^{+}\}\) |
---|---|---|---|---|---|---|
BS | 8.918 | 4.493 | 0.76 | 0 | 0 | {0, 0.401} |
AA | 7.472 | 6.97 | 1.914 | 2.565 | 0 | {0, 1.152} |
ITC | 15.062 | 10.591 | 1.235 | 1.231 | 0.184 | {0, 0.985} |
ION | 9.484 | 7.669 | 1.749 | 3.834 | 0 | {0.255, 0.292} |
USC | 19.869 | 15.765 | 5.692 | 10.453 | 0.159 | {0.396, 0.7} |
3980 | 8.938 | 3.018 | 0.386 | 0 | 0 | {0, 0.77} |
686 | 7.26 | 0.847 | 0.435 | 0.826 | 0 | {0.021, 0.282} |
3437 | 2.186 | 1.567 | 0.635 | 0.522 | 0.077 | {0, 0.419} |
ID | e* | \(e^{S_{1}}\) | \(e^{S_{2}}\) | \(e^{S_3}\) | \(e^{S_{4}}\) | \(e^{RobGA}\) | \(e^{{RobGA}\{L^{+}\}}\) |
---|---|---|---|---|---|---|---|
BS | [43 47] | [32 25] | [14 24] | [3 6] | [3 6] | [43 47] | [43 47] |
AA | [32 37] | [23 3] | [27 52] | [15 33] | [7 36] | [32 37] | [32 37] |
ITC | [34 59] | [48 19] | [40 80] | [40 109] | [40 109] | [34 59] | [34 59] |
ION | [4 55] | [30 20] | [7 72] | [5 55] | [54 103] | [4 55] | [104 55] |
USC | [80 93] | [78 67] | [56 72] | [116 148] | [41 48] | [79 77] | [79 78] |
3980 | [36 42] | [37 5] | [4 39] | [23 42] | [36 42] | [36 42] | [36 42] |
686 | [26 62] | [140 145] | [62 89] | [62 164] | [88 153] | [26 62] | [7 62] |
3437 | [243 440] | [388 165] | [410 434] | [366 477] | [440 430] | [440 503] | [440 503] |
USPG | – | [2847 3401] | [1853 3148] | [799 4463] | – | [3925 1776] | [4432 2747] |
ID | \(R_{G}\) | \(R_{G+\{e\}}^*\) | \(R_{G+\{e\}}^{S_{1}}\) | \(R_{G+\{e\}}^{S_{2}}\) | \(R_{G+\{e\}}^{S_3}\) | \(R_{G+\{e\}}^{S_{4}}\) | \(R_{G+\{e\}}^{RobGA}\) | \(R_{G+\{e\}}^{{RobGA}\{L^{+}\}}\) |
---|---|---|---|---|---|---|---|---|
USPG | 6.377e+07 | – | 6.242e+07 | 6.314 e+07 | 6.173e+07 | – | 6.105e+07 | 6.107e+07 |
ID | \(\Delta R_{G+\{e\}}^{S_{1}}\) | \(\Delta R_{G+\{e\}}^{S_{2}}\) | \(\Delta R_{G+\{e\}}^{S_3}\) | \(\Delta R_{G+\{e\}}^{S_{4}}\) | \(\Delta R_{G+\{e\}}^{RobGA}\) | \(\Delta R_{G+\{e\}}^{{RobGA}\{L^{+}\}}\) |
---|---|---|---|---|---|---|
ER_128 | 1.028 | 0.029 | 0.044 | 0.093 | 0.004 | 0.103 |
WS_128 | 0.694 | 0.055 | 0.083 | 0.038 | 0.027 | 0.122 |
BA_128 | 0.607 | 0.219 | 0.064 | 0.012 | 0 | 0.0426 |
Network type | Strategy | n = 128 | n = 256 | n = 512 | n = 1024 |
---|---|---|---|---|---|
Erdős–Rényi | RobGA | 1.984 | 5.381 | 7.612 | 10.261 |
\(S_{4}\) | 1.985 | 101.993 | 401.451 | 1097.735 | |
Watts–Strogatz | RobGA | 1.805 | 3.53 | 5.076 | 9.708 |
\(S_{4}\) | 1.311 | 97.859 | 216.135 | 885.474 | |
Bárabasi–Albert | RobGA | 1.781 | 2.535 | 7.347 | 7.141 |
\(S_{4}\) | 2.933 | 59.4267 | 379.817 | 795.38 |
Network type | p = 300 | p = 500 |
---|---|---|
ER_128 | {2.726, 0.085} | {3.015, 0.071} |
WS_128 | {2.747, 0.071} | {4.121, 0.058 } |
BA_128 | {2.154, 0.027} | {2.998, 0.011} |
Link protection
ID | \(\Delta R_{G-\{e\}}^{S_{1}}\) | \(\Delta R_{G-\{e\}}^{S_{2}}\) | \(\Delta R_{G-\{e\}}^{S_3}\) | \(\Delta R_{G-\{e\}}^{S_{4}}\) | \(\Delta R_{G-\{e\}}^{RobLPGA}\) | \(\Delta R_{G-\{e\}}^{{RobLPGA}\{L^{+}\}}\) |
---|---|---|---|---|---|---|
ER_128 | 0.049 | 0.049 | 0.049 | 0 | 0 | 0.782 |
WS_128 | 0.67 | 0.507 | 0 | 0 | 0.003 | 1.452 |
BA_128 | 1.008 | 0.365 | 0.0013 | 0.004 | 0 | 1.953 |
Network type | Strategy | n = 128 | n = 256 | n = 512 | n = 1024 |
---|---|---|---|---|---|
Erdős–Rényi | RobLPGA | 5.409 | 4.155 | 6.244 | 5.543 |
\(S_{4}\) | 1.532 | 4.974 | 10.517 | 19.174 | |
Watts–Strogatz | RobLPGA | 4.125 | 4.506 | 3.504 | 5.344 |
\(S_{4}\) | 0.934 | 3.096 | 5.596 | 11.323 | |
Bárabasi–Albert | RobLPGA | 3.473 | 3.4257 | 5.848 | 5.27 |
\(S_{4}\) | 0.698 | 1.58 | 5.409 | 11.924 |
Network type | p = 300 | p = 500 |
---|---|---|
ER_128 | {4.592, 0.701} | {6.388, 0.682} |
WS_128 | {4.915, 1.377} | {7.943, 1.356} |
BA_128 | {4.943, 1.93} | {8.299, 1.892} |