Performance of complex networks: Efficiency and Robustness

Network performance is determined by the interplay of underlying structures and overlying dynamic processes on networks. This thesis mainly considers two types of collective dynamics on networks, spread and transport, which are ubiquitous in our daily lives, ranging from information propagation, disease spreading, to molecular motors on cytoskeleton and urban traffic. Exploring the approaches on optimizing the network performance is the fundamental motivation of this work, which helps to control processes on networks and to upgrade network-based services.

Although the properties of phase transition in Susceptible-Infected-Susceptible (SIS) processes have been investigated intensively, the time-dependent behavior of epidemics is still an open question. This thesis starts with the investigation of the spreading time (Chapter 2), which is the time when the number of infected nodes in the metastable state is first reached, starting from the outbreak of the epidemics. We observe that the spreading time resembles a lognormal-like distribution both for the Markovian and the non-Markovian infection processes.

As a follow-up work of Chapter 2, we identify the fastest initial spreaders with the shortest average spreading time in epidemics on a network, which helps to ensure an efficient spreading (Chapter 3). We show that the fastest spreader changes with the effective infection rate of a SIS epidemic process, which means that the time-dependent influence of a node is usually strongly coupled to the dynamic process and the underlying network. We propose the spreading efficiency as a metric to quantify the efficiency of a spreader and identify the fastest spreader, which is adaptive to different infection rates in general networks.

For maximizing the utility of spread, we introduce induced spreading, which aims to maximize the infection probabilities of some target nodes by adjusting the nodal infection rates (Chapter 4). We assume that the adjustment of the nodal infection rates has an associated cost and formulate the induced spreading for SIS epidemics in networks as an optimization problem under a constraint on the total cost. We address both a static model and a dynamic model for the optimization of the induced SIS spreading. We show that the infection rate increment on each node is coupled to both the degree and the average hops to the target nodes in the static optimization method. In the dynamic method, the effective resistance is a good metric to indicate the minimum total cost for targeting a single node.

The average fraction of infected nodes in the NIMFA steady state, also called the steady-state prevalence, in terms of the effective infection rate can be expanded into a power series around the NIMFA epidemic threshold. Practically, we can faster compute the nodal infection probability of the NIMFA steady-state by the truncated expansion with enough terms and an effective infection rate within the radius of convergence. Thus, we investigate the radius of convergence that validates the Taylor expansion of the steady-state prevalence in Chapter 5. We show that the radius of convergence of the steady-state prevalence expansion strongly depends upon the spectral gap of the adjacency matrix.

The research on the robustness of transport on networks mainly encompasses two robustness assessment approaches, along with their applications in communication networks and freight transport networks, respectively. Network recoverability refers to the ability of a network to return to a desired performance level after suffering malicious attacks or random failures (Chapter 6). We propose a general topological approach and recoverability indicators to measure the network recoverability in two scenarios: 1) recovery of damaged connections and 2) any disconnected pair of nodes can be connected to each other. By applying the effective graph resistance and the network efficiency as robustness metrics, we employ the proposed approach to assess 10 real-world communication networks. For vehicle transport systems, Chapter 7 proposes a robustness assessment for multimodal transport networks. The representation of interdependent networks is an excellent proxy for the structure of multimodal transportation systems. We apply our robustness assessment model to the Dutch freight transport, taking into account three modalities: waterway, road and railway. The node criticality, defined as the impact of a node removal on the total travel cost, resembles a power-law distribution, which implies scale-free property of the robustness against infrastructure disruptions.

Many transport processes have a similar objective that all nodes reach an agreement regarding a certain quantity of interest by exchanging the nodal states with their neighboring nodes, which are described by the consensus model in networks (Chapter 8). The robustness of consensus processes is related to the convergence speed to the stability under external perturbations. The (generalized) algebraic connectivity of a network characterizes the lower-bound of the exponential convergence rate of consensus processes. We investigate the problem of accelerating the convergence of consensus processes by adding links to the network. We propose a greedy strategy for undirected network and further extend our approach to directed networks. Numerical tests verify the better performance of our methods than other metric-based approaches.

This thesis considers two dynamic processes on networks and covers performance analysis and optimizations, by means of problem proposal, theoretical analysis, case study and algorithm designing. The developed concepts related to network efficiency and robustness provide a better understanding of collective dynamics on complex networks. The applicability of our methodologies bridges theoretical network models and realistic applications, as well as demonstrates the promising efficacy of network science.