Talk:Small-world network

Wiki Education Foundation-supported course assignment

This article was the subject of a Wiki Education Foundation-supported course assignment, between 19 January 2021 and 16 April 2021. Further details are available on the course page. Student editor(s): Neuroam.

Above undated message substituted from Template:Dashboard.wikiedu.org assignment by PrimeBOT (talk) 09:31, 17 January 2022 (UTC)

The role of clustering

Currently the definition given at the start of this article is entirely about how the diameter scales with N. There is no mention of clustering in this definition. I have always seen high clustering + short path lengths given as the definition. Clustering has always been a key part of the definition in the papers I've read, and in the discussion of properties, it already contains the quote "This follows from the defining property of a high clustering coefficient" (further numerous statements in this talk section mention things like "small average distance PLUS a high clustering coefficient", "Most prefer the term... 'small world network' for networks that has some or a lot of clustering") The reference given for the currently presented definition which ignores clustering is the 1998 Nature paper by Watts and Strogatz. This paper devoted significant attention to clustering, and focused on the existence of an interesting class of network for which the diameter scaled roughly like log(N), but the clustering coefficient is quite large. I have updated the definition to mention high clustering. If there is any disagreement, a different reference is needed for the current definition and a section should be included discussing the fact that often clustering is a key component of the definition.Joelmiller (talk) 01:02, 7 October 2016 (UTC)

Degree diameter graphs?

I can find no reference that states that degree-diameter graphs are small-worlds networks. I do not believe these have the clustering that is typically assumed for a small worlds network. I propose to delete this from the section on examples if no-one can provide a competing reference.Joelmiller (talk) 01:23, 7 October 2016 (UTC)

Scale-Free Networks != Small-Worlds

Another point that is lingering around here is the mix-up between scale-free networks and small-worlds. As has already been discussed on this page, the small-world definition contains both, a small average distance PLUS a high clustering coefficient. It is agreed that scale-free networks (or other networks with a fat-tail degree distribution) have a very small average distance but they do not need to have a high clustering coefficient. Thus, I would suggest to remove this part or to state that often these two things are confused but that the agreement today is that small-worlds need to have both structures to classify. There is a thesis in which the author tries to dissect the small-world effect (low average distance) from the small-world phenomenon (low average distance DESPITE high clustering coefficient). If we pick this up, the messy situation can be neatly resolved by saying that scale-free networks show the small-world effect but not necessarily the small-world phenomenon. Netzwerkerin (talk) 16:24, 6 April 2011 (UTC)

Road maps as small-worlds?

Road maps are very possibly one of the few real-world networks that are NOT small-worlds (which is actually not so easy! :-)). So, I'd like to delete this if no evidence/reference for this is provided and might even add it as one of those types of networks which are not small-worlds. Anyone up for discussion?

Netzwerkerin (talk) 16:17, 6 April 2011 (UTC)

Actually this paper discusses how road and transportation networks can become small-world networks depending on how you define neighbors. I'm removing it from either section because its behavior is very dependent on edge defintion.

— Preceding unsigned comment added by Atashsiah (talk • contribs) 17:38, 12 August 2016 (UTC)

References

A picture might appeal?

Does anyone else think this article might benefit from a picture. Just an example, or perhaps a demonstration of the algorithm for growing a small-world graph? Grj23 (talk) 07:39, 2 December 2009 (UTC)

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)

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)

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)

I agree with the above comment, currently the article overemphasizes the role of "hubs", bringing up the subject in most sections, whereas "hubs" are not necessary for a network to be small-world. Hubs are a requirement for power-law distributed networks, and are thus covered in the Scale-free networks article. It would be better if the present article focused on explaining the consequences of short path lenghts and high clustering coefficient, for example to disease spreading and information flow - the whole point of Watts' original paper is that even if the world seems distant because you live in a tight community, a few random links are enough to bring everyone close without disrupting the tightness. Of course, it's still worth mentioning that many small-world networks found in nature are also scale-free, linking to the corresponding article, but that's it. Another thing, if you decided that "small world" requires high culstering coefficient, besides short path length, then the section on "Costruction" is plain wrong as preferential attachment dynamics does not yield high clustering networks. As mentioned above, you need to combine it with other dynamics such as duplication to get a high clustering coefficient. If any, the Construction section should explicitly mention the Watts and Strogatz model. --solstag (talk) 05:23, 7 March 2009 (UTC)

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)

question

How do these networks relate to the kind of networks that are used in electrical engineering, e.g. resistor networks, from a mathematical perspective?

