Chapter 1
Introduction

1.1 Background and Motivation

Between two randomly selected persons in the world, roughly how many friends are there connecting them together? When searching from one webpage to another through the World Wide Web (WWW), how many clicks are needed on average? How can computer viruses propagate so fast and so wide through the Internet? How are people infected by epidemics such as AIDS, SARS, and Avian Influenza all over the world? How do rumors spread in human societies? How does a regional financial recession trigger a global economic crisis? How does an electric power blackout emerge from a small local system failure through the huge-scale power grid? How can the human brain work so efficiently while every brain cell is relatively so simple? . All these seemingly different issues have something to do with "networks" - Internet, WWW, social relationship networks, viruses and rumors propagation networks, economic trading and competition networks, power and traffic flow networks, wired and wireless communication networks, biological neural networks, ecosystem networks, and so on. Noticeably, and most important above all, these apparently different networks have a lot in common.

Since the 1990s, the rapid growth of the Internet as an icon of the high-tech era has led our life to an age of networks. The influence of various complex and dynamical networks is currently pervading all kinds of sciences, ranging from physical to biological, even to social sciences. Its impact on modern engineering and technology is prominent and will be far-reaching. There is no doubt that we are living in a networked world today. On the one hand, networks bring us convenience and benefits, improve our efficiency of work and quality of life, and create tremendous advantages and opportunities which we never had before. On the other hand, however, networks also generate harm and damage to nature and human societies, typically with epidemic spreading, computer virus propagation, and power blackouts, to name just a few. Therefore, the increasing demand for networks and networking also requires a correct view and a serious investigation of the complex properties of various networks and the dynamic mechanisms of networking. For a long time in history, studies of communication networks, power networks, biological networks, economic networks, social networks, etc., were carried out separately and independently. However, recently there has been some rethinking of the general concept and theory of complex dynamical networks towards a better understanding of the intrinsic relations, common properties and shared features of all kinds of networks in the real world, which are not isolated but actually networked together - network of systems and, more generally, network of networks. The new intention and desire of studying the fundamental properties and dynamical behaviors of most if not all complex networks, both qualitatively and quantitatively, is important and timely, although very challenging technically. The current research along this line has been considered as a "new science of networks" [1, 2], or network science and engineering, and has become overwhelming today.

Life science is perhaps the most exciting revolutionary area of scientific research in this new century. The mainstream of research in life science in the last century was reductionism-based molecular biology. The fundamental principle of reductionism is that, within different levels of the structure of a biosystem, high-level dynamical behaviors are completely determined by those at the lower levels. There was a common belief that if the individual basic ingredients of life (e.g., DNA, RNA and proteins) could be well understood, then the activities and behaviors of cells at the higher level could be comprehended, while the interactions among these basic elements even among molecules could be neglected. Yet, this traditional reductionism has been seriously challenged at the beginning of the new century due to the many significant discoveries of the importance and essence of networking interactions and interactive dynamics between different levels of life structure and among large numbers of tiny ingredients. Barabási pointed out [3]: "Reductionism, as a paradigm, is expired, and complexity, as a field, is tired. Data-based mathematical models of complex systems are offering a fresh perspective, rapidly developing into a new discipline: network science."

All these have led to a new paradigm of network science, and more recently engineering and technology as well, not just about biology but literally about almost everything.

A network is a diagrammatical representation of some physical system or structure. A network consists of some nodes (vertices) connected by some edges (links) in a certain topology (structure). A graph, on the other hand, is a mathematical notion that represents only the structure of a network without physical meanings. Throughout the textbook, however, these two terms are often used for descriptive convenience without precise distinction. Likewise, the terms of structure and topology of a network or a graph are often arbitrarily used without distinction.

Real-work networks are generally complex, and the complexity of networks may be viewed from different perspectives:

1. Structural complexity: A network usually appears structurally complicated, which may even be seemingly messy and disordered (Figure 1.1). The network topology (i.e., structure) may vary in time (e.g., the WWW has new webpages to join and old websites removed everyday). Moreover, the edge connections among nodes may be directed and weighted (e.g., brain cells can be stimulated or restrained and the connections among cells can be strong or weak).
2. Node-dynamic complexity: A node in a network can be a dynamical system, which may have bifurcating and even chaotic behaviors (e.g., gene networks and Josephson lattices, which have dynamically evolving nodes). Moreover, a network may have different kinds of nodes (e.g., a power grid has electric generators and also has loads such as motors and machines).
3. Mutual interactions among various complex factors: A real-world network is typically affected by many internal and external factors (e.g., if the coupled brain cells are repeatedly excited by certain stimuli then their connections will be strengthened, which is considered the basic reason for learning and memorization). Furthermore, the close relations among networks or subnetworks make the already-complicated behaviors of each of them become much more complex and intrinsic (e.g., the blackout of a huge-scale power grid may lead to chain reactions in human lives and industrial productions, which may also slowdown the activities of other related networks such as traffic, communication and financial transactions). These are referred to as interdependent networks, which have received increasing attention recently.

Figure 1.1 Three illustrative graphs with complex structures (from the Internet): (a) Illustrative graph of a social relationship structure in Canberra, Australia (Alden S. Klovdahl, Australian National University); (b) illustrative graph of some IP addresses on the Internet (William R. Cheswick, Lumeta Corporation, New Jersey, USA); (c) illustrative graph of interactions among proteins (Hawoong Jeong, Korea Advanced Institute of Science and Technology)

In the intensive study of nonlinear science and dynamical systems, on the other hand, networked systems have been one of the focal topics for research since the mid-twentieth century. However, most such coupled dynamical systems were placed in a fixed and regularly connected network model for investigation, where the main interest was the complexity caused by the node dynamics but not that by the network topology. Typical examples of this type are coupled map lattice (CML) [4] and cellular neural (or nonlinear) networks (CNN) [5], which can generate rich spatiotemporal patterns. By assuming a network with a regular topology, one can focus on the effects of the node dynamics on the collective behaviors of the network in interest, setting aside the troublesome influence of the network structure. Moreover, the networked elements in a regular topology can be easily implemented by integrated circuits, which is a main concern in commercial applications of networked devices, systems and infrastructures.

1.2 A Brief History of Complex Network Research

1.2.1 The Königsburg Seven-Bridge Problem

Complex network research has a long history. The recent study of complex networks has directed most interests to the modeling and understanding of various complex networks, especially the relations between the complexity of the network topology and the behaviors of the network dynamics.

To describe the common properties and characteristic features of different types of networks, a rigorous and efficient analytic tool is needed, which has been introduced in the form of graph theory in mathematics. A network can be viewed as a graph consisting of nodes connected by edges according to a certain rule or form, in which the nodes and edges do not necessarily have physical meanings in the discussion of graphs.

Representing a physical problem by a graph and then solving it by mathematical analysis and computation is not a new idea. This approach can be traced back to as early as the eighteenth century when the great mathematician Leonhard Euler (1707-83) studied and solved the famous...