Talk:Scale-free network

From Wikipedia, the free encyclopedia
Jump to: navigation, search

I opened this discussion page because I have seen many active flip-flop of versions in a fairly short period recently. It seems that some like the Lun Li, et al. paper and definition, but some don't. I like the frankness of the paper although it may appear as "opening fire" to many recent papers contributed in the last six years. I think critique is good to healthy science and helps us in knowing the truth. The current version [1] seems to put the Lun Li, et al. paper in a weaker position in the exchange of ideas about the science of scale-free network, which I oppose.


I agree, I'm putting it back in especially considering the edit was made by an unregistered user. Also to answer the question below, the formal definition captures the notion of self-similarity, while Barabasi's definition really doesn't (From my understanding he basically just picked the name because it sounded good and would catch people's attention. Presumably he had some ideas about self-similarity but I haven't seen him talk about it) Meekohi 13:56, 12 December 2005 (UTC)
I consider that paper too scandalous and inaccurate. E.g. HOT model obviously has more dimensions than SF model. It is just a more specific case. You can't say that "horses are better than mammals" or "horses are faster than mammals". It is... well... a bit incorrect. On the formal definition. Just give me formal definition of a cat first. OK, the topic of degree correlations is actively studied, so it will settle to something in some years... let's consider that paper a "critique". Victor Grishchenko

The name "scale free"[edit]

This is my first time using the talk page, so please forgive any missed wikiquette.

The article was most helpful to me, however I am curious about one thing. Why are these networks called "scale free"? I assume that this is a reference to self-similarity, but what exactly is self-similar in a scale-free network? The sample diagrams of networks I have seen are not obviously fractal.

David M.

scale-free is not self-similar. Scale-free (as I understand it) is that there is no meaningful "average" for the behavior of the system. ChaTo 17:19, 12 December 2005 (UTC)
For the old definition of Scale-free this was true, but the Lun Li definition actually includes the concept of self-similarity. Meekohi 15:34, 13 December 2005 (UTC)
As I understand it, the term "scale-free" is closely related to the term "scale-invariant", which is perhaps a more intuitive phrase. It means (roughly) that regardless of how much you "zoom in or out", the structure is going to look essentially the same. Kmote (talk) 21:05, 8 October 2008 (UTC)
I was only partially correct. Here is the real answer, as described by Barabasi himself (in "Linked: The New Science of Networks", Basic Books, 2003, p.70): "The power law distribution thus forces us to abandon the idea of a scale, or a characteristic node. In a continuous hierarchy there is no single node which we could pick out and claim to be characteristic of all the nodes. There is no intrinsic scale in these networks. This is the reason my research group started to describe networks with power-law degree distribution as scale-free." Kmote (talk) 15:58, 13 October 2008 (UTC)

Original research, against Wikipedia guidelines?[edit]

Please forgive me if I am mistaken, but on reading, 'the authors...', it seems that an original viewpoint is being expounded, I thought that this was against Wikipedian principles of no new or original research being included?

Jim lewis1 (talk) 22:28, 3 April 2008 (UTC)

I believe "the authors..." refers to Pennock et al., rather than to the authors of the wikipedia article, I have changed "the authors..." to "they" in order to make this clearer Echinoidea (talk) 21:09, 2 September 2008 (UTC)

Link directly to graph theory[edit]

You should link directly to graph theory.

I realize that the article links to complex network which again links to network which again links to graph theory. But the first two pages do not give a definition of the term. They cannot be read and understood by readers that do not know graph theory beforehand.

Confusing figure (fixed)[edit]

The figures shows a directed graph, but the text does not mention directed graphs. the reader will ask herself. What is the meaning of the arrows? Must a hub necesarily be a source? etc..

