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.@en

Water Distribution Networks (WDNs) are critical infrastructures that ensure a continuous supply of safe water to homes. In the face of challenges, like water scarcity, establishing resilient networks is imperative, especially in regions vulnerable to water crises. This study evaluates the resilience of network designs through graph theory, including its hydraulic feasibility using EPANET software, an aspect often overlooked. Novel mathematical algorithms, including Resilience by Design (RbD) and Resilience-strengthening (RS) algorithms, provide cost-effective and resilient network designs, even with budget constraints. A novel metric, Water Availability (WA), is introduced to offer a comprehensive measure of network resilience, thereby addressing ongoing discrepancies in resilience evaluation methods. Practical benefits are illustrated through a case study in which a resilient-by-design reclaimed water network is created, and an existing equivalent non-resilient network is improved. The resilient-by-design network demonstrates remarkably better results compared to the equivalent non-resilient design, including up to a 36 % reduction in the probability of service disruptions and a nearly 65 % decrease in the annual average unserved water due to service disruptions. These findings underscore the enormous advantages of a resilience-focused network design approach. When compared to the equivalent non-resilient design, the resilient-by-design network generated effectively safeguards up to a significant 91,700m³ of water from the impacts of water disruption events over a 50-year operational period. In addition, the resilient-by-design WDN solution incurs a subtle decrease in overall costs compared to consuming tap water from the drinking WDN baseline over a 50-year operational period. These findings highlight the cost-effectiveness of the approach, even offering financial benefits. This paper builds on our previous research by expanding its scope to include resilience considerations, providing algorithms that can be easily adapted from reclaimed to drinking WDNs. Ultimately, we contribute to the enhancement of water resource management and infrastructure planning in ever-evolving urban environments.

@en

We propose an analytical approach to approximate the average two-Terminal reliability (ATT R) for graphs where a fraction of the nodes is removed. The approximation is based on the generating function of the network's degree distribution under random node removals and stochastic degree-based node removals. Through validation on synthetic graphs, including Erdos Renyi random graphs and Barabasi-Albert graphs, as well as four real-world networks from the Internet Topology Zoo, we observe that the analytical method effectively approximates the average two-Terminal reliability under random node removals for synthetic graphs. In the case of real-world graphs under random and stochastic degree-based node removals or synthetic graphs under stochastic degree-based node removals, the analytical ap-proximation yields reasonably accurate results when the fraction of removed nodes is small, specifically less than 10%, provided that the initial analytical approximation closely aligns with the real ATT R values.

@en

In this paper we investigate the controller placement problem on networks using controller reachability as the network performance metric. This metric is defined as the probability that each node can reach at least one controller, given that each link is operational with a fixed probability. By exploring placements for more than 100 real-world networks and by varying the number of controllers from two to five, we find that controller reachability varies greatly with different placements. Obviously, increasing the number of controllers increases the controller reachability. However, the extent of this increase depends on the strategy with which the controllers are placed. The findings indicate that efficient controller placement strategies should be developed to ensure good network performance. In this research, we propose four controller placement strategies. One strategy is based on topological network metrics: node degree and path length between controllers and nodes. The other three heuristic strategies are the greedy algorithm, the classic genetic algorithm and the heuristic genetic algorithm. By validating strategies on real-world networks, we find that all four strategies work well to solve the controller placement problem with respect to controller reachability.@en

Network controllability is a critical attribute of dynamic networked systems. Investigating methods to restore network controllability after network degradation is crucial for enhancing system resilience. In this study, we develop an analytical method based on degree distributions to estimate the minimum fraction of required driver nodes for network controllability under random node additions after the random removal of a subset of nodes. The outcomes of our method closely align with numerical simulation results for both synthetic and real-world networks. Additionally, we compare the efficacy of various node recovery strategies across directed Erdös-Rényi (ER) networks, swarm signaling networks (SSNs), and directed Barabàsi Albert (BA) networks. Our findings indicate that the most efficient recovery strategy for directed ER networks and SSNs is the greedy strategy, which considers node betweenness centrality. Similarly, for directed BA networks, the greedy strategy focusing on node degree centrality emerges as the most efficient. These strategies outperform recovery approaches based on degree centrality or betweenness centrality, as well as the strategy involving random node additions.

@en

