Talk:Small-world network

From Wikipedia, the free encyclopedia

Contents 1 Usage of terms "small world network" and "random network" 2 possible article sub sections 3 power law distribution vs. small world network 4 random network?

[edit] Usage of terms "small world network" and "random network"

"If the clustering coefficient is significantly higher than would be expected for a random network, and the mean shortest-path length is lower than would be expected for a regular network, then the network is a small world."

I disagree. Also random networks are small world networks. They are a special case (or if you will an ideal case) of a small world network. What is important in the expression "small world network" is the Small world phenomenon. That is that the number of jumps between any two nodes in the network is short. The name does not imply that it is a network of several different but connected small worlds. It is about that the WHOLE world seems small due to short jump distances. This means a random network is very much a small world network, actually the ideal small world network since it does have shorter average jump distances then networks that has some or a lot of clustering.

Oh by the way, since random networks are part of the research I am doing here's some nice facts about random networks: If each node has about 4 randomly chosen connections the network almost never splits into separate islands. ("Never" as in very statistically unlikely.) If you lower the number of connections to 3 you see netsplits pretty often. Of course more connections means more robust. If the network is heavily clustered (not a random network) you might need more or even much more then 4 connections to avoid netsplits.

--Davidgothberg 09:13, 25 May 2005 (UTC)

This is how Watts and Strogatz defined them. As such we need to state it -- I've made it clearer that this is their definition, not a general statement of fact. If you know of / have published work that shows this definition is incorrect then please do add it. --stochata 18:57, 25 May 2005 (UTC)

Ah well. I have now surfed around the Internet and also talked/chatted with other researchers to check how they use the terms. Seems you are right Stochata. Most prefer the term "random network" for networks where all links are chosen randomly from the whole set of nodes and the term "small world network" for networks that has some or a lot of clustering. Also it seems people who have not heard those terms before tend to understand them that way. They tend to think that "small world networks" means several "small worlds" that are connected to each other, instead of the small world effect. (Although the small world effect very much applies to random networks too.) So the current use of the terms seems the best in the long run. (Which means I just spent some time editing my own research web pages to reflect the "correct" use of the terms...)

--Davidgothberg 29 June 2005 06:26 (UTC)

[edit] possible article sub sections

Hello All. It is highly likely this article is going to become next week's Mathematics Collaboration of the Week, and so it is slated to undergo a rapid expansion. Just to seed some of the discussion, I would like to start listing possible sections for the expanded article:

• Definitions
• Properties, including a discussion of edge degree distributions, and how degree distributions with fat tails, like power-laws, contribute to networks that have low average shortest path metrics, maybe talk about tests for power-laws and power-law tails.
• SWNs in the natural sciences - gene networks, ecological webs etc
• SWNs in the social sciences - the WWW, social networks, the classical letter-sending experiments, Kevin Bacon, maybe even Wikipedia wikilink network (can we find anything out about that?)
• Robustness of small world networks vs random networks to random vs targetted attacks
• Methods to create small world networks synthetically, like preferential attachment, analogy can be drawn between that and new web page links.
• SWNs in pop culture, ideally we can find amusing or illustrative allusions to SWNs in movies/TV shows, Simpsons episodes about Kevin Bacon game, that sort of stuff.

(Debivort)

This is a great list of suggestions. Please do bear in mind there is also the page on the small world phenomenon, as well as Six degrees of Kevin Bacon, Erdos number and that we should avoid overlap. I'd be particularly in favour of SWNs in natural sciences -- though again, linkage to scale-free networks and Zipf's law is important. --stochata 14:20, 14 January 2006 (UTC)

[edit] power law distribution vs. small world network

It seems implied in the latter part of this article that power law distribution networks with hubs and such are the same thing as small-world networks, but this isn't really true. For example, randomly rewiring a lattice is a popular way of creating a small-world network, but does not create any hubs (in fact all nodes have the same degree). Meekohi 13:28, 17 January 2006 (UTC)

Didn't mean to imply this. Will clarify. But I am totally surprised the method above works. How do you get short path lengths out of random rewiring lattices? The stated definition here seems like a clique alone would qualify. Do you know if it does? I've started the construction section, and you can add your method there, and any others you know of. Debivort 14:32, 17 January 2006 (UTC)

I believe that's correct, a clique would be considered a small-world network (although certainly a trivial example). If you randomly rewire a lattice a few times, the shortest-path length rapidly decreases. I think this was in the orignal paper by Watts and Strogatz, but I'll have to check it out before I add it into the section. Meekohi 15:51, 17 January 2006 (UTC)

Aah this makes sense. For some reason I had it in mind that the new random edges would be adjacent to the original, but if they are chosen from random points in the lattice, and especially if the lattice is large, then path length would decrease quickly. Debivort 18:35, 17 January 2006 (UTC)

Small-world networks and power law networks are two different things. A small world network has a short average path length relative to its average degree, while a power law/scale free network simply has a degree distribution that is the same independent of size. Preferential attachment will create scale free networks, but will not automatically lead to a small world network. A small world network can be, as discussed above, created by taking a low-dimensional latice and randomly bridging a few nodes. This is by analogy to the original small world experiment of Milgram: the assumption is that we know our neighbors (hence, the 2D lattice), but a few people also know people who are physically distant. Creating a network with both scale-free and small world properties can be done by selecting random nodes in proportion to their degree (scale free), and then duplicating a fixed number of their neighbors (small world). See Steyvers & Tanenbaum (2005) [Cognitive Science 29 41–78]. 203.86.44.40 04:37, 27 July 2007 (UTC)

[edit] random network?

This edit switched small world networks from types of graph to types of random graphs. I think this is incorrect, as one can construct small world networks non-randomly, such as the one in this image. Debivort 02:21, 14 May 2007 (UTC)

Oops, not the fault of that particular edit, but you get my point and I've changed the article per this interpretation. Debivort 02:26, 14 May 2007 (UTC)