Next: Network manipulation and Novelty Creation
Up: Table of contents
Previous: Networks

Traditionally, physical networks are defined on real finite dimensional regular lattices, or by mean field fully connected graphs, or random graphs. Problems such as those of interest to participants of this action require a systematic study of dynamic networks. The subject has gained impetus recently from the realisation that two universal graphs seem to represent a diverse range of networks. Many systems have now been identified that display so-called 'small-world phenomena', These systems have a high degree of local clustering, reminiscent of finite dimensional systems, combined with a small finite path length between any pair of vertices, reminiscent of highly connected random networks. Systems that display this property include many friendship and social networks, and power line networks such as those for high voltage transmission across countries. Some researchers have also sought to apply these ideas to 'explain' recent Brazilian election results and UK football results.

Similarly, many systems have been identified where the degree distribution, the probability that a node in the network is connected to k other nodes, decays as a power law. This generic observation is supported by observations from, for example, the World Wide Web, where pages are the vertices and hyperlinks are the edges between them; the graph of film actors, where actors are the vertices and two actors are connected when they have appeared in a film together; large complex network of scientific citations, in which the vertices are papers and the edges are the directed links to the papers cited within an article. This example has shown that the probability that a paper is cited k times (representing the connectivity of the paper within the network) follows a power law.

Simple models have been developed to understand these two graphs. Watts and Strogatz have developed models that interpolates between a regular ordered graph and a random graph. In a region between these two extremes, their model displays the small-world phenomenon. Barabási and Albert recognised that all networks having a power law connectivity distribution grow and display preferential attachment, with a higher probability to be linked to a vertex that already has a large number of connections. As a result they built a scale free model in which a vertex is added at each time step, and is connected to a vertex with a rate proportional to its connectivity. This model has a power law connectivity distribution, with an exponent between 2 and 3, in agreement with empirical studies of a range of networks.

From empirical studies of real networks we know that scale invariance and local ordering are important. We know that the mechanisms of network development can profoundly affect its large scale topology. We do not know the underlying principles that govern network growth. In the same way as symmetry principles and conservation laws allow us to define universality classes in critical phenomena, we need to identify the underlying principles of network growth, in order to categorize networks that appear in nature, technology and social sciences.

Consequently one of the main objectives is to uncover the basic ingredients that determine network topology. Investigating both the concept of universality and the mechanisms that determine scaling exponents will do this. A second objective will be to investigate the various dynamical rules on these networks and the interplay between these rules and the geometry. The World Wide Web is a manifestation of the largest global social network for which quantitative topological information is currently available and represents an important test bed for ideas about growing networks.

Next: Network manipulation and Novelty Creation
Up: Table of contents
Previous: Networks