Abstract
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 networkbased services.
Although the properties of phase transition in SusceptibleInfectedSusceptible (SIS) processes have been investigated intensively, the timedependent 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 lognormallike distribution both for the Markovian and the nonMarkovian infection processes.
As a followup 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 timedependent 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 steadystate 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 steadystate 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 steadystate prevalence in Chapter 5. We show that the radius of convergence of the steadystate 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 realworld 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 powerlaw distribution, which implies scalefree 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 lowerbound 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 metricbased 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.
Although the properties of phase transition in SusceptibleInfectedSusceptible (SIS) processes have been investigated intensively, the timedependent 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 lognormallike distribution both for the Markovian and the nonMarkovian infection processes.
As a followup 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 timedependent 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 steadystate 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 steadystate 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 steadystate prevalence in Chapter 5. We show that the radius of convergence of the steadystate 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 realworld 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 powerlaw distribution, which implies scalefree 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 lowerbound 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 metricbased 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.
Original language  English 

Qualification  Doctor of Philosophy 
Awarding Institution 

Supervisors/Advisors 

Award date  17 Mar 2020 
Place of Publication  Delft 
Edition  1 
Print ISBNs  9789463841 
DOIs  
Publication status  Published  2020 
Keywords
 Complex Networks
 Network Robustness
 Epidemic Spreading
 Transport
 Network Optimization