Talk:Scale-free network

	This article is rated C-class on Wikipedia's content assessment scale. It is of interest to the following WikiProjects:
Systems This article is within the scope of WikiProject Systems, which collaborates on articles related to systems and systems science.SystemsWikipedia:WikiProject SystemsTemplate:WikiProject SystemsSystems articles ??? This article has not yet received a rating on the project's importance scale. This article is within the field of Scientific modeling. Mathematics Low‑priority

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)[reply]

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

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)[reply]

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)[reply]

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)[reply

]

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)[reply]

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)[reply]

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

talk) 21:09, 2 September 2008 (UTC)[reply

]

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.

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)[reply]

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)[reply]

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)[reply]

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)[reply]

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)[reply]

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)[reply]

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)[reply]

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)[reply]

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)[reply]

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)[reply]

Now define

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

where s_max 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)[reply]

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)[reply]

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)[reply]

A scale-free network should has a large population.

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

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)[reply]

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)[reply]

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)[reply]

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 (talk • contribs) 16:05, 7 February 2011 (UTC)[reply]

I think that

 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)[reply]

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)[reply]

What is strange in this? There are literally thousands of generative models of network formation. What makes the model that you are talking about special in any sense?

Snehalshekatkar (talk) 11:41, 25 January 2017 (UTC)[reply]

I think the following paragraph from the section "Characteristics" should be rewritten

Another important characteristic of scale-free networks is the clustering coefficient distribution, which decreases as the node degree increases. This distribution also follows a power law. This implies that the low-degree nodes belong to very dense sub-graphs and those sub-graphs are connected to each other through hubs. Consider a social network in which nodes are people and links are acquaintance relationships between people. It is easy to see that people tend to form communities, i.e., small groups in which everyone knows everyone (one can think of such community as a complete graph). In addition, the members of a community also have a few acquaintance relationships to people outside that community. Some people, however, are connected to a large number of communities (e.g., celebrities, politicians). Those people may be considered the hubs responsible for the small-world phenomenon.

The very first sentence in this para doesn't look correct to me. Certainly some real networks that seem to follow a power-law type of degree distribution and certain mathematical models of scale-free network do indeed have this trend for their local clustering coefficients but this is not generic feature of scale-free networks. For example, the Price model (as well as the Barabasi model) does not reproduce any such trend. Similarly, there exist real networks with power-law distributions for which this feature does not hold (especially those which are actually embedded in geographical space).

Snehalshekatkar (talk) 15:09, 4 August 2016 (UTC)[reply]

The first sentence of this article:

A scale-free network is a network whose degree distribution follows a power law, at least asymptotically, so that any part of the network has a similar structure to the whole

Really? Can I not have a network with a power-law degree distribution whose parts don't look like the whole network? A Trivial example is the one with a core-periphery structure. For now, I am removing this description. Please discuss if I have misunderstood it.

Snehalshekatkar (talk) 11:46, 25 January 2017 (UTC)[reply]

I guess it means any part of the scale-free network would show the same power law, while for core-periphery example, any part of it doesn't obey the similar law compared with the whole network.

Barabasi-Albert model has already been followed by a large number of variants and also many new models have been proposed which have been claimed to be giving rise to the scale-free structure. Such models certainly occupy important place in the study of networks. However, many such models have assumed many things about real networks and hence as the field maturates over time, the naive models tend to lose their importance since they don't add much to our knowledge. This implies that many recent models which claim to give rise to scale-free structure etc do not deserve mention in this article unless they are extra-ordinarily new and are well supported by empirical data providing a completely new knowledge. I have just now removed one such model and I request everyone to refrain adding more models without discussing them on the talk page.

Snehalshekatkar (talk) 17:40, 3 February 2017 (UTC)[reply]

Is this grammatical, semantics notwithstanding?

7 Novel characteristics Edit For a scale-free network with {\displaystyle n} n nodes and power-law exponent {\displaystyle \beta >3} {\displaystyle \beta >3}, the induced subgraph is constructed by vertices with degrees larger than {\displaystyle \log {n}\times \log ^{*}{n}} {\displaystyle \log {n}\times \log ^{*}{n}} is a scale-free network with {\displaystyle \beta '=2} {\displaystyle \beta '=2}, almost surely (a.s.).[42] ... Zezen (talk) 20:05, 15 November 2019 (UTC)[reply]

If you remove the first "is", then its grammatical. Semantically, it seems plausible, it someone explained what the heck ${\displaystyle \log ^{*}{n}}$ is supposed to mean. 67.198.37.16 (talk) 02:13, 25 February 2020 (UTC)[reply]

In the article, it has a template that says "This article needs attention from an expert in mathematics." It asks for a reason. I don't know how to add a reason to the template, but I'll give a reason here.

I don't think the article contains errors, but it is somewhat disordered and repetitive, especially in the second half.

It should be edited by somewhat who knows the subject well enough to have confidence in what should be emphasized, and what should be rewritten.

2001:171B:2274:7C21:985E:DD36:E438:7F83 (talk) 14:55, 6 November 2021 (UTC)[reply]