Directed complex networks and their structure and dynamics under link deletion

Abstract

Complex networks, with their ability to model the essential elements of a system of interacting entities, have become a versatile tool with immense scope for application. Network science, as a tool, has found relevance in studying physical, biological and chemical systems, transport systems, social systems, medicine, finance and risk etc. While there are many different aspects to a complete and systematic study of complex networks, one of the more important properties is their robustness to perturbation. In this thesis, we are particularly interested in those types of perturbations that result in loss of connectivity of the network. We focus our study on the effects of loss of links in directed complex networks. Investigating the performance of a network, when it is subject to loss of links, helps to design precautionary measures, introduce fail-safes and implement alternate solutions, thus resulting in improved overall performance. Alternatively, it can also be used to design effective strategies to maximally disrupt the connectivity in a network. With this very concise motivation, we set out to explore the structural and dynamical response of directed networks to failures (random loss of links) and attacks (targeted removal of links).

The organization of the thesis is as follows: In chapter-1, we provide a brief introduction to the field of complex networks, discuss their wide range of applications and ever-increasing relevance. From local to intermediate to global scales, we define the most important and relevant network properties and their corresponding measures. Based on these properties, we discuss some standard models of network generation, their advantages and limitations. We finish with a brief mention of a couple of dynamical processes taking place on networks.

In chapter 2, we introduce methods, based on degree preserving rewiring (DPR), to tune clustering and degree-correlations in random and scale-free directed networks. They provide null-models to investigate the role of the mentioned properties along with their strengths and limitations. For both clustering and degree-correlations, we first discuss how they get redefined for the case of directed networks. As we tune clustering, we qualitatively analyze the results of rewiring, as a function of the respective topological parameters. In both random and scale-free networks, we fix the parameter values so that they have the same average degree, and then study the effect of topology itself on the rewiring process. We rewire the two types of networks, for both assortative and dissortative correlations, and study the role of topology, as well as the effects of the respective topological parameters. To explain the observations in scale-free networks, we explore the role of 1-node correlations for both assortative and dissortative rewiring. In both topologies, we study the behavior of the limiting value of dissortative degree-correlation, as a function of parameters of the networks.

Besides the intended purpose of tuning network properties, the proposed mechanisms are also used as a tool to reveal structural relationships and topological constraints. We take a deeper look at the effects of DPR mechanisms that we have introduced and treat the process of rewiring as exploring the space of second-order maximally random directed graphs. Based on this, we make analytic arguments to show that the DPR mechanisms, designed to tune specific type of correlations, also uniquely affect the clustering coefficients. We provide numerical corroboration and present explanations for the same. Consequent to the explanation, we expect to see changes in sizes of the connected components, specific to the type of correlations being tuned.

In chapter 3, we look at the structural response of directed networks to link deletion. We conduct a systematic and detailed analysis of the robustness of the networks under random and targeted removal of links. We work with a set of network models of random and scale-free type, generated with specific features of clustering and assortativity. Besides random deletion, we define strategies based on global (Edge Betweenness Centrality) and local (Edge Degree) properties and use them to breakdown the networks by targeted removal of links. The robustness of the networks to the sustained loss of links is studied in terms of the sizes of the connected components and the inverse path lengths. The effects of clustering and 2-node degree correlations, on the robustness to attack, are also explored. We provide specific illustrations of our study on three real-world data-sets: protein-protein interaction networks, road-network based on the city of Austin TX and the worldwide airport network.

In chapter 4, we explore the dynamical response to link deletion. We study the effects of random and weighted link deletion on a 1-to-1 transmission process, taking place simultaneously on the network. By characterizing the performance of the transmission process in terms of the average number of successful transmissions and the average transmission time, we analyze the results, first by topology and then by strategy, and also study the role of assortative and dissortative correlations. We provide qualitative arguments to show that the behaviours of probability of successful transmission and normalized transmission times are captured by the fractional size of the strongly connected component (SCC) and the average path-length of the SCC respectively, and also provide numerical evidence. In the context of a specific road-network, derived from road intersections in the city of Barcelona, we study the roles of various process parameters like request-rate, probability of transmission and probability of deletion, and interpret the results in the context of traffic flow. We conclude the chapter by proposing and detailing a method, based on weighted selection of nodes, to partially mitigate the loss of transmission.

In the concluding chapter, we compile all the important results from earlier chapters and present them in a broader perspective.