Small world networks

When studying small world networks, one might be curious about the mechanism which can generate such a network and which is usually used in order to carry out various numeric simulations. When discussing random networks, it is obvious that large numbers of different networks can be generated by simply flipping a coin (of probability p) for each potential edge, or alternatively, selecting a random K pairs of nodes. For scale-free networks, we have mentioned the “Rich Get Richer” model for network generation.

However, when it comes to small world networks, another method must be developed. After all, most of these real-world networks are neither entirely regular nor entirely random. The reality is that people usually know their neighbors, but their circle of acquaintances may not be confined to those who live right next door, as the lattice model would imply. On the other hand, cases, like links among Web pages on the World Wide Web, were certainly not created at random, as the Erdos-Renyi process would expect. Aiming to describe the transition from a regular lattice to a random graph, Watts and Strogatz introduced an interesting small-world network model (“Collective dynamics of ‘small world’ networks”, Watts, Strogatz, Nature, 1998), that can be described as follows:

Begin with the nearest neighbor-coupled network which consists of N nodes arranged in a ring, wherein each node i is adjacent to its neighbor nodes, i = 1, 2, · · · , K/2, with K being even. Then, randomly rewire each edge of the network with probability p; varying p in such a way that the transition between order (p = 0) and randomness (p = 1) can be closely monitored.

The following example is taken from “Complex Networks: Small-World, Scale-Free and Beyond“, by Wang and Chen, IEEE Circuits and Systems Magazine, 2003:

In this completely regular friendship network (left picture), people are friends with only their four nearest neighbors. The network is highly cliquish, and any two people are, on average, many degrees apart. Rewiring some of the edges at random, a small-world network is received (middle picture), where people still know four others on average, but a few have distant friends. The network is still highly cliquish, but the average degree of separation is small. Continue the random rewiring process we finally get a random network (right picture), where everyone still knows four others on average, but friends are scattered; few people have many friends in common, and pairs are, on average, only a few degrees apart.

Now that we know what small world networks are, and how they can be generated, we can proceed to discuss how well they can be used when acting as an infrastructure for trading information sharing.http://www.etoro.com/blog/forex-news/24122011/efficient-social-configurations-for-collaborative-trading-%E2%80%93-small-world-networks-i/