Agreed. I'll contact the original artist and ask if he wouldn't mind making the modification, I think having a figure is very useful for people seeing this for the first time. Meekohi 14:05, 12 December 2005 (UTC)
changed to undirected graph, thank you for contacting me Meekohi. The source of this image is my Ph.D. thesis on web crawling: (Carlos Castillo: "Efficient Web Crawling". PhD Thesis. Universidad de Chile, 2004.) ChaTo 17:15, 12 December 2005 (UTC)


Confusing figure (not yet fixed)[edit]

The figure labeled "Complex network degree distribution of random and scale-free" has two curves. Presumably one (I'm guessing the one with the semi-normal distribution) is for random networks, the other for scale-free networks. Can the curves be labeled, or otherwise distinguished? (Also, the label is odd--not quite English. Maybe "Complex degree distribution of random and scale-free networks"? Although I'm not sure what "complex" has to do with it.) Mcswell (talk) 17:07, 2 July 2014 (UTC)

Ah, Lun Li, Lun Li...[edit]

There are no such thing as "SF vs HOT story". HOT model just has more dimensions. SF reflects connectivity only, while HOT also involves bandwidth. I may introduce, say, GEO model (and I do) which also involves RTT times. There will be a picture quite different both from SF and HOT but there will never be any "GEO vs HOT" or "GEO vs SF story". Further, regarding the core hubs debate, here is an AS graph from CAIDA: http://www.caida.org/analysis/topology/as_core_network/pics/ascoreApr2005.png The core looks like a core formed by hubs, not something like "low-degree core routers" like in Li et al HOTnet model. Authors don't address this issue and limit scope of their critics to router-level topology, which is much more subjected to geographical and technical limitations. So, Li et al are too selective in their critics. Also, they sometimes oppose their own claims (e.g. "...a vulnerability that has presumably been overlooked by networking engineers", p.11) etc etc Till this moment, nobody did blow up top 5% internet routers to test whether the Internet will survive that. So, Li et al argument on "legendary... high resilience" (p. 13) is also questionable. Given that level of inaccuracy, that theory better be read with caution (Victor Grishchenko 11 Mar 2006)

I don't think this article intends to say anything about how that paper relates to router topology. The HOT model's Graph just hapens to be a graph with very low s(g). My main point is just that regardless of whether you or Li are correct about the real nature of the Internet's topology, graphs with low-degee cores always have low s(g), and graphs with high degree cores have high s(g), because it's built into the definition. Meekohi 00:46, 13 March 2006 (UTC)
1) let G be a router graph with a high-degree core (S(G) close to 1.0) 2) let insert intermediary router ("relay") between every two adjacent hubs 3) Result: packet flows remained nearly the same, but S(G) is very low. Am I correct?
Yeah I see your point. Since s(g) is just the sum of all neighboring degrees, the way to maximize it is to have the highest degree nodes connected to each other, and the way to minimize it is to have high degree nodes connected only to low degree nodes. I think one big problem is that defining the "core" of the network is hard to do, and depending on how you visualize the graph it can be misleading. The way I am thinking of the graph you've descibed, I would say the intermediary routers are part of the core... so I wouldn't describe it as having a high-degree hub core either, but by making sure the high-degree hubs don't connect directly, you effectively lower the s(g) value. I might rewrite the article some this afternoon if it seems too misleading. Meekohi 14:13, 13 March 2006 (UTC)
Just put more emphasis on degree distribution. At least, it is something most authors are agree on. S(g) is just one of the theories. Me personally is a supporter of the skeleton approach by Kahng et al http://phya.snu.ac.kr/~kahng/paper1.html (I may add a respective paragraph to the article). Also, there are some other theories. (Victor Grishchenko 13 Mar 2006)
Well, I'm still in support of using S(g) as the formal definition. It's a lot better than "any graph with a power-law degree distribution". S(g) at least says something about the network structure, even if it doesn't apply well directly to router throughput. Nobody else has really put forth a meaningful formal definition as far as I know. Meekohi 04:26, 14 March 2006 (UTC)

History[edit]

