Complex network

Complex networks are the backbone of a complex system. They are special networks at the edge of chaos where the degree of connectivity is neither regular nor random.

The most complex networks of the real world are either small-world networks or scale-free networks at the border between regular and random networks, between order and randomness. They can be described by means of mathematics and Graph Theory.

Contents

1 Scale-Free Networks 2 Small-World Networks 3 Common characteristics 4 Researchers and Scientists 5 Links 6 References 7 Books

Scale-Free Networks

A network is named scale-free, if it does not have a certain scale. A network with a single scale is similar to grid: every node has the same degree or the same number of links/edges. In a scale-free network, some nodes have a huge number of connections to other nodes, whereas most nodes have only a few. Typically the degree of connectivity can be described by a power law.

According to Mark Newman in [1], "when the probability of measuring a particular value of some quantity varies inversely as a power of that value, the quantity is said to follow a power law, also known variously as Zipf's law or the Pareto distribution. The distributions of the sizes of cities, earthquakes, solar flares, moon craters, wars and people's personal fortunes all appear to follow power laws".

Scale-free networks and networks which can be described by power-laws are robust against accidental failures but vulnerable to deliberate attacks against hubs and supernodes.

Small-World Networks

A network is called small-world network by analogy with the small-world phenomenon, (popularly known as six degrees of separation). The small world hypothesis, which has been tested in experiments (see The Small World Project), is the idea that two arbitrary people are connected by only six degrees of separation, i.e. the diameter of the corresponding graph of social connections is not much larger than six.

Small-world networks have been described first by Duncan J. Watts and Steven H. Strogatz. They appear to be 'small' because they have a small average and characteristic path length, like random or complete graphs. Yet they can be highly clustered, like regular lattices. They can be found at the edge or boundary between regular networks and random networks, and are created from regular networks through rewiring of a few short cuts.

Common characteristics

Both classes of complex networks, small-world and scale-free networks are very similar. They can be found at the edge of chaos between complete randomness and total order. Small-world networks or graphs emerge through the random rewiring of regular grids or lattices: you add randomness to order. Scale-free networks arise in networks if you add order to randomnes: instead of considering a pure random growth of a network, you consider a random growth with preferential attachment.

The small-world property can be associated with global connectivity and the shortest path length, it arises in regular networks through the addition of random shortcuts. The scale-free property can be associated with local connectivity, it arises in random networks through clustering.

Researchers and Scientists

• L.A.N. Amaral
• Steven Strogatz
• Albert-László Barabási
• Duncan J. Watts
• Mark Newman

Links

• Self-Organized Networks
• Scale-Free and Small-World Networks

References

• L.A.N. Amaral and J.M. Ottino , Complex networks - Augmenting the framework for the study of complex systems, Eur. Phys. J. B 38 (2004) 147-162
• A. Barabasi and E. Bonabeau, Scale-Free Networks, Scientific American, May 2003, 50-59
• K. Wiesenfeld, P. Colet, S.H. Strogatz, Exploring Complex Networks, Nature Vol 410 (2001) 268-276
• D.J. Watts and S. H. Strogatz., Collective dynamics of 'small-world' networks, Nature Vol 393 (1998) 440-442
• M. E. J. Newman Power laws, Pareto distributions and Zipf's law
• M. E. J. Newman The structure and function of complex networks

Books

• Duncan J. Watts, Six Degrees: The Science of a Connected Age, W. W. Norton & Company, 2003, ISBN 0393041425
• Duncan J. Watts, Small Worlds : The Dynamics of Networks between Order and Randomness, Princeton University Press, 2003, ISBN 0691117047
• Albert-László Barabási, Linked: How Everything Is Connected to Everything Else and What It Means, Plume, 2003, ISBN 0452284392