ABSTRACT
Complex networks are ubiquitous. In biological systems, the brain is a network of neurons connected by synapses, the cardiovascular system is a vast network of veins and arteries, the foodchain is a vast interconnected web of predators and prey, within a single cell, the complex inter-reaction of various chemical actions and signals serves as a dynamic cellular communication system; and, disease transmission between individuals follows specific infection pathways which characterise the spread of an infection. The science of complex networks has arisen from the mathematical field
of graph theory. In graph theory (and hence in complex network science), a network (or graph) is a set of nodes connected by edges. The nodes may represent individual neurons and the edges the synapses connecting them. Or, in disease modelling, the nodes are (infected) individuals and the edges are infection pathways. One of the earliest examples of such mathematical modelling with a network is due to Leonard Euler (at least according to Wikipedia1). In the city of Kaliningrad (which once was known as Ko¨nigsberg), there are (or were, in 1735) seven bridges connecting both banks of the Pragel River and two islands. Is it possible to construct a walk through the city crossing each bridge once and only once? Euler constructed a simple network and showed that no such path existed (since more than two nodes in the network had an odd number of links). Euler’s transformation of the topography of Ko¨nigsberg into a network is depicted in Fig. 10.1. Figure 10.1 illustrates the reduction of a physical problem to representation
as a network, and then the further reduction of that network to a matrix encoding the connectivity information between nodes in the network. The Adjacency Matrix Aij is defined as follows: element aij is 1 if nodes i and j are connected, and zero otherwise. Of course, in the Ko¨nigsberg bridge problem there is, in some cases, more than one bridge connecting two landmasses, and so the definition in Fig. 10.1 is generalised to also encode this information
Figure 10.1: The seven bridges of Ko¨nigsberg. The upper panel depicts the north and south bank of the river Pragel, together with the two islands and the seven bridges. In the lower panels this is reduced to a network of four nodes and seven links. The nodes correspond to the four landmasses and the links to the seven bridges. Finally, we represent this as an adjacency matrix: an n in row i column j indicates that landmass i is linked with landmass j by n distinct bridges, and 0 indicates that there are no bridges joining these landmasses.