Probably silly question, but if "This model was originally discovered by Derek de Solla Price in 1965 under the term cumulative advantage", how was it "further developed by Herbet Simon in the 1950s"? Mmt 03:12, 5 April 2006 (UTC)

Sounds like a pretty good question to me actually. Does anyone have a source for this Herbert Simon? I've never heard of him before. Meekohi 03:26, 5 April 2006 (UTC)
Part of the problem was a typo. Should have been Herbert Simon, but the dates still make no sense so I took that part out of the article for now. Meekohi 03:30, 5 April 2006 (UTC)


Excuse me if I am way off, but does cumulative advantage mean the same as 'first mover advantage', I believe these are not equivalent to preferential attachment as first mover still holds with random linking in a growing network  ?... RamseyPalace (talk) 16:48, 9 April 2009 (UTC)

Identical degree distribution[edit]

Now define

 S(g) = \frac{s(g)}{s_{max}}

where smax is the maximum value of s(h) for h in the set of all graphs with an identical degree distribution to g.

I was wondering. What is an identical degree distribution? Is the amount of vertices of a certain degree exactly the same across these identical distributions? Or is the power-law exponent exactly the same? Or are they all power-law distributions or Poisson distributions? Andy 10:53, 6 October 2006 (UTC)

Derek de Solla Price did not "Discover" Cumulative Advantage[edit]

In the entry for Derek J. de Solla Price, it says that his contribution was "his interpretation of Herbert Simon's theory on cumulative advantage processes, or Robert K. Merton's Matthew effect, respectively (Price 1976)." So shouldn't Simon or Merton be credited with the discovery? --Nick 17:05, 1 December 2006 (UTC)

Sounds reasonable to me, but someone should track down a source for this before making a final statement about it probably. Meekohi 04:49, 3 December 2006 (UTC)

Population[edit]

A scale-free network should has a large population.

A real-world network always obtain a large number of individuals.

Web is not random[edit]

To their surprise, the Web did not have an even distribution of connectivity. Why is this surprising? Kope (talk) 19:42, 18 June 2008 (UTC)

No links from text to references[edit]

This article has a lot of references, but it's more like a paper article in that there are no links from the text to the reference section. - Dougher (talk) 02:02, 24 February 2009 (UTC)

Reference from Antiquity[edit]

It may not merit mention in the article, but I think it is interesting that perhaps the earliest reference to scale free phenomenon is recorded in Luke 19:26:

"[Jesus] replied, 'I tell you that to everyone who has, more will be given, but as for the one who has nothing, even what he has will be taken away."

Perhaps if other references could be compiled from antiquity, it might be worthy of a small section. (Of course, I'm not suggesting that Jesus had anything like social network dynamics in mind when he uttered this, but the reference seems striking to me in this context.) Kmote (talk) 21:02, 17 August 2010 (UTC)

Power law versus logNormal[edit]

I'm a little worried about characterizing the degree distribution as a power law; in the original BA paper, if I'm correct, they used a least-squares linear regression which is a no-no (see http://arxiv.org/abs/0706.1062). It has been argued that the distribution of web links more closely follows a log-normal distribution. Before I change this, am I completely off base here? — Preceding unsigned comment added by Octochimps (talkcontribs) 16:05, 7 February 2011 (UTC)

Merger with generalized scale-free model[edit]

I think that Generalized scale-free model should be merged into Scale-free network#Generative models, as the former is fairly short and doesn't seem like it could/should be a substantive article on its own. Joe SchmedleyTalk 15:59, 21 August 2011 (UTC)

Yes check.svg Done. There was a lot of overlap between the two articles, and so I agree it seems better to cover both of them in one article. --DavidCary (talk) 14:08, 19 April 2014 (UTC)

Generative models[edit]

It is strange that the article does not mention the generative model described in the PhD thesis of Lada Adamic circa 1999. Gritzko (talk) 15:54, 21 February 2013 (UTC)