Robustness of complex networks

Abstract

A complex network is a set of items, named vertices or nodes, with connections between them, called edges or links. Complex networks describe a wide range of systems in nature and society (Albert and Barabasi 2002). Networks (or graphs) can describe real world systems such as the Internet, the World Wide Web, social networks (of acquaintance, organizational among individuals, work relationship, sexual relationship, and so on), networks of business relations between companies, neural networks, metabolic networks, food webs or other ecological networks, distribution networks such as roads, airlines, blood vessels or postal delivery routes, networks of citations between papers, and others (Newman 2003). Since the network structure is useful to shape a very large range of real world systems, it has been extensively studied in many field of science in the last twenty years. The study of complex networks analyze the properties of these systems, such as the degree distribution, the connectivity, the diameter, the clustering coefficient, and so on; these properties and the network structure are then compared with the aim to describe more general patterns and functioning of the real systems (Albert and Barabasi 2002; Newman 2003). A fundamental issue concerning the functioning of a complex network is the robustness of the overall system to the failure of its constituent parts (Albert et al. 2000; Holme 2004). The integrity and the functioning of the network can be addressed by analyzing how the network structure changes as vertices or links are removed. To understand how the networks functioning changes with the removal of the vertices is the same to understand the degree of system robustness. Many works have considered how the structure of complex networks change as vertices are removed uniformly at random, in decreasing order of their degree, or in decreasing order of their betweenness centrality (Albert et al 2000; Albert and Barabasi 2002; Holme 2004). The robustness of the network is an interdisciplinary field ranging from social and Internet network, to biological networks as food webs. For these reasons, the robustness of real-world complex networks, such as Internet, electrical power grids, airline routes, ecological and biological networks to “node failure” (i.e. node malfunctioning or removal) is a topic of fundamental importance for both theoretical and applied network science. Node failure can cause the fragmentation of the network, which has consequences in terms of system performance, properties, and architecture, such as transportation properties, information delivery efficiency and the reachability of network components (i.e. ability to go from node of the network to another). In ecology, food webs have been central to ecological research for decades and the study of the robustness of food webs to species loss is increasingly relevant for species and ecosystem conservation (Dunne et al. 2002; Allesina and Bodini 2004). The loss of a species in ecosystems (primary extinction) can cascade into further extinctions (secondary extinctions), as consumers’ persistence depends on the persistence of their resources. Many theoretical and empirical studies have investigated how food web properties, such as modularity, degree distribution (i.e. the probability distribution of the number of trophic connections of species), presence and distribution of keystone species may influence the pattern of secondary extinctions in ecosystems as well as food web robustness (Dunne et al. 2002; Jordan et al. 2003; Solé and Montoya 2001). In the vast majority of studies on extinction patterns in food webs, a species is assumed to go extinct after a primary extinction when is left without any resources to exploit (Allesina and Bodini 2004; Allesina and Pascual 2009; Dunne et al. 2002; Solé and Montoya 2001). This thesis investigates the robustness of real and model networks. In the first chapter “Efficiency of attack strategies on complex model and real-world networks” we analyse the robustness of physics networks models and real world networks introducing new strategies to remove nodes. In the second chapter “Optimization strategies with resource scarcity: from immunization of networks to the traveling salesman problem”, we analyse the immunization process in complex networks introducing the problem of resource scarcity. In the third chapter “Robustness of ecological networks” we study the robustness of ecological networks focusing on empirical food webs with a new stochastic methods to select species to remove. Each chapter starts with a summary paragraphs that describes the research focus and the main results.