CiteULike: Tag smallworldvis

Complexity vs stability in small-world networks

Sitabhra Sinha — 2004-11-22T00:17:30-00:00

(24 July 2004)

According to the May-Wigner stability theorem, increasing the complexity of a network inevitably leads to its destabilization, such that a small perturbation will be able to disrupt the entire system. One of the principal arguments against this observation is that it is valid only for random networks, and therefore does not apply to real-world networks, which presumably are structured. Here we examine how the introduction of small-world topological structure into networks affect their stability. Our results indicate that, in structured networks, the parameter values at which the stability-instability transition occurs with increasing complexity is identical to that predicted by the May-Wigner criteria. However, the nature of the transition, as measured by the finite-size scaling exponent, appears to change as the network topology transforms from regular to random, with the small-world regime as the cross-over region. This behavior is related to the localization of the largest eigenvalues along the real axis in the eigenvalue plain with increasing regularity in the network.

Energy models for drawing clustered small-world graphs

A Noack — 2005-06-06T20:44:45-00:00

(2003)

We introduce energy models for drawing clustered small-world graphs.

Collective dynamics of 'small-world' networks.

DJ Watts — 2004-11-22T00:17:30-00:00

Nature, Vol. 393, No. 6684. (4 June 1998), pp. 440-442.

Networks of coupled dynamical systems have been used to model biological oscillators, Josephson junction arrays, excitable media, neural networks, spatial games, genetic control networks and many other self-organizing systems. Ordinarily, the connection topology is assumed to be either completely regular or completely random. But many biological, technological and social networks lie somewhere between these two extremes. Here we explore simple models of networks that can be tuned through this middle ground: regular networks 'rewired' to introduce increasing amounts of disorder. We find that these systems can be highly clustered, like regular lattices, yet have small characteristic path lengths, like random graphs. We call them 'small-world' networks, by analogy with the small-world phenomenon (popularly known as six degrees of separation. The neural network of the worm Caenorhabditis elegans, the power grid of the western United States, and the collaboration graph of film actors are shown to be small-world networks. Models of dynamical systems with small-world coupling display enhanced signal-propagation speed, computational power, and synchronizability. In particular, infectious diseases spread more easily in small-world networks than in regular lattices.

Multiple Scales in Small-World Graphs

Rajesh Kasturirangan — 2005-06-06T20:08:08-00:00

(5 April 1999)

Small-world architectures may be implicated in a range of phenomena from disease propagation to networks of neurons in the cerebral cortex. While most of the recent attention on small-world networks has focussed on the effect of introducing disorder/randomness into a regular network, we show that that the fundamental mechanism behind the small-world phenomenon is not disorder/randomness, but the presence of connections of many different length scales. Consequently, in order to explain the small-world phenomenon, we introduce the concept of multiple scale graphs and then state the multiple length scale hypothesis. Multiple scale graphs form a unifying conceptual framework for the study of evolving graphs. Moreover, small-world behavior in randomly rewired graphs is a consequence of features common to all multiple scale graphs. To support the multiple length scale hypothesis, novel graph architectures are introduced that need not be a result of random rewiring of a regular graph. In each case it is shown that whenever the graph exhibits small-world behavior, it also has connections of diverse length scales. We also show that the distribution of the length scales of the new connections is significantly more important than whether the new connections are long range, medium range or short range connections.

Small-world phenomena and the dynamics of information

J Kleinberg — 2005-06-06T20:05:10-00:00

(2001)

Introduction The problem of searching for information in networks like the World Wide Web can be approached in a variety of ways, ranging from centralized indexing schemes to decentralized mechanisms that navigate the underlying network without knowledge of its global structure. The decentralized approach appears in a variety of settings: in the behavior of users browsing the Web by following hyperlinks; in the design of focused crawlers [4, 5, 8] and other agents that explore the Web's links...

The Small World Web

Lada Adamic — 2005-06-06T20:03:30-00:00

No. 1696. (1999), pp. 443-452.

I show that the World Wide Web is a small world, in the sense that sites are highly clustered yet the path length between them is small. I also demonstrate the advantages of a search engine which makes use of the fact that pages corresponding to a particular search query can form small world networks. In a further application, the search engine uses the small-worldness of its search results to measure the connectedness between communities on the Web.

Analysis and Visualization of Social Networks

Dorothea Wagner — 2005-06-06T20:53:10-00:00

Lecture Notes in Computer Science, Vol. 2647 (January 2003), pp. 261-266.

Social network analysis is a subdiscipline of the social sciences using graph-theoretic concepts to understand and explain social structure. We describe the main issues in social network analysis. General principles are laid out for visualizing network data in a way that conveys structural information relevant to specific research questions. Based on these innovative graph drawing techniques integrating the analysis and visualization of social networks are introduced.

Interactive Visualization of Small World Graphs

Frank van Ham — 2005-06-06T20:46:55-00:00

(2004), pp. 199-206.

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...

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.