CiteULike: bigbossman's world

The Small-World Phenomenon: An Algorithmic Perspective

Jon Kleinberg — 2005-01-02T16:34:15-00:00

(# 2000)

Long a matter of folklore, the "small-world phenomenon" -- the principle that we are all linked by short chains of acquaintances -- was inaugurated as an area of experimental study in the social sciences through the pioneering work of Stanley Milgram in the 1960's. This work was among the first to make the phenomenon quantitative, allowing people to speak of the "six degrees of separation" between any two people in the United States. Since then, a number of network models have been proposed as...

Emergence of a Small World from Local Interactions: Modeling Acquaintance Networks

Jörn Davidsen — 2007-11-02T01:52:04-00:00

Physical Review Letters, Vol. 88, No. 12. (March 2002), 128701.

How do we make acquaintances? A simple observation from everyday experience is that often one of our acquaintances introduces us to one of his or her acquaintances. Such a simple triangle interaction may be viewed as the basis of the evolution of many social networks. Here; it is demonstrated that this assumption is sufficient to reproduce major nontrivial features of social networks: short path length; high clustering; and scale-free or exponential link distributions.

Multiscale visualization of small world networks

D Auber — 2005-06-06T20:46:04-00:00

Information Visualization, 2003. INFOVIS 2003. IEEE Symposium on (2003), pp. 75-81.

Many networks under study in information visualization are "small world" networks. These networks first appeared in the study of social networks and were shown to be relevant models in other application domains such as software reverse engineering and biology. Furthermore, many of these networks actually have a multiscale nature: they can be viewed as a network of groups that are themselves small world networks. We describe a metric that has been designed in order to identify the weakest edges in a small world network leading to an easy and low cost filtering procedure that breaks up a graph into smaller and highly connected components. We show how this metric can be exploited through an interactive navigation of the network based on semantic zooming. Once the network is decomposed into a hierarchy of sub-networks, a user can easily find groups and subgroups of actors and understand their dynamics.

Scaling and percolation in the small-world network model

MEJ Newman — 2006-11-02T08:48:38-00:00

(6 May 1999)

In this paper we study the small-world network model of Watts and Strogatz, which mimics some aspects of the structure of networks of social interactions. We argue that there is one non-trivial length-scale in the model, analogous to the correlation length in other systems, which is well-defined in the limit of infinite system size and which diverges continuously as the randomness in the network tends to zero, giving a normal critical point in this limit. This length-scale governs the cross-over from large- to small-world behavior in the model, as well as the number of vertices in a neighborhood of given radius on the network. We derive the value of the single critical exponent controlling behavior in the critical region and the finite size scaling form for the average vertex-vertex distance on the network, and, using series expansion and Pade approximants, find an approximate analytic form for the scaling function. We calculate the effective dimension of small-world graphs and show that this dimension varies as a function of the length-scale on which it is measured, in a manner reminiscent of multifractals. We also study the problem of site percolation on small-world networks as a simple model of disease propagation, and derive an approximate expression for the percolation probability at which a giant component of connected vertices first forms (in epidemiological terms, the point at which an epidemic occurs). The typical cluster radius satisfies the expected finite size scaling form with a cluster size exponent close to that for a random graph. All our analytic results are confirmed by extensive numerical simulations of the model.