Graph Theory and Small-World Networks
Dynamical networks constitute a very wide class of complex and adaptive systems. Examples range from ecological prey–predator networks to the gene expression and protein networks constituting the basis of all living creatures as we know it. The brain is p
- PDF / 1,018,473 Bytes
- 40 Pages / 439.36 x 666.15 pts Page_size
- 79 Downloads / 238 Views
Graph Theory and Small-World Networks
Dynamical networks constitute a very wide class of complex and adaptive systems. Examples range from ecological prey–predator networks to the gene expression and protein networks constituting the basis of all living creatures as we know it. The brain is probably the most complex of all adaptive dynamical systems and is at the basis of our own identity, in the form of a sophisticated neural network. On a social level we interact through social networks, to give a further example – networks are ubiquitous through the domain of all living creatures. A good understanding of network theory is therefore of basic importance for complex system theory. In this chapter we will discuss the most important concepts of graph1 theory and basic realizations of possible network organizations.
1.1 Graph Theory and Real-World Networks 1.1.1 The Small-World Effect Six or more billion humans live on earth today and it might seem that the world is a big place. But, as an Italian proverb says, “Tutto il mondo e´ paese” – “The world is a village”.
The network of who knows whom – the network of acquaintances – is indeed quite densely webbed. Modern scientific investigations mirror this century-old proverb. Social Networks Stanley Milgram performed a by now famous experiment in the 1960s. He distributed a number of letters addressed to a stockbroker in Boston to a random selection of people in Nebraska. The task was to send these letters to the addressee (the stockbroker) via mail to an acquaintance of the respective sender. In other words, the letters were to be sent via a social network.
1
Mathematicians generally prefer the somewhat more abstract term “graph” instead of “network”.
C. Gros, Complex and Adaptive Dynamical Systems, DOI 10.1007/978-3-642-36586-7 1, © Springer-Verlag Berlin Heidelberg 2013
1
2
1 Graph Theory and Small-World Networks
1
A
B
2
C
D
3
E
F
4
G
H
I
J
K
H
A B
F
D
G
I
C E
K J
Fig. 1.1 Left: illustration of the network structure of the world-wide web and of the Internet (from Albert and Barab´asi 2002). Right: construction of a graph (bottom) from an underlying bipartite graph (top). The filled circles correspond to movies and the open circles to actors cast in the respective movies (from Newman et al. 2001)
The initial recipients of the letters clearly did not know the Boston stockbroker on a first-name basis. Their best strategy was to send their letter to someone whom they felt was closer to the stockbroker, socially or geographically: perhaps someone they knew in the financial industry, or a friend in Massachusetts. Six Degrees of Separation About 20 % of Milgram’s letters did eventually reach their destination. Milgram found that it had only taken an average of six steps for a letter to get from Nebraska to Boston. This result is by now dubbed “six degrees of separation” and it is possible to connect any two persons living on earth via the social network in a similar number of steps. The Small-World Effect. The “small-world effect” denotes th
Data Loading...