Hm - I'm not an electrical engineer, so I'm taking the Wolfram definition of 'resistor network' in this response. A simple resistor network with resistors in parallel will probably exhibit small-world-like nature because you (I think) have only two choices each time one adds a resistor - increase the maximal path length by one or by zero. If, say, you randomly distribute this choice (which you would not) then the maximal path length between any two nodes is going to be around $n/2$, and the minimal far shorter than this. You would have to be unlucky to see a long chain of single resistors - in fact, if you /did/ see this then you wouldn't really be considering a 'resistor network' in the electrical sense. Interesting question; why not write it up and add it to the article? 131.111.184.8 (talk) 00:13, 6 April 2010 (UTC)

neural network addition

That a "small world network of neurons can exhibit short-term memory" is not surprising. Two neurons can do this. It's a property of neurons, not small world networks. I propose removing this section. de Bivort 20:41, 14 November 2010 (UTC)

Source request

In which publication was the small-worldness measure proposed? I didn't find that formula in neither the references 4 nor 5. I'm new to this field of network science as well as talks on the wiki, so if this is not appropriate way to publish my idea please delete it anyway. — Preceding unsigned comment added by 123.149.144.27 (talk) 01:23, 21 January 2014 (UTC)

Illustration

I've made an illustration - example of small-world network. Do you have any comments for illustration? Do you have any objections not to include illustration to article?

Small-world network example
Hubs are bigger than other nodes
Clusterization coefficient = 0,522
Average shortest path length = 1,803

Schulllz (talk) 13:51, 30 January 2014 (UTC)

definition of nodes being neighbours

How is being a nieghbour rigourously defined? Could someone add a link in the article? — Preceding unsigned comment added by Alrichardbo1 (talk • contribs) 17:50, 6 September 2014 (UTC)

Is Small-worldness defined for undirected graph only?

Regarding the small-worldness defined below, is it defined for undirected graph only? How does the definition look like for directed graph, e.g. internet?--128.92.121.91 (talk) 20:55, 27 October 2020 (UTC)

$\sigma ={\frac {\frac {C}{C_{r}}}{\frac {L}{L_{r}}}}$

GENERAL INFORMATION ADDITION [Small World Network - Neural Architecture]

This edit would provide evidence from the research literature to 'Applications' > 'Small world neural networks in the brain'. Information on short-term memory exists, but the section lacks general background of how the model is applied to neural networks. Key points are as follows: application of the small-world model reflects functional brain regions (nodes), highly connected regions (hubs), and characteristic short path length between hub regions indicates functional connectivity. The balance of global and local networks is supported by the application of the small-world network model. The model is associated with efficient brain function (high processing/integration with low energy cost). Signed neuroam (talk) 15:19, 17 April 2021 (UTC)

Incorrect context: Computer modeling in the brain vs. Neural Network Characteristic

The paragraph beginning with, "small-world network of neurons can exhibit short-term memory" is misleading as it is describing a computer modeling application that can be applied to short-term memory or seizures. This convolutes the application of small-world networks in the brain because there is no transition or introduction to the new topic of computer models. It would be the most effective to limit this section to the direct application of small-world network to functional and structural connections in the brain. See Talk post above for the general application as used in Neuroscience research. Signed neuroam (talk) 9:49, 28 April 2021 (UTC)

[Neural Networks] - Attention to context of "Small World Network"

While the visual system / brainstem exhibit small world characteristics, that is not more general than entire brain connectivity. It should be noted that these systems do exhibit small-world structure, but ultimately because those systems function within the whole-brain network. Any suggestions to clarifying? Or any oppositions to removing "on a more general level" or the entire last sentence until it can be properly introduced? *the cited paper refers to application of the network to the reticular formation and asserts small-world properties in terms of the network's rapid processing and adaptability. Signed neuroam (talk) 10:19, 28 April 2021 (UTC)

Small World Distribution of link length - out of place?

This small section at the end has no context and seems out of place after the applications section. Might this section be a better fit after network robustness? Signed neuroam (talk) 10:29, 28 April 2021 (UTC)

Definition of small world networks

The definition of small-world networks does not look good to me. I am not sure what is the correct definition, but "[L] grows proportionally to the logarithm of the number of nodes N" only makes sense if we are talking about a series of networks. It does not make sense if we are talking about one specific graph and that seems to be the case now.

A little question of big pedant

The formula $L\propto \log N$ means that N is an infinitely growing variable. Thus an infinite sequence of graphs is defined, but not a graph in any way. Сурбас (talk) 11:34, 30 April 2022 (UTC)

Introduction

Perhaps I am misreading something badly but the very first sentence just doesn't seem correct "A small-world network is a mathematical graph in which most nodes are not neighbors of one another, but the neighbors of any given node are likely to be neighbors of each other" . It describes a sparse network with high clustering, for example triangular lattice. The second sentence does not look accurate either. I will wait a couple of days for any objections and then I'll update the introduction. Guggger (talk) 06:46, 16 November 2023 (UTC)