Analysis of Complex Networks

4.1 Introduction

The best way to understand how things work is by understanding their structures [1]. Complex networks are not an exception [2]. To understand why some networks are more robust than others, or why the propagation of a disease is faster in one network than in another, it is necessary to understand how these networks are organized [3–5]. A complex network is a simplified representation of a complex system in which the entities of the system are represented by the nodes in the network and the interrelations between entities are represented by means of the links joining pairs of nodes [3–5]. In analyzing the architecture of a complex network we are concerned only with the topological organization of these nodes and links. That is to say, we are not concerned with any geometric characteristic of the systems we are representing by these networks but only with how the parts are organized or distributed to form the whole system. Some of these topological characteristics of a network can be evident by simple visual inspection. This is particularly easy when the networks (graphs) are small. For instance, the first two graphs displayed below do not contain cycles, i.e., they are trees. The first of them is simply a linear chain and the second a star. The third and fourth graphs are cyclic. The third graph is the cycle of four nodes, C₄, and the last is a graph having a connection between every pair of nodes, i.e., the complete graph K₄ [6]. All these graphs are connected, ...