Talk:Scale-free network

From Wikipedia, the free encyclopedia

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

Contents

[edit] The name "scale free"

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)


[edit] Original research, against Wikipedia guidelines?

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)

[edit] Link directly to graph theory

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.

[edit] Confusing figure (fixed)

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)

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

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)

[edit] History

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)

[edit] Identical degree distribution

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)

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

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)

[edit] Population

A scale-free network should has a large population.

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