Abstract
Failures of systems are ubiquitous, such as the blackouts of electrical systems and road disruptions in transport systems. Understanding the properties of systems can benefit the control of the system and the design of robust systems. Complex networks are widely used to model complex systems. In this dissertation, we explore the performance of complex networks under link or node failures, provide strategies to recover the networks and discover the behaviors of processes spreading on networks. This dissertation comprises three parts, containing seven chapters, including the introduction chapter, five chapters discerning the research contributions, and a conclusion chapter which summarizes the main contributions and gives directions for future work.
Part I of the thesis deals with network robustness and reliability and contains two chapters. In Chapter 2, we investigate the robustness of network controllability, calculated by the minimum fraction of driver nodes required to fully control the networks. Under random and targeted node removals based on in-degree, out-degree, and total degree, we develop analytical methods using generating functions of the in-degree and out-degree distributions to approximate network controllability. Validated on synthetic and real-world networks, we find that analytical methods work well under random node removals and reasonably well for different types of targeted node removals. In Chapter 3, assuming each link has a given operational probability and nodes are always operational, we define controller reachability, which is the probability that each node can reach at least one controller. Using real-world networks, we explore how performance changes as the number of controllers increases from one to five. We propose four placement strategies to place controllers with a fixed number of controllers: the placement strategy based on graph metrics, the greedy placement strategy, and two genetic placement strategies. The placement strategies demonstrate good performance on real-world data.
After a network is degraded, recovering the system and measuring its recovery performance are essential. Therefore, Part II of this thesis studies network recoverability. This part contains two chapters. In Chapter 4, we explore how to approximate the network controllability in case of a random recovery process and how to recover the network controllability efficiently. We propose an analytical method to approximate network controllability under random node additions. The outcomes of our method closely align with numerical simulation results for both synthetic and real-world networks. Furthermore, to recover network controllability efficiently, we find that greedy strategies outperform recovery strategies based on degree centrality or betweenness centrality as well as the random recovery strategy. Chapter 5 investigates recovery strategies after random link failures on power grids. To explore the effectiveness of recovering failed links based solely on topological network metrics, we consider 13 recovery strategies. To evaluate the performance of these proposed strategies, we conducted simulations on three distinct power systems: the IEEE 30, IEEE 39, and IEEE 118 systems. Our results conclude that relying solely on a single metric to develop a recovery strategy is insufficient to restore power grids after link failures. For comparison, recovery strategies that employ greedy algorithms are more effective choices.
Finally, Part III looks into spreading processes on networks. Chapter 6 focuses on exploring the time-dependent behaviors of the ε-SIS model. We find that the prevalence (the average fraction of infected nodes) as a function of time typically exhibits a "two-plateau" behavior. Furthermore, the time-dependent mean-field approximation for the complete graph performs reasonably well for relatively large self-infection rates but completely fails to mimic the typical behavior with small self-infection rates. The observations may explain why absorbing processes are hardly observed in reality, even over long intervals, because of the ignorance of the interplay of nodal self-infection with small self-infection rates and spread over links. Chapter 7 concludes the thesis by summarizing the main contributions and gives directions for future research.
Part I of the thesis deals with network robustness and reliability and contains two chapters. In Chapter 2, we investigate the robustness of network controllability, calculated by the minimum fraction of driver nodes required to fully control the networks. Under random and targeted node removals based on in-degree, out-degree, and total degree, we develop analytical methods using generating functions of the in-degree and out-degree distributions to approximate network controllability. Validated on synthetic and real-world networks, we find that analytical methods work well under random node removals and reasonably well for different types of targeted node removals. In Chapter 3, assuming each link has a given operational probability and nodes are always operational, we define controller reachability, which is the probability that each node can reach at least one controller. Using real-world networks, we explore how performance changes as the number of controllers increases from one to five. We propose four placement strategies to place controllers with a fixed number of controllers: the placement strategy based on graph metrics, the greedy placement strategy, and two genetic placement strategies. The placement strategies demonstrate good performance on real-world data.
After a network is degraded, recovering the system and measuring its recovery performance are essential. Therefore, Part II of this thesis studies network recoverability. This part contains two chapters. In Chapter 4, we explore how to approximate the network controllability in case of a random recovery process and how to recover the network controllability efficiently. We propose an analytical method to approximate network controllability under random node additions. The outcomes of our method closely align with numerical simulation results for both synthetic and real-world networks. Furthermore, to recover network controllability efficiently, we find that greedy strategies outperform recovery strategies based on degree centrality or betweenness centrality as well as the random recovery strategy. Chapter 5 investigates recovery strategies after random link failures on power grids. To explore the effectiveness of recovering failed links based solely on topological network metrics, we consider 13 recovery strategies. To evaluate the performance of these proposed strategies, we conducted simulations on three distinct power systems: the IEEE 30, IEEE 39, and IEEE 118 systems. Our results conclude that relying solely on a single metric to develop a recovery strategy is insufficient to restore power grids after link failures. For comparison, recovery strategies that employ greedy algorithms are more effective choices.
Finally, Part III looks into spreading processes on networks. Chapter 6 focuses on exploring the time-dependent behaviors of the ε-SIS model. We find that the prevalence (the average fraction of infected nodes) as a function of time typically exhibits a "two-plateau" behavior. Furthermore, the time-dependent mean-field approximation for the complete graph performs reasonably well for relatively large self-infection rates but completely fails to mimic the typical behavior with small self-infection rates. The observations may explain why absorbing processes are hardly observed in reality, even over long intervals, because of the ignorance of the interplay of nodal self-infection with small self-infection rates and spread over links. Chapter 7 concludes the thesis by summarizing the main contributions and gives directions for future research.
Original language | English |
---|---|
Qualification | Doctor of Philosophy |
Awarding Institution |
|
Supervisors/Advisors |
|
Thesis sponsors | |
Award date | 25 Sept 2024 |
Print ISBNs | 978-94-6366-906-1 |
DOIs | |
Publication status | Published - 2024 |
Keywords
- Complex Networks
- Network Robustness
- Network Reliability
- Network Recoverability
- Spreading