For this study, we investigated efficient strategies for the recovery of individual links in power grids governed by the direct current (DC) power flow model, under random link failures. Our primary objective was to explore the efficacy of recovering failed links based solely on topological network metrics. In total, we considered 13 recovery strategies, which encompassed 2 strategies based on link centrality values (link betweenness and link flow betweenness), 8 strategies based on the products of node centrality values at link endpoints (degree, eigenvector, weighted eigenvector, closeness, electrical closeness, weighted electrical closeness, zeta vector, and weighted zeta vector), and 2 heuristic strategies (greedy recovery and two-step greedy recovery), in addition to the random recovery strategy. 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 findings revealed several key insights: Firstly, there were notable variations in the performance of the recovery strategies based on topological network metrics across different power systems. Secondly, all such strategies exhibited inferior performance when compared to the heuristic recovery strategies. Thirdly, the two-step greedy recovery strategy consistently outperformed the others, with the greedy recovery strategy ranking second. Based on our results, we conclude that relying solely on a single metric for the development of a recovery strategy is insufficient when restoring power grids following link failures. By comparison, recovery strategies employing greedy algorithms prove to be more effective choices.@en

Higher Education Institutions (HEIs) play an increasingly significant role in the practice of sustainability. For HEIs in their early stages of sustainability, they are still in need of sustainable assessment tools (SATs) that are suitable for their local context and also lead international sustainable development. The purpose of this paper is to develop a two-hierarchy sustainability assessment tool (THSus) for Chinese higher education institutions, including a quick analysis tool (QAT) and an in-depth benchmarking tool (IBT). The QAT provided a general overview of campus sustainability for HEIs to initiate initial actions and screen cases for the IBT. The IBT then provides more targeted analysis to plan long-term strategic changes. Based on the analysis of HEI cases, a 34-person Chinese research team was enlisted to discuss and select characteristics to formulate THSus. Indicators and weightings were developed according to the tool’s purpose and applied to 15 cases to test its effectiveness. Results showed that THSus is suitable for systematically analyzing campus issues, particularly in research areas. It offers a regional solution for Chinese campuses that is adaptable and considers the comprehensive core of sustainability.@en

Network controllability and its robustness has been widely studied. However, analytical methods to calculate network controllability with respect to node removals are currently lacking. This paper develops methods, based upon generating functions for the in- and out-degree distributions, to approximate the minimum number of driver nodes needed to control directed networks, during random and targeted node removals. By validating the proposed methods on synthetic and real-world networks, we show that our methods work very well in the case of random node removals and reasonably well in the case of targeted node removals, in particular for moderate fractions of attacked nodes.

@en

Network controllability and its robustness have been widely studied. However, analytical methods to calculate network controllability with respect to node in- and out-degree targeted removals are currently lacking. This paper develops methods, based on generating functions for the in- and out-degree distributions, to approximate the minimum number of driver nodes needed to control directed networks, during node in- and out-degree targeted removals. By validating the proposed methods on synthetic and real-world networks, we show that our methods work reasonably well. Moreover, when the fraction of the removed nodes is below 10% the analytical results of random removals can also be used to predict the results of targeted node removals.@en

We introduce a Markov Modulated Process (MMP) to describe human mobility. We represent the mobility process as a time-varying graph, where a link specifies a connection between two nodes (humans) at any discrete time step. Each state of the Markov chain encodes a certain modification to the original graph. We show that our MMP model successfully captures the main features of a random mobility simulator, in which nodes moves in a square region. We apply our MMP model to human mobility, measured in a library.

@en

A nearly universal trend in science today is the prominence of ever-increasing collaborative teams. Hence, identifying the relative credit due to each collaborator of published studies is of high significance. Although numerous methods have been employed to address this issue, allocating credit to all co-authors of new papers remains challenging. To address this cold-start issue, we introduce a credit allocation algorithm based on the co-citing network that captures the co-authors' shared credit of a multi-authored publication. Using the American Physical Society publication data, we validate the method by examining papers by Nobel laureates. Accordingly, we perform many experiments to demonstrate that the proposed method can be implemented on academic papers in any period after publication with a significantly higher degree of accuracy and robustness than the existing algorithms applied to new papers. This method enables us to explore the universal credit evolution pattern of scientific elites. Importantly, by testing the relation between an author's credit and authorship byline, we observe that the first authors of papers are currently assigned less credit than in the early days with respect to physics. With collaboration and a large team set to dominate the agenda of the current science system, our study provides a more effective method for allocating early credit to co-authors of a paper, which may be beneficial to various academic activities, including faculty hiring, funding, and promotion decisions.

@en

The average fraction of infected nodes, in short the prevalence, of the Markovian ɛ-SIS (susceptible-infected-susceptible) process with small self-infection rate ɛ>0 exhibits, as a function of time, a typical "two-plateau" behavior, which was first discovered in the complete graph KN. Although the complete graph is often dismissed as an unacceptably simplistic approximation, its analytic tractability allows to unravel deeper details, that are surprisingly also observed in other graphs as demonstrated by simulations. The time-dependent mean-field approximation for KN performs only reasonably well for relatively large self-infection rates, but completely fails to mimic the typical Markovian ɛ-SIS process with small self-infection rates. While self-infections, particularly when their rate is small, are usually ignored, the interplay of nodal self-infection and spread over links may explain why absorbing processes are hardly observed in reality, even over long time intervals.

